Common Lisp the Language, 2nd Edition


next up previous contents index
Next: Series Functions Up: Series Previous: Series

A.1. Introduction

change_begin
Series combine aspects of sequences, streams, and loops. Like sequences, series represent totally ordered multi-sets. In addition, the series functions have the same flavor as the sequence functions-namely, they operate on whole series, rather than extracting elements to be processed by other functions. For instance, the series expression below computes the sum of the positive elements in a list.

(collect-sum (choose-if #'plusp (scan '(1 -2 3 -4)))) => 4

Like streams, series can represent unbounded sets of elements and are supported by lazy evaluation: each element of a series is not computed until it is needed. For instance, the series expression below returns a list of the first five even natural numbers and their sum. The call on scan-range returns a series of all the even natural numbers. However, since no elements beyond the first five are ever used, no elements beyond the first five are ever computed.

(let ((x (subseries (scan-range :from 0 :by 2) 0 5))) 
  (values (collect x) (collect-sum x))) 
  => (0 2 4 6 8) and 20

Like sequences and unlike streams, a series is not altered when its elements are accessed. For instance, both users of x above receive the same elements.

A totally ordered multi-set of elements can be represented in a loop by the successive values of a variable. This is extremely efficient, because it avoids the need to store the elements as a group in any kind of data structure. In most situations, series expressions achieve this same high level of efficiency, because they are automatically transformed into loops before being evaluated or compiled. For instance, the first expression above is transformed into a loop like the following.

(let ((sum 0)) 
  (dolist (i '(1 -2  3 -4) sum) 
    (when (plusp i) (setq sum (+ sum i))))) => 4

A wide variety of algorithms can be expressed clearly and succinctly with series expressions. In particular, at least 90 percent of the loops programmers typically write can be replaced by series expressions that are much easier to understand and modify, and just as efficient. From this perspective, the key feature of series is that they are supported by a rich set of functions. These functions more or less correspond to the union of the operations provided by the sequence functions, the loop clauses, and the vector operations of APL.

Some series expressions cannot be transformed into loops. This is unfortunate, because while transformable series expressions are much more efficient than equivalent expressions involving sequences or streams, non-transformable series expressions are much less efficient. Whenever a problem comes up that blocks the transformation of a series expression, a warning message is issued. On the basis of information in the message, it is usually easy to provide an efficient fix for the problem (see section A.3).

Fortunately, most series expressions can be transformed into loops. In particular, pure expressions (ones that do not store series in variables) can always be transformed. As a result, the best approach for programmers to take is simply to write series expressions without worrying about transformability. When problems come up, they can be ignored (since they cannot lead to the computation of incorrect results) or dealt with on an individual basis.


Implementation note: The series functions and the theory underlying them are described in greater detail in [52,53]. These reports also discuss the algorithms required to transform series expressions into loops and explain how to obtain a portable implementation.

change_end



next up previous contents index
Next: Series Functions Up: Series Previous: Series


AI.Repository@cs.cmu.edu