Last clab we demonstrated that something called non-deterministic computing is nice. Today we will look at a copule of more nondeterministic solutions then the insides of our nondeterministic simulator (called ambeval). Finally, we will try prolog. Copy everything from my /home/cfk/pub/cs37/week13/ directory to your week13 directory.

We'll look at a couple of solutions together.

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.

Now open both ambeval.scm and aneval.scm (from week12) in drscheme. We will compare and contrast these evaluators in an attempt to understand ambeval.

In your favorite editor, open the file family-tree.pl. We will start up prolog and look at this together at first. Then you can add details about your family and a couple of new rules.