Lambda the Ultimate

Try googling for "parser generator" - there are zillions of them. Which one you choose can depend a lot on what language you want to use to host the parser. One recent LtU thread which contains relevant links is Parsers that allow syntax extensions. The classic parser generator is YACC, and the GNU version of that is Bison. Two well known Java ones are Antlr and JavaCC. There's also a Toy Parser Generator for Python. This list is ludicrously incomplete.

Thank you for the links!
Looking into it.

the Gold Parser.

I've been using it a lot and it has got some nice graphical tools...plus engines for lots of programming languages.

Unfortunately I won't be able to use Gold as it is available only on Windows. Never mind, I can look at the other options here.

One of the parser frameworks that may be worth a look is the Spirit parser framework -

The Spirit home page

Spirit is a C++-based framework which is (imo) very easy to use.
I say that and I'm really not a C++ coder at all - I'm just a copy-and-paster in C++. But, that's all you need to be in order to use Spirit. It's *really* fun to use.

You can write your grammar (in what is *very close* to BNF syntax) directly in C++. Have a look at a few examples in the apps repository, and that should give you a good feel for things.

When you say "I spotted a couple of ambiguities in the syntax already", I wonder if you are looking for a tool that will take a context-free grammar and tell you if it is ambiguous.

Unfortunately, it is undecidable whether a context-free grammar is ambiguous, but it is often possible to prove that some particular grammar is unambiguous; some parser generators will do this for you as part of generating the parser, but others will not. For YACC and Bison, if you don't use any precedence declarations in your input grammar and the tool runs successfully without printing out any messages about "shift/reduce conflicts" or "reduce/reduce conflicts", then the input grammar was unambiguous; if they do print such messages, then the grammar may or may not be unambiguous.

It is a matter of opinion whether support for ambiguous grammars in a parser generator (with no compile-time ambiguity test) is a bug or a feature; presumably, the authors of the Spirit framework think it's a feature, or they wouldn't put "capable of parsing rather ambiguous grammars" in the first paragraph of their website. My own view is that a programming language should have a formal grammar definition, and that an unambiguous LALR(1) context-free grammar is the form of formal grammar definition which will give implementors the most flexibility in correctly implementing the grammar. (LALR(1) is the name for the set of grammars that YACC and Bison can prove to be unambiguous.)

Other possibilities for formal grammar definitions would include ambiguous grammars augmented with precedence information, intended to be fed into YACC or Bison (but be careful here; YACC precedence declarations don't always mean what you might expect), or Parsing Expression Grammars (which have disambiguation information built into the grammar, in a formally specified way; but again, be careful, the disambiguation isn't always what you might expect).

Well I take it for granted that the syntax of the language should not be ambiguous. My reasoning is that if it is difficult for the computer to parse it, how will it be for the person who reads the code?

I think I will simply try writing a BNF grammar for the language. That should help weed difficulties out. Should I use left recursion for LALR(1)? For example:

  arguments ::= arguments "," argument
              | argument

It seems several of the tools (Spirit, Gold) aim at being BNF compatible so it is a good starting point.

I'd use left or right recursion as appropriate for the subproblem at hand. For example, in parsing
1:2:3:4:5:[]
I'd use right recursion.

YACC can handle left as well as right recursion, although there may be a fixed limit with right recursion due to parse stack size.

A common source of ambiguity is having both IF predicate THEN consequent and IF predicate THEN consequent ELSE alternative. There are two distinct concepts.

IF..THEN.. makes some code optional. When the predicate evaluates to false the code is skipped. An IF..THEN.. will always be a statement, even if the consequent is an expression; what would its value be when the predicate is false?

IF..THEN..ELSE.. choses between alternatives. If the consequent and alternatives are both expressions, then the IF..THEN..ELSE.. could also be an expression.

If you use distinct initial keywords, perhaps OPT and ALT or WHEN and IF, you will not need a precedence rule to disambiguate elses because they will no longer dangle. For example

IF p1 THEN 
  IF p2 THEN a1 
    ELSE c

is either

OPT p1 THEN 
  ALT p2 THEN c2 ELSE a2

or it is

ALT p1 THEN OPT p2 THEN c2 
  ELSE a1

There is then neither a conflict in the grammar, nor a paragraph in the language manual describing dangling else, nor a defensive coding convention to reduce errors.

