From: ajtd@honey.st-and.ac.uk (Tony Davie)
Newsgroups: comp.lang.functional
Subject: Re: Documentation required
Date: 30 Sep 92 09:31:02 GMT
Organization: St.Andrews University

Kees de Bruin says:

> I have got the book of Peyton-Jones (implementation of
> functional programming languages) but this does not say anything about how
> to implement higher order functions.
> 

Forgive me for mentioning it, but I don't think you have understood Simon
Peyton Jones' book if you think that. Simon's book says EVERYTHING about how to
implement h.o. fns and moreover that's really what the whole book is about.
However his book does not use the closure model. It's more geared to the G-machine
which does things in a different way (but see pp 378 et. seq.). Functions
are lambda lifted using a process (invented independently by John Hughes
and Thomas Johnsson) so that they don't have any free variables. In effect
what used to be free variables are passed to the function as extra parameters.
This means that closures which are used as the implementation of functions by
carrying around their free variables are not needed.

Really of course the closures are still there in an implicit form.
Consider a function f, of 4 variables say. Suppose it is partially applied
to three of them, a, b and c. This gives rise to a function stored in graph
space

                                       @
                                      / \
                                     @   c
                                    / \
                                   @   b
                                  / \
                                 f   a

-- and what is this but a closure with a,b and c being the free variables?

> I know how the closure model works, but I need some background on the subject.
> Is there anyone who has got some ideas?
> 

An early paper on the closure model is Landin's original SECD machine paper:

P.J. Landin Q The Mechanical Evaluation of Expressions Q Computer Journal 6,4
1964, pp308-320

other interesting ones are

Luca Cardelli Q The Functional Abstract Machine Q Bell Labs Tech. Rep.
TR--107, 1983 --- also in Polymorphism --- The ML/LCF/Hope Newsletter
I,1, 1983

Luca Cardelli Q Compiling a Functional Language Q In Conference Record of
the 1984 ACM Symposium on LISP and Functional Programming Q Austin,
August 1984, pp208-217

A.J.T. Davie, D.J. McNally Q- CASE - A Lazy Version of an SECD Machine with
a Flat Environment Q Proc. IEEE TENCON '89, Bombay, also University of
St.Andrews Department of Computational Science Report St.A/88/2

Many functional programming books have explanations of how to implement h.o.
functions using closures. e.g.

Hugh Glaser, Chris L. Hankin, David Till Q Principles of Functional
Programming Q ISBN 0137091486 and 013709163X Prentice-Hall, 1984

C. Reade Q Elements of Functional Programming Q Addison Wesley, 1989,
ISBN: 0-201-12915-9

A.J. Field, P.G. Harrison Q Functional Programming Q Addison Wesley 1988,
ISBN 0-201-19249-7

and my own book:

A. Davie Q An Introduction to Functional Programming Systems using
Haskell Q CUP, Cambridge Computer Science Texts 27,
ISBN 0 521 25830 8 (hard) & 0 521 27724 8(paperback), 1992

I hope these help.

Tony Davie               Department of Mathematical and Computational Sciences
Tel: +44 334 76161 x8136 St.Andrews University
Fax: +44 334 77068       North Haugh
ad@dcs.st-andrews.ac.uk   St.Andrews
                         Scotland
                         KY16 9SS

Heard recently: Why do computer scientists confuse Halloween and Christmas?

Because oct 31 = dec 25.