HomeBlogAmb() in JavaScriptTake two

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 valType 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

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

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

    Page info
    Created:
    2011/04/09 21:09
    Modified:
    2011/04/10 01:05
    Author:
    Mihai Bazon
    Comments:
    4
    Tags:
    javascript, lexical closures, programming
    See also