wasabi315
ENJA

lazy.js

JavaScriptで実装された遅延評価機構

lazy.js

lazy.jsはJavaScriptで実装された遅延評価機構です．昔Haskellに使われていたeval/apply形式のSTGをもとにしています．

GitHub - wasabi315/lazy: STG-like lazy evaluation mechanism in JavaScript
STG-like lazy evaluation mechanism in JavaScript. Contribute to wasabi315/lazy development by creating an account on GitHub.
GitHub - wasabi315/lazy: STG-like lazy evaluation mechanism in JavaScript favicon github.com
GitHub - wasabi315/lazy: STG-like lazy evaluation mechanism in JavaScript

目次

例

lazy.jsで何ができるか見てみましょう．

不動点演算子

Haskellの不動点演算子fixの定義ってかっこいいですよね．

fix :: (a -> a) -> a
fix f = let x = f x in x

これ，lazy.jsでもできるんです！嬉しい！

const fix = Fun((f) => {
  const x = Thunk(() => f(x));
  return x;
});

このfixを使うと，例えば階乗関数を次のように定義できます．

const factBody = Fun((f, n) =>
  Case(n, {
    [0]: () => 1,
    default: (n) => {
      const fm = Thunk(() => f(n - 1));
      return mul(n, fm);
    },
  })
);
const fact = Thunk(() => fix(factBody));

const main = Thunk(() => {
  const factN = Thunk(() => fact(10));
  return traceInt(factN);
});

// 3628800が表示される
Evaluate(main);

フィボナッチ数列の無限リスト

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

この有名なフィボナッ数列のリストの定義もlazy.jsでできます．やった〜！

const fibs = Thunk(() => {
  const xs = Thunk(() => tail(fibs));
  const ys = Thunk(() => zipWith(add, fibs, xs));
  const zs = Thunk(() => Cons(1n, ys));
  return Cons(0n, zs);
});

const main = Thunk(() => {
  const ns = Thunk(() => map(traceInt, fibs));
  return rnfList(ns);
});

// フィボナッチ数が延々と表示される
Evaluate(main);

たらいまわし関数やTardisモナドなど，他の例はリポジトリを見てみてください．

API

lazy.jsでは，Fun，Con，Case，Thunkの各コンストラクタを使って遅延計算を組み立てるように設計しています．その組み立てられた計算はEvaluate関数で評価できます．

Fun

Funは関数を定義するためのコンストラクタです．生成される関数はカリー化されており，部分適用も自動的に処理されます．

const flip = Fun((f, x, y) => f(y, x));
// can be used like
... flip(sub, 1) ...

Con

Conはデータコンストラクタを定義するためのものです． Funとは違って，Conは全部の引数を一度にまとめて適用しないといけません．

const Nil = Con("Nil");
const Cons = (x, xs) => Con("Cons", x, xs);

Thunk

Thunkは遅延された計算(サンク)を定義するためのものです．計算の結果は最初の評価された後にメモ化されます． 参考にした論文と同様に，lazy.jsでは値(関数やサンク，数値)に対してしか関数やコンストラクタを適用できません． そのため，式をラップするのにThunkをよく使うことになります．

const pred = Thunk(() => flip(sub, 1));
const num = Thunk(() => pred(43));
Evaluate(traceInt(num)); // 42が表示される

Case

Caseは評価したい計算と，各ケースの計算を持ったレコードを受け取ります． 評価される計算は値でなくてもいいです． defaultはデフォルトのケースを表す特別なケースです．

const filter = Fun((p, xs) =>
  Case(xs, {
    Nil: () => Nil,
    Cons: (x, xs) =>
      Case(p(x), {
        True: () => {
          const ys = Thunk(() => filter(p, xs));
          return Cons(x, ys);
        },
        False: () => filter(p, xs),
      }),
  })
);

const seq = Fun((x, y) => Case(x, { default: (_) => y }));

実装の参考文献