HomeBlogAmb() in JavaScript

Amb() in JavaScript

(Update: I wrote a follow-up to this article with better code and a working implementation for “who owns the fish?”)

You might have heard of the mysterious “ambiguous operator”.  Just for fun, I wrote an implementation of it in JavaScript.  It might even be useful. ;-)

So what is amb?  Given a list of values, amb nondeterministically returns one of them in such a way that the rest of the program succeeds.  When it is possible, of course.  If it's not possible, then the program fails.

Say what?  So it picks one value from a list, such that the rest of the program is successful!

Here is a hypothetical use for this operator:

var a = amb([ 1, 3, 5 ]);
var b = amb([ 7, 8, 9 ]);
if (a + b <= 10)
    fail();
// amb will return in such way that the fail() line is never reached
console.log(a, b); // 3 and 8, or maybe 5 and 9, etc.

The exact usage will actually be a bit different in JavaScript, but the above is the way you could write it in Scheme because Scheme has first class continuations.  A continuation is an "abstraction of the rest of the program" — so amb is able to “test” the rest of the program multiple times, giving it each value from the list, until it succeeds.  I find this really cool.

I've seen a nice implementation for Common Lisp at Rosetta Code, even though Common Lisp doesn't have first-class continuations.  With macros it can be made to look almost as a part of the language.  That inspired me to try the JavaScript version.  Following there are some examples of usage, and at the bottom of this article you can find the full amb code.

Examples

Find adjacent strings

This is the example used at Rosetta Code.  Given a few lists of strings, find a sequence of strings (one from each list) such that they are adjacent (meaning, last char of a string is the first char of the next one).  Here is my implementation in JS:

amb_run(function(amb, fail){
/* <preamble> */
    // utility function to test if two strings are adjacent
    function adjacent(str1, str2) {
        return str1.charAt(str1.length - 1) == str2.charAt(0);
    }
    // input data
    var w1 = amb([ "the", "that", "a" ]);
    var w2 = amb([ "frog", "elephant", "thing" ]);
    var w3 = amb([ "walked", "treaded", "grows" ]);
    var w4 = amb([ "slowly", "quickly" ]);
/* </preamble> */
    return function(w1, w2, w3, w4) {        
    /* <main-program> */
        if (!(adjacent(w1, w2) && adjacent(w2, w3) && adjacent(w3, w4)))
            fail();
        console.log(w1, w2, w3, w4);
    /* </main-program> */
    };
});

// result is "that" "thing" "grows" "slowly"

Some explanations here.  First, note that we have two sections—which I'm calling the “preamble”, and “main program”.  I couldn't figure out a different possible implementation in JavaScript.  Basically amb needs to know which program to “try”.  In Scheme it can get that easily via call/cc, but that's not possible in JS.

(in fact, our implementation is similar to the Common Lisp one: one can only use amb in the initialization part of amblet).

So, the function that we pass to amb_run receives two arguments, amb and fail, and does two things:

  • places calls to amb in the preamble (and only in the preamble!), and
  • returns a function which tests various conditions for the arguments given by amb and calls fail if the values aren't good.

Note that in the preamble I wrote “var w1 = amb(...)” etc.  That wasn't really necessary, and as you can see, that variable is not used anywhere (in the main function it's shadowed).  In fact, amb() doesn't return a meaningful value.  I wrote it like this just for clarity.

Each call to amb in the preamble arranges for a new argument to be passed to the main function.  So for w1 we will get, in order, one of "the", "that", "a".  For w2 we get "frog", "elephant", "thing".  Etc.

If the main program calls fail, the first argument is “incremented”.  If it had all possible values, it restarts from first value and we move to “increment” the second argument.  And so on.  The main function is called for all possible combinations of values that amb gets to chose from.

Most problems that can be solved with backtracking can be conveniently expressed in terms of amb.  Of course, there are probably faster/better ways to solve these problems; note that I don't care about speed at all here.  Just showing how amb might be used.

Permutations

A quick test:

