▼Make your own meta-circular evaluator!
►10 Ambiguousness
On this page:
10.1 Some tests
10.2 Some stuff will have a fail-parameter
10.3 require
10.4 amb
10.5 Btw let’s add a list-function to our primitives
10.6 evaluate*
10.7 Done?
7.2
    ← prev  up  next → 

10 Ambiguousness

If we’ve been through the previous part, we can keep using the same file. Or we can use 6-booleans.rkt as our starting point.

Now that we have continuations, we will add continuations.
We want to add support for the new forms amb and require. An amb with multiple expressions, (amb exps ...) is a form that evaluates to the value of one of its expressions. A require with an expression, (require exp), succeeds if the expression evaluates to true (#t) and fails if it evaluates to false (#f). If a require fails, the evaluator should backtrack to the last amb and try to continue from there with the value of one of the “remaining” expressions of that amb.
For taking care of the backtracky bits, we will use a fail-continuation in addition to the continue-continuation.

10.1 Some tests

You might want to copy them into the test module at the bottom of your Racket file. The tests are going to fail at first. By the end of this chapter they should pass.

(check-equal?
 (eval-require primitives
               (λ (x f) #t)
               (λ () #f)
               '(< 3 6))
 #t)
(check-equal?
 (eval-require primitives
               (λ (x f) #t)
               (λ () #f)
               '(> 3 6))
 #f)

(check-equal?
 (evaluate
  '(begin
     (define a (amb 1 (- 5 3) 6 8))
     (require (> a 5))
     a))
 6)
(check-exn
 exn:fail?
 (λ()
   (evaluate
    '(begin
       (define a (amb 1 2 3))
       (require (> a 5))
       a))))
(check-equal?
 (evaluate
  '(begin
     (define a (amb 1 3 5 7))
     (define b (amb 2 4 3 6))
     (require (= (+ a b) 9))
     (list a b)))
 '(3 6))
(check-equal?
 (evaluate*
  '(begin
     (define a (amb 1 (- 5 3) 6 8))
     (require (> a 5))
     a))
 '(6 8))
(check-equal?
 (evaluate*
  '(begin
     (define a (amb 1 3 5 7))
     (define b (amb 2 4 3 6))
     (require (= (+ a b) 9))
     (list a b)))
 '((3 6) (5 4) (7 2)))

10.2 Some stuff will have a fail-parameter

The functions we use as continue-continuations, as well as all functions that have continue-parameters, should also have fail-parameters. Like, we will change continuation-lambdas like (λ (value) stuff) to ones like (λ (fail value) stuff), and things like (eval-exp env continue exp) to things like (eval-exp env continue fail exp). For now, the different functions will just pass their fails along.

The evaluate-function should work like before. Just, it’s continue-argument should accept a failure-continuation in addition to the result, and it should pass some fail-argument to eval-exp:
(define (evaluate input)
  (eval-exp primitives
            (λ (fail res) res)
            (λ () (error 'ohno))
            input))

10.3 require

In eval-exp we will add a clause:
[(list 'require exp)
 (eval-require env
               continue
               fail
               exp)]
And make the function (eval-require env continue fail exp). In eval-require we will evaluate exp.

The continuation we pass along to eval-exp should carry on with continue if exp evaluated to true, or use fail if it evaluated to false. The fail-continuation should not take any arguments.

The two tests that use eval-require should pass after this.

10.4 amb

To eval-exp we add:

[(list 'amb exps ...)
 (eval-amb env
           continue
           fail
           exps)]

And we make the function (eval-amb env continue fail exps).

In eval-amb we will match the exps-list. If exps is empty, we (fail). If exps has at least one element, we will evaluate that expression with eval-exp:
We can pass our continue-continuation along.
But we need to make a new failure-continuation, (λ () your code here). We will make it so that if anything fails later in the program, we will eval-amb with the remaining elements of the exps-list. (When we run out of elements in exps, we will invoke our “original” fail-continuation, as per our first match-clause.)

10.5 Btw let’s add a list-function to our primitives

Just, it would be nice to return multiple values now, so we will add Racket’s list-function to the primitives list.

10.6 evaluate*

So evaluate should work mostly like before, and it will return the first solution, or throw an error if there aren’t any.

It would be neat to have an evaluation-function that could return a list of solutions instead. So we will make one. In evaluate*, we, uh, “replace failure with a list of successes,” maybe:

(define (evaluate* input)
  (eval-exp primitives
            (λ (fail res) (cons res (fail)))
            (λ () '())
            input))

Now we can, say, make a program for finding numbers that add up to 10:

(define adds-up-to-10
  '(begin
     (define a (amb 1 2 3 4 5 6 7 8 9))
     (define b (amb 1 2 3 4 5 6 7 8 9))
     (require (= (+ a b) 10))
     (list a b)))

And we can get one solution with (evaluate adds-up-to-10), or several solutions with (evaluate* adds-up-to-10).

10.7 Done?

Run and see that all the tests pass.

Next: Maybe It’s puzzle time, or we can go Towards zebras. We should be equipped for either. We can keep using the Racket-file we’re working with, or skip to 7-amb.rkt..

    ← prev  up  next →