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).
Lambda 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.
Exactly one year ago I was in the middle of reading “Seven languages in seven weeks” by Bruce Tate. This book introduced me to functional programming with languages like Erlang, Scala, Haskell and Lisp. Now, the Lisp part is the interesting one. I was googling some things about Lisp and somehow I landed on Paul Graham’s page. His essays on Lisp fascinated me so much that I decided to learn me some Lisp for great good. So when I reached the chapter about Clojure (Lisp dialect for JVM) I actually decided to skip it and learn more on my own. After some googling I settled on Scheme (another alternative was Common Lisp). I began with reading the official R5RS specification (only about 50 pages) but that definitely wasn’t enough. On various blogs and sites on the Internet I found people talking about this book The Little Schemer by Daniel P. Friedman and Matthias Felleisen, how great and different from other books it is and how it can change the way you think. I decided to give The Little Schemer a try.
The first thing I noticed after opening the book is that it is indeed unlike anything I have read so far. Instead of explaining things directly, the book presents a dialogue between the authors and a reader. There are no paragraphs, just two columns of text – left with authors’ questions, the second with reader’s responses. This dialogue is very informal and usually ends up with talking about food. Sounds strange? Well, it was at first but as I went on I found this style very fun. Of course reading is not enough – you have to actually work through the code on your own and I admit that I found that part very entertaining and rewarding, especially when I was able to figure out solutions before reading them.
The book consist of ten chapters. Eight of them are dedicated to general lisp programming. Book starts with simple concepts like basic operations on lists and moves on to more and more advanced aspects of recursion. I feel that it has learned me how to think in a recursive way, which in turn made learning Haskell much easier. Last two chapters of the book are quite difficult though. Chapter 9 gives a step by step derivation of the Y-combinator. Well, almost step by step – I had a feeling that some parts were actually left out and I had problems understanding what is going on. Luckily Peteris Krumins has written a great post in which he derives Y-combinator and fills the gaps present in The Little Schemer. Even after reading that post I still needed about 3 days to understand what’s going on in the Y-combinator, but once things clicked it was my “Aha!” moment. That’s probably the most fascinating thing I’ve learned so far in computer science. Chapter 10 pursues the goal of writing Lisp interpreter in Lisp. The beauty of Lisp lies in the fact that it is actually a relatively easy task requiring surprisingly little lines of code. Check out this article by Paul Graham to see for yourself. Solution from The Little Schemer is actually a bit more complex than the one given by Graham and again it took me some considerable effort to work my way through this chapter.
At the end of The Little Schemer there are some references to books that in the authors’ opinion are worth reading. This is not only computer science stuff – among references is The Annotated Alice: Alice’s Adventures in Wonderland and Through the Looking Glass by Lewis Carroll – and I found one of the listed books to be very fascinating: To Mock a Mockingbird by Raymond Smullyan. It’s an introduction to combinatory logic given in a form of riddles. I’m somewhere in the middle and will hopefully finish reading it some day.
I guess the opinions on the internet were right – The Little Schemer is a great book and it really teaches how to think in a recursive way. I suggest reading it to anyone who is interested in being a better programmer, functional or not. This will be a good investment, especially that reading the book doesn’t take much time (authors warn the reader not to read it in less than three sittings).
Finally, there’s a sequel to The Little Schemer called The Seasoned Schemer. Unfortunately I was unable to find it so if any of you has a spare copy and would be willing to send it to Poland just let me know :-)