Common Lisp is a functional language (and also an imperative, object-oriented one, which, moreover, can be used in a declarative fashion). As a functional language it falls in the category of strict languages like ML and OCaml, unlike Haskell, which is in the category of normal-order or lazy languages.
That is to say that the following code will enter an infinite loop, should be executed at the CL prompt.
cl-prompt> (defun si (condicio ergo alternatio)
(if condicio
ergo
alternatio))
SI
cl-prompt> (si t 42 (loop))
; ... looping ...
In a lazy language the function si (if in Latin) would return 42 instead of waiting for the form (loop) to produce a value.
In a bout of Haskell envy, I decided to look into some extensions to CL that would introduce ways to program in a lazy way. The result may sound crazy, and, in fact, a little bit it is.
The notion of lazy evaluation dates back to the Algol days and the notion of by-name parameter passing. In the Lisp camp, the best known way to introduce a form of lazy evaluation is to implement streams as described in Structure and Interpretation of Computer Programs (SICP) [SICP]; incidentally this form of lazy evaluation is also used by Okasaki [O98] in his exposition of functional data structures in ML.
In SICP, streams are implemented using two primitives, force and delay, which can then be used to build a lazy container (the "stream") using a macro cons-stream, and two accessors head and tail. A sufficient implementation in CL is the following:
(defmacro delay (expr) `(lambda () ,expr))
(defun force (thunk) (funcall thunk))
(defmacro cons-stream (head tail) `(cons ,head (delay ,tail)))
(defun head (lazy-stream) (car lazy-stream))
(defun tail (lazy-stream) (force (cdr lazy-stream)))
At this point there are several CL packages floating around the net, that implement this flavor of lazy evaluation. E.g., Heresy, funds and FSet are exemplars of this approach. CLAZY goes off a (different) tangent and provides a more fundamental way to build such lazy contructions.
Of course, one could always implement the operator si as a macro using delay, as in
(defmacro si (condicio ergo alternatio)
`(if (force ,condition)
(force (delay ,ergo))
(force (delay ,alternatio))))
but this is a bit unsatisfactory as far as Haskell envy is concerned. si cannot be funcalled in any meaningful way and cannot be passed around as we would expect a regular function to be.
It turns out that it is possible to come up with a more satisfactory solution that will allow us to bypass delay and force, and write si as:
(deflazy si (condicio ergo alternatio)
(if condicio ergo alternatio))
at the price of tweaking the "calling convention". deflazy defines also a strict version of the operator.
The lazy function si can now be called as
CL prompt> (lazy:call 'si t 42 (loop))
42
I.e., lazy:call is the lazy version of funcall. The complexity of writing lazy code is thus moved to the call points. This may or may not be desirable, but it can be argued that this is a slightly better way than having to manually force expressions. In any case, the CLAZY approach still uses the delay/force duo under the hood, and they are available for more manual intervention.
From the example above, it should be apparent that lazy:call is a macro that does something special with the call, recognizing functions that are defined via deflazy. As a matter of facts, the expansion of lazy:call looks like this:
(lazy:call <op> <arg1> <arg2> ... <argn>) ⇒ (funcall <lazyfied op> <thunked arg1> <thunked arg2> ... <thunked argn>)
The "lazy" version of <op> is defined by deflazy and each <thunked argi> is a closed over version of the argument as if delay was invoked on it.
Of course, a simple version of such idea can be easily implemented with a few macros, however, a well integrated version within the overall CL environment requires a few more bits and pieces. As example, CLAZY wants to make the analogy between lazy:call and funcall as tight as possible. This means that we need a way to pass (almost) regular lambda's to lazy:call. This can be done the indicator lazy.
CL prompt> (lazy:call (lazy (lambda (condicio ergo alternatio)
(if condicio
ergo
alternatio)))
t
(+ 20 20 2)
(loop))
42
Extra work is needed to handle &optional and &key parameters, but the overall design lies in this tweaking of the calling point and in allowing lazy functional objects to be passed around as regular functions (of course to be called via lazy:call).
Another example which turns out to be more easily realizable with CLAZY is the standard "conses are functions" one.
;;; Using the LAZY package...
;;; You may also have to turn off implementation dependent 'package locks'.
(def-lazy-function cons (head tail)
;; DEF-LAZY-FUNCTION defines only the lazy version of a function.
(<cons> ; This call is 'strict'.
(delay head)
(delay tail)))
;;; <cons> could really be CONS. However, in the
;;; implementation it is the lazy-cons structure constructor.
;;; HEAD and TAIL accordingly...
Now, we can build truly lazy lists.
CL prompt> (defparameter ll (lazy:call 'cons (loop) (lazy:call 'cons 2 (lazy:call 'cons 3 (loop))))) LL CL prompt> (head (tail ll)) 2
Or the usual streams from SICP.
(defun integers-from (n) (lazy:call 'consing n (integers-from (1+ n)))) (defparameter integers (integers-from 0))
Using the convenience lazily block and the convenience
diverge function, the consing
example above becomes:
CL prompt> (defparameter ll
(lazily (cons (loop) (cons 2 (cons 3 (diverge))))))
LL
CL prompt> (head (tail (tail ll)))
3
Now that we have a lazy CONS we can build a lazy LIST with
(def-lazy-function LIST (&rest args) ...).
CL prompt> (defparameter ll
(lazily
(format t "Calling LIST lazily.~%") ; FORMAT is called strictly.
(list (loop) 2 3 (diverge)))
Calling LIST lazily.
LL
CL prompt> (head (tail (tail ll)))
3
CLAZY is supposed to be used in a very controlled way. While it is true that it adds normal order evaluation to CL, the user must remember that s/he is not using Haskell or a similar language. At its core, CL is a strict language, which allows side-effects; not a good mix to produce code in a careless way. See also the note on normal order evaluation in SICP section on streams.
I am sure there is. Most likely by leveraging the CLOS, and, in particular FUNCALLABLE-STANDARD-CLASS/OBJECT where appropriate. It is a direction worth exploring.
The CLAZY reference implementation can be found at common-lisp.net. The implementation lies within a package nicknamed LAZY and is based on the macros lazy:call, lazy:deflazy, and lazy:lazy.
The lazy:call macro is used at calling time (as the name implies). The deflazy macro is used to define functions. The lazy "special operator" returns a functional object that should be called in a lazy way, although the system is set up in such a way to "pass through" constant values (as tested by constantp).
The reference implementation is based on the pre-processing of lambda list arguments by deflazy and def-lazy-function: each argument is substituted by an internal name, which is expected to be bound to a thunk generated by lazy:call as per delay. In the body of a lazy function (or of a lazy lambda) each lambda list argument is actually a symbol-macrolet, which expands in the appropriate force call.
Finally the reference implementation contains a number of
"lazy list" utility functions based on those available in
the Haskell
Data.List module (i.e., take,
drop-while and friends). These functions are collected
in the LAZY-SEQS package.
A complete description of the exported API can be found in the Dictionary section.
The CLAZY library comes with its own test suite. It uses the tester package from Franz Inc.
The usual ones. Plus tons of past discussions on C.L.L. and elsewhere.
[SICP] H. Abelson, J. Sussman, J. Sussman, Structure and Implementation of Computer Programs, Second Edition, MIT Press, 1996.
[O98] C. Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998.
The code associated to these documents is not completely tested and it is bound to contain errors and omissions. This documentation may contain errors and omissions as well.
The file COPYING contains a Berkeley-style license. You are advised to use the code at your own risk. No warranty whatsoever is provided, the author will not be held responsible for any effect generated by your use of the library, and you can put here the scariest extra disclaimer you can think of.