Delay and Force: Streams Implementing Delay and Force: Expr Expr

Delay and force: streams
Implementing Delay and Force
(delay expr) returns a value that freezes evaluation of expr
We cant implement delay in Scheme as an ordinary function.

(Why not?)
(force expr) thaws expr and memoizes the result

so future thaws just return the thawed value
But we can come close:
Can use these to implement streams and unbounded data

structures:
(define (ints-from n)
(cons n (delay (ints-from (+ n 1)))))
(define nats (ints-from 0))
(define (first-n n strm)
(if (= n 0) nil
(cons (car strm)
(first-n (- n 1)
(force (cdr strm))))))
(define (my-delay fn)

(let ((run-once #f)
(value ()))
(lambda ()
(cond ((eqv? run-once #f)
(set! run-once #t)
(set! value (fn))))
value)))
(define (my-force d)
(d))
Trivial example of use:
(define (map-stream f strm)

(cons (f (car strm))
(delay (map-stream f
(force (cdr strm))))))
(define test(my-delay
(lambda () (horrible 1))))
(my-force test) ; or just (test)
This is handled more cleanly by lazy evaluation in Haskell.

Alan Borning
CSE 505
Alan Borning
Using Lambda to Delay Evaluation
How Other Languages Address this Issue
We can use lambda to delay evaluation in Scheme (although as

with my-delay we have to do something special to cache the
value after it is first computed).
Ada:
CSE 505
two version of and

and
This version evaluates both arguments:
and then
(define (my-and x y
(if x y #f)
Haskell: uses lazy evaluation, so problem doesnt arise

Smalltalk:
(and (= 1 2) (= 1 (/ 2 0))) => error

This version always evauates the first argument, and evaluates
the second argument only if necessary:
two versions of and -- both use call-by-value, but Smalltalk has

a lightweight syntax for creating blocks (lambda expressions)
This version evaluates the argument:
(define (my-and x fn)

(if x (fn) #f)
(1=2) & (2/0=1) => error
(and (= 1 2) (lambda () (= 1 (/ 2 0)))) => #f
[ ] creates a block (lambda):

(1=2) and: [2/0=1] => false
Alan Borning
CSE 505
Alan Borning
CSE 505
Continuations
Continuations continued
We could also do arithmetic this way.
This is a powerful and sometimes confusing construct.
Lets define continuation versions of +, -, *, and expt:
Suppose that we call a function and never return. Then this is

like a goto, but with parameters. (Recall that Scheme
supports tail recursion, so this can be made efficient.)
Continuation-passing version of factorial:
(define (fact n c) ; c is the continuation
(if (zero? n) (c 1)
(fact (- n 1) (lambda (x) (c (* n x))))))
We can get the value out by passing the identity function as the
continuation function:
(define (cplus j k f)
(f (+ j k)))
(define (cminus j k f)
(f (- j k)))
(define (ctimes j k f)
(f (* j k)))
(define (cexpt j k f)
(f (expt j k)))
(fact 3 (lambda (x) x))

=> 6
or by passing write as the continuation:
(fact 3 write)
=> no value (prints 6 as a side effect)
Note that we care about the value of fact only if we care about
the value of its continuation.
Alan Borning
CSE 505
Alan Borning
CSE 505
Continuations (3)
Continuations (4)
Then we can rewrite b2 - 4ac as follows:
This is an obscure way to write an algebraic expression, and we

would be unlikely to write code this way in general.
(Although in the IO language one does just that, albeit with
plenty of syntactic sugar to make it more palatable!)
Standard Scheme version:

(- (expt b 2) (* 4 a c))
However ...
Continuation passing version:
Operations to be performed appear in eactly the order in which

they must be performed. This will make continuations a
useful tool when we come to I/O in Haskell.
(cexpt b 2
(lambda (x) (ctimes 4 a
(lambda (y)(ctimes y c
(lambda (z)(cminus x z
the-continuation)))))))
Continuations are also useful in compiler writing. For example

Steeles Rabbit compiler for Scheme was continuationbased.
The same example, reformatted to emphasize how the Scheme
code could be converted to 3-register instructions (and a
procedure call for exponentiation):
(cexpt b 2 (lambda (x)
(ctimes 4 a (lambda (y)
(ctimes y c (lambda (z)
(cminus x z the-continuation)))))))
Alan Borning
CSE 505
Alan Borning
CSE 505
Continuations in More Standard Use in Scheme

Programs
Can be used to implement a wide variety of control structures.
Most common use is loop exits.
Can also implement catch/throw, coroutines, scheduling,
backtracking, etc.
Continuations are first-class citizens in Scheme.
To use continuations in Scheme:
(call-with-current-continuation proc)
This packages up the current continuation (i.e. the rest of the
computation) and calls proc with the continuation as an
argument.
Sometimes named call/cc (but not in our implementation of
Scheme)
(define (fast-prod lst)
(call/cc (lambda (exit)
(reduce
(lambda (x y)
(if (zero? x) (exit 0) (* x y)))
1 lst))))
Alan Borning
CSE 505

Delay and Force: Streams Implementing Delay and Force: Expr Expr

Uploaded by

Copyright:

Available Formats

Delay and Force: Streams Implementing Delay and Force: Expr Expr

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Delay and Force: Streams Implementing Delay and Force: Expr Expr

Uploaded by

Copyright:

Available Formats

Delay and force: streams

Implementing Delay and Force

(delay expr) returns a value that freezes evaluation of expr

We cant implement delay in Scheme as an ordinary function.

(force expr) thaws expr and memoizes the result

But we can come close:

Can use these to implement streams and unbounded data

(define (my-delay fn)

(define (map-stream f strm)

This is handled more cleanly by lazy evaluation in Haskell.

Using Lambda to Delay Evaluation

How Other Languages Address this Issue

We can use lambda to delay evaluation in Scheme (although as

two version of and

This version evaluates both arguments:

Haskell: uses lazy evaluation, so problem doesnt arise

(and (= 1 2) (= 1 (/ 2 0))) => error

two versions of and -- both use call-by-value, but Smalltalk has

(define (my-and x fn)

(1=2) & (2/0=1) => error

(and (= 1 2) (lambda () (= 1 (/ 2 0)))) => #f

[ ] creates a block (lambda):

This is a powerful and sometimes confusing construct.

Lets define continuation versions of +, -, *, and expt:

Suppose that we call a function and never return. Then this is

(fact 3 (lambda (x) x))

Then we can rewrite b2 - 4ac as follows:

This is an obscure way to write an algebraic expression, and we

Standard Scheme version:

Continuation passing version:

Operations to be performed appear in eactly the order in which

Continuations are also useful in compiler writing. For example

Continuations in More Standard Use in Scheme

You might also like