Thank you for your suggestion. I will go through the syntax to check again, but I don't think dodo suffers from that problem.

In dodo "if" is used as a ternary operator

if (x > 0) sqrt(x) else exp(x/2)

The conditional branching uses "test", which is similar to "switch" in C

test
{
   x > 0   {return sqrt(x)}
   default {return exp(x/2)}
}

There can be other constructs that are not safe but I have none on the top of my head.

I am using Aurochs as parser at the moment, you can find a preview of the grammar on the dodo web site.

The reason that parser works for me is that you can see immediately the structure of your AST (it outputs a XML tree). The reason I do not recommend anybody using it is that when you output a XML tree, the only error you will see is "Parse Error (0)" when you do something wrong. Nice heh?

Anyway check out the current grammar, I was able to parse one of the examples with it.

This is my description of dodo qualifiers, is that different from mixins?
------

A qualifier can be specified to add properties to the class that are the same for all classes that respond to that qualifier. For example the qualifier Motorised could add the attributes engine, wheels and speed to the class.

A qualifier is defined like a class with an attribute parent that is an instance of the class it is applied to. For example, if I want to define a Inhabited qualifier for the house I could write:

qualifier Inhabited
{
    link People[] inhabitants
    Drawing draw(Canvas support):
        Drawing result parent.draw(support)
        loop foreach(inhabitant in inhabitants)
        {
            .result = inhabitant.draw(result) #Drawing can act as Canvas
        }
        return result
    .
}

This qualifier replaces the draw function in House with its own that draws the inhabitants as well as the house. That supposes Inhabited is applied to a class that has a draw function, of course.

...the big three are Map, Filter, Fold. I gather the one you are looking for is fold (which can either be left-to-right or right-to-left). In Standard ML, fold left could be defined recursively as:

   fun foldl f u nil     = u
     | foldl f u (x::xs) = foldl f (f(u,x)) xs

A simple use is to sum the contents of a list:

   val mysum = foldl (fn (x,y) => x+y) 0 [1,2,3,4])

Or to put it in your terms:

f - function to apply
u - initial value
nil or x::xs - the list

I guess I should also add that you can use currying to define functions in terms of fold. So for example, a sumlist function could be defined as:

   val sumlist = foldl (fn (x,y) => x+y) 0
   val mysum = sumlist [1,2,3,4]

OK so map and filter seem to be like SELECT and WHERE in SQL:

 SELECT f(p.*)
 FROM Person p, Toothpaste t
 WHERE p.job = "Salesman"
   AND t.taste = "strawberry"
   AND p.toothpaste_id = t.id

We already talked about fold, except it is sometimes called reduce and the initial value can be part of the list. I will keep fold and a separate initial value.

I also read about unfold which looks like a C for loop, I think I can ignore it.

What may be missing is some kind of join to combine two lists.

Concatenation's actually just another fold if you've got a typical list structure: you use cons and then the second list as the initial value. You might want to look at the zipWith family though - map is effectively zipWith1.

I am not looking at concatenation, I am looking at combining the two lists (like vector product):

  [ a, b, c ]  *  [ 1, 2 ]
=
 /               \
 | a*1, b*1, c*1 |
 |               |
 | a*2, b*2, c*2 |
 \               /

If I flatten the matrix it is effectively a concatenation of [ a, b, c ] * 1 and [ a, b, c ] * 2. So I guess your remark was relevant to my problem after all.

The combination operator would probably be pair(a, b). For example I could generate all the possible pairs (salesperson, strawberry toothpaste). Then I could filter again, like the join filter in the SQL statement above: p.toothpaste_id = t.id

In Haskell, you can easily write all this using list comprehensions. E.g. your example (assuming properly typed persons and toothpaste lists):

[(p,t) | p<-persons, t<-toothpastes, job p==Salesman, taste t==Strawberry]

Not sure if it helps, but here's an ML version to define the two:

   fun map f nil     = nil
     | map f (x::xs) = (f x)::(map f xs)

   fun filter f nil = nil
     | filter f (x::xs) =
         if (f x)
            then x::(filter f xs)
            else (filter f xs)

As Chris said, you're looking for fold. See the paper Tutorial on the universality and expressiveness of fold. Note that this paper is also mentioned in the Getting Started thread, which is full of references worth reading if you're designing a language.

The fold version of your example would look something like this in Scheme:

