The Lambda Papers

I’m reading about functional programming as much as I can. Aside from staying up-to-date with the latest publications I also spend some time reading the older papers. Among the classics are true pearls: John Backus’ “Can Programming Be Liberated from the von Neumann Style. A Functional Style and Its Algebra of Programs” took hours to read but was an eye-opener for me (I think this was the first paper on FP I ever read) and Phil Wadler’s “Comprehending monads” and “The essence of functional programming” are a beautiful demonstration of power and elegance of monads. But today I want to write about The Lambda Papers – a series of approximately 10 papers (mostly AI Lab Memos) written by Guy Steele and Gerald Sussman between 1975 and 1980. I originally heard about them while browsing Lambda The Ultimate (which, by the way, takes its name from these papers).

ltuiLambda papers revolve around the programming language Scheme, a simple dialect of Lisp developed by Steele and Sussman at MIT in the seventies. So far I have read two of these papers – “Lambda: The ultimate imperative” and “Lambda: The ultimate declarative”. The first one discusses the implementation of programming constructs know from imperative languages – for example GOTOs, blocks, assignments, loops or exceptions – in Scheme. Authors demonstrate that lambda expressions, that is anonymous functions, suffice to implement all these imperative constructs. Moreover, they show that using lambdas we can easily implement different scoping strategies (dynamic vs. static) and calling conventions (call by name vs. call by value vs. call by need). “Lambda: The ultimate declarative” continues the discussion of GOTO expressions started in “Lambda: The ultimate imperative”. Main focus in placed on relation between GOTOs, function calls and operations that modify environment (function call is one of them, assignments are another). The paper provides some really deep insight into the mechanisms of compiling function calls. For example, authors demonstrate that in compiled Scheme code it is not necessary to make any function calls – GOTOs (unconditional jumps) are all that is needed. There’s also an interesting discussion on defining data types using closures and named variables vs. temporaries (unnamed variables generated by the compiler). Paper concludes with a thought that the expressive power of Lisp makes it a good candidate for an intermediate language used in compilers.

As I already mentioned I consider these papers to be one of the best papers I have read. I am truly impressed with the amount of knowledge squeezed into these 90 pages. Probably the most surprising thing is that after almost 40 years since their original publication Lambda Papers remain relevant. It is interesting to see that some ideas are mentioned briefly in those papers and today these ideas have evolved into really important concepts. For example Steele mentions in “Lambda: The ultimate declarative” about the idea of annotating functions with information about possible side effects, which is done in Haskell’s type system to separate pure and impure code. I have also found it interesting to learn a bit about history of computer science and trace the origin of concepts like thunks and continuations.

That’s only the outline of the Lambda Papers. They provide a lot more insightful information and I strongly encourage anyone interested in programming languages to read these two publications. They are not too difficult – if you know Scheme you’ll be able to grasp them.

4 Responses to “The Lambda Papers”

  1. Wei Qiu says:

    Nice post.
    Made me also want to read these original papers.

    There is a typo here, maybe you need to find a better spell checker:)

    “That?s only the outline of the Lmabda Papers. “

  2. Jan Stolarek says:

    Typo fixed. I just need to pay more attention to my spell checker :-)

  3. Edwin Dalorzo says:

    Great article. These references are great. Your link to The Essence of Functional Programming is not working. I tried to download the postcript file but it takes me to a page that says the link I am looking for no longer exist.

  4. Jan Stolarek says:

    Sorry about the broken link, I didn’t add http:// – it’s fixed now.

Leave a Reply


Staypressed theme by Themocracy