amb.js

// ambiguous
//
// a dirty implementation of
// http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines/

function amb(possibilities, cc) {
  while (possibilities.length > 0) {
    try {
      return cc(possibilities[0]);
    } catch (e) {
      if (e == "AssertionError") {
        possibilities.shift();
      } else {
        throw e;
      }
    }
  }
  throw "AssertionError";
}

function assert(cond) {
  if (!cond) {
    throw "AssertionError";
  }
}

// The amb ('ambiguous') procedure takes a list of values, and chooses one of
// them. The catch here is that amb must choose a value so that all assert
// statements encountered in the future of the computation are true. This
// implements a sort of 'time-traveling search'. For example, the following
// Javascript code: 
amb([1,2,3,4,5,6,7], function(a) {
amb([1,2,3,4,5,6,7], function(b) {
amb([1,2,3,4,5,6,7], function(c) {
    // We're looking for dimensions of a legal right triangle using the
    // Pythagorean theorem:
    assert(a*a + b*b == c*c);
    // And we want the second side to be the shorter one:
    assert(b < a);
    // Print out the answer.
    console.log(a, b, c);
    //=>  4 3 5
}); }); });
// The amb procedure chose these values so that when the assertions were
// encountered later on, they were true.