(fold (lambda (result inhabitant) (draw inhabitant result))
      result
      inhabitants)

or in Haskell:

foldl (\result inhabitant -> draw inhabitant result) result inhabitants

In both cases, the first argument to fold is a function which is applied in turn to each element of 'inhabitants'. The second argument is the starting value for 'result'; I'm assuming result is defined in the enclosing scope.

I am not sure why you use a lambda expression here, is it just so that you can swap the arguments of draw? Is there no "foldr" or such that works with arguments in reverse order?

Anyway, if I do not take into account the arguments order what you wrote is like:

 (fold draw result inhabitants)

Which is close to my notation in dodo:

 fold inhabitants.draw(result)

Thank you for the links to read. I hope to ingest some of this before I have an interpreter out! :-)

There's a "foldr" in Haskell, but it doesn't do what you're asking. Foldr is a "right-associative fold" - it traverses the list from right to left, building up a value by applying the binary operation between each pair of elements.

Anton's example could've been written (in Haskell) like this:

foldl (flip draw) result inhabitants

Flip is a Haskell built-in that swaps the order of two arguments, eliminating the need for a lambda.

In fact, I came with a style for continuation-passing style lambda functions that I quite like and I don't really see the use for standard lambda functions any more. Are there drawbacks in keeping only CPS lambdas in dodo? I would make sure that the continuation invokation is tailing so I imagine it can be optimised easily.

If desired, normal named functions are still there to use.

According to Anton: "For the most part, first-class continuations should be seen as a tool-building feature, not something you'd regularly use directly in an ordinary program."

Does the same apply to CPS?
Would you recommend continuations to build a control flow such as a parser algorithm or web site navigation (applications that make also use of abstract state and possibly versionning)?

As James McCartney pointed out in a followup to my comment, the same doesn't necessarily apply to CPS. As my reply to James indicated, I was really thinking more of call/cc when I wrote that.

Whether to recommend using continuations (or CPS) depends on the language, the application, the requirements, the available alternatives. A number of web frameworks, for example, use call/cc under the hood so that the user's code doesn't have to be in CPS.

As James McCartney pointed out in a followup to my comment, the same doesn't necessarily apply to CPS. As my reply to James indicated, I was really thinking more of call/cc when I wrote that.

That seems to imply that the use of call/cc is not required to practice Continuation Passing Style. I was wondering about it, and I will need to make sure of it for my documentation work. Back to the textbook it seems...

That seems to imply that the use of call/cc is not required to practice Continuation Passing Style

Is there any theorem that associative functions have a neutral element such that f(x, neutral) = x?

No. You must assume that. In particular (and as will become relevant) monoids are a set (type) with a binary operation that satisfies three independent axioms: associativity and left and right unit.

I am specially interested in the single argument question in relation to fold, if I am correct that means that using fold with an associative function does not require a seed.

Lists are the free monoids (the binary operation is ++ and the unit is [], Haskell syntax). foldr is the unique monoid homomorphism from the free monoid (lists) to any other monoid (this is what freeness means). (f : A -> B is a monoid homomorphism (A,+,0) -> (B,x,1) if f(a+b) = f(a)xf(b) and f(0) = 1 where +, x, 0, 1 are the binary operations and units respectively and are meaningless despite their name (though if f(x) = e^x then that is a monoid homomorphism with the usual interpretations of the operations and constants)).

foldr :: (a -> b -> b) -> b -> [a] -> b
doesn't look like a monoid homomorphism. This is because we use the associativity of (++) to fix the lists into a right associative form, i.e. [1,2,3] = [1]++([2]++[3]) = 1:2:3:[].

fold :: (m -> m -> m) -> m -> (a -> m) -> [a] -> m
fold mappend mempty f = foldr (\x xs -> f x `mappend` xs) mempty

foldr = flip . fold (.) id

-- or using the old instance for functions for Monoid
fold :: Monoid m => (a -> m) -> [a] -> m
fold f = foldr (mappend . f) mempty
foldr = flip . fold -- (edit: not quite so slick)

fold can use whatever parenthesization it feels like though assuming mappend is associative and mempty is its unit.

That settles it then. Thank you for monoids. In my case associative is all I want, so I will introduce a special fold that returns the seed if the list is empty instead.
How would you name such a beast?

If you drop the identity element you get what is called a semigroup. Non-empty lists should be the free semigroup and foldr without the nil argument should be their fold.

