Subject: Re: Lazy Evaluation From: Joe English <jenglish@xxxxxxx> Date: Wed, 11 Jun 1997 12:41:48 -0700 |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: Lazy Evaluation, Paul Prescod | Thread | jadetex and line-field FO, Taranov Alexander |
Re: DSSSL Documentation Project?, Tony Graham | Date | Re: DSSSL Documentation Project?, Axel Ramge |
Month |