amb_run(function(amb, fail){
    amb([ "a", "b", "c" ]);
    amb([ "a", "b", "c" ]);
    amb([ "a", "b", "c" ]);
    return function(a, b, c) {
        if (a == b || a == c || b == c) fail();
        console.log(a, b, c);
        fail();                 // to get all solutions
    };
});

One thing to note is is that we call fail() even when we got a solution.  amb won't mind and will move on to find the next solution, therefore calling fail on each iteration will make sure you get all solutions.  Here is a more versatile function based on amb that returns permutations of elements of an arbitrary array:

function permutations(elements) {
    var PERM = [];
    amb_run(function(amb, fail){
        var a = [], n = elements.length, i;
        for (var i = 0; i < n; ++i) a[i] = i;
        for (var i = 0; i < n; ++i) amb(a, i);
        return function() {
            if (!has_duplicates(this)) {
                PERM.push(this.map(function(i){ return elements[i] }));
            }
            fail();
        };
    });
    return PERM;
}

This is a bit more pragmatic.  It uses a for loop to construct an array of integers [ 0, 1, 2, ..., n ] — where n is the number of elements that we want to permute.  Instead of working with elements from the original array (which could be any objects, thus we'd have to implement special logic for ensuring their uniqueness) we will permute this list of integers, which are indexes into the original elements array.  Once a solution is found, we map those indexes on the original array, thus fetching permuted original elements instead; then push this solution to PERM (so we can return it at the end) and fail(), in order to continue finding other permutations.

Also note that instead of getting arguments, the main function uses the this keyword.  This is passed by amb and it's an array containing the arguments.  If you want, it's a shortcut for arguments (but better, as it's a real array).

You can notice it uses a has_duplicate helper function, which I'll paste below.  It's only safe when called with a list of strings or numbers (but that suffices for our implementation of permutations).

function has_duplicates(list) {
    var h = {}, el;
    for (var i = 0; i < list.length; ++i) {
        el = list[i];
        if (h[el] != null) return true;
        h[el] = true;
    }
    return false;
}

Queens problem

amb_run(function(amb, fail){
    var N = 6;
    var a = [];
    for (var i = 0; i < N; ++i) a[i] = i + 1;
    for (var i = 0; i < N; ++i) amb(a, i);
    return function() {
        for (var i = 0; i < N; ++i) {
            for (var j = i + 1; j < N; ++j) {
                var a = this[i], b = this[j];
                if (a == b || Math.abs(a - b) == j - i) fail();
            }
        }
        console.log(this);      // solution found
        fail();                 // search for more
    };
});

Pretty much like the last permutations function, this one sets up an array of numbers [ 1, 2, ..., N ] (where N is the board size).  Then calls amb for that array N times.  Then the main function iterates through this (which again contains the values picked up by amb) and tests that no two are equal, or attack in diagonal (the condition for this is Math.abs(a - b) == j - i — says that if the difference between the rows is the same as the difference between the cols, then those queens are attacking each other).

You might have noticed that in this example, as well as in the permutations one, we call amb with two values — the array to pick from and an index.  When we do that we request that values come starting with the one at that index.  It's convenient because otherwise we would start with [ 1, 1, 1, 1 ], [ 1, 1, 1, 2 ] etc. — they obviously don't make sense because we need them unique — so by passing the second argument to amb we make sure that the first arguments that the main function will get are like [ 1, 2, 3, 4 ].

Map coloring

This problem seems more complicated, but it's not.  It's just that the input data is larger.  We want to assign colors to 10 countries such that no two neighboring countries use the same color.  We start by defining an array of countries—so we can use some IDs for each of them—then the array of neighbors has the elements of the form [ main_country, neighbor1, neighbor2, ... ] (ids of countries, returned by cix).  I used the same countries as in Dorai Sitaram's book.

amb_run(function(amb, fail){
    var countries = [
        "austria",
        "belgium",
        "france",
        "germany",
        "holland",
        "italy",
        "luxembourg",
        "portugal",
        "spain",
        "switzerland",
    ];
    function cix(c) { return countries.indexOf(c); }
    var neighbors = [
        [ cix("austria"), cix("italy"), cix("switzerland"), cix("germany") ],
        [ cix("belgium"), cix("france"), cix("holland"), cix("luxembourg"), cix("germany") ],
        [ cix("france"), cix("spain"), cix("italy"), cix("switzerland"), cix("belgium"), cix("germany"), cix("luxembourg") ],
        [ cix("germany"), cix("france"), cix("austria"), cix("switzerland"), cix("holland"), cix("belgium"), cix("luxembourg") ],
        [ cix("holland"), cix("belgium"), cix("germany") ],
        [ cix("italy"), cix("france"), cix("austria"), cix("switzerland") ],
        [ cix("luxembourg"), cix("framce"), cix("belgium"), cix("germany") ],
        [ cix("portugal"), cix("spain") ],
        [ cix("spain"), cix("portugal"), cix("france") ],
        [ cix("switzerland"), cix("france"), cix("italy"), cix("austria"), cix("germany") ],
    ];

    // call amb for each country; we only need at most 4 colors
    for (var i = 0; i < countries.length; ++i)
        amb([ 1, 2, 3, 4 ]);

    return function() {
        // remember, *this* is a convenience array that stores the arguments
        var colors = this;

        // condition is no two neighboring countries have the same color
        for (var i = 0; i < neighbors.length; ++i) {
            var c = neighbors[i];
            var main = colors[c[0]];
            for (var j = 1; j < c.length; ++j) {
                if (colors[c[j]] == main) fail();
            }
        }

        for (var i = 0; i < countries.length; ++i) {
            console.log(countries[i], "- color:", colors[i]);
        }
    };
});

Who owns the fish?

(Update: check a new version that actually works.)

Note that the following program doesn't really work.  I'm still thinking whether I did it right or not (or maybe it's just too dumb slow; that seems to be the case, in fact).

// "who owns the fish?" (http://weitz.de/einstein.html)
// this needs some more care, for the time being it doesn't quite work.
/*
   1. The Brit lives in the red house
   2. The Swede keeps dogs as pets
   3. The Dane drinks tea
   4. The green house is on the left of the white house
   5. The green house's owner drinks coffee
   6. The person who smokes Pall Mall rears birds
   7. The owner of the yellow house smokes Dunhill
   8. The man living in the centre house drinks milk
   9. The Norwegian lives in the first house
  10. The person who smokes Marlboro lives next to the one who keeps cats
  11. The person who keeps horses lives next to the person who smokes Dunhill
  12. The person who smokes Winfield drinks beer
  13. The German smokes Rothmans
  14. The Norwegian lives next to the blue house
  15. The person who smokes Marlboro has a neigbor who drinks water
 */
console.log("\n* Who owns the fish?");
amb_run(function(amb, fail){

    var NATIONALITIES = [ "British", "Swedish", "Danish", "Norwegian", "German" ];
    var BEVERAGES = [ "tea", "coffee", "milk", "beer", "water" ];
    var TOBACCO_BRANDS = [ "pallmall", "dunhill", "marlboro", "winfield", "rothmans" ];
    var PETS = [ "dogs", "cats", "horses", "birds", "fish" ];
    var COLORS = [ "red", "green", "white", "yellow", "blue" ];

    // now, this was the tricky part.  I thought we'd only need to
    // call amb(NATIONALITIES), amb(BEVERAGES) etc. and describe the
    // conditions.  But we need more than that.  How do you describe
    // positional conditions, for example, if you only get one pick
    // from each type?
    //
    // so what we want amb to pick from is in fact a permutation of
    // NATIONALITIES, one of BEVERAGES, etc.
    //
    // the full problem space is 5!^5 = 24883200000

    amb(permutations(NATIONALITIES));      // -> anat
    amb(permutations(COLORS));             // -> acol
    amb(permutations(TOBACCO_BRANDS));     // -> atob
    amb(permutations(PETS));               // -> apet
    amb(permutations(BEVERAGES));          // -> abev

    return function(anat, acol, atob, apet, abev) {
        assert(abev[2] == "milk");
        assert(anat[0] == "Norwegian");
        assert(acol[1] == "blue"); // because Norw. is neighbor to the blue house

        for (var i = 0; i < 5; ++i) {
            var nat = anat[i], bev = abev[i], tob = atob[i], pet = apet[i], col = acol[i];
            iff( nat == "British"   , col == "red" );
            iff( nat == "Swedish"   , pet == "dogs" );
            iff( nat == "Danish"    , bev == "tea" );
            iff( col == "green"     , acol[i + 1] == "white" );
            iff( col == "green"     , bev == "coffee" );
            iff( tob == "pallmall"  , pet == "birds" );
            iff( col == "yellow"    , tob == "dunhill" );
            iff( tob == "marlboro"  , apet[i + 1] == "cats" || apet[i - 1] == "cats" );
            iff( pet == "horses"    , atob[i + 1] == "dunhill" || apet[i - 1] == "dunhill" );
            iff( tob == "winfield"  , bev == "beer" );
            iff( nat == "German"    , tob == "rothmans" );
            iff( tob == "marlboro"  , abev[i + 1] == "water" || abev[i - 1] == "water" );
        }

        console.log(anat);
        console.log(abev);
        console.log(atob);
        console.log(apet);
        console.log(acol);
    };

    // helpers

    function assert(cond) { if (!cond) fail(); }
    function iff(c1, c2) { assert(c1 === c2); }
});

Source code of amb_run()

Here is without further comments the source code of amb_run.

function amb_run(program) {
    var slice = Array.prototype.slice;
    var main = program(amb, function(){ throw FAIL });
    var FAIL = {};
    try {
        return curried();
    } catch(ex) {
        if (ex === FAIL) return null;
        throw ex;
    }
    function amb(list, delta) {
        if (delta == null) delta = 0;
        curried = (function(curried, list){
            var N = list.length;
            return function() {
                var args = [ null ].concat(slice.call(this));
                for (var i = 0; i < N; ++i) try {
                    args[0] = list[(i + delta) % N];
                    return curried.apply(args, args);
                } catch (ex) {
                    if (ex !== FAIL) throw ex;
                }
                throw FAIL;
            };
        })(curried, slice.call(list));
    }
    function curried() { return main.apply(this, this) }
}

Update

Aliaksey Kandratsenka posted a gist with a better version than my original implementation.  This one requires less boilerplate and it's more flexible, in that the values that amb gets to pick from can depend on values returned by a previous amb.  The examples would need to be rewritten though, but for the better. :-)  I edited it a bit, and here goes:

function amb_run(program, failure_value) {
    var index = 0, steps = [];
    while (true) try {
        return program(amb, fail);
    } catch(ex) {
        if (ex !== fail) throw ex;
        for (var i = steps.length; --i >= 0;) {
            var a = steps[i];
            if (++a[0] < a[1]) break;
        }
        if (i < 0) return failure_value;
        index = 0;
        steps.length = i + 1;
    }
    function amb(values) {
        if (values.length == 0) fail();
        if (index == steps.length)
            steps[index] = [ 0 ];
        steps[index][1] = values.length;
        return values[steps[index++][0]];
    }
    function fail() { throw fail }
}

With this new version, the permutations function would be written like this:

function permutations(elements) {
    var PERM = [], N = elements.length, indexes = [];
    for (var i = 0; i < N; ++i) indexes[i] = i;
    var test = 0; // let's count how many times we enter the function
    amb_run(function(amb, fail){
        console.log("call " + (++test));
        var p = [];
        for (var i = 0; i < N; ++i) {
            p[i] = amb(indexes);
            if (has_duplicates(p)) fail();
        }
        PERM.push(p.map(function(i){ return elements[i] }));
        fail();
    });
    return PERM;
}

permutations([ "a", "b", "c" ]);

Not only is the code cleaner, but it's also faster because we avoid looking into unproductive cases: since we can check partial permutations for correctness, the main program is entered 21 times, instead of 27.

Comments

Page info
Created:
2011/04/07 16:21
Modified:
2011/04/09 22:48
Author:
Mihai Bazon
Comments:
15
Tags:
javascript, lexical closures, programming
See also