Define and give an example of the Amb operator.

The Amb operator (short for "ambiguous") expresses nondeterminism. This doesn't refer to randomness (as in "nondeterministic universe") but is closely related to the term as it is used in automata theory ("non-deterministic finite automaton").

The Amb operator takes a variable number of expressions (or values if that's simpler in the language) and yields a correct one which will satisfy a constraint in some future computation, thereby avoiding failure.

Problems whose solution the Amb operator naturally expresses can be approached with other tools, such as explicit nested iterations over data sets, or with pattern matching. By contrast, the Amb operator appears integrated into the language. Invocations of Amb are not wrapped in any visible loops or other search patterns; they appear to be independent.

Essentially Amb(x, y, z) splits the computation into three possible futures: a future in which the value x is yielded, a future in which the value y is yielded and a future in which the value z is yielded. The future which leads to a successful subsequent computation is chosen. The other "parallel universes" somehow go away. Amb called with no arguments fails.

For simplicity, one of the domain values usable with Amb may denote failure, if that is convenient. For instance, it is convenient if a Boolean false denotes failure, so that Amb(false) fails, and thus constraints can be expressed using Boolean expressions like Amb(x * y == 8) which unless x and y add to four.

A pseudo-code program which satisfies this constraint might look like:

let x = Amb(1, 2, 3)
let y = Amb(7, 6, 4, 5)
Amb(x * y = 8)
print x, y
The output is 2 4 because Amb(1, 2, 3) correctly chooses the future in which x has value 2, Amb(7, 6, 4, 5) chooses 4 and consequently Amb(x * y = 8) produces a success.

Alternatively, failure could be represented using strictly Amb():

unless x * y = 8 do Amb()
Or else Amb could take the form of two operators or functions: one for producing values and one for enforcing constraints:

let x = Ambsel(1, 2, 3)
let y = Ambsel(4, 5, 6)
Ambassert(x * y = 8)
print x, y
where Ambassert behaves like Amb() if the Boolean expression is false, otherwise it allows the future computation to take place, without yielding any value.

The task is to somehow implement Amb, and demonstrate it with a program which chooses one word from each of the following four sets of character strings to generate a four-word sentence:

"the" "that" "a"
"frog" "elephant" "thing"
"walked" "treaded" "grows"
"slowly" "quickly"
The constraint to be satisfied is that the last character of each word (other than the last) is the same as the first character of its successor.

The only successful sentence is "that thing grows slowly"; other combinations do not satisfy the constraint and thus fail.

The goal of this task isn't to simply process the four lists of words with explicit, deterministic program flow such as nested iteration, to trivially demonstrate the correct output. The goal is to implement the Amb operator, or a facsimile thereof that is possible within the language limitations.

;; This is the exception that will be thrown if an amb expression is
;; unsatisfiable.
AmbError ::= Exception clone tap {
 
  self message := "Amb expression failed".
 
  AmbError := self.
 
}.
 
;; The Amb object itself is primarily for internal use. It stores the
;; "next" backtracking point if an amb expression outright fails or
;; exhausts its possibilities at some point.
Amb ::= Object clone tap {
 
  ;; The default "next" point is to throw an exception. This will be
  ;; overridden in many cases, if there is an actual next handler to
  ;; jump to.
  self nextHandler := { AmbError clone throw. }.
 
  Amb := self.
 
}.
 
callAmb := {
  ;; We need an object which will be accessible from inside the
  ;; continuations that will store the next backtracking point which
  ;; will be called.
  backtracker := Amb clone.
  ;; We define the dynamically-scoped method $amb which will try each
  ;; possibility that it is given. If all of those possibilities fail,
  ;; it will call the next handler.
  $amb := {
    takes '[cases].
    ;; This is the return point. We're going to try each element of
    ;; the cases variable (probably an array, but it could feasibly be
    ;; any collection type). For each element, we'll jump to this
    ;; point (which will wind up being the end of the $amb method). If
    ;; it ends up failing, the backtrack point will get called and
    ;; we'll try the next one.
    callCC {
      escapable.
      ;; Get the current backtrack point from the toplevel object and
      ;; store it within this continuation. The backtrack object's
      ;; current backtrack point will change as we make new attempts,
      ;; but this prevHandler variable is stored locally in this scope
      ;; and will not change, so we can always use it later.
      prevHandler := #'(backtracker nextHandler).
      ;; We iterate over the collection to try each element.
      cases visit {
        takes '[curr].
        callCC {
          ;; This inner continuation will be our new backtrack point.
          ;; We store the continuation object itself in the backtrack
          ;; object so that future $amb calls know to return to this
          ;; point if something goes wrong.
          nextExit := #'$1.
          backtracker nextHandler := { nextExit call (Nil). }.
          ;; Now we actually try the value by jumping to the end of
          ;; the $amb method and returning control to the caller.
          return (curr).
        }.
      }.
      ;; If we exhaust each possibility, then that means every value
      ;; in the cases variable has been tried and has failed. So we
      ;; set the backtrack point back to what it was before we tried
      ;; all of these values, and then we jump back to that previous
      ;; backtrack point.
      backtracker nextHandler := #'(prevHandler).
      prevHandler.
      ;; prevHandler will always either perform a continuation jump
      ;; (if there is a new backtrack point to try) or throw an
      ;; exception (if we've exhausted all possibilities), so this
      ;; continuation block will never exit normally.
    }.
  }.
  ;; An instant failure at a point in an amb expression is equivalent
  ;; to an $amb call on an empty collection.
  $fail := { $amb (Nil). }.
  ;; Now that the dynamic variables are in place, let's call the
  ;; block.
  #'($1) call.
}.