Thursday, January 04, 2007

Does Haskell need macros?

Haskell has higher-order functions, and lazy evaluation, but not macros. Does Haskell need macros? For the purpose of this, I'm talking about macro in the "a little piece of code that expands out" sense, rather than the conditional compilation that macros quite often get used for in C++.

If Haskell needs macros then there must be some benefit to adding them. The reason that a lot of languages need macros is because they have strict evaluation. Consider trying to write a function that selects one of two arguments, based on the first condition variable - some sort of if:

iff a b c = if a then b else c

You can write this in Haskell. You can also write this in VB (and it is pre-defined), but it doesn't do what you might expect in VB. Haskell's lazy evaluation is a big win here, opening up entirely new opportunities.

So what are the reasons to add macros?

Speed

This is just a silly argument. First off, a pure function can always be inlined away, so performance is not an issue. A compiler might choose not to inline a function, but you can usually persuade it that it should with pragma's etc. And finally, there is the real possibility that you (the author of code) doesn't have a clue what should be inlined and is actually throwing away speed for premature optimisation.

Generate code

One thing that macros can do is to generate definitions, functions can be used to generate expressions (essentially a function is an expression with some pre-defined structure). You can't define a Haskell function that takes some data, and generates classes/instances etc. For example, imagine that you want to define lots of constructors for binary operations. Instead of:

data Expr = Add Expr Expr
| Mul Expr Expr
...

Here a macro might let you write something like:

data Expr = binary(Add) | binary(Mul) ...

Of course, this is something you really can't do with Haskell as it stands. However most of the ways you might use a macro like this are covered by Haskell. There are type synonyms, which may actually let you do the above trick with GADT's (I haven't tried, but its certainly feasible they could work like that, even if they currently don't). Classes has defaults which is another situation where otherwise this functionality might be required.

For most purposes generating code with macros is not about doing clever stuff, but about cutting out repetitive stuff. Haskell has (by design) cut out most of the repetitive tasks, so no longer requires macros. For truly repetitive tasks, Template Haskell can be used, or things like Drift and Scrap Your Boilerplate. All of these techniques reduce the number of places where macros might otherwise be required.

LHS of a pattern match

One place where expressions are present, but functions are not allowed is on the left hand side of a pattern match. For example:

f 3.14159265358979 = 2.71828182845905

Of course, it's silly to write this using hardcoded values, what if either of these constants change?

f pi = exp 1

Unfortunately without macros, this is not allowed in Haskell since pi is a function (a constant arity function, but still a function). You'd instead have to write:

f x | pi == x = exp 1

Not too painful, but what if you are trying to match a LHS with a free variable in it:

f (Neg (Neg (Neg a))) = Pos $ Pos $ Pos a

Here you are matching a deeply nested constructor, and on the right have to explicitly bracket the terms. However on the right you are able to use the function ($) which due to precedence issues removes the need for brackets. One thing you can't do however is:

f (Neg $ Neg $ Neg a) = Pos $ Pos $ Pos a

If ($) was a macro, this would be valid however.

Haskell has no feature here that can reduce the redundancy in the pattern match.

But while macros would be useful here, how far would standard C style macros take us? Let's consider defining a useful auxiliary:

apply 0 f x = x
apply n f x = f (apply (n-1) f x)

Now we can rewrite this as:

f (Neg (Neg (Neg a))) = apply 3 Pos x

But we really can't write:

f (apply 3 Neg a) = apply 3 Pos x

However, its entirely possible to come up with a consistent semantics for this, so maybe one day this might be something people decide is useful.

For the moment the lack of macros on the LHS is occasionally annoying, but generally is not a feature that anyone is crying out for. The LHS is rarely sufficiently complex for macros to show great benefit.

Type checking with rank-2 types

While standard Haskell (mainly, ignoring MR and seq - for those who care) has the fold and unfold law, i.e. you can inline a function and then contact it back, once you introduce rank-2 types you loose this property. Unfold still holds, but fold doesn't. This leads to lots of typing problems for things like runST which present rank-2 types to the user.

