Indiana University Bloomington

School of Informatics and Computing

Technical Report TR44:
CONS should not Evaluate its Arguments

Daniel P. Friedman and David S. Wise
(Jan 1976), 26 pages plus appendix
[I. S. Michaelson and R. Milner (eds. ), Automata, Languages and Programming, Edinburgh University Press, Edinburgh (1976), 256--284]
The constructor function which allocates and fills records in recursive, side-effect-free procedural languages is redefined to be a non-strict (Vuillemin 1974) elementary operation. Instead of evaluating its arguments, it builds suspensions of them which are not coerced until the suspensions is accessed by strict elementary function. The resulting evaluation procedures are strictly more powerful than existing schemes for languages such as LISP. The main results are that Landin's streams are subsumed into McCarthy's LISP merely by the redefinition of elementary functions, that invocations of LISP's evaluator can be minimized by redefining the elementary functions without redefining the interpreter, and as a strong conjecture, that redefining the elementary functions yields the least fixed-point semantics for McCarthys evaluation scheme. This new insight into the role of constructor fdunctions will do much to ease the interface between recursive programmers and iterative programmers, as well as the interface between programmers and data structure designers.

Available as: