関数型プログラミングの基礎 継続を使った非決定計算機

継続について書いてあるが、かなりこみ入っている。
とりあえず、以下のようにしたら、動作させることはできた。
おおまかな流れを把握するので精一杯だった。
式の評価とか、なんらかの構造をもつものについてのアルゴリズムは、複雑になりやすいので、こういった方法で少しでも、整理してプログラミングをしていくということなのでしょう。。。

①add(amb(リスト１）,amb(リスト２）)がdirverの中のcalculateの第１引数へ
②calculateの中のmatchにより、add:(x,y)にマッチ
③その中で再帰でcalculateの第１引数へ amb(リスト）の形なので
④amb:(choice)にmatch　また再帰でcalculateの第１引数へ headであるnum()の形で
⑤最終的には num:(n)にmatch　return contiuesOnSuccess(n,contiunesOnFailure);
に到達する。 contiuesOnSuccessは第１引数anyvalue（今の場合n)をそのまま返している。suspendedComputationにはfailureのほうにある残りのリストが保持されることになるらしい。

代数的データ構造のパターンマッチについては、以前でてきた方法
      var exp = {
        match : (anExp, pattern) => {
          return anExp.call(exp, pattern);
        },
 　　  amb : (alist) => {
          return (pattern) => {
            return pattern.amb(alist);
          };
        },
        num : (n) => {
          return (pattern) => {
            return pattern.num(n);
          };
        },
        add : (exp1, exp2) => {
          return (pattern) => {
            return pattern.add(exp1, exp2);
          };
        }
      };


評価関数
      var calculate = (anExp,  continuesOnSuccess, continuesOnFailure) => {
                         return exp.match(anExp, {
 ※数値の場合           num: (n) => {
                             return continuesOnSuccess(n, continuesOnFailure);
                           },
 ※足し算の場合       add: (x, y) => {
                             return calculate(x, (resultX, continuesOnFailureX) => {
                               return calculate(y, (resultY, continuesOnFailureY) => {
　引数xとyがともに成功すれば、両者の値で足し算を計算
                                 return continuesOnSuccess(resultX + resultY, continuesOnFailureY);
                               }, continuesOnFailureX);
　 y の計算に失敗すれば、xの失敗継続を渡す
                             }, continuesOnFailure);
 　x の計算に失敗すれば、おおもとの失敗継続を渡す
                           },
 ※amb式の場合     amb: (choices) => {
                              var calculateAmb = (choices) => {
                               return list.match(choices, {
                                 empty: () => {      
                                   return continuesOnFailure();
                                 },
                                 cons: (head, tail) => {
                                   return calculate(head, continuesOnSuccess, (_) => {
　失敗継続で後尾を計算
                                     return calculateAmb(tail);
                                   });
                                 }
                               });
                             };
                             return calculateAmb(choices);
                           }
                         });
                       };

非決定計算機の駆動関数
      var driver = (expression) =>{　
        var suspendedComputation = null;//中断された計算を継続として保存する変数
　成功継続
        var continuesOnSuccess = (anyValue,
                                  continuesOnFailure) => {//再開に備えて、失敗継続を保存
                                    suspendedComputation = continuesOnFailure;
                                    return anyValue;
                                  };
　失敗継続
        var continuesOnFailure = () => {
          return null;
        };
　内部に可変な状態suspendedComputationを持つクロージャーを返す
        return () => {　//中断された継続がなければ、最初から計算
          if(suspendedComputation === null) {
            return calculate(expression, continuesOnSuccess,  continuesOnFailure);
          } else {　//中断された継続があれば、その継続を実行
            return suspendedComputation();
          }
        };
      };


リストモジュールも必要
  // expect(array).to.an('array');はコメントアウトしないとだめだった。
  var list = { match : (data, pattern) => { return data.call(list, pattern); }, empty: (_) => { return (pattern) => { return pattern.empty(); }; }, cons: (value, alist) => { return (pattern) => { return pattern.cons(value, alist); }; }, head: (alist) => { return list.match(alist, { empty: (_) => { return null; }, cons: (head, tail) => { return head; } }); }, tail: (alist) => { return list.match(alist, { empty: (_) => { return null; }, cons: (head, tail) => { return tail; } }); }, isEmpty: (alist) => { return list.match(alist, { empty: (_) => { return true; }, cons: (head, tail) => { return false; } }); }, /* append:: LIST[T] -> LIST[T] -> LIST[T] */ append: (xs) => { return (ys) => { return list.match(xs, { empty: (_) => { return ys; }, cons: (head, tail) => { return list.cons(head, list.append(tail)(ys)); } }); }; }, /* map:: LIST[T] -> FUNC[T -> T] -> LIST[T] */ map: (alist) => { return (transform) => { return list.match(alist,{ empty: (_) => { return list.empty(); }, cons: (head,tail) => { return list.cons(transform(head),list.map(tail)(transform)); } }); }; }, reverse: (alist) => { var reverseAux = (alist, accumulator) => { return list.match(alist, { empty: (_) => { return accumulator; // 空のリストの場合は終了 }, cons: (head, tail) => { return reverseAux(tail, list.cons(head, accumulator)); } }); }; return reverseAux(alist, list.empty()); }, toArray: (alist) => { var toArrayAux = (alist,accumulator) => { return list.match(alist, { empty: (_) => { return accumulator; // 空のリストの場合は終了 }, cons: (head, tail) => { return toArrayAux(tail, accumulator.concat(head)); } }); }; return toArrayAux(alist, []); }, fromArray: (array) => { // expect(array).to.an('array'); return array.reduce((accumulator, item) => { return list.append(accumulator)(list.cons(item, list.empty())); }, list.empty()); } };
テスト
var ambExp = exp.add(
          exp.amb(list.fromArray([exp.num(1),exp.num(2)])),
          exp.amb(list.fromArray([exp.num(3),exp.num(4)])));
var calculator = driver(ambExp);


  calculator() ;
  calculator() ;
  calculator() ;
  calculator() ;