The Implementation of Functional Programming Languages
Stats for nerds
22recommend
44mentions
33people
2008–2026years
70% recommend27% neutral2% critical
Mentions per year
What Hacker News says
- The C in CPS and the cc in call/cc are exactly the same thing.
It’s a continuation. You don’t need to express your program in continuation passing style to use continuation which is why call/cc exists.
The idea of continuation is interesting in and of itself independently of if your compiler uses CPS because continuation as a concept is useful. It appears in effect system for exemple.
Apple book is very good by the way. It gives a very hand on overview of how to implement a compiler in a functional style and neatly introduces some quite complex ideas. To me it’s amongst the books you can’t regret reading also it’s quite short and easy which helps. Timeless classic like Peyton Jones The implementation of functional programming languages and is great introduction to lambda calculus and presentation of how to implement a type checker in Miranda.
- I enjoyed Types and Programming Languages by Benjamin Pierce. Also vaguely related is the Implementation of Functional Programming Languages by Simon Peyton Jones (this is more about lambda calculus, but I found that when you pair type theory with lambda calculus you get some nice synergies as a programmer).
- > I think that depends on what you meany by "pattern matching"
Oh, yes, that's true. "Pattern matching" as that what normally is used in "functional programming languages". This kind of pattern matching does not need unification. The IMHO best (correct, but understandable and with all needed definitions) explanation of it is in chapters 4 "STRUCTURED TYPES AND THE SEMANTICS OF PATTERN-MATCHING" and 5 "EFFICIENT COMPILATION OF PATTERN-MATCHING" of Peyton Jones et al., "The implementation of functional programming languages".
https://simon.peytonjones.org/slpj-book-1987/
> In programming cirlces "pattern matching" usually means matching strings.
Depends on the "circle" ;) https://en.wikipedia.org/wiki/Pattern_matching
- This is a bit Haskell oriented, but the "Implementation of Functional Programming Languages" by SPJ is one of my all time favorite books.
https://simon.peytonjones.org/slpj-book-1987/
These compilers were pulling heroic data structure optimization stunts in 1985, that no modern production compiler for major compiled languages can replicate in 2024.
- TL;DR — Nope, but here is a list of what such a course would use for reading material.
As referenced in another comment, Simon Peyton Jones has a 1987 book on compiling functional languages, The Implementation of Functional Programming Languages. Follow that up with some of the referenced papers contained therein and you will have a base level to start at. Following the FP academic boom of the 80’s I would look to the following (in no particular order): papers of Stephanie Weirich, Simon Peyton Jones, Simon Marlow, Odersky, Philip Wadler and other authors you would find being referenced in their papers; the webpages for the Koka language, Idris, the Granule project, Haskell, and Ocaml all have references/publication sections that will contain a wealth of material.
It is kind of a shame there is not a more ‘one-stop-shop’ for functional language compiling, but the research is so broad it would be hard to condense. You aren’t going to go wrong starting from SPJ’s book as the basis. Jones has a talk on YouTube about ‘Fitting Haskell into Nine Terms’ which is based on a paper that discusses the compilation strategy for GHC regarding the push to keep the internal System Fc language small and clean that is a good watch, along with the Jones talk on Compiling without Continuations also on YouTube and gives more internal views of GHC.
Sorry the list is a bit scattershot, if you need more specifics I will certainly try to find a more narrow selection.
- A (IMHO) good and easy to read introduction is Wadler's "EFFICIENT COMPILATION OF PATTERN-MATCHING", chapter 5 of "The Implementation of Functional Programming Languages" https://simon.peytonjones.org/assets/pdfs/slpj-book-1987-2up... - actually I can recommend the whole book as an instruction to (the interesting stuff of) writing a compiler for a functional language. It also contains an introduction to the lambda calculus.
Related
Implementing functional languages
3 recommend · 4
Functional Programming in C++
3 recommend · 6
Structure and Interpretation of Computer Programs
347 recommend · 761
Real-world functional programming
12 recommend · 19
Purely functional data structures
87 recommend · 209
Practical Common Lisp
218 recommend · 400
