# Amb() in JavaScript, take two

(this is a follow-up on a first article I wrote about amb in JavaScript).

I kept reflecting on this—mostly because the first version was unable to help solving “Einstein's puzzle”, and I got determined to find a fix.

So what, in fact, should **amb** do? It has to pick a value and make sure *something* succeeds with that value. What is *something*? In the Scheme version of the operator, it's the “current continuation”. That is, if you use **amb** multiple times in your program, when one fails only that one restarts (well, and subsequent ones) — it doesn't trigger a restart for the previous **amb** calls which didn't (yet?) fail.

When taken to the simplest description, it's clear that it should look like this:

var amb = (function(){ function fail() { throw fail } function amb(values, program, fail_value) { if (!values) fail(); var n = values.length; if (n == 0) fail(); for (var i = 0; i < n; ++i) try { return program(values[i]); } catch(ex) { if (ex !== fail) throw ex; } return fail_value; }; amb.fail = fail; return amb; })();

So **amb** is a function of two required arguments — *values* and *program* — and optionally a fail value. *Program* is a function that **amb** will call passing it each element from *values* until it does not fail. To fail, a function calls **amb.fail()**. If *program* fails for every value, then **amb** returns *fail_value* (undefined, if not given).

This is the simplest implementation I could think of, and I think the best. Syntactically it's not as nice as you can do with Scheme, because in JS you can't get the “current continuation”—so basically if you have dependent **amb**-s you need to nest functions. Classical I guess for the NodeJS community. Anyway, despite the ugly syntax it's quite fast and as powerful as the Scheme **amb**.

## Examples

So let's rewrite a few examples, culminating with the working version for “who owns the fish?”.

### Permutations

function permutations(elements) { var indexes = [], N = elements.length; for (var i = 0; i < N; ++i) indexes[i] = i; var ALL = []; function add(partial) { amb(indexes, function(p){ for (var i = partial.length; --i >= 0;) if (partial[i] == p) amb.fail(); a = partial.concat([ p ]); if (a.length == N) { ALL.push(a.map(function(i) { return elements[i] })); } else { add(a); } amb.fail(); }); } add([]); return ALL; }

This seems a little more contrived than the example using the first version of amb. The add() inner function receives a partial permutation and adds to it one element such that the new partial permutation is correct. Initially it's called for an empty array and keeps building on it until it gets to a complete permutation (a.length == N). When so it pushes it to the result and fails() in order to generate more solutions. If it's not full, it calls itself recursively to add another element to the partial permutation.

Note that even though the code is a bit longer than the other version, it doesn't need the has_duplicates additional function; also, checking for duplicates becomes very easy: just test that the new element is not already in the partial permutation. The partial permutation is correct by definition.

### Queens problem

function queens(N) { var indexes = []; for (var i = 0; i < N; ++i) indexes[i] = i; var ALL = []; function add(partial) { amb(indexes, function(p){ for (var i = partial.length; --i >= 0;) { if (partial[i] == p || Math.abs(partial[i] - p) == partial.length - i) amb.fail(); } a = partial.concat([ p ]); if (a.length == N) { ALL.push(a); } else { add(a); } amb.fail(); }); }; add([]); return ALL; }

Note how striking similar this is to the permutations code. Except for the condition, the rest is the same. We could easily abstract away the boilerplate and create a, say, “make_permuter” function which would receive a predicate testing whether it's legal to add an element to a partial solution and returning a function that solves the problem at hand; but I'll skip this for now.

### Who owns the fish?

Again, for a description of the problem and an implementation in Common Lisp see this.

So now here is the working code in JavaScript. It takes 0.16s on my laptop (via NodeJS). Optimizations are possible, but clarity is better. ;-)

