OLisp: Lazy Evaluation in a Small Purely Functional Lisp System

Ora Lassila

Appeared in: Matti Karjalainen, Jouko Seppänen and Markku Tamminen (eds.), STeP-86 Symposium Papers: Methodology, volume 2, Finnish Artificial Intelligence Symposium, Otaniemi (Finland), Finnish Society of Information Processing Science, 1986


The paper presents the results obtained from the implementation of a lazy evaluation scheme in a purely functional Lisp system on a microcomputer . The mechanisms of lazy evaluation in list constructors and maps are described. Examples of computing with infinite structures and parallel routines in a lazy system are given. Lazy evaluation liberates the programmer from defining termination conditions in recursive functions and from the need of explicitly specifying the flow of control in parallel, coroutine -like computations. Thus a more declarative style of programming can be achieved. Test results are given of a comparison of normal and lazy evaluation schemes.

With functional languages the terms delayed and lazy evaluation mean an evaluation strategy where the values of argument forms in a function call are not computed until actually needed. Forms are delayed, which means that a new form called a delay is substituted for an old form. When the value of the old form is later required, the computation of the delay is forced, i.e. the old form is evaluated in the environment in which it was delayed. Delaying and forcing may be effected by the programmer (we will call that delayed evaluation) or automatically by the system (lazy evaluation).

The aim of the paper is to present a practical Lisp-based solution where evaluation order and parameter handling are normal except with list constructor functions, which delay their last argument, causing the cdr of a list to be constructed not until it is accessed for the first time. Despite its restrictedness our scheme offers considerable advantages over the conventional evaluation scheme.