JavaScript で Lazy K インタプリタを実装した

github.com

Emscriptenを使って変換したもの? は見つかったのですが, 生の JavaScript で書かれたものが見つからなかったので書きました. たぶん上手く動いてるんじゃないかしら.

Lazy K ってなんですか

詳しくは Lazy K - Wikipedia とか The Lazy K Programming Language (日本語版: 翻訳:プログラミング言語Lazy_K) を読みましょう.

要はネタ言語の一種です. Brainfuck の関数型版ってよく言われているイメージ.

使い方

npm でインストールできます.

npm install -g lazyk-js
lazykjs /path/to/src

例えば, The Lazy K Programming Language にある, エラトステネスの篩で素数を計算するコード

K
(SII(S(K(S(S(K(SII(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(SS(S(S(KS)K))(KK)))))
(S(S(KS)(S(KK)(S(KS)(S(S(KS)(S(KK)(S(KS)(S(S(KS)(S(KK)(SII)))
(K(SI(KK)))))))(K(S(K(S(S(KS)(S(K(SI))(S(KK)(S(K(S(S(KS)K)(S(S(KS)K)I)
(S(SII)I(S(S(KS)K)I)(S(S(KS)K)))))(SI(K(KI)))))))))(S(KK)K)))))))(K(S(KK)
(S(SI(K(S(S(S(S(SSK(SI(K(KI))))(K(S(S(KS)K)I(S(S(KS)K)(S(S(KS)K)I))
(S(K(S(SI(K(KI)))))K)(KK))))(KK))(S(S(KS)(S(K(SI))(S(KK)(S(K(S(S(KS)K)))
(SI(KK))))))(K(K(KI)))))(S(S(KS)(S(K(SI))(SS(SI)(KK))))(S(KK)
(S(K(S(S(KS)K)))(SI(K(KI)))))))))(K(K(KI))))))))))(K(KI)))))(SI(KK)))))
(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))(S(SII)I(S(S(KS)K)I)))))))K))))
(S(S(KS)(S(KK)(SII)))(K(SI(K(KI)))))))(SII(S(K(S(S(KS)(S(K(S(S(SI(KK))
(KI))))(SS(S(S(KS)(S(KK)(S(KS)(S(K(SI))K)))))(KK))))))(S(S(KS)
(S(K(S(KS)))(S(K(S(KK)))(S(S(KS)(S(KK)(SII)))(K(S(S(KS)K)))))))(K(S(S(KS)
(S(K(S(S(SI(KK))(KI))))(S(KK)(S(K(SII(S(K(S(S(KS)(S(K(S(K(S(S(KS)(S(KK)
(S(KS)(S(K(SI))K))))(KK)))))(S(S(KS)(S(KK)(S(K(SI(KK)))(SI(KK)))))
(K(SI(KK))))))))(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(S(KS)(S(KK)(SII)))
(K(SI(K(KI))))))))(K(K(SI(K(KI)))))))))(S(K(SII))(S(K(S(K(SI(K(KI))))))
(S(S(KS)(S(KK)(SI(K(S(K(S(SI(K(KI)))))K)))))(K(S(K(S(SI(KK))))
(S(KK)(SII)))))))))))(K(SI(K(KI))))))))(S(S(KS)K)I)
(SII(S(K(S(K(S(SI(K(KI)))))K))(SII)))))

primes.lazy といった名前で保存して,

lazykjs primes.lazy

としてやると (遅いけど) 素数がどんどん出てきます.

技術小話

前から何度も作って遊んでいるλ計算的なものの実装を遅延評価に書き換えて, そいつを使っています.

ただし, 普通にサンクを作ってやるだけでは入力待ちができないので, サンクの評価結果は Promise で返すようにしています. ついでにメモ化もできて一石二鳥っぽい. でも結果としてなんかコードの見た目が割とひどいことになりました (このへんとか).