Compiling Lambda Calculus | Hacker News Reader

Compiling Lambda Calculus

t3x.org

78 pointsnils-m-holm15 comments

Seeing how Scheme is enjoying a temporary HN frontpage resurgence:

This is from the same author as the more popular:

"Scheme 9 from Empty Space" "A Guide to Implementing Scheme in C"

which walks you through the design and implementation of a portable Scheme in C89, with awesome cover art to match the name.

(http://t3x.org/s9book/index.html)

How does this relate to https://www.microsoft.com/en-us/research/publication/the-imp... or https://www.microsoft.com/en-us/research/publication/impleme... ?

The book by Peyton Jones et al is certainly broader, covering denotational semantics, pattern matching, polymorphism, list comprehension, type-checking, laziness, garbage collection, etc. It has also quite a few chapters on Miranda, Wadler's (one of the co-authors) favorite language.

Compiling Lambda Calculus (CLC) concentrates on one thing: compiling untyped lambda calculus (or its incarnation, Scheme) to abstract machine code and then to C. It goes more into the depths of lambda calculus and has more examples (like Church numerals, etc). It also contains the complete source code to all compilers described in the text.

I would argue that CLC would be the better choice for a beginner.

The SPJ book is from 1987, so more than 3 decades old. There has been quite a bit of progress in compilers since. While I'm not up to scratch on the latest version of the GHC compiler, it's quite a bit different. I recommend looking at Peyton Jones and Marlow's overview article [1]. The Scala compiler(s) are also interesting. I'm not aware of an overview article, but I found last year's [2] worth reading. A big breakthrough in the compilation of functional languages was Xavier Leroy's on (O)Caml. I am not aware of any recent descriptions, but maybe [3, 4] are better than nothing. Note that languages like Javascript have full functional sublanguages, so all recent progress in JIT compilation for Javascript could/should be considered here too.

Historically, the main issue in the compilation of FP languages has been laziness. In a statically-scoped call-by-value language, compilation is not that different from compilation of 'normal' languages.

[1] S. Marlow, S. Peyton-Jones, The Glasgow Haskell Compiler. http://www.aosabook.org/en/ghc.html

[2] D. Petrashko, O. Lhotak, M. Odersky, Miniphases: Compilation using Modular and Efficient Tree Transformations. https://infoscience.epfl.ch/record/228518/files/paper.pdf

[3] X. Leroy, Functional programming languages Part II: abstract machines.

[4] X. Leroy, The ZINC experiment: an economical implementation of the ML language.

Looking at the table of contents, it seems like an implementation oriented version of part 1 of "Semantics Engineering with PLT Redex" by Felleisen et al. Anyone know what abstract machine it uses? I'm guessing Landin's SECD machine since that seems to be the most common.

The book uses a virtual stack machine that may be thought of as an ad-hoc implementation of the SECD machine.

I find larger text bodies in a grotesque font hard to read. A serif font would be friendlier.

I think it is excusable in this case, because there is a lot of leading space between the lines and most paragraphs are short.

Have you tried reading a few pages? It grotesque really distracting in this particular case or is it just your general experience?

If you're not making any money from selling your books, why not make them available for free? They will reach a much wider audience.

(1) People do not value free stuff.

(2) To some people (like me), a few 100 EUR per month can make a huge difference.

I do value free stuff, but I also value you as an author. Happy to pay for my PDFs of your work.

Good to hear, thank you!

And I agree, the generalization above was too broad -- I also value free stuff!

But as a generalization I think it holds true. On average, free stuff is not valued very highly by the general public. Or rather, a person selected at random will not perceive much of any value is something given away for free.

Bought a copy, into chapter 2,good read so far, font is readable too as far as I can tell

I'll echo GeoffKnauth, I'm glad to have paid you for several of your books. I'm looking forward to starting the introduction to Klong book, as I find array languages fascinating but there's a regrettable lack of beginner materials for many.

Incidentally, the 6x9 PDF size is great on a Kindle Oasis, the print is a bit small but it works. This is in contrast to most other PDF ebooks, which I would have great difficulty reading on the Kindle, so thank you also for that!

Reply on news.ycombinator.com