Implementation of Functional Languages (a.k.a. Graph Reduction) Course Plan (Preliminary)

Thomas Johnsson 10 October 1995

This course is about the implementation of lazy functional languages using lazy graph reduction, and in particular techniques for efficient compiled implementations.

This course covers 5 points of the basic block of 10 points in “Functional languages: compilation, analysis and transformation” (second half given by John Hughes).

Plan for lectures (preliminary)

• Introductory overview. What is graph reduction? Overview of compilation steps.

• Supercombinators and lambda lifting. SPJ ch 13,14,15. (alt: PJ-L92 ch 6).

• The G-machine. SPJ ch 18,20

• Compiling/transforming pattern matching. SPJ87 ch 5, (and/or Aug87a).

• Compiling/transforming list comprehensions. SPJ87 ch 7, (and/or Aug87b).

• Memory management and garbage collection. Appel 91 (suplementary handout: Wilson 93).

• Target code generation. Johnsson87.

• (Possibly also: Basic polymorphic type inference.)

Summary of Litterature

SPJ87 Simon L. Peyton Jones, The Implementation of Functional Programming

Languages, Prentice-Hall, 1987.

PJ-L92 Simon L. Peyton Jones, David Lester, Implementing Functional Languages:

A tutorial, Prentice-Hall 1992.

Wilson 1993 P. R. Wilson, Uniprocessor Garbage Collection Techniques, ACM Comput-

ing Surveys, 1993 (?).

Appel 1991 Andrew Appel, Garbage Collection, chapter 4 of Peter Lee (ed.), Topics in

Advanced Language Implementation, MIT Press 1991.

Peyton Jones 1992 Simon L. Peyton Jones, Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine, Journal of Functional Programming, April 1992.

Johnsson 1987 Target code generation from G-machine code, PMG report 39 (thesis part

D). (1987).

Augustsson 1987a Compiling pattern matching, PMG report ?? (thesis part D). Augustsson 1987b The Semantics and Compilation of List Comprehensions, PMG report ??

(thesis part E ?).

My slides from my lectures are also available for copying (handed out when possible).

The project

This course also has a project; in fact I think that the main bit of the course should be the project. The only way to learn this stuff properly is to do all the bits oneself! So therefore I require that the number of people in each project group is at most one.

The project is to build a little implementation of a lazy language containing most of the essential ingredients of a fully fledged implementation.

Below are the minimum requirements of the implemented language and the implementation itself. Language The intention is that the language should be a tiny subset of Haskell. The language that your compiler deals with should have at least the following things:

• types: integers and lists.

• expressions:

1. integer constants

2. identifiers

3. applications (of course)

4. case expressions, with non-simple patterns

5. lambda expressions

6. letrec (or where rec) expressions, i.e., local (recursive) definitions. a definition is simple: identifier = expression . There could be more that one definition in a letrec/where(rec).

7. a few representative primitive basic valued operators, for example <, +, - and *.

• A program is a sequence of definitions, of which one must be main = ... . The compiler Your system should contain at least the following things:

1. A lambda lifter (of the simplest possible kind).

2. A pattern matching transformer,

3. G-code generator, with at least the schemes E and C, but preferably also R and B (they should be easy to add once you have E and C !)

4. a ‘target code generator’ generating code in the C language.

You may write your compiler in whatever language you like. But to encourage you to use Haskell or Gofer, I’ll (try to) dig out a parser you can use as a front end. For the keen/adventurous: Here are some ideas on how you could extend the language/system if you feel like it (in no particular order):

• The book mentions several ways to do lambda lifting: implement a more clever one!

• Use a spineless abstract machine (to improve the efficiency of higher order functions).

• Add a full-laziness transformation phase.

• Add list comprehensions.

• Add a garbage collector to your system.

• Add a polymorphic type checker.

• Write a simulator for parallel graph reduction.

• Add user definable data types.

• Extend your compiler to accept full Haskell (warning: life-time project:-)

Examination:

You demonstrate your system to me.