 | Level: Advanced Jonathan Bartlett (johnnyb@eskimo.com), Director of Technology, New Medio
18 Dec 2006 Lazy programming is a general concept of delaying the processing of a
function or request until the results are needed. This concept has numerous
applications, from the obvious to the obscure. Thinking in terms of lazy programming
can help you rid your code of unneeded computation and restructure programs to be
more problem-oriented.
Simple lazy programming
in Scheme
Lazy programming is a technique that lets you delay the evaluation of code until
you need the resulting value. In Scheme, for example, lazy programming is
explicitly supported through two special constructs. Scheme's delay special
form takes a block of code and, rather than executing it, stores the code and its
parameters as a promise. If you force the promise to produce a
value, it will then run the code. The promise then saves the result, so that
future requests for the value will be returned instantly without having to execute
the code again.
Here is a simple example of how delay and
force work together:
Listing 1. Example usage of delay and force
;;The multiplication is saved but not executed
(define my-promise (delay (* 5 6 7 8 9)))
;;Again, saved but not executed
(define another-promise (delay (sqrt 9)))
;;Forces the multiplication to execute. Saves and returns the value
(display (force my-promise))
(newline)
;;This time, the multiplication doesn't have to execute. It just returns
;;the value that was previously saved.
(display (force my-promise))
(newline)
;;This produces an error, because the promise must be forced to be used
(display (+ my-promise (force another-promise)))
|
These constructs are fairly simple to use, but what are they used for?
Generally, lazy programming is used when a function generates a value that may not
be used by the calling program. For example, let's say you had a function that
computed the mean, variance, and standard deviation of a list of numbers. Here's
one way of doing it:
Listing 2. Simple statistical calculations
(define (square x) (* x x))
(define (calculate-statistics the-series)
(let* (
(size (length the-series))
(sum (apply + the-series))
(mean (/ sum size))
;variance is the sum of (x[i] - mean)^2 for all list values
(variance
(let* (
(variance-list (map (lambda (x) (square (- x mean))) the-series)))
(/ (apply + variance-list) size)))
(standard-deviation (sqrt variance)))
(vector mean variance standard-deviation)))
;Run the program
(display (calculate-statistics '(2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)))
(newline)
|
Now, let's say that you want the standard deviation only under certain
conditions, but this function has already spent a lot of computational power
computing it. There are several ways you could solve this. You could have separate
functions for calculating the mean, variance, and standard deviation. In that
case, however, each function would have to re-do the work of calculating the mean.
If you needed all three, you would wind up calculating the mean three times, the
variance twice, and the standard deviation once. That's a lot of extra, useless,
work. Now, you could also require that the mean be passed to the standard
deviation function and force the user to call the mean-calculating function for
you. Although possible, it makes a really horrendous API, with the interface
reflecting all sorts of implementation-specific pieces.
A better way might be to use lazy evaluation to delay computation:
Listing 3. Statistical calculations with lazy evaluation
(define (square x) (* x x))
(define (calculate-statistics the-series)
(let* (
(size (delay (length the-series)))
(mean (delay (/ (apply + the-series) (force size))))
;variance is the sum of (x[i] - mean)^2
(variance
(delay
(let* (
(variance-list (map (lambda (x) (square (- x (force mean))))
the-series)))
(/ (apply + variance-list) (force size)))))
(standard-deviation (delay (sqrt (force variance)))))
(vector mean variance standard-deviation)))
;Run the program
(define stats (calculate-statistics '(2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)))
(define mean (force (vector-ref stats 0)))
(define variance (force (vector-ref stats 1)))
(define stddev (force (vector-ref stats 2)))
(display (list mean variance stddev))
(newline)
|
In this version of calculate-statistics, nothing
happens until a value is needed and, just as importantly, nothing is
calculated more than once. If you request the variance first, it will run
and save the mean first, then it will run and save the variance. If you
next ask for the mean, it has already been calculated, so it simply returns the
value. If you next ask for the standard deviation, it uses the saved value for the
variance, and calculates it from that. Now there is no unnecessary computation
performed, and the function interface is essentially retained.
This type of laziness can be done fairly simply in an object-oriented language
as well. Anywhere you need a group of related calculations, you can create a class
to hold intermediate values. The constructor takes the initial values used, and
all of the computed values would be set to null. Instead of using force, you would
have a getter for each value that would check to see if the value is null and, if
not, run the calculation. Here is the skeleton of such a class in the
Java™ language:
Listing 4. Reformulating lazy evaluation in the Java language
public class StatisticsCalculator {
private List the_series;
private Double mean;
private Integer size;
private Double variance;
private Double standard_deviation;
public StatisticsCalculator(List l)
{
the_series = l;
}
public int getSize()
{
if(size == null)
{
size = the_series.size();
}
return size;
}
public double getStandardDeviation()
{
if(stddev == null)
{
stddev = Math.sqrt(getVariance());
}
return stddev;
}
...
...
}
|
The class itself acts as a multivalued promise, and the instance variables hold
the results of the calculations. Each function checks whether or not the code has
been executed by checking to see if the variables are null. If a variable does not
have a value when it is needed, the code is executed and the value is saved. Note
that if null was in the valid range for the value, you
would need an auxiliary flag to use for whether or not the code had been executed,
rather than just checking to see if the value is null.
As you can see, lazy programming techniques can be used to help make a sensible
and efficient API for functions that return interdependent values. In addition,
lazy techniques can be implemented through classes in languages that do not have
direct support for lazy programming.
Indeterminate lists
Let's say you have a list of all the numbers that are a multiple of five. Then,
you want to square all those numbers. Finally, you want to iterate through the
result and display all of those whose results are less than 500. What? You can't
operate on infinite lists? Why not?
Indeed, while it may be counter-intuitive, infinite lists can take less room to
store than many finite ones, provided the infinite list is based on a
generative rule. In the above example, the original list is based on the
rule X[i] = (i + 1) * 5, where
X[i] is the value at list index
i. X[i] can also be
expressed in terms of its predecessor:
X[i] = X[i-1] + 5; X[0] = 5. Using Scheme's
force and delay, we can
construct a stream of values based on this rule:
Listing 5. Example of a stream
;This is the generative rule for the list. It returns a pair
;with the car being the next value, and the cdr being a promise
;for the next pair
(define (my-generative-rule last-val)
(let (
;generative formula based on previous value
(next-val (+ last-val 5)))
;put the next value together with a promise for another one
(cons next-val (delay (my-generative-rule next-val)))))
;Since the cdr is a promise of a pair, rather than a pair itself,
;we have our own functions for getting the car and cdr.
(define (mystream-car the-stream) (car the-stream))
(define (mystream-cdr the-stream) (force (cdr the-stream)))
;Create our list
(define multiples-of-five (cons 5 (delay (my-generative-rule 5))))
;Display the fourth element of the list
(display (mystream-car (mystream-cdr (mystream-cdr (mystream-cdr multiples-of-five)))))
(newline)
|
Now, remember that you wanted to square all the numbers. To do this, you need a
function that can create a new stream from existing streams and generative rules
-- kind of like map, but for streams. Here's the
function:
Listing 6. A specialized map for streams
(define (mystream-map function the-stream)
(cons
;;The first value will be the function applied to the car
(function (car the-stream))
;;The remaining values will be stored in a promise
(delay (mystream-map function (mystream-cdr the-stream)))))
(define squared-stream (mystream-map (lambda (x) (* x x)) multiples-of-five))
;Display the fourth element of this new list
(display (mystream-car (mystream-cdr (mystream-cdr (mystream-cdr squared-stream)))))
(newline)
|
Now, all that's left to do is to iterate through the stream and print out the
values less than 500:
Listing 7. Iterating through a stream
(let loop (
(remaining-stream squared-stream))
(if (>= (mystream-car remaining-stream) 500)
#f
(begin
(display (mystream-car remaining-stream))
(newline)
(loop (mystream-cdr remaining-stream)))))
|
Obviously, for such a trivial program there are ways of approaching the subject
more directly. However, even in this example, streams helped us view the problem
from less of an implementation point of view and more as an abstract idea. Streams
let you focus on the problem rather than the implementation. Streams
ease both the conceptualization and the implementation of algorithms involving
generative elements.
The streams I have discussed so far are useful for learning the concepts behind
streams. However, the implementation suffers from numerous pitfalls. First of all,
there are many occasions where streams may need a terminator. This implementation
doesn't provide that facility. Also, the style of streams shown here is known as
odd streams, and the odd style is easy to implement.
But such streams can lead to more evaluation than
is intended, since the car of the list is always evaluated. Standard streams, as
defined in SRFI-40, take care of these and other issues (see Resources for more details).
Skipping transitional
variables
So far, all of our examples of lazy evaluation have caused the intermediate
values to be fully realized before continuing. Part of this stems from the
requirements of the problems we were solving, and part comes from the operation of
delay and force themselves.
For example, consider the following code:
(define val1 20)
(define val2 30)
(define val3 40)
(define val4 0)
(define val5 (delay (* val1 val2)))
(define val6 (delay (* val4 val3)))
(define val7 (* (force val5) (force val6)))
In this case, we know that the answer will be zero, simply because we know that
anything times zero is zero. So, while this would seem to be a case where lazy
evaluation might be appropriate (as we are trying to prevent unnecessary
computations), in fact using delay and
force doesn't help us out.
In cases like this, we need specialized lazy algorithms to delay processing in
order to not process intermediate results. Instead, we would need to
implement code that would queue up requests. Then, when the final answer was
requested, it could search the queue for values that can help it optimize the
process, and then use those values to skip processing of other values. In the case
of multiplication, the presence of a zero could cause it to skip all processing.
Here is a specialized
delay/force pair,
specialized for multiplication:
Listing 8. Simple specialized delay/force pair
;This will simply use a list to keep track of the values to be multiplied
(define (multiply-delay x y)
(let (
;convert to lists if they aren't already
(x-list (if (list? x) x (list x)))
(y-list (if (list? y) y (list y))))
;append them together
(append x-list y-list)))
(define (multiply-force mul-list)
(let (
(has-zero? #f))
(for-each
(lambda (x)
(if (eqv? 0 x)
(set! has-zero? #f)
#f))
mul-list)
(if has-zero?
0
(apply * mul-list))))
(define a (multiply-delay 23 54))
(define b (multiply-delay 0 5))
(define c (multiply-delay a b))
(define d (multiply-delay c 55)
(display (multiply-force d))
(newline)
|
However, this implementation has problems of its own. The individual pieces are
no longer lazy, and no longer save their values. We have lost all of the benefits
of the original delay and
force in order to achieve a single optimization.
Therefore, rather than keeping one long list of all the parameters, we need to
keep them compartmentalized in individual promises so that we can still have the
previous benefits. What we need is a tag that tells whether or not the value has
been computed. If it has been, there is only one element there that does not need
computation. Otherwise, both the multiplier and the multiplicand will be present.
Here is the new code:
Listing 9. Another specialized lazy construct
;Unevaluated promises will have the structure ('delayed val1 val2)
;Evaluated promises will have the structure ('forced result)
;Create an unevaluated promise
(define (multiply-delay x y)
(list 'delayed x y))
;Checks promises (and values) to see if they contain any zeros
(define (has-zero promise)
(if (pair? promise)
(if (eq? (car promise) 'forced)
;check forced value
(if (eqv? (cdr promise) 0)
#t
#f)
;check unforced value
(if (or (has-zero (cadr promise)) (has-zero (caddr promise)))
#t
#f))
;Check scalar value
(if (eqv? promise 0)
#t
#f)))
;Attempts zero optimization, then defaults to regular delay/force behavior
(define (multiply-force promise)
(if (eq? (car promise) 'forced)
;if we've already been forced, return the value
(cdr promise)
;otherwise, search for a zero
(if (has-zero promise)
(begin
(set-car! promise 'forced)
(set-cdr! promise 0)
0)
(multiply-force-nonzero promise))))
;This is for promises which are known to be free of zeros
(define (multiply-force-nozero promise)
(if (pair? promise)
(if (eq? (car promise) 'forced)
;if the promise has been forced, just return the value
(cdr promise)
;otherwise, compute the value, and convert this into a "forced" promise
(begin
(set-car! promise 'forced)
(set-cdr! promise
(*
(multiply-force-nonzero (cadr promise))
(multiply-force-nonzero (caddr promise))))
;return the forced value
(cdr promise)))
;This is just a number, so return it
promise))
|
This has all of the beneficial behaviors of regular
delay/force. Now, because
multiplication is a fairly fast operation anyway, this whole operation is probably
a waste of time, but it makes for a good example. This can save a whole lot of
time for more expensive operations, especially those that may require context
switches or heavy processor usage.
One popular use of this technique is in doing string appends. Rather than having
to allocate new space every time an append is done, you can simply maintain a list
of strings that need to be concatenated. Then, when the final version of the
string is needed, you only have to allocate space for the new string once. This
saves several malloc calls, as well as time copying
each string.
Lazy evaluators
So far I have focused on lazy constructs within an otherwise non-lazy language.
However, some languages, such as Haskell, have laziness as part of the normal
evaluation process. This is termed lazy evaluation. No parameter in lazy
evaluation is evaluated until it is needed. The programs essentially start from
the end and work backwards. It figures out what it needs to return, and continues
backwards to determine what values are required to do that. Basically, every
function is called with promises to each of the parameters. When the computation
needs a value, it then executes the promise. Since code is executed only when the
value is needed, this is called call-by-need. In traditional programming
languages, values are passed instead of promises, which is called
call-by-value.
Call-by-need programming has several advantages. Streams are implemented
automatically. Unneeded values are never computed. However, the behavior of lazy
programs is often hard to predict. In call-by-value programs, the evaluation order
is very predictable, so any time- or sequence-based computations are relatively
easy to implement. This is much more difficult in lazy languages, where special
constructs such as monads are needed to describe explicitly-sequenced
events. All of this also makes interfacing with other languages more difficult.
There are several languages that do lazy programming by default, including
Haskell and Clean. There are lazy versions of a number of other languages as well,
including Scheme, ML, and others.
Conclusion
Sometimes by delaying an evaluation until just before the value is needed, you
can either optimize the speed of a program or restructure a program into a more
intelligible form. Though valuable, lazy programming techniques are not widely
implemented or even known about. Consider adding them to your repertoire of
techniques.
Resources Learn
Get products and technologies
-
Order the SEK for Linux, a two-DVD set containing the latest IBM trial
software for Linux from DB2®, Lotus®, Rational®, Tivoli®,
and WebSphere®.
- With IBM trial software, available for download directly from developerWorks,
build your next development project on Linux.
Discuss
About the author | | | Jonathan Bartlett is the author of the book Programming from the Ground Up, an introduction to programming using Linux assembly language. He is the lead developer at New Medio, developing Web, video, kiosk, and desktop applications for clients. |
Rate this page
| |
