Lambda the Ultimate

Simon Peyton Jones book on the Implementation of Functional Programming Languages, circa 1987, is available online.

This book is about implementing functional programming languages using lazy graph reduction, and it divides itnto three parts.



The first part describes how to translate a high-level functional language into an intermediate language, called lambda calculus, including detailed coverage of pattern-matching and type checking. The second part begins with a simple implementation of the lambda calculus, based on graph reduction, and then develops a number of refinements and alternatives, such as super-combinators, full laziness and SK combinators. Finally, the third part describes the G-machine, a sophisticated implementation of graph reduction, which provides a dramatic increase in performance...

via the Haskell mailing lists. I've seen lots of references to this work, as it was one of the seminal works in the development of the Haskell programming language. But I can't find where it was directly discussed on LtU before.

So I think it's really important that we approach metaprogramming with caution. I think Guido has been right to resist macros. Not because they are necessarily wrong, but because we haven't yet figured out how to do them right. And maybe we never will, maybe source code simply isn't the right level for abstractions. I think it's good that Python doesn't do tail-call elimination; it seems like a nice feature, but in subtle ways it makes the language harder. And I think continuations could lead to bad things. There are wrong paths on the road to higher-level programming. (Though in some ways I also feel the opposite: tell us not to shoot ourselves in the foot, and expect us to listen, don't assume we'll abuse every feature that exists; there's always a tension in these design choices.)

This deserves more attention than I can give it right now, but I am sure others here will want to comment.