20090219

Feeling lazy....

In my bouts of "other higher programming language envy" (no SLDJs), I wandered the realm of lazy evaluation. The results are being slowly collected in the CLAZY library. In principle it is not difficult to write up a lazy library in Common Lisp. What is difficult is the balancing act you want to achieve in making your library work nicely with and within the language. My choice has been to concentrate on the function call point by providing an explicit extra call operator patterned after funcall. The result is lazy:call.

This has a number of nice consequences w.r.t. re-defining each of your lazy functions as macros (which is another implementation strategy). The foremost is that lazy calls (which, let's remember, are the exception and not the rule in a strict language like Common Lisp) are clearly marked. Let's see a simple example. A function which chooses the first of its non-null 4 arguments and returns 0, 1, 2, or 3. A call in strict Common Lisp could be:

cl-prompt> (choose4 nil nil t t)
2

Using CLAZY, the same function called lazily would appear in expressions like the following ones.

cl-prompt> (lazy:call #'choose4 nil t nil t)
1

cl-prompt> (lazy:call #'choose4 nil nil t (loop (print 42)))
2

The lazy call is clearly marked. An alternative would be to define special syntax to mark lazy calls. Something like:

cl-prompt> {choose4 nil nil t (loop (print 42))}
2

But I don't like to highjack parenthesis syntax (more on this subject later; note that there are no reader macros defined in CLAZY). If I need to improve my self-esteem I can always start progamming in Perl. Besides, given the CLAZY implementation, it is easy to do something like the following.

cl-prompt> (lazy:slacking
              (choose4 nil nil t (loop (print 42))))
2

cl-prompt> (lazy:lazily
              (choose4 nil t (loop (print 42)) t))
1

slacking and lazily are block-like macros (they do expand into a block) and do exactly the same thing: all lazy functions are lazy:called within the scope.

How is the choose4 function written? Like this:

(deflazy choose4 (e0 e1 e2 e3)
   (or e0 e1 e2 e3))

The deflazy macro defines both strict and lazy versions of a function. The def-lazy-function macro defines only the lazy version, which allows you to write

(def-lazy-function cons (car cdr) ...) ; You don't want to know... yet.

So, where does this lead us? To a nice Haskellesque library, where you can say (assume you are using the right packages).

cl-prompt> (take 4 (distinct (repeatedly 'random 64)))
(3 45 92 12)

How does this work? First of all, this last bit came out of a huge thread on C.L.L.... Second, I am too lazy now to tell you. Just hang around and wait.

(cheers)

2 comments:

  1. Is the cvs tree on common-lisp.net up to date? The tree is 8 months old, and the .asd is malformed.

    ReplyDelete
  2. Yep. I fixed these problems. There is still an annoying package locking problem on some implementations, but usually you can just "continue it" away.

    ReplyDelete