Skip to content

Instantly share code, notes, and snippets.

@alk
Created April 9, 2011 04:10
Show Gist options
  • Save alk/911094 to your computer and use it in GitHub Desktop.
Save alk/911094 to your computer and use it in GitHub Desktop.
var AmbTest = TestCase("AmbTest");
AmbTest.prototype.testBasic = function () {
function beats(ix, iy, jx, jy) {
return ix == jx || Math.abs(ix-jx) == jy-iy;
}
var result = ambRun(function (amb, fail) {
var queenPos = [];
for (var i = 0; i < 8; i++) {
var lastPos = amb([0,1,2,3,4,5,6,7]);
for (var j = 0; j < i; j++) {
if (beats(queenPos[j], j, lastPos, i))
fail();
}
queenPos.push(lastPos);
}
return queenPos;
});
console.log(result);
}
function ambRun(body, failureValue) {
var currentIndex = 0;
var ambs = [];
function fail() {
throw fail;
}
function amb(choices) {
// return old choices initially
if (currentIndex < ambs.length) {
// assuming choices are equal ambs[currentIndex][1]
return choices[ambs[currentIndex++][0]];
}
if (currentIndex > ambs.length) {
throw new Error("BUG");
}
if (!choices.length) {
throw fail;
}
// and then initiate new choice level
ambs[currentIndex++] = [0, choices];
return choices[0];
}
do {
try {
// if we succeeded return
return body(amb, fail);
} catch (e) {
if (e !== fail) {
throw e;
}
}
if (currentIndex != ambs.length) {
throw new Error("BUG or non-deterministic body");
}
currentIndex = 0;
for (var i = ambs.length-1; i >= 0; i--) {
var currentAmb = ambs[i];
// try 'incrementing' choice
if (++currentAmb[0] < currentAmb[1].length) {
// and stop when that succeeds
break;
}
// if we run out of choice at some level, try level before that
// while deleting this level from ambs (ambs.length assignment
// after loop)
}
// if we run out of choices, abort
} while ((ambs.length = i+1) > 0);
return failureValue;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment