TweetFollow Us on Twitter

Lazy Lists
Volume Number:5
Issue Number:10
Column Tag:Lisp Listener

(Mumble Paul(About Lisp))

By Paul Snively, Wheeling, IL

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

It’s been a while since anyone has written anything about any dialect of Lisp or, for that matter, anything that has anything to do with Lisp in MacTutor. This might lead one to the conclusion that nothing of any importance is going on in the Lisp world, or with Lisp as it relates specifically to the Macintosh. This is somewhat saddening, because nothing could be further from the truth.

The most obvious and most visible thing that’s happened in the Lisp world relative to the Macintosh is that Apple Computer, Inc. purchased the assets of Coral Software, Inc. in a move that appears to have surprised several people, myself included. It’s quite rare for Apple to out-and-out buy a third-party software-development house; my interpretation of the acquisition is that it serves to prove Apple’s corporate commitment to many different kinds of artificial intelligence research with respect to future system architectures, and it also serves to prove that Apple uses Allegro CL on the Macintosh a great deal internally (Apple seems to be a stickler for having control of the development systems that they themselves use internally, which is why MPW exists in the first place).

I won’t go into great detail in this space about Allegro CL [for details, see MacTutor, March 1988]. Suffice it to say that the current version, as of this writing, is 1.2.2, and that when it ships through APDA it will include the base language, the Foreign Function Interface that will allow linking MPW C or Pascal code into your Lisp program, and the Standalone-Application Generator that will allow you to turnkey your Lisp program. Also available from APDA for twenty dollars will be the current version of Portable CommonLOOPS, about which I’ll have more to say a bit later.

The other big news in the Common Lisp community on the Macintosh is that ExperTelligence, Inc. has licensed Procyon Common Lisp from Procyon Research, Ltd. in the United Kingdom for distribution in the United States of America. The Procyon implementation has a great deal going for it, not the least of which is an almost religious adherence to the specification of Common Lisp set forth in Steele’s Common LISP: The Language, hereafter called CLtL, which is the canonical description of the language published in 1984. This is a two-edged sword: there is a fair amount of Common Lisp source out there that presumes a somewhat more liberal interpretation of CLtL than the Procyon implementation supports. This is rarely, if ever, damaging (the only example I’ve come across in actual practice is that FIND-SYMBOL wants an honest-to-goodness package object as its optional second parameter, whereas Allegro CL, and apparently most Common Lisp implementations, will allow a package name to be passed).

Another thing that can be considered a plus of the Procyon system is that it seems to know a fair amount about the Macintosh as far as data structures are concerned. For example, Procyon includes a pretty nifty structure editor. A structure editor, as opposed to a text editor, deals with Lisp data structures in the heap, rather than their textual representation in a file. One of the interesting things that it does is to treat bit-vectors, one of Common Lisp’s data types, as bitmaps, providing a fatbits-style editor to modify the contents of the bit-vector. It’s touches like this that make the Procyon system a pleasure to use.

In terms of system performance, Procyon and Allegro subjectively seem very close. Both companies, upon hearing that I intended to write about the two systems, made comments about how performance could be tweaked out of their systems, but I’m going to adopt here the attitude that there are really only two levels of performance for any given system: good enough and not good enough. It’s a subjective measurement anyway; FullWrite Professional’s performance is “good enough” to me, but I know a great many people who do not use it precisely because its performance is “not good enough” to them. To me, both Allegro CL and Procyon Common Lisp perform well enough.

Another thing about Procyon that you may or may not appreciate is the fact that it comes with a two-volume set of documentation, and that Procyon Common Lisp’s DOCUMENTATION function is indexed to the printed documentation (although, happily, lambda lists for functions are still available online). It’s a good thing that Procyon’s documentation is so comprehensive and large; the implementation offers quite a few extensions above and beyond CLtL’s standard definition.

Procyon includes several examples, both of generic Common Lisp programming and of several of the Procyon-specific extensions, such as the so-called “Common Graphics” system that implements Procyon’s interface to the Macintosh Toolbox and OS. Oddly, Procyon, an ostensibly complete Common Lisp implementation, does not ship with CLtL, a must for any Common Lisp programmer, nor does it ship with any of the standard Common Lisp-based texts such as Winston and Horn. It’s my opinion that this somewhat mars the educational value of an otherwise well-documented system.

In the 2.0 release that I received for evaluation, Procyon’s text editor is limited to a maximum of 32K, a limitation that both Procyon and ExperTelligence assure me will be removed, if it hasn’t been already by the time of this writing, or by the time it reaches the shelves. I’m also told that some items, such as a file compiler and an implementation of the forthcoming Common Lisp Object System (CLOS), are under development and will either be integrated into the system or available separately for a modest charge.

Speaking of CLOS, Procyon 2.0 does not ship with any kind of object system, meaning that it can’t easily be extended to support new types of OS and/or Toolbox data structures and functions. In fact, there is a fair amount of documentation given describing how to create custom stream types, since most Common Lisp I/O revolves around streams. Since there is no object system, adding new stream types seems needlessly complex and unwieldy, at least when compared to Allegro CL, which allows you to define subclasses of the basic *STREAM* class and then simply define a few methods to have a new stream type (a good example of this is given in Allegro’s Serial-Streams.Lisp source file, which defines a stream type that allows Allegro CL to do stream-oriented I/O through the serial ports).

