Implementing functional languages

What Hacker News says

1. Joker_vDSep 2020
   K. Cooper, L. Torczon "Engineering a Compiler", 2nd ed. (2011)

   A. W. Appel, M. Ginsburg "Modern Compiler Implementation in Java" (2007)

   S. Muchnick "Advanced Compiler Design and Implementation" (1997)

   The last book focuses entirely on program analysis and optimization. It even has a chapter on optimization for the memory hierarchy! Of course, since it's a rather dated book, the specific details in that chapter are mostly useless today, but the rest is solid.

   However, those books mostly cover imperative languages (although Appel & Ginsburg devote a chapter on functional languages, both of strict and lazy variety and discuss some optimization challenges), so if you want to learn about implementing functional languages...

   S. L. Peyton Jones et al. "The Implementation of Functional Programming Languages" (1987)

   A. W. Appel "Compiling with Continuations" (1992)

   Holy fatcats, those are some old books! But sadly, I am not aware of more modern ones. Try searching for papers on the topics that interest you in particular, I guess (for example, there are several papers that discuss appropriateness of using CPS as IL: "Compiling with Continuations, Continued", "Compiling without Continuations", and "Compiling with Continuations, or without? Whatever". Yes, the puns seem to be the noble tradition in the PL implementation circles). The first book starts as a general introduction but starting at about the middle firmly steers into implementing a lazy languages. The second is pretty much a description of how SML/NJ compiler was made, based on its state in about 1991, of course, and has some interesting benchmarks on efficiency of different implementations of closures.

   Plus, there are lot of random pages on the web with resources for various compiler implementation courses from different universities. For one arbitrary example, https://course.ccs.neu.edu/cs4410/

   Show morethread
2. toolsliveDec 2015
   "Implementing functional languages: a tutorial" Simon Peyton Jones http://research.microsoft.com/en-us/um/people/simonpj/Papers...

   Is very good and shows different strategies for the runtime.

   thread
3. RiderOfGiraffesJul 2009
   It's not the same thing, in the same sense that "Lazy Evaluation" is not the same thing as "Non-strict Semantics", but "Term Re-Writing" is closely allied with "Graph Reduction. Simon Peyton-Jones' books "The Implementation of Functional Programming Languages" and "Implementing Functional Languages: a tutorial" are excellent works. Now out of print, they can both be found on-line.

   The following references also help ...

   http://www.google.com/search?q=implementing+functional+langu...

   http://www.google.com/search?q=graph+reduction+term+rewritin...

   Show morethread
4. mcguireMay 2014
   In addition to the article here and "Write Yourself a Scheme in 48 Hours" (the implementation language is Haskell, which may be a barrier)[1], and some others mentioned in the comments here, there's Peter Norvig's "(How to Write a (Lisp) Interpreter (in Python))"[2] and "(An ((Even Better) Lisp) Interpreter (in Python))"[3].

   Every last Lisp book out has at least one implementation of a Lisp evaluator, although most don't go into all of the other stuff you have to do like parsing. On the other hand, there are a lot of books and articles that focus on parsing as if it were the most important part.

   Someone has already mentioned Structure and Interpretation of Computer Programs[4], additionally, there is the Essentials of Programming Languages[5], Paul Wilson's An Introduction to Scheme and its Implementation[6], and some things I haven't read, like Simon Peyton Jones and David Lester's Implementing functional languages: a tutorial[7].

   [1] http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H...

   [2] http://norvig.com/lispy.html

   [3] http://norvig.com/lispy2.html

   [4] http://mitpress.mit.edu/sicp/full-text/book/book.html

   [5] http://www.eopl3.com/

   [6] ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html

   [7] http://research.microsoft.com/en-us/um/people/simonpj/Papers...

   Show morethread