CS 22
Clab 41: Continuations and the Amb Evaluator
Last clab we demonstrated that something called non-deterministic
computing is nice. Today we will look at the insides of our
nondeterministic simulator (called ambeval).
ambeval is based on the special form amb. The expression (amb e1 e2
e3 ... en) 'nondeterministically' evaluates and returns the value of
one of the expressions e1, e2, e3, ..., en. However, it provides the
capability to get another value if further execution with the first
value 'fails'. This is not exactly the idea but close: In order to
achieve this, code generated for part of an expression, EXP, must
carry two kinds of additional code along: a) code to continue the
evaluation of EXP if evaluation of the part is successful, and b) if
evlauation of the part 'fails', code to return to the choice point,
get another value (if any left), and then continue the computation of
EXP from the choice point with the new value. The first kind of
carry-along code will be called a success continuation; the second
kind will be called a failure continuation.
Let's look at a simplified example:
<![CDATA[
(define sqr
(lambda (x) (* x x)))
(define addy
(lambda (x) (+ x y)))
(define f
(lambda (x) (+ x 1)))
(define e1
(lambda (x)
(sqr (addy (f x)))))
(define succ
(lambda (val)
(sqr (addy val))))
]]>
Now open both ambeval.scm and aneval.scm in drscheme. We will
compare and contrast these evaluators in an attempt to understand
ambeval.
Let's try the following in the interaction window of the session with
ambeval.
<![CDATA[
AMB-EVALUATOR-LOADED
> the-global-environment
> (define xvalproc (analyze 'x))
> xvalproc
#<procedure>
> (define succ1
(lambda (val fail)
(newline)
(display "this is succ1 value: ")
(display val)))
> (define fail1
(lambda ()
(newline)
(display "fail1 was called")))
> (fail1)
fail1 was called
> (succ1 3 fail1)
this is succ1 value: 3
> (xvalproc the-global-environment succ1 fail1)
. . Macintosh HD:Users:cfk:fromsun:cs22:bef01:week13:mceval.scm:
257.9-257.39: Unbound variable x
> (driver-loop)
;;; Amb-Eval input:
(define x 25)
;;; Starting a new problem
;;; Amb-Eval value:
ok
;;; Amb-Eval input:
q
;;; Starting a new problem
. . Macintosh HD:Users:cfk:fromsun:cs22:bef01:week13:mceval.scm:
257.9-257.39: Unbound variable q
> (xvalproc the-global-environment succ1 fail1)
this is succ1 value: 25
]]>
We will continue to look at and discuss the code for ambeval.