Both Allegro CL and Procyon Common Lisp are good, solid, reliable implementations of the Common Lisp standard, a standard which seems to be of increasing importance in the world at large and the Macintosh world in particular. Both will at least consider running on a two-megabyte machine, although realism dictates at least four to get anything accomplished, and, as with all systems, eight is something of a dream. Procyon offers a few more tools, such as the structure editor, and seems somehow “Macier.” Allegro offers an object system, easier Toolbox and OS access, and feels “Lispier.” Allegro CL also now benefits somewhat from being supported by Apple Computer, Inc. Individual preference will be the final arbiter in terms of which system you find yourself using.

[In the late-breaking news department, ExperTelligence will have Procyon Common Lisp 2.1 available by the time you read this. 2.1 will remove the limitations noted above, and as a product line is divided into three different levels, as shown:

Personal Professional Developer

Retail: $620.00 $1250.00 $2000.00

Education: $445.00 $900.00 $1450.00

Includes: Procyon 2.1 Procyon 2.1 Procyon 2.1





CLOS = Common Lisp Object System, FFI = Foreign Function Interface, Runtime = Standalone Application Generator, and ID = Interface Designer.

If the Developer’s version of Procyon sounds intriguing, it should. As you may know, ExperTelligence’s Interface Designer was the precursor to NeXT’s Interface Builder, which is a significant element in why the NeXT computer is so easy to program. CLOS answers my criticisms about Procyon lacking a real object system, and the FFI and Runtime systems are great if you’re doing serious commercial work. ExperTelligence tells me I’ll receive a review copy of the Developer’s system once all components of it have cleared customs as they come from the United Kingdom, and I will report on them once I have them. Procyon 2.0 owners should call ExperTelligence at (805) 967-1797 for upgrade information.]

A little bit earlier I mentioned Portable CommonLOOPS in passing. For some time there has been something of a war waging among a variety of object-oriented programming systems that have been written in Lisp. Lisp Machines, Inc. (now defunct) had Object Lisp, which survives in Allegro CL. Symbolics, Inc. and MIT have Flavors, which is offered by a variety of vendors and is available as an option for Allegro CL. Xerox PARC has Portable CommonLOOPS, the current generation of what started as LOOPS, became CommonLOOPS when Common Lisp was defined, and was then made “portable” in the sense that it has been customized for several of the most popular implementations of Common Lisp, including Allegro CL for the Macintosh.

One reason that I think Portable CommonLOOPS is important is because it’s a very powerful, flexible object-oriented programming environment that runs very well in Allegro CL. The other, and perhaps more important, reason is that an ANSI committee is standardizing the Common Lisp language, and that standard will include the Common Lisp Object System (CLOS), and each version of Portable CommonLOOPS that is released by Xerox PARC is a little bit closer to CLOS, which means that it’s a little bit closer to the future. Also, Portable CommonLOOPS is in the public domain, which means the price is right, and you get source code. If you’re thinking about writing a large object-oriented program in Common Lisp, think strongly about writing it in Portable CommonLOOPS. That way it will stand a much better chance of surviving the inevitable transition to an ANSI-standard Common Lisp implementation. The Portable CommonLOOPS sources are available via anonymous FTP from a number of UNIX sites on the nets, as well as from APDA (my understanding is that they’ll charge $20.00 or so for the distribution).

One problem with Portable CommonLOOPS is that the source code is the only documentation, apart from a handful of release notes that are really only of use if you’re already part of the “intelligentsia” with respect to Portable CommonLOOPS. Luckily, since Portable CommonLOOPS is moving toward being a CLOS implementation, you can largely get away with reading CLOS documentation and applying it to Portable CommonLOOPS (which is the whole point anyway). To that end, I recommend Winston and Horn Third Edition to the person who needs a complete Common Lisp text that devotes some space to CLOS, and Object-Oriented Programming in Common Lisp to the person who already has a working knowledge of Common Lisp but is perhaps a CLOS tyro. This book, by Sonya Keene, takes the reader through most aspects of CLOS from the bare basics to advanced subjects, using examples that actually mean something, such as process locking and implementing I/O streams within CLOS. Keene, an employee of Symbolics, Inc. and a member of the ANSI committee responsible for the CLOS standard and specification, obviously knows her subject well and presents it in a highly coherent manner.

All that has been going on has not necessarily been going on in the Common Lisp world, however. Since I last wrote about Lisp in MacTutor, Semantic Microsystems, developers of MacScheme and MacScheme+Toolsmith, have also been busy. As of this writing, the current version of MacScheme+Toolsmith is 1.51. This version includes support for much of Inside Macintosh Volume V; a few new items in the menus, such as “Load ,” which allows you to load a Scheme file without first opening it and without typing the full pathname in the transcript window; and some new contributed code.

The first contribution is a very nice macro called ExtendSyntax that uses a pattern-matching system to allow the construction of other macros that extend Scheme’s syntax. This utility is described in The Scheme Programming Language by R. Kent Dybvig. It makes writing fairly complex macros much less painful than it normally is in Scheme. As an example, consider the LET special form. As most Scheme programmers realize, what LET does is to encapsulate the body of the LET in a lexical environment, which it then applies to the values assigned to the names. With EXTEND-SYNTAX, you would express this idea like this:

; Here’s how the let macro could have been defined:

(extend-syntax (lett)
               ((lett ((x e) ...) body ...)
                ((lambda (x ...) body ...)
                 e ...)))