Sure. But since I am only looking at the associativity property, and the only notable property of semigroups seems to be associativity, I don't see what I can leverage from knowing that it is a semigroup. Maybe you were trying to tell me something about the free semigroup?

Crikes. I just read Fold - HaskellWiki which introduces foldr as

 foldr f z []     = z                  -- if the list is empty, the result is the initial value z
 foldr f z (x:xs) = f x (foldr f z xs) -- if not, apply f to the first element and the result of folding the rest

Am I wrong in suggesting that it should be instead

 foldr f z (x:[])   = f z x            -- if the list has only one element, apply f to the first
                                       -- element and the initial value z
 foldr f z (x:xs) = f x (foldr f z xs) -- if not, apply f to the first element and the result of folding the rest

since the "initial element" introduces a singularity, not being necessarily part of the set of values returned by f? I don't like that foldr can return z even if f has no neutral element.

In short, yes - it loses far too many useful properties. Consider

foldr (:) []

as a trivial example that ought to work.

In short, yes - it loses far too many useful properties. Consider
foldr (:) []
as a trivial example that ought to work.

Sure that is convenient. But what about that other simple example?

def sign a b = if a < 0 then if b < 0 then +1 else -1
   else if b < 0 then -1 else +1

foldr sign 0 [-3 5 -2] = +1
foldr sign 0 [-10] = -1
foldr sign 0 [] = 0

lf the input list is empty, I get a value that is neither +1 or -1!
Sometimes that may be useful, but it does not look correct as the default.

just do

foldr sign +1 [-3 5 -2] = +1
foldr sign +1 [-10] = -1
foldr sign +1 [] = +1

instead

...which is part of the return set of the function.
Agreed, that is what a good programmer would do. But I can easily see an inexperienced programmer making the mistake and introduce weird bugs.

I guess that's only me. I will probably follow the convention, with a paragraph in the documentation for the caveats.

Unless your language supports currying (like haskell and ML) I think it makes more sense to have the function argument positioned last, as its often a lambda, and considerably larger than the other arguments. Something like:

foldr [] someList (acc x => acc + x)

someList is often a rather large expression itself often. Further if your language supports higher order functions then it supports currying. I would have no problem with foldr :: (a->b->b,b) -> [a] -> b in a language that doesn't favor currying. Often function definitions are of the form f = foldr c n and it would still be nice to compose them.

Its my experience that the function argument often is the largest, but thats obviosly dependent on programing style. With support for currying i meant part synctax suport, and more importantly if the fold function is defined as a curried function. foldr :: (a->b->b,b) -> [a] -> b is a curryed function, so I think a language that includes that in its prelude is by definition a language that favors currying, at least in some regard.

My language does not support currying. The syntax is strictly to my taste, which is a bit backwards at times. For example fold is a special construct, to use it just do a normal function call with fold in front of the list and seed in front of the initial element:

fold someList + seed 0        or
int.add(fold someList, seed 0)

Lambda expressions are a pain to write though, due to static typing ala Java.

In that case wouldnt be better even to have some more looplike syntax for folds? perhaps like:

fold (list 

edit: hm that doesnt look right

Lambda expressions are a pain to write though, due to static typing ala Java.

Haskell is statically typed, and lambda expressions are not a pain to write there. Do you mean lack of type inference so you have to add a type signature, perhaps?

Yes. It is more like Java than Haskell.
I do want type inference, but am a bit scared of it.

(Wow, is every reply of mine in this thread going to start with a structure from abstract algebra?)

Well the issue is that every monoid homomorphism is a foldr, but not every foldr is a monoid homomorphism. I goofed slightly earlier in my definition of foldr (I editted it earlier today). The way my foldr definition in terms of fold works is by being a monoid homomorphism to the endofunction monoid, we then just apply 'z' to the composed list of actions. If foldr :: (a -> b -> b) -> b -> [a] -> b then foldr f is actually an action of [a] on b. I.e. b is a [a]-Set. Every monoid induces an action on itself. The upshot is that b does not have to be a monoid, 'z' is not the identity of anything.

A system like this could be type-safe, or it could fail to be type-safe. It could also make it very easy to accidentally introduce non-termination. So it's a fine direction, but I think you need to be a little bit careful. If you haven't already, I would take a close look at Scala's implicit conversions, which do something very similar to this.