Re: Lazy Evaluation

[Joe English <jenglish@xxxxxxx>]

Paul Prescod <papresco@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
>
> I meant: "In DSSSL, basically only nodelists (and sosofos?) are defined
> such that their implementations can be lazy" but I got lazy. For
> instance I would be surprised if an implementation of node-list->list
> resulted in a lazily-created Scheme list. Am I being overly pessimistic?
> Would the original DSSSL (before we may or may not add side effects)
> permit lazy creation of Scheme lists?


Yes: in the absense of side effects, lazy evaluation yields
the same results as strict evaluation, modulo non-termination.
(More precisely: two different reduction orders will never reduce an
expression to two different normal forms, as a consequence
of the first Church-Rosser Theorem [1].)  So in theory,
*all* of DSSSL could be implemented lazily.

Of course if you allow side effects this is not the case.
In fact, even Scheme leaves some things explicitly undefined
(or rather, unpredictable) when side effects are involved,
for example

  (let* ((x 0)
         (y 1)
         (f1 (lambda () (begin (set! x (+ 1 x)) (* x y))))
         (f2 (lambda () (begin (set! y (+ 1 y)) (* x y)))) )
        (+ (f1) (f2)))

can yield either 2 or 3 { (+ (* 1 2) (* 0 2)) or (+ (* 1 1) (* 1 2)) }.
SML avoids this ambiguity by mandating left-to-right evaluation
order; Scheme allows arguments to be evaluated in any order to
enhance optimizability and freedom of implementation technique.

In the absense of side effects however, the only observable differences
between normal-order reduction ("lazy" evaluation) and applicative
order reduction ("eager" or "strict" evaluation) are: (1) some
expressions that terminate when evaluated lazily may fail to do so
when evaluated strictly, and (2) they may not perform the same number
of reductions so one may be more efficient than the other.

For (1), compare:

	let f x = x:(f (x+1)) in head (f 1)

in Haskell with

	let fun f x = x::(f (x+1)) in hd (f 1) end;

in ML or

	(letrec ((f (lambda (x)
		     (cons x (f (+ 1 x))))))
		(car (f 1)))

in Scheme.  The Haskell version (which uses lazy evaluation)
returns '1', the Scheme and ML versions loop infinitely.

For (2), lazy evaluation will generally perform fewer reductions
than strict evaluation (as long as the implementation uses
graph reduction and not tree reduction!), but is more expensive
to implement overall.


[1] Source: Peyton Jones, Simon L., The Implementation of
Functional Programming Languages, section 2.3.1 p. 24.


--Joe English

  jenglish@xxxxxxx

 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist