views:

309

answers:

5

I've been mulling over creating a language that would be extremely well suited to creation of DSLs, by allowing definitions of functions that are infix, postfix, prefix, or even consist of multiple words. For example, you could define an infix multiplication operator as follows (where multiply(X,Y) is already defined):

a * b => multiply(a,b)

Or a postfix "squared" operator:

a squared => a * a

Or a C or Java-style ternary operator, which involves two keywords interspersed with variables:

a ? b : c => if a==true then b else c

Clearly there is plenty of scope for ambiguities in such a language, but if it is statically typed (with type inference), then most ambiguities could be eliminated, and those that remain could be considered a syntax error (to be corrected by adding brackets where appropriate).

Is there some reason I'm not seeing that would make this extremely difficult, impossible, or just a plain bad idea?

Edit: A number of people have pointed me to languages that may do this or something like this, but I'm actually interested in pointers to how I could implement my own parser for it, or problems I might encounter if doing so.

A: 

Haskell has just what you're looking for.

Justice
I'm pretty sure Haskell doesn't do prefix operators except '-', and I'm not sure about postfix either - let alone the more complicated structures.Anyway, I'm looking to create such a language, not just to find one.
sanity
The *implementation* of fixity of functions in Haskell can potentially shed some on how *you* would implement it in your own language.
Justice
A: 

Well, you have a day job, and the rest of the time browse SO... so, thats a good reason: NO TIME TO DO IT?

DFectuoso
Probably true, but not really the kind of answer I was looking for...
sanity
A: 

What are you going to do about order of operations?

a * b squared
WW
Good question. I think perhaps some way to specify operator precedence, and a syntax error if it is still ambiguous.
sanity
A: 

You might want to check out Scala which has a kind of unique approach to operators and methods.

I'm more interested in pointers to ways to implement my own parser for this type of thing, or problems I might encounter in doing so.
sanity
+4  A: 

This is not too hard to do. You'll want to assign each operator a fixity (infix, prefix, or postfix) and a precedence. Make the precedence a real number; you'll thank me later. Operators of higher precedence bind more tightly than operators of lower precedence; at equal levels of precedence, you can require disambiguation with parentheses, but you'll probably prefer to permit some operators to be associative so you can write

x + y + z

without parentheses. Once you have a fixity, a precedence, and an associativity for each operator, you'll want to write an operator-precedence parser. This kind of parser is fairly simply to write; it scans tokens from left to right and uses one auxiliary stack. There is an explanation in the dragon book but I have never found it very clear, in part because the dragon book describes a very general case of operator-precedence parsing. But I don't think you'll find it difficult.

Another case you'll want to be careful of is when you have

prefix (e) postfix

where prefix and postfix have the same precedence. This case also requires parentheses for disambiguation.

My paper Unparsing Expressions with Prefix and Postfix Operators has an example parser in the back, and you can download the code, but it's written in ML, so its workings may not be obvious to the amateur. But the whole business of fixity and so on is explained in great detail.

Norman Ramsey