[mod.ai] Lisp & lazy evaluation

DESMEDT@HNYKUN52.BITNET.UUCP (06/02/86)

In AIList Digest V4 #134, Mike Maxwell reluctantly prefers the efficiency
of a hand-coded "do" construction in Lisp, although mapping a function on
a list would be more elegant. Indeed, mapping sometimes causes many
unnecessary computations. Consider the following example:

(defun member (element list)
  (apply 'or (mapcar #'(lambda (list-element)
                         (eql element list-element))
                     list)))

One solution to prevent wasteful computation is a "lazy" evaluation mechanism,
which computes only as much as is needed by other computations. For example,
the mapping in the above example would be performed only up to the point where
"or" finds a non-nil value and doesn't want to evaluate any more arguments.

Anyway, I don't really want to lecture here, but I want to ask a question:
has anyone out there experimented with lazy evaluation in a Lisp system?
Are any working systems (or prototypes) available? Any good references to
the literature?

Koenraad de Smedt            desmedt@hnykun52.bitnet

@gatech.UUCP (06/07/86)

The bibliographies contained in the two books

	Henderson, Peter,
	``Functional Programming:  Application and Implementation,''
	Prentice-Hall International,
	London,
	1980.

and

	Darlington, J., Peter Henderson and David A. Turner, editors,
	``Functional Programming and its Applications:  an Advanced Course,''
	Cambridge University Press,
	Cambridge,
	1982.

point to the following historical references:

	Burge, W. H.,
	``Recursive Programming Techniques,''
	Addison-Wesley,
	Reading, Massachusetts,
	1975.

	Friedman, D. P., and D. S. Wise,
	`CONS Should Not Evaluate its Arguments,'
	in ``Automata, Languages and Programming,''
	S. Michaelson and R. Milner, editors,
	Edinburgh University Press,
	Edinburgh,
	1976

	Henderson, Peter and J. M. Morris,
	`A Lazy Evaluator,'
	in ``Proceedings of the 3rd POPL Symposium,''
	Atlanta, Georgia,
	1976.

	Kahn, G., and D. McQueen,
	`Coroutines and Networks of Parallel Processors,'
	in ``Information Processing 77''
	North-Holland,
	Amsterdam,
	1977.

	Landin, P. J.,
	`A Correspondence between Algol 60 and Church's Lambda Calculus,'
	in ``Communications of the ACM''
	Volume 8, number 3,
	pages 158-165,
	1965.

	Vuillemin, J. E.,
	``Proof Techniques for Recursive Programs,''
	Memo AIM-318, STAN-CS-73-393,
	Stanford University,
	1973.


You may also want to ask David Turner about his experiences with his ``Miranda''
functional programming environment.  Indeed, he is distributing it, if you would
like to play with it yourself.  His electronic address is:

	dat%ukc@ucl-cs

(He's currently at the University of Kent at Canterbury.)