In other words, we’re defining a new piece of syntax, LETT, that can accept some list of pairs (that’s what the “(x e) ” means) and some body of expressions (the “body ”) and will expand to “(lambda” followed by the list of the first elements of the pairs (that is, the names), followed by all the expressions of the body, followed by all of the second elements of the pairs (that is, the values). In other words,

(lett ((x 3) (y 4))
 (+ x y))

would expand to:

(lambda (x y)
 (+ x y)
 3 4)

This is just a simple example, but hopefully you can see how expressing macros as syntactical patterns that expand to other syntactical patterns makes macro-writing much easier.

The other major contribution shipped with 1.51 is a MacScheme implementation of Texas Instruments’ SCOOPS system. This is the object-oriented programming system that TI wrote for and ships with their own PC-Scheme system, and Semantic Microsystems’ own John Ulrich did the MacScheme version. If you’ve never tried your hand at object-oriented programming and you own MacScheme+Toolsmith 1.51 or later, take a look at SCOOPS. The MacScheme version leaves some fairly important optimizations out, and unfortunately uses EVAL, which means that standalone applications generated with it will not have any dead code removed, since the routine that finds dead code can’t rip anything out lest it be needed for EVALing at run-time. These shortcomings aside, SCOOPS remains a nice example of how object-oriented programming can be implemented, and seems to be a fairly powerful system.

All of this assumes that you have some Scheme experience. However, it sometimes seems that only people who went to MIT or Indiana University to study computer science have even heard of Scheme. Semantic Microsystems must feel the same way--they recently announced the introduction of Scheme Express, a compact Scheme for those who want to learn the language while investing a minimal amount of money. Priced at $69.95, Scheme Express should fit the bill quite nicely. Apparently Scheme Express is extremely small and extremely slow--it will apparently fit into 512K, and will be quite comfortable even on a Mac Plus. It also claims to run at about 25% of the speed of MacScheme, and that compiled Scheme Express programs will be one quarter of the size of compiled MacScheme programs.

My advice to anyone and everyone who is curious about Lisp at all is this: give Semantic Microsystems a call at (503) 643-4539. Chances are pretty good that you’ll hear the cheerful voice of Kathi Williams at the other end of the line, or perhaps you’ll speak to John Ulrich (if you do, ask him about object-oriented programming using lexical closures as objects. Then sit back and be prepared to learn a lot). And please tell either of them that I sent you. Then ask about Scheme Express. At $69.95, you can’t go too far wrong as far as a learning environment is concerned. If you do get Scheme Express, the next step is to run out and buy a copy of Structure and Interpretation of Computer Programs, by Abelson and Sussman.

Abelson and Sussman is MIT’s introductory computer-science text. Don’t let that scare you off; many students face it every year with no computer programming experience, let alone any Scheme experience. The book is a gem; the principles that it espouses and design theory that it purveys apply regardless of your background or language preferences. The code given happens to be in Scheme, and the exercises are geared toward being implemented in Scheme. So with Scheme Express and this book by your side, you are well-equipped to learn Lisp, and have invested about $100 or so. That’s not unreasonable, even if you’re only mildly curious. There is much for me to learn from Abelson and Sussman; you might discover that there is for you, too.

Abelson and Sussman isn’t your everyday intro text. Things start off easily enough with Chapter 1, Section 1 having you find square roots using Newton’s method.

Section 2 deals extensively with why some algorithms are “better” than others (“better” in most cases meaning significantly faster) and has you write a function that tests for the primality of some number. This section is worth paying a lot of attention to--it thoroughly describes the various “orders” of certain algorithms (O(n2), O(n), O(log n), etc.) and gives you some mental tools with which to reduce the order of your algorithm (that elusive O(log n) algorithm is much faster than that intuitively obvious O(n2) one).

Section 3 introduces the idea that functions are just another kind of data, and in particular that functions can take other functions as parameters, and/or can return functions as their values. This is one of Lisp’s more unique features as a language--there is no enforced distinction between code and data. Functions can be passed as arguments, returned as values, stored in variables, etc. In chapter 1, a good grasp of procedural abstraction is conveyed in only sixty-seven pages.

Chapter 2 is about data abstraction. Section 1 covers how you might implement arithmetic operators for rational numbers, such as 1/3. A later example describes interval arithmetic, such as is used every day by engineers who use electronic components that have tolerance ranges, such as a resistor that is within 5% of having 10 ohms of resistance.

Section 2 provides a lucid discussion of hierarchical data, such as trees, and covers such seemingly divergent examples as symbolic differentiation, representing sets, and Huffman encoding trees.

Section 3 revolves around the notion that the representation of data should be irrelevant to whatever uses the data, assuming that the published interface remains the same. The example of complex numbers is used; complex numbers can be expressed either in rectangular form (real part and imaginary part) or polar form (magnitude and angle). The user of the complex number system should neither know nor care which representation is being used (in fact, both might be used at different times). A complex arithmetic system is implemented to demonstrate this idea, and is then generalized to demonstrate data-directed programming.

Section 4 deals with defining generic operators that can manipulate data of varying types. The exercises in this section integrate the normal arithmetic functions with the rational and complex ones that you wrote in earlier exercises. Problems of data type coercion are dealt with. The example of adding symbolic algebra (adding and multiplying univariate polynomials) is given, demonstrating that by taking advantage of the generic arithmetic operators, the polynomial functions can operate on polynomials with coefficients of any type known by the generic arithmetic functions. If coercion was added according to a prior exercise, then the functions can also handle polynomials with differing types of coefficients. Rational functions (rational numbers whose numerators and denominators are polynomials) are also added to the generic arithmetic system.

Chapter 3 is perhaps the most interesting chapter in the book, in my opinion. It talks about issues of “Modularity, Objects, and State.” Section 1, interestingly, talks about assignment. It may seem rather strange to have a textbook not get around to mentioning assignment until 167 pages have gone by, but the thing that most people don’t seem to understand about Lisp is that it’s not one of the so-called “procedural” languages. It is rather one of the so-called “functional” languages. “Functional” doesn’t mean that the language does things; it means that everything in Lisp is a function that returns some value. There is an entire branch of computer science devoted to the exploration of this approach to programming (for example, there’s an interesting beast called the applicative-order Y-combinator that allows you to write recursive functions without naming them--that is, without using assignment--a task that, on the face of it, seems impossible).

Section 2 explains in depth exactly what “environments” are, and how they influence how expressions are evaluated, and their relationship to variables and internal definitions.

Section 3 details how mutable data can be used to represent data structures such as queues and tables. The examples given here are among the most interesting in the book, in my opinion. The first is a digital circuit simulator that allows you to build circuits out of AND gates, OR gates, and inverters, specifying a signal delay for each component, and applying probes to various wires and then applying signals to various wires. The probes show the signal and the simulation time at which the signal appeared, so that you can determine, for example, the component configuration(s) that will enable a binary adder to work as far as the delays are concerned. The second example is a system supporting the propagation of constraints through a constraint network. One box might constrain one connector to be the multiple of the other two connectors, for example. Another constrains its single connector to have a constant value, and so on. By building networks of these constraints, arithmetic relationships (as opposed to functions, which are one-way) can be supported. For example, the relationship between Celsius and Fahrenheit temperatures is 9C = 5(F-32). Note that this relationship can be solved algebraically for either C in terms of F or F in terms of C, and in most programming languages, that is exactly what you must do: solve for one variable in terms of the other, and express that as a function in the language. With the constraint system, you can make a network out of two multiplication constraints, an additive constraint, and three constant constraints. You can then put a probe on the two connectors, C and F, and set one or the other to a value. The probes in either case will show the values of C and F as the various constraints are activated. The system is bidirectional; it doesn’t matter whether you provide a value for C or F as the probes will provide the correct answer in either case.

Section 4 is where life really gets interesting. The previous three sections have dealt extensively with the concepts underlying assignment and local state, and have employed rather crude, “homebrew” techniques to implement what amounts to object-oriented programming. Section 4 instead takes advantage of the fact that functions are simply another Lisp data type that can be stored in lists or variables for later use to implement a beautifully strange and strangely beautiful data structure called a stream. This is not a “stream” in the Common Lisp sense. Rather, an Abelson and Sussman stream is a collection of data that “feels” very much like a list, but has some special properties. First of all, you must be very careful about using assignment in the presence of streams. That is, a stream is not mutable in the same way that a list is. Secondly, streams can represent some data structures much more efficiently than a list can, in the sense that not all of its elements have been evaluated (I’ll say more about this later). For this same reason, a stream can represent some infinitely-long data structures that cannot be represented as lists at all. A good example of this last ability would be the stream of all prime numbers, which isn’t difficult to generate as a stream, but is quite impossible to generate as a list.

Chapter 4 conveys the importance and power of metalinguistic abstraction. That is, it points out that oftentimes the best approach to using a programming language to solve a problem is to use that language to implement another language in which the problem can be trivially solved. Previous applications of this idea (the language for simulating digital circuits and the language for expressing networks of constraints) are pointed out. In Section 1, Scheme’s own evaluator is rewritten in Scheme.

In Section 2, this new evaluator is modified to examine the effects of using normal-order evaluation as opposed to applicative-order evaluation, as well as to examine the results of using various methods of binding values to variables.

Section 3 discusses packages, which are environments that distinguish among variables having the same name. Their implementation and use to prevent name conflicts in a generic arithmetic system is explained.

Section 4 shows how metalinguistic abstraction can be used to create a programming language that follows an entirely different paradigm than Lisp’s. Logic programming, also known as declarative programming, is discussed. Much attention is paid to the issues surrounding logical expressions such as AND, OR, and NOT (not to be confused with the Lisp primitives of the same names) and their differences from mathematical logic.

Section 5 details the logical query system, and goes into great depth about pattern matching, rules, and unification (a generalization of pattern matching that makes the application of rules possible). Again the emphasis is on the usefulness of being able to implement a new language in Lisp that can then be used to solve the original problem.

Chapter 5, ironically, delves from what might seem the extreme high end of the programming spectrum--using a language to implement another language--to what might seem the low end of that same spectrum, namely creating processes built around the concept of having a certain number of registers, a handful of simple instructions, and a stack. Section 1 covers the simulation of an arbitrary “register machine.”

Section 2 describes the “explicit-control” evaluator. This differs from the evaluator of chapter 4 in that rather than being written metacircularly (that is, rather than being a Scheme evaluator written in Scheme) it is written in the language of the simulated register machine. Issues such as sequence evaluation and tail recursion optimization are covered, as are the handling of special forms, such as conditionals. A sample run of the evaluator is discussed, and then the issue of internal definitions is touched upon.

Section 3 discusses the compilation of Scheme programs for the simulated register machine. Compiling expressions, compiler data structures, code generation, interfacing to the evaluator, and lexical addressing are all presented in some depth.

Finally, Section 4 reveals some of the secrets of Lisp’s dynamic memory management, discussing how memory is allocated and how unused memory is automagically returned to the heap for later reuse.

The scope of Structure and Interpretation of Computer Programs may seem a bit daunting at first, but with a real Scheme such as Scheme Express in front of you, the secrets within this text come tumbling out at a sometimes alarming rate, and there is a great deal of pleasure to be had from mastering some aspect of programming that had eluded you before (at least, that has been my experience).

When talking about chapter 3, I mentioned streams in passing and promised to talk about them in more detail, which I will do, because you can do some pretty interesting things with them. Since I’m going to implement them from top to bottom in Common Lisp, I’d better call them lazy-lists instead of streams, since Common Lisp uses the term “stream” to describe an I/O sink. First of all, an important thing to understand is that lazy-lists are generally used to model some situation where there is a flow of data from point A to point B. As a result, there are a handful of standard operations that you might like to be able to apply to the contents of any given lazy-list. For example, there may be some function that you wish to apply to every element of the lazy-list. Similarly, there may be elements of some lazy-list that you wish to filter out of that lazy-list if they satisfy some predicate. It is also quite common to take the elements of a lazy-list and accumulate them together somehow. Another common function is to append one lazy-list to another.

Let’s define the lazy-list data structure and primitive operations first. Then we can define these higher-order operations on lazy-lists. A lazy-list is nothing more than a list of two elements. The first element is anything; the second element is a function that, when evaluated, returns another lazy-list consisting of the next element in the lazy-list followed by a function that returns the next lazy-list, etc. At any point along this process, the function in question could actually be the-empty-lazy-list, signifying the end of the lazy-list (although, as has been noted, this is not always necessary; some lazy-lists are infinitely long).

Lazy-lists are built using something very much like CONS. In fact, we’ll call the function LAZY-CONS. The different between LAZY-CONS and CONS is that LAZY-CONS doesn’t immediately evaluate its second parameter. Instead it delays it. DELAY is a standard part of Scheme, but it isn’t in most Lisps. In Common Lisp, you would implement DELAY something like this:

(defun memoize (fun)
 (let ((already-evaled nil) (value nil))
 #’(lambda ()
 (if already-evaled
 (setf already-evaled t)
 (setf value (funcall fun)))))))

