標高+1m

Don't be rational.

名前渡しと暗黙的なカリー化とLispを組み合わせたら面白かった

この記事は2012年アドベントカレンダーの記事ではありません。

Nadekoympbyc/Nadeko · GitHub

少し前に『すごいHaskell楽しく学ぼう』を買いまして、にわかHaskellerやってたんですが、使う言語は仕組みを理解したいと思ってとりあえずデフォルトの遅延評価とデフォルトのカリー化をLispにくっつけてみました。
もともとLispにしようとは思ってなかったんですが、S式よりかっこいい構文が思いつかなかったので。(優先順位嫌い)

本質的でないところを書く手間を省くために、パーサはSchemeの(read)で済ませました。

VMは最初SECDマシンを書いて、後からKrivine's Machine(Kマシン)を改造したものに置き換えました。ここ少し詳しく書こう。
Krivine Machineで検索かけるといろいろ論文が出てきますが、
http://pop-art.inrialpes.fr/~fradet/PDFs/HOSC07.pdfhttp://pauillac.inria.fr/~xleroy/talks/zam-kazam05.pdf
このあたりが簡単でわかりやすかったです。
Kマシンは名前渡しと継続を使ったVMで、全ての関数呼び出しが末尾呼び出しになるので最適化とかしなくても意外と速いみたい。SECDマシンと比べるとその差は歴然。

Kマシンはそのままだとλ計算しかできない(ほんとにλ抽象と関数適用しかない)ので、気軽に書ける言語を作るには色々機能を足さなくちゃですね。 Nadekoでは関数定義、定数(数値、シンボル、文字列)、プリミティブ手続き(ホスト言語の機能を呼び出す)、あたりを追加しました。
関数定義は普通にグローバルに参照できるハッシュテーブルで、定数は定数専用にもう一つスタックを作って、プリミティブは定数スタックから好きなだけ引数を拾って計算結果をまた定数スタックに積むっていうふうに実現しました。
定数とかプリミティブを扱う方法はTIM(Three Instruction Machine)の　　www.cse.iitb.ac.in/~as/fpcourse/TIM.ps.gz　これとかが参考になりました。


そんな感じ。

Nadekoコード見てもらいましょう。

(integers -map (* 2) -take 5 -fold + 0) ;=>20

なんの変哲もないLispで……はないですね。これをSchemeで書くと例えばこうなります。

(fold + 0 (take (map (lambda (x) (* x 2)) (iota ∞)) 5)) ;そのまま翻訳

Schemeでのdelayとforceを使った遅延評価については省きます。ここで書くのがめんどくさいのと同じくらい使うのもめんどくさいとだけ。
なにが起きてるかというと、

  1. リストが2引数(car部とcdr部)関数を取るクロージャとして書かれてる. (要するにリストは組み込みで提供してない)
  2. これを不正に利用して、後置関数っぽく見せかけてる。
  3. S式っぽいけど実は括弧はただの結合指定で、関数適用は左結合でどんどん続けられる(カリー化されてるから全部1引数)
  4. カリー化のおかげで部分適用ができるからlambdaを書かなくていい。関数合成も使えばほとんどlambdaがいらない。

リストの後置風関数はこんな感じになってます。(srfi-1.nadeko)

(:= (cons h t f) (f h t))
(:= (map h t f) (null? t (f h) (cons (f h) (t map f))))

実際には普通に前置で定義して、後置のものにマップしてるので、前置でも使えるし、後置でも使えるようになっています。とても便利。

遅延評価(名前渡しだけど)とカリー化のせいで、関数を書くときはLispのものよりもむしろHaskellのものの方が参考になります。そしてだいたいそのまま動きます(遅いけど)。

たとえばフィボナッチ数列
Haskellだと

fib = 1:1:zipWith (+) fib (tail fib)

Nadekoだと

(:= (fib) (cons 1 (cons 1 (fib -zipWith + (fib -cdr)))))

かっこつけてYコンビネータを使えば呼び出しまで1行でできます。

(show (Y (-> (f) (cons 1 (zipWith f + (cdr f)) -cons 1)) -take 10))

たとえば素数列
有名な偽sieve

sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]
primes = sieve [2..]

Nadekoで偽sieve

(:= (inf-int n) (cons n (inf-int (+ n 1))))
(:= (-sieve p ps)
  (cons p
    (ps -remove (-> (x) (= (% x p) 0)) -sieve)))
(:= (primes) (inf-int 2 -sieve))


いまのところこんな感じです。
今後の予定としては、後置関数をもうちょっと深追いしてOOPっぽい見た目を作ってみたりだとか、型システム作ってみたりだとか必要呼び出しにしてほんとのlazyにしたいとか、いろいろあります。

というわけで。