ksb@mentor.cc.purdue.edu (Kevin Braunsdorf) (02/15/90)
When I was a student here at Purdue I read a few papers about lazy evaluation and became interested in it. Since I was writing a LISP interp. for a class project I set about to implement a lazy eval feature. What I did was much simpler than most of the systems I saw described at the time. I simply made `cons' defer evaluation of its arguments until either `car' or `cdr' was called on the resulting CONSBOX (which was tagged as being LAZY, and had a saved environment hung on it). Later I made the deferred one be `lcons' and put back the original `cons' because `lcons' is slow if you do not need the power. An example: (defun ilister (n) (lcons n (ilister (+ '1 n)))) This function will produce an infinite list of integers, starting at n. If we had a function `head' (like the UNIX command) (head '10 (ilister '0)) would only compute (about) the first 11 elements in the sequence, and output: (0 1 2 3 4 5 6 7 8 9) If anyone is interested in a silly Pure LISP interp that does this... -- Lightning strikes! Maybe once, maybe twice. Oh, and it lights up the night! Kevin Braunsdorf, ksb@cc.purdue.edu, pur-ee!ksb, purdue!ksb
djones@megatest.UUCP (Dave Jones) (02/16/90)
From article <7476@mentor.cc.purdue.edu>, by ksb@mentor.cc.purdue.edu (Kevin Braunsdorf): ... > > What I did was much simpler than most of the systems I saw described at > the time. I simply made `cons' defer evaluation of its arguments until > either `car' or `cdr' was called on the resulting CONSBOX (which was > tagged as being LAZY, and had a saved environment hung on it). Just for the record, what you did is not full lazy evaluation. But as I noted earlier, defering the evaluation of a CONS is probably the most important 'lazy deferal' for practical purposes. There's a book that explains an implementation of lazy evaluation pretty well, called _Functional Programming, Application and Implementation_, by Peter Henderson, Prentice-Hall 1980. I don't know if it's still in print or not.
db@lfcs.ed.ac.uk (Dave Berry) (02/22/90)
The best explanation I've read of evaluation orders is in Field and Harrison's book "Functional Programming", pp. 118-130. Their summary defines lazy evaluation as: Normal-Order Reduction to Weak-Head Normal Form + Sharing + Lazy Constructors or, equivalently Call By Need + Lazy Constructors They point out that other combinations are possible, such as Hope+, which uses Applicative-Order Reduction and Lazy Constructors, Othis book is a very good introduction to the different kinds of functional languages around and the different methods of implementing them. It also discusses Type Inference and Program Transformation. I'd recommend it (even though it resolutely ignores ML throughout). It's published by Addison-Wesley, ISBN 0-201-19249-7 Dave Berry, LFCS, Edinburgh Uni. db%lfcs.ed.ac.uk@nsfnet-relay.ac.uk "The thought of someone sharing one's own preferences without also sharing one's aversions strikes most people as utterly inconceivable." - C. A. Tripp.