function who_owns_the_fish() { var NATIONALITIES = [ "British", "Swedish", "Danish", "Norwegian", "German" ]; var BEVERAGES = [ "tea", "milk", "coffee", "beer", "water" ]; var TOBACCO_BRANDS = [ "pallmall", "dunhill", "marlboro", "winfield", "rothmans" ]; var PETS = [ "dogs", "cats", "horses", "birds", "fish" ]; var COLORS = [ "red", "green", "white", "yellow", "blue" ]; function assert(cond) { if (!cond) amb.fail() } function iff(c1, c2) { if (c1 != c2) amb.fail() } function amb_all(values, program){ amb(values, program); amb.fail(); } function find_house(houses, type, val) { for (var i = houses.length; --i >= 0;) if (houses[i][type] == val) return i; } function neighbors(houses, t1, v1, t2, v2) { var h1 = find_house(houses, t1, v1), h2 = find_house(houses, t2, v2); assert(Math.abs(h1 - h2) == 1); } function add_house(houses){ var this_house = houses.length; function other(values, type) { var a = []; for (var i = 0; i < values.length; ++i) if (find_house(houses, type, values[i]) == null) a.push(values[i]); return a; } amb(other(NATIONALITIES, "nat"), function(nat){ amb_all(other(COLORS, "col"), function(col){ amb_all(other(PETS, "pet"), function(pet){ amb_all(other(BEVERAGES, "bev"), function(bev){ amb_all(other(TOBACCO_BRANDS, "tob"), function(tob){ iff( nat == "British", col == "red" ); iff( nat == "Swedish", pet == "dogs" ); iff( nat == "Danish", bev == "tea" ); iff( col == "white", this_house > 0 && houses[this_house - 1].col == "green" ); iff( col == "green", bev == "coffee" ); iff( tob == "pallmall", pet == "birds" ); iff( col == "yellow", tob == "dunhill" ); iff( this_house == 2, bev == "milk" ); iff( this_house == 0, nat == "Norwegian" ); iff( tob == "winfield", bev == "beer" ); iff( nat == "German", tob == "rothmans" ); var h = { nat: nat, bev: bev, tob: tob, pet: pet, col: col }; var a = houses.concat([ h ]); if (a.length == 5) { neighbors(a, "tob", "marlboro", "pet", "cats"); neighbors(a, "pet", "horses", "tob", "dunhill"); neighbors(a, "nat", "Norwegian", "col", "blue"); neighbors(a, "tob", "marlboro", "bev", "water"); // if we get thus far, we have a solution! console.log(a); } else { add_house(a); } })})})})}); // now I dare you, tell me that lisp syntax is ugly. }; add_house([]); }

My first version was way too dumb, checking every possible case; I never let it run to completion.

This one uses a few helper functions:

- assert(condition) — call amb.fail() if the condition is not true
- iff(condition1, condition2) — assert(condition1 == condition2) — basically, if one is true, then both have to be true.
- amb_all — like amb, but fail() every time. That's needed so that the program backtracks — for example when all values of an inner
**amb**were exhausted, we need to “increment” the current one, and so on. - find_house(houses, type, val) — in a list of houses, find the index of the one which has the property
*type*set to*val*.*Type*can be "nat", "col", "bev", "tob" and "pet" for, respectively, nationality, color, beverage, tobacco and animal type. - neighbors(houses, t1, v1, t2, v2) — asserts that houses having
*t1=v1*and*t2=v2*are neighbors (distance between them is 1). - other(values, type) — returns those values that were not already used for currently “built” houses. For example if two houses are built at the current step and they have "British" and "German", it makes no sense to try those values for further houses and discard them thereafter.

For the first call we use plain **amb**, not amb_all — that's because if we exhausted it then we've already searched all the problem space. If we fail there we'd only get an exception. (in fact, I think the proper solution to this would be to make **amb** simply fail if no solutions were found, and wrap everything in a toplevel try/catch block).

#### Possible optimizations

Write each condition as soon as possible. For example immediately after amb(NATIONALITIES) line we can say iff(this_house == 0, nat == "Norwegian"). If we carefully rearrange conditions in this way we could improve speed quite a bit (several times faster, probably) at the expense of having the code a bit harder to read. I didn't care about speed at all (in fact I believe 0.16 sec is very good, for didactic purposes).

Related to the above, we could also notice for example that because Norwegian lives in the first house and it neighbors a house which is blue, then the second house must be blue. Thus we could add this condition:

iff( col == "blue", this_house == 1 );

right after the amb_all line that supplies COLORS. This alone doubles the execution speed (0.07s here).

## Comments

alkApr 09 (22:54) 2011RE: Amb() in JavaScript, take two §I recalled that I have some JS code for generic problem solving. So far it's only DFS and BFS, but more is possible. You might be interested. It's here: https://github.com/alk/jssearch

Chris DoneApr 10 (04:03) 2011RE: Amb() in JavaScript, take two §Haskell version: http://hpaste.org/45504/who_owns_the_fish List monad isn't the fastest thing to use for this, but more or less identical to amb.

Mike KossApr 16 (00:48) 2011RE: Amb() in JavaScript, take two §Thanks so much for posting about this. I'd not seen this style of non-deterministic programming before - I kind of blew my mind.

I wrote my own version in JavaScript, which I think is a bit simplified. You can also edit the script on this page itself to play around with it (hit the edit button in the upper right corner).

http://wiki.pageforest.com/#js-patterns/amb

Radu GrigoreSep 01 (00:38) 2011RE: Amb() in JavaScript, take two §It's late now so I only skimmed thru the post... but it sounds like you might like Scala^Z3 http://lara.epfl.ch/w/scalaz3