While macros would paper over the cracks here, the real solution probably lies in the type system, which I believe GHC has in various flavours of impredictive polymorphism. The other solution is not to use rank-2 types, something I have been happily avoiding for years now.

Conclusion

Despite macros being useful in languages like Lisp, in Haskell their usefulness is probably minimal. Lazy evaluation is often a substitute for macros, and where other languages require macros to define domain specific languages, Haskell solves these problems naturally.

Macros are quite a painful cost to a language, they reduce the assumptions that people can make and require people to play hunt the macro. Haskell really doesn't need them!

15 comments:

Dan said...

Someone asked this already on reddit, to witch I had written a long post (don't know where it is)


But, the short of it is macros are only useful in untyped languages like lisp.Since haskell is statically typed, you may as well just write the actual code due to the implicit constraints already on your functions

Anonymous said...

Look at MetaML and MacroML. The thing missing from Lisp macros that Haskell would need is type safety and Multi-Stage Programming seems the best way so far of doing it.

It's seems very similar to Template Haskell (sans AST manipulation).

Being able to define do notation as a type-safe macro in a library should be enough of a boon. Of course MSP would also allow type safe compilation of a DSL to Haskell at run-time, which is more than a little cool. Partial evaluation is also closely related.

Conor said...

For the record, I'm on the record proposing "Pattern Synonyms" (certainly not general untyped macros), precisely to cut down clutter on the LHS of functions. I have lots of examples where this would be useful. There are lots of abstractions which Haskell doesn't support, or supports very clumsily (mutter mutter type class hackery). Macros are a bad solution to a failure of abstraction. But a good solution might still be desirable.

Neil Mitchell said...

Dan: My argument is more that you don't need macros in a lazy language - the typed/untyped thing is less of an issue.

Conor: Yes, I remember your Haskell' proposal (I think it was), but was too lazy to find a link when I was writing this :)

andrew cooke said...

one reason haskell "needs" macros is that it's an interesting area of design space. macros / staged evaluation in a lazy, typed system sounds like an intersting problem. this is the "fly to the moon" argument - there may not be a simple practical case, but who knows what we might learn on the way?

Greg Buchholz said...

There are type synonyms, which may actually let you do the above trick with GADT's (I haven't tried, but its certainly feasible they could work like that, even if they currently don't).

That's what macros are for, right? Trying stuff out that's not currently supported.

For truly repetitive tasks, Template Haskell can be used, or things like Drift

It might help if you can tell us why you don't consider TH a macro system.

It might also help to specify what types of macros we're talking about. Common Lisp has a whole host of different macro types, including...

* defmacro
* Reader macros
* compiler macros
* symbol macros

Besides the obvious list of things that might become possible with macros, here's a few more off the top of my head...

* First class patterns
* Views
* Open data types
* HaRP
* DriFT
* All those polytypic generic Haskell derivatives
* Partial evaluation/compile time evaluation/multi-stage programming
* optional and keyword arguments
* postfix, new mixfix operators (like "do" notation, if-then-else, etc.)
* Literal syntax for arrays, sets, hexadecimal/binary numbers, etc.
* better syntax for DSLs (regexes, parsec, etc.)
* Type system extentions (linear/unique types, associated types, etc.)

Sure, you can fake some of that stuff, but why not try to make it nice/easy to use?

Laurence Tratt said...

As Greg said, I'd be interested (and perhaps amused) to know why you don't consider Template Haskell a macro system. Just because they called it "compile-time meta-programming" doesn't mean it's not a macro system (I wonder if perhaps "macro" didn't sound complicated enough?).

That said, I believe that your basic argument has an element of truth in it, but not for the reasons you think. I designed the Converge language which, for this discussion, is basically Python-plus-Template-Haskell-macros. And I can tell you that in their raw form macros aren't spectacularly helpful in Converge either. That's got nothing to do with lazy evaluation, monads, types, or anything else Haskell specific. It's because syntactically rich high-level languages contain enough raw primitives so, unlike LISP, one doesn't need to build new primitive-like things very often.

However one can put a lot of value-add on top of a macro system - Converge uses it to embed DSLs of arbitrary syntax within it. And no amount of type systems, monads, lazy evaluation, will get you close to that sort of feature - it's essentially independent of the "base" features of the language.

anon said...

Neil, I am curious why you think compile time evaluation isn't important? I am interested in building a language that generates haskell code, and what better way than to use something like template-haskell?

Maybe I'm misunderstanding something, but how could I be sure that all the primitives that I build on top of haskell won't just be interpreted at runtime? (previously I was considering using parsec, but I don't want an interpreter, and I don't want to create intermediate haskell files unnecessarily.

I'll admit when I was using scheme, most of what I used macros for were to make a dsl that had a primitive for defining functions that had normal order evaluation, and a few alternate forms like case and a few others.

Lawrence, I agree with most of what you are saying, but where I disagree is that I think that lazy evaluation does reduce uses of macros -- at least in my experience, anyway. The reason why I say this is because this is almost exclusively what I use them for in scheme and emacs-lisp, so I think that they would potentially be an asset even for the syntactially-rich python, (or your language converge, but since you're already supporting compile-time metaprogramming so it's not an issue) for that reason alone.

In general: (not to anyone specific)

I think that if I were not using haskell, a special form that I made in scheme (scsh actually), called sudo (a specific synactic sugar for delaying an expression until the user put in their password) would be still a viable use of macros that wouldn't be in the case of lazy evaluation. Now I know things like that sound cheesy, but I like to add domain specific features of that nature. (and of course that would be effortless in haskell)

Other than that, in a language with a minimalist syntax I was also interested in adding an optional whitespace syntax to scheme, but of course both python or haskell already have that...

Interesting thoughts, anyhow.

Neil Mitchell said...

anon: I think compile time evaluation is very important, but optimising lazy compilers already do absolutely loads of this already. I just don't think the user should have to decide what's a compile time thingy, and whats a runtime thingy.

Ashish Hanwadikar said...

I tried to write a GNU Make replacement in Haskell. One place I really missed lisp (or scheme) macros, is when I had to use two statements in order to a get a build rule in the system: one statement to declare the rule (build this target when its dependencies are out of date, with this command) and another one to register the rule in the rules database. See the post for details .
The conjure system, written in scheme48, uses the syntax-rules to automatically register the goal and its rules when they are declared.

Omar AntolĂ­n Camarena said...

Just chiming in to say I also wonder why you don't consider Template Haskell to be a (slightly awkward) macro system for Haskell.

Neil Mitchell said...

Omar: I would consider template Haskell to be a macro system for Haskell - and all I said about macros still applies to Template Haskell to some degree.

Anonymous said...

Wouldn't Haskell have macro's automatically if everything was first class including types and Haskell programs?
Then a macro would be able to accept a Haskell program, parse it, replace the types and functions, and return a new program.
There doesn't seem to me to be anything mathematically ambiguous about this. Certainly its use cases seem limited, but...

Patrick Mahoney said...

Anonymous,
yes, Haskell would have the ability to parse trees of Haskell code if everything, including types, were first class. However, making everything first class isn't an easy fix. It would require the adoption of a new type theory in Haskell. What you propose is still on the horizon of computer science, and is one of the things that mathematical type theorists have struggled for years to accomplish-a type system that can adequately express types. Second-order logic based type systems like the one in Haskell were created specifically to avoid the problems and paradoxes that are created by making everything first class. Making everything first class (without implementing something like dependant typing), is regressive to the extreme. The programming language of the future may have first class everything, but it is not as easy as you make it out to be-it is one of the hardest problems facing computer science today.

Anonymous said...

> pi is a function (a constant arity function, but still a function)

No, it’s not.