サーバーサイドJavaScript(Rhino)の継続でambを書いてみた

"amb は天使のオペレータです。" 独習 Scheme 三週間

参考

ambで、三平方の定理を満たす整数の組を探す。

var fail = [];

function amb(l) {
  if (l.length == 0)
    return (fail.pop())();
  var k = new Continuation();
  fail.push(function () {k(amb(l.slice(1)))});
  return l[0];
}

function pythag(a,b,c) {
  if (a * a + b * b == c * c)
    return [a,b,c];
  amb([]);
}

print((function() {
        var k = new Continuation();
        fail.push(function() {k("no choise")});
        return pythag(amb([1,2,3]),amb([3,4,5]),amb([4,5,6]));
       })());

% rhino -opt -1 -f pythag.js
3,4,5

("-opt -1"をつけるのは継続を使うため)

次は、ambで論理パズルを解いてみる。

SICP の問題 4.42. を解いてみましょう。問題は以下の通りです：
５人の女子生徒が試験を受けた。彼女らの両親は結果に対し過度の関心を持っている、と彼女らは考えている。そこで彼女らは自宅へ試験についての手紙を書くのに、誰もが１つの正しい情報と１つのうその情報を書こうと約束した。以下は彼女らの手紙の関係する部分である。
Betty: 「Kitty は試験が２番で私は３番でした。」
Ethel: 「私がトップと聞いてうれしいでしょう。Joan が２ばんでした。」
Joan: 「私は３番でした。可哀想な Ethel はビリでした。」
Kitty: 「私は２番になりました。Mary は４番でしかありませんでした。」
Mary: 「私は４番でした。トップの座は Betty がとりました。」
５人の女子生徒の本当の順番はどうなっているのか。

var fail = [];

function amb(l) {
  if (l.length == 0)
    return (fail.pop())();
  var k = new Continuation();
  fail.push(function () {k(amb(l.slice(1)))});
  return l[0];
}

function assert(pred) {
  pred ? true : amb([]);
}

function xor(a,b) {
  return a ? !b: b;
}

function allDifferent() {
  if (arguments.length <= 1)
    return true;
  for (var i = 0; i < arguments.length; i++) {
    for (var j = i + 1; j < arguments.length; j++) {
      if (arguments[i] == arguments[j])
        return false;
    }
  };
  return true;
}

//SICP Exercise 4.42
function girlsExam() {
  var kitty = amb([1, 2, 3, 4, 5]);
  var betty = amb([1, 2, 3, 4, 5]);
  assert(xor((kitty == 2), (betty == 3)));
  var mary  = amb([1, 2, 3, 4, 5]);
  assert(xor((kitty == 2), (mary  == 4)));
  assert(xor((mary  == 4), (betty == 1)));
  var ethel = amb([1, 2, 3, 4, 5]);
  var joan  = amb([1, 2, 3, 4, 5]);
  assert(xor((ethel == 1), (joan  == 2)));
  assert(xor((joan  == 3), (ethel == 5)));
  assert(allDifferent(kitty, betty, ethel, joan, mary));
  return ["kitty", kitty,
          "betty", betty,
          "ethel", ethel,
          "joan" , joan,
          "mary" , mary];
}

print((function () {
         var k = new Continuation();
         fail.push(function() {k("no choise")});
         return girlsExam();
       })());

% rhino -opt -1 -f girls.js
kitty,1,betty,3,ethel,5,joan,2,mary,4