Amb, the time travelling operator

Posted on November 8, 2015

I was talking to a friend recently, and wanted to explain how Racket can be used for solving logic puzzles. This was a bit unwieldy to explain in chat, so I've written it up here.

The operator I want to explore today is call called amb (short for ambiguous), and unfortunately is not part of Racket's standard library. Fortunately for us, there is a package in Racket's community package repository, so I'll use that one for now¹.

Here's how you would import the library:

#lang racket
;; The external lib that defines amb:
(require (planet murphy/amb:1:1/amb))

I've going to be running somewhat imperative looking Racket code, here are a few things to look out for:

define can have multiple expressions one after another: scheme (define (foo) (a) (b) (c)) It runs them from top to bottom, and then returns the value of (c), throwing out the return values of (a) and (b).
Because of this, there are a few new conditional statements I will be using: when and unless. These are just like if or cond, but are meant to be called from statments like (b) in the example above, where their return value will be discarded, so they don't need to have an else branch.

(when condition statement) is the same as (if condition statement (void)), and (unless condition statement) is the same as (if condition (void) statement).

The general way in which you interact with amb is by writing some expression such as (amb x y z), where you pass it any number of arguments. In general (amb x y z) looks like it just returns x, but amb hates getting called with zero arguments, and will even go back in time to previous calls to amb and remove the x and re-evaluate it as (amb y z), so it will return y instead.

The way this library works, we have to enclose all our examples with a call to amb-find to get back the first successful answer². This also isolates the examples from each other, as amb can't jump outside of a call to amb-find. Each amb-find expression is completely independent.

(define (example-zero)
    (amb-find (amb 1))
    ; => 1
    (amb-find (amb 1 2))
    ; => 1
    (amb-find (amb))
    ; Oh no, there's nothing to backtrack to. We have to give up.
    ; (We can't jump back to (amb 1 2) since it's in a different
    ; `amb-find` expression.)
    ; => Error:
    ;  amb-find: out of alternatives
    )

We'll define a more informative name for calling (amb), since it causes us to roll back to the previous call to amb, cross out the argument we tried, and try the next one in the list.

(define (fail) (amb))

And here's a small example.

(define (example-one)
    (define apple (amb 'red-delicious 'russet))
    ; `when` is just like an `if` statement, but it lacks an `else`
    ; clause.  We run it only for its side effects.
    (when (eq? apple 'red-delicious)
        (fail))  ; The worst kind of apple. Try again.
    apple)

;; Lets step through this example:
(amb-find (example-one))
;; First, we assign
;;     apple = 'red-delicious
;; Then, we run the `when` statement:
;;     (when (eq? apple 'red-delicious)
;;          (fail))
;;
;; Which happens to reduce to:
;;     (when #t (fail))
;;
;; So we call (fail) and start over from the last call to `amb`,
;; but knowing that we should not use 'red-delicious leaves us with:
;;     apple = 'russet
;;
;; We check the when clause again:
;;     (when (eq? apple 'red-delicious)
;;          (fail))
;;
;; This reduces to:
;;     (when #f (fail))
;;
;; So we don't call (fail) and continue on to return `apple`,
;; finally evaluating to 'russet.

Lets say we want to solve a simple riddle (stolen from here), such as:

Suppose we have two groups of people that look alike, the Liars and the Truthtellers. The Liars are compelled to always lie, and cannot tell the truth. The Truthtellers are compelled to always tell the truth, and cannot lie.

One day, you meet two people, Alice and Bob. You are unsure if Alice and Bob are both Truthtellers or Liars, or if one is a Truthteller and the other a Liar. Alice helps you by saying:

"We are both Liars"

What should you conclude?

Now, I will admit that you might not need to write a program to solve this, when a 2x2 truth-table will do, but it makes for a good example.

The way we will solve this in Racket using amb is

;; This just restarts the computation when a liar says something
;; true, or a truthteller says something false.
(define (says who statement)
    (match who
    ; When liars speak true statments, something is wrong, restart.
    ['liar (when statement
             (fail))]
    ; Unless truthtellers speak true statements, something is wrong.
    ['truthteller (unless statement
                    (fail))]))


(define (solve-riddle)
    (define alice (amb 'liar 'truthteller))
    (define bob (amb 'liar 'truthteller))

    ; We encode Alice's statement
    (says alice
        (and (eq? 'liar alice) (eq? 'liar bob)))

    ; Return a nice string result.
    (format "Alice is a ~a and Bob is a ~a" alice bob))

;; Run the example.
(amb-find (solve-riddle))

;; Lets step through the execution of (solve-riddle) to see what's going on.
;;
;; (amb 'liar 'truthteller) will return 'liar, its first parameter,
;; unless we've already witnessed some call to (fail) by doing so.
;;
;; First time:
;;     alice = 'liar  from (amb 'liar 'truthteller)
;;     bob   = 'liar  from (amb 'liar 'truthteller)
;; We try (says alice
;;           (and (eq? alice 'liar) (eq? bob 'liar)))
;; Which is the same as
;;        (says 'liar (and #t #t))
;; since both alice and bob are liars,
;; but, that fails, since liars can't say true statments.
;;
;; So we go BACK IN TIME, and re-do the assignment of bob.
;; Second time:
;;     alice = 'liar  from (amb 'liar 'truthteller)
;;     bob   = 'truthteller (as we trie'd 'liar and it didn't work)
;;
;; Now we try again to run
;;    (says alice (and (eq? alice 'liar) (eq? bob 'liar)))
;; And it reduces to
;;    (says 'liar (and #t #f))
;; So a liar says a false statement, that's ok.  We don't call (fail).
;; And now we return "Alice is a liar and Bob is a truthteller"

If you're curious as to how it works, I'll be publishing another post later implementing it in in terms of call-with-current-continuation.↩︎
There is also amb-list, which will keep running it and return a list of all possible answers.↩︎