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).

Moby Grape on the Mike Douglas Show

The video is not perfect, and the sound is not a lot better, but Moby Grape plays a couple of really good songs on the Mike Douglas Show. And it looks like they're having fun being there.

I Have Monkeys In My Clouds

I took advantage of Amazon's offer for a year of 20GB free Cloud Drive storage by purchasing an album stored directly into the cloud. So far I am happy using the Cloud Player from linux, mac, and android. And I am v.happy uploading tons of music that had been spread over several machines and largely unsync'd together in a playable fashion.

The album I purchased to enable the additional storage is The Monkeys, "Head".

The Monkeys started as a TV show, and most of their work was produced and marketed as such. But they did have some talent, and fought, and broke through occasionally as a group that could sing and perform. On "Head" they reflect on their origins.

Hey, hey, we're The Monkeys
...
The money's in, we're made of tin
We're here to give you more!

"Head" is a movie starring The Monkeys and produced by Jack Nicholson. The music is a soundtrack and a really good album in its own right. It's no more dated than the best music from the late 60s, and it's more fresh because it hasn't been overplayed. Or even played.