Implementing McCarthy's AMB Operator in Javascript Using a Trampoline

John McCarthy in 1963 wrote about his "AMB" operator for making nondeterministic choices. ("A Basis for a Mathematical Theory of Computation", PDF) AMB is also explained in detail in the (free, online) book Structure and Interpretation of Computer Programs.

AMB provides nondeterministic choices with backtracking in the case of failure. This is one of the major components of logic programming, with unification being the other major component. But AMB is useful even without unification. For example AMB makes it easy to collect all permutations of mutliple choices and to generate selective permutations. (Remember writing permutations as a beginning programmer? Yeah - you probably wish you had been taught AMB ahead of that.)

The SICP book uses Scheme for AMB. Scheme makes this easy, using call/cc and macros. And Common Lisp makes this manageable and pretty using macros. Javascript should not be too bad either - no continuations, no macros, but first-class functions help.

Mihai Bazon recently provided an implementations of AMB in Javascript. (Along with some great examples of using AMB, for example to implement N-Queens and Map Coloring).

Implementing AMB benefits from first-class functions, but they are not necessary. Some mechanism for a dynamic escape is needed. In C this is setjump/longjump. In Javascript (and many other languages) this is throw/catch. C does not have first-class functions, so that part gets ugly. Javascript though is a semi-functional language with first-class functions.

Rather than throw/catch, another versatile way to implement control structures with dynamic extent is to use a trampoline. A few weeks ago I wrote here about NCONC, the core of a Scheme interpreter written in Javascript using a "trampoline" for tail-recursion efficiency as well as for first class continuations.

The project ambjs is an implementation of AMB I wrote in Javascript using a trampoline. The source and the tests are explained using docco.

Using trampolines for dynamic-extent control structures can be cleaner, and they can provide more control options. In the case of AMB this implementation exposes fewer mechanisms than Mihai's, the nesting of AMBs is more apparent (to me), and there are fewer rules to be obeyed (and so fewer opportunities for bugs).