3

Are there any practical references (with actual examples) for getting started implementing a small, lazy functional programming language with graph reduction? A reference that included the lexing and parsing steps would be especially helpful.

So far I've read most of the Implementation of Functional Programming Languages by Simon Peyton Jones and the Wizard book (SICP).

Improve this question

1 Answer 1

Reset to default
5

SPJ has written two books with very similar titles:

  • The implementation of functional programming languages, Simon Peyton Jones, Prentice Hall 1987.
  • Implementing functional languages: a tutorial, Peyton Jones and Lester.

Both are available here. The second one is more focused on compiling and executing code, including G-machines in Chapter 3. Quoting its overview:

The principal content of the book is a series of implementations of a small functional language called the Core language. The Core language is designed to be as small as possible, so that it is easy to implement, but still rich enough to allow modern non-strict functional languages to be translated into it without losing efficiency. It is described in detail in Chapter 1, in which we also develop a parser and pretty-printer for the Core language.

Appendix B contains a selection of Core-language programs for use as test programs thoughout the book.

The main body of the book consists of four distinct implementations of the Core language.

  • Chapter 2 describes the most direct implementation, based on template instantiation.
  • Chapter 3 introduces the G-machine, and shows how to compile the program to sequences of instructions (G-code) which can be further translated to machine code.
  • Chapter 4 repeats the same exercise for a different abstract machine, the Three Instruction Machine (TIM), whose evaluation model is very different from that of the G-machine. The TIM was developed more recently than the G-machine, so there is much less other literature about it. Chapter 4 therefore contains a rather more detailed development of the TIM's evaluation model than that given for the G-machine.
  • Finally, Chapter 5 adds a new dimension by showing how to compile functional programs for a parallel G-machine.

For each of these implementations we discuss two main parts, the compiler and the machine interpreter. The compiler takes a Core-language program and translates it into a form suitable for execution by the machine interpreter.

...

Improve this answer
2
  • Wow, fantastic that's exactly what I was looking for—I'm surprised I hadn't run into it before.
    – user60017
    Commented Feb 9, 2013 at 19:51
  • @JoshVoigts It's somewhat hard to find. I read the first book and I didn't know about the other too, until one student showed it to me. Probably it's because they're named so similarly and the first one is more known, so the other one is easily overlooked.
    – Petr
    Commented Feb 9, 2013 at 19:56