(defmacro delay (thing)
 ‘(memoize #’(lambda () ,thing)))

This is actually an optimized delay; the MEMOIZE function is a bizarre little thing that takes a function as a parameter and wraps it up in a neat little package that basically determines whether the function has ever been called before. If it hasn’t, it calls it and preserves (and returns) its returned value. If it has, it simply returns the stored value. In other words, any function that we pass to MEMOIZE will only get called once, assuming that what is actually called is the function that MEMOIZE returns.

DELAY, then, is a macro (so it doesn’t evaluate “thing,” which would defeat the whole purpose) that first makes a function that, when called, returns “thing” as its value (by wrapping “thing” in a lambda expression of no arguments), then passes that function to MEMOIZE, so that “thing” only gets evaluated when it absolutely has to, and even then only once.

Building a lazy-list, then, would look something like this:

;;Here is our lazy-list CONStructor:
(defmacro lazy-cons (thing lazy-list)
  ‘(cons ,thing (delay ,lazy-list)))

The flip side of building a lazy-list, of course, is accessing its elements. Since it’s like a list, we’ll write LAZY-CAR and LAZY-CDR to get at its components. LAZY-CAR is very straightforward:

;;Here is LAZY-CAR:
(defun lazy-car (lazy-list)
  (car lazy-list))

LAZY-CDR is only slightly more involved, since the remaining item in the lazy-list data structure has been delayed:

;;Here is LAZY-CDR:
(defun lazy-cdr (lazy-list)
  (force (cdr lazy-list)))

FORCE is used to return the value of the cdr of the lazy-list, and thanks to MEMOIZE, it will do so whether it’s the first time or the umpteenth time without re-evaluating the original object every time. Since the cdr of a lazy-list is a function, FORCE is simply:

(defun force (promise)
 (funcall promise))

With these functions, we have the bare-bones basics of the lazy-list manipulation functions. First let’s define a couple of useful items:

;;Define the empty lazy list:
(defconstant the-empty-lazy-list ‘())

;;How do we know if a lazy-list is empty?
(defun empty-lazy-list-p (lazy-list)
  (eq the-empty-lazy-list lazy-list))

Once we’ve defined these, for the sake of termination testing, formulating the remaining higher-order lazy-list functions isn’t too difficult. For example, appending lazy-list l2 to lazy-list l1 works like this:

;;This is to lazy lists what Common Lisp’s APPEND is to normal lists.
(defun append-lazy-lists (l1 l2)
  (if (empty-lazy-list-p l1)
    (lazy-cons (lazy-car l1)
               (append-lazy-lists (lazy-cdr l1) l2))))

Accumulating the elements of a lazy-list looks like this:

;; This is a nice, generic accumulation function that takes a combiner
;; function (usually #’+ or #’cons or something like that), an initial
;; value (typically 0 or 1 for numeric accumulations or ‘() for lists)
;; and some lazy-list to apply all of this to.
(defun accumulate (combiner initial-value lazy-list)
  (if (empty-lazy-list-p lazy-list)
    (funcall combiner (lazy-car lazy-list)
             (delay (accumulate combiner
                         (lazy-cdr lazy-list))))))

;;This function prevents infinite recursion when accumulating infinite
(defun interleave (l1 l2)
  (if (empty-lazy-list-p l1)
    (force l2)
    (lazy-cons (lazy-car l1)
               (interleave (force l2) (delay (lazy-cdr l1))))))

There are times when what you have is a lazy-list of lazy-lists, and you want to reduce that to a lazy-list of non-lazy-list elements. Using ACCUMULATE and INTERLEAVE, both defined above, it’s easy:

;;This handy thing uses ACCUMULATE to flatten a lazy-list of lazy-lists.
(defun flatten (lazy-list)
  (accumulate #’interleave the-empty-lazy-list lazy-list))

There are many times when you want a lazy-list that has been constructed by applying some function to every element of some other lazy-list. That’s what LAZY-MAP is for:

;;This maps some proc across every element of some lazy-list.
(defun lazy-map (proc lazy-list)
  (if (empty-lazy-list-p lazy-list)
    (lazy-cons (funcall proc (lazy-car lazy-list))
               (lazy-map proc (lazy-cdr lazy-list)))))

It’s also sometimes desirable to remove all elements from a lazy-list that don’t pass some test. FILTER is the function that does that:

;;This returns the lazy-list that contains all items that, when passed 
;;pred, return something non-NIL.
(defun filter (pred lazy-list)
  (cond ((empty-lazy-list-p lazy-list) the-empty-lazy-list)
        ((funcall pred (lazy-car lazy-list))
         (lazy-cons (lazy-car lazy-list)
                    (filter pred (lazy-cdr lazy-list))))
        (t (filter pred (lazy-cdr lazy-list)))))

The next function is useful on those occasions that you need to apply a function to a lazy-list that side-effects the lazy-list, rather than producing a new lazy-list:

;;This is an awful lot like LAZY-MAP, except that it doesn’t accumulate 
;;results, which is a fancy way of saying that you use LAZY-MAP if you 
;;a function result and FOR-EACH if you need side-effects.
(defun for-each (proc lazy-list)
  (if (empty-lazy-list-p lazy-list)
    (progn (funcall proc (lazy-car lazy-list))
           (for-each proc (lazy-cdr lazy-list)))))

Finally, there’s FLATMAP, which is just the combination of FLATTEN and LAZY-MAP. LAZY-MAP often produces a lazy-list of lazy-lists that needs to be flattened, so this is just some syntactic sugar to make that easier:

;;Flattening the result of lazy-mapping is so useful and so common that 

;;there’s a whole separate function for it.
(defun flatmap (f s)
  (flatten (lazy-map f s)))

Once in a great while, it’s nice to convert a regular list to a lazy-list:

;;Sometimes (ok, rarely) it’s nice to convert a list to a lazy-list:
(defun lazy-list (list)
  (if (null list)
    (lazy-cons (car list) (lazy-list (cdr list)))))

Another fairly common operation is nested mapping. That is, several lazy-lists are generated and some function is mapped across them, and the results are accumulated according to some other function. It’s worth defining a fairly complex macro, COLLECT, that will make code that does this easier to read, because the expanded code can be pretty illegible, and contrary to popular belief, good Lisp programmers do care about their code being readable! The goal of the COLLECT macro is to take expressions of the form:

(collect <result>
 ((<v1> <set1>)
  (<vn> <setn>))

and expand them to:

(lazy-map #’(lambda (tuple)
 (let ((<v1> (car tuple))...(<vn> (ca...dr tuple)))
 (filter #’(lambda (tuple)
 (let ((<v1> (car tuple))
       (<vn> (ca...dr tuple)))
 #’(lambda (<v1>)
 #’(lambda (<v2>)
 (lazy-map #’(lambda (<vn>)
 (list <v1>...<vn>))

It’s probably not too hard to see why you’d want a macro like COLLECT to create these kinds of structures. Abelson and Sussman doesn’t list this macro; it’s left as an exercise for the reader. Here’s my Common Lisp solution to that exercise:

;;This is the tricky one.  The COLLECT macro makes nested mappings a 
;;easier than they would be otherwise, but this is the most complex macro
;;I’ve ever had to write.  Here goes nothing:
(defmacro collect (result pairs &optional (restriction t))
  (let ((vars (mapcar #’car pairs))
        (sets (mapcar #’cadr pairs))
        (lets (genlets pairs)))
    ‘(lazy-map #’(lambda (tuple)
                   (let ,lets
               (filter #’(lambda (tuple)
                           (let ,lets
                       ,(genmaps vars sets)))))

;;Given a list of pairs, this creates a let body based on tuple.
(defun genlets (pairs)
  (do ((i (1- (length pairs)) (1- i))
       (result ‘() (cons (cons (car (nth i pairs))
 (list (list ‘nth i ‘tuple))) result)))
      ((< i 0) result)))

;;This beast generates the flatmap/lazy-map sequence for the vars and 
(defun genmaps (vars sets)
  (labels ((genmaps-1 (vars sets depth)
                      (if (null (cdr sets))
                        ‘(lazy-map #’(lambda (,(car (last vars)))
 (list ,@vars))
 ,(car sets))
                        ‘(flatmap #’(lambda (,(nth depth vars))
 ,(genmaps-1 vars (cdr sets) (1+ depth)))
 ,(car sets)))))
    (genmaps-1 vars sets 0)))

Infinitely long lazy-lists can be both interesting and useful:

;;An infinite lazy-list of 1’s:
(defconstant ones (lazy-cons 1 ones))

;;A function to add two lazy-lists together:
(defun add-lazy-lists (l1 l2)
  (cond ((empty-lazy-list-p l1) l2)
        ((empty-lazy-list-p l2) l1)
         (lazy-cons (+ (lazy-car l1) (lazy-car l2))
                    (add-lazy-lists (lazy-cdr l1) (lazy-cdr l2))))))

;;The lazy-list of all integers:
(defconstant integers (lazy-cons 1 (add-lazy-lists ones integers)))

;;A function to scale all elements of a lazy-list by some constant:
(defun scale-lazy-list (c lazy-list)
  (lazy-map #’(lambda (x) (* x c)) lazy-list))

There are many interesting things that can be done with these functions and data structures. It isn’t terribly difficult, for example, to define the lazy-list of all prime numbers:

;;Here’s the sieve of Eratosthenes written using lazy-list functions:
(defun sieve (lazy-list)
 (lazy-car lazy-list)
 (sieve (filter
 #’(lambda (x) (not (divisiblep x (lazy-car lazy-list))))
 (lazy-cdr lazy-list)))))

(defconstant primes (sieve (lazy-cdr integers)))

Theoretically, all prime numbers can be easily gotten from this data structure. In actual practice you’re likely to run out of memory asking for large ones. Speaking of asking for elements of lazy-lists, a LAZY-NTH function would be very helpful:

;;Like NTH for normal lists, except lazy:
(defun lazy-nth (n lazy-list)
 (if (= n 0)
 (lazy-car lazy-list)
 (lazy-nth (1- n) (lazy-cdr lazy-list))))

The hairy COLLECT macro that I wrote is used for nested mappings, as I mentioned above. One simple example is generating the lazy-list of all triples that represent wins on a tic-tac-toe board that’s numbered like this:

This tic-tac-toe board is actually a “magic square”--the numbers in all of the “win” directions add up to fifteen. So what we’re interested in generating is the lazy-list of all distinct positive integers i, j, and k less than or equal to n that sum to s where n is 9 and s is 15. Let’s write triples using collect:

;;Find all triples of i, j, and k <= n that sum to s.
(defun triples (n s)
 (collect (list i j k)
 ((i (enumerate-interval 1 n))
  (j (enumerate-interval 1 (1- i)))
  (k (enumerate-interval 1 (1- j))))
 (= (+ i j k) s)))

ENUMERATE-INTERVAL simply returns the lazy-list of integers from its first parameter to its second parameter, inclusive. It looks like this:

;;Return the lazy-list of integers from low to high:
(defun enumerate-interval (low high)
 (if (> low high)
 (lazy-cons low (enumerate-interval (1+ low) high))))

As you can see, lazy-lists can be a powerful medium for expressing some interesting mathematical and logical ideas. If there is interest, I can explore more uses in future articles. One other example could be a lazy-list-based solution to the classic eight-queens problem. Another, somewhat more practical, idea would be to discuss why lazy-lists are useful in the design and implementation of a forward- and backward-chaining inference engine for deductive information retrieval. As always, I love to hear from you readers what you want to hear, so please feel free to write or call!

That’s all for this time. Enjoy!


Community Search:
MacTech Search:

Software Updates via MacUpdate

GarageSale 7.0.8 - Create outstanding eB...
GarageSale is a slick, full-featured client application for the eBay online auction system. Create and manage your auctions with ease. With GarageSale, you can create, edit, track, and manage... Read more
Backblaze - Online backup serv...
Backblaze is an online backup service designed from the ground-up for the Mac. With unlimited storage available for $5 per month, as well as a free 15-day trial, peace of mind is within reach with... Read more
Parallels Desktop 13.0.0 - Run Windows a...
Parallels allows you to run Windows and Mac applications side by side. Choose your view to make Windows invisible while still using its applications, or keep the familiar Windows background and... Read more
Mellel 4.0.0 - The word processor for sc...
Mellel is the leading word processor for OS X and has been widely considered the industry standard for long form documents since its inception. Mellel focuses on writers and scholars for technical... Read more
Adobe Muse CC 2017 2017.1.0 - Design and...
Muse CC 2017 is available as part of Adobe Creative Cloud for as little as $14.99/month (or $9.99/month if you're a previous Muse customer). Adobe Muse 2017 enables designers to create websites as... Read more
WhatsApp 0.2.5862 - Desktop client for W...
WhatsApp is the desktop client for WhatsApp Messenger, a cross-platform mobile messaging app which allows you to exchange messages without having to pay for SMS. WhatsApp Messenger is available for... Read more
WhatsApp 0.2.5862 - Desktop client for W...
WhatsApp is the desktop client for WhatsApp Messenger, a cross-platform mobile messaging app which allows you to exchange messages without having to pay for SMS. WhatsApp Messenger is available for... Read more
Things 3.1.3 - Elegant personal task man...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
BetterTouchTool 2.292 - Customize Multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Things 3.1.3 - Elegant personal task man...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more

KORG iMono/Poly (Music)
KORG iMono/Poly 1.0.0 Device: iOS Universal Category: Music Price: $19.99, Version: 1.0.0 (iTunes) Description: *** Special Sale for a limited time to celebrate the debut of KORG iMono/Poly (33% OFF) until Sep 30! *** Reviving a... | Read more »
Super Phantom Cat 2 beginner's guid...
Super Phantom Cat 2 presents a whole new world of fun platforming challenges and perplexing puzzles. It's a well-designed platformer with a bright, neon aesthetic that brings the genre up to date. [Read more] | Read more »
Shadow Fight 2 Special Edition (Games)
Shadow Fight 2 Special Edition 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: ** New story chapter! **** No Ads! **** No energy! ** The best fighting series on mobile has returned and... | Read more »
4 RPGs like Final Fantasy XV that deserv...
Square Enix announced another Final Fantasy XV spin-off today - Final Fantasy XV Pocket Edition. This mobile, episodic version of the hit RPG gives the game a chibi-fied makeover. The first episode will be free, followed by 9 more premium episodes... | Read more »
Guild sieges and soul gems in latest upd...
Webzen’s MU Origin hit app stores last year, giving fans of fantasy hack-n-slash MMOs like Diablo a new fix to fixate on. This latest update introduces a competitive guild battle, a fresh dungeon challenge, a mini-game and some elemental gems to... | Read more »
Little Red Lie (Games)
Little Red Lie 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: ARE YOU MORE AFRAID OF POVERTY THAN DEATH? Little Red Lie is a narrative-focused, interactive fiction experience that reduces... | Read more »
You can now apply to be Clash of Clans...
Earlier this month, word got out that the Builder, the trusty handiman who tirelessly built every single building inevery singleClash of Clansbase had called it quits. Sick of seeing his work destroyed endless, the Builder has set out for our world... | Read more »
Meshi Quest beginner's guide - how...
Meshi Quest is Square Enix's newest free-to-play release, and it's a real charmer. You start off as the head of a sushi restaurant, upgrading your food and equipment as you serve visitors heaping helpings of your delicious meals. As you progress,... | Read more »
BUST-A-MOVE JOURNEY 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: BUST-A-MOVE Features:- Shoot bubbles and match 3 or more bubbles of the same color to make them pop!- Complete your... | Read more »
The best card combos in Clash Royale
Clash Royale is all about building a deck of units that synergise well. To help you get off to a flying start, we've put together a list of unit combinations that are incredibly effective. Looking for some choice 2v2 combos? Check out our guide. [... | Read more »

Price Scanner via

Clearance 2016 13-inch MacBook Airs, Apple re...
Apple has Certified Refurbished 2016 13″ MacBook Airs available starting at $809. An Apple one-year warranty is included with each MacBook, and shipping is free: – 13″ 1.6GHz/8GB/128GB MacBook Air: $... Read more
2017 13-inch MacBook Airs on sale for $100 of...
B&H Photo new 2017 13″ MacBook Airs on sale today for $100 off MSRP, starting at $899: – 13″ 1.8GHz/128GB MacBook Air (MQD32LL/A): $899, $100 off MSRP – 13″ 1.8GHz/256GB MacBook Air (MQD42LL/A... Read more
Sale! 13-inch 2.3GHz MacBook Pros for $100 of...
B&H Photo has 13″ 2.3GHz MacBook Pros in stock today and on sale for $100 off MSRP including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Space Gray MacBook Pro (MPXQ2LL... Read more
2016 MacBook Pros, Apple refurbished, availab...
Apple has Certified Refurbished 2016 15″ and 13″ MacBook Pros available starting at $1189. An Apple one-year warranty is included with each model, and shipping is free: – 15″ 2.7GHz Touch Bar Space... Read more
Apple offers Certified Refurbished iPhone 6s...
Apple has Certified Refurbished unlocked iPhone 6s’s and 6s Plus’s available starting at $449. An Apple one-year warranty is included with each phone, and shipping is free: – 16GB iPhone 6s: $449, $... Read more
Apple offers Certified Refurbished Pencils fo...
Apple has Certified Refurbished Apple Pencils available for $85 including free shipping. Their price is $14 off MSRP, and it’s the lowest price available for a Pencil. Read more
2016 15-inch 2.6GHz Touch Bar MacBook Pro ava...
B&H Photo has clearance 2016 15″ 2.6GHz MacBook Pros in stock today and on sale for $500 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: – 15″ 2.6GHz Touch... Read more
21-inch 2.3GHz iMac on sale for $999, save $1...
Amazon has the new 2017 21″ 2.3GHz iMac (MMQA2LL/A) in stock and on sale for $999.99 including free shipping. Their price is $100 off MSRP, and it’s the lowest price available for this model. Read more
Free Instant Translator 2.0 App For iOS Relea...
Mobile application development company, Neoappz has announced the release and immediate availability of Instant Translator 2.0 for iOS devices. Instant Translator is a user-friendly application which... Read more
2017 15-inch MacBook Pros on sale for $200 of...
Amazon has 2017 15″ MacBook Pros on sale for $200 off MSRP. Shipping is free: – 15″ 2.8GHz MacBook Pro Space Gray: $2199.99, $200 off MSRP – 15″ 2.8GHz MacBook Pro Silver: $2296, $103 off MSRP – 15″... Read more

Jobs Board

Development Operations and Site Reliability E...
Development Operations and Site Reliability Engineer, Apple Payment Gateway Job Number: 57572631 Santa Clara Valley, California, United States Posted: Jul. 27, 2017 Read more
Frameworks Engineering Manager, *Apple* Wat...
Frameworks Engineering Manager, Apple Watch Job Number: 41632321 Santa Clara Valley, California, United States Posted: Jun. 15, 2017 Weekly Hours: 40.00 Job Summary Read more
Development Operations and Site Reliability E...
Development Operations and Site Reliability Engineer, Apple Payment Gateway Job Number: 57572631 Santa Clara Valley, California, United States Posted: Jul. 27, 2017 Read more
Frameworks Engineering Manager, *Apple* Wat...
Frameworks Engineering Manager, Apple Watch Job Number: 41632321 Santa Clara Valley, California, United States Posted: Jun. 15, 2017 Weekly Hours: 40.00 Job Summary Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.