不変性を仮定した、環境をキャプチャしないクロージャ生成アルゴリズムとその問題
この記事は言語実装 Advent Calendar 2017の、 12月1日の記事です。
ファーストバッターやっていき 💪
始まり
皆さんは常々クロージャを作っていると思うのですが、 どのように作ってらっしゃるのでしょうか。
環境全てをキャプチャ？
包含される変数のみをキャプチャ？
ユーザ（プログラマ）の選択した変数のみをキャプチャ？
今回僕がLisp処理系を作るに当たって、 不変性を仮定した場合に（多分）マクロでない（副作用のない）変数を 任意のタイミングで簡約できるということを利用した、 クロージャ生成アルゴリズムを採用しました。
備考
このLisp処理系の評価戦略は値呼びで、 スコープはレキシカルスコープです。
どんなアルゴリズム？
以下のようなとても基本的なクロージャを考えます。
(def x 10)
(def f (fn (a) x))
(f 0)
; 10defマクロは、渡された式を評価し、その結果をグローバル変数に束縛します。
fnマクロは一時関数を作成します（いわゆるラムダ式）。
このとき(def f (fn (a) x))によって(fn (a) x)が評価されたタイミングで、
その中の変数xをその実値である(fn (a) 10)として展開し、
最後にそれをfに束縛します。
（以下、===は展開を表します）
(def f (fn (a) x))
===
; xを削除（置き換え）
(def f (fn (a) 10))展開？
※追記
これは一般的に「定数伝播」と呼ばれるらしいです。
知らなかった。
知らなかったので、ここでは「展開」と呼称するのを貫いていきます。
ほら、一貫性って大事ですよね。
「展開」は、外部環境の変数をその変数の値で（再帰的に）置き換えます。
(def x 10)
(def f (fn (a) x))
===
; xを削除
(def f (fn (a) 10))「展開」は仮引数の変数を展開しません。
(def x 10)
(def f (fn (a) (do
x
a)))
===
; aを削除しない
(def f (fn (a) (do
10
a)))「展開」は+ - * /などの基本的なシンボルとマクロのシンボルを展開しません。
（ここで「基本的な」とは、
実体がS式でない、これ以上は他のS式に展開できないことを表しますこと（実装がネイティブ実装である）
ことを表します。）
(def *x* 10)
(def plus (fn (x y) (+ x y *x*)))
(def f (fn () (do
(print (plus 1 2))
(plus 1 2))))
===
(def *x* 10)
; plusを削除（plusは(fn (x y) (+ x y *x*))に展開できる）
(def f (fn () (do
(print ((fn (x y) (+ x y *x*)) 1 2))
((fn (x y) (+ x y *x*)) 1 2))))
===
; *x*を削除
(def f (fn () (do
(print ((fn (x y) (+ x y *x*)) 1 2))
((fn (x y) (+ x y *x*)) 1 2))))
; +, print, fnは展開されない「展開」は再帰的に行われます。
(def x 10)
(def y x)
(def f (fn (a) y))
===
(def f (fn (a) x))
===
(def f (fn (a) 10))「展開」は（いわゆる）評価を行いません。
(def x 10)
(def f (fn (a) (do
(print x)
(+ x 1))))
===
(def f (fn (a) (do
(print 10) ; 10は出力されない
(+ 10 1)))) ; (+ 10 1)は11に評価されない
; ここで展開は止まるつまるところ展開は、 できるところまで変数をその値に置き換え、 そしてそれは（いわゆる）評価ではない。 って感じです。
備考1: 展開が行われるタイミングについて
「展開」は、(fn {func-name} {body})の書式に沿ったS式が被評価される際に実行されます。
例えば
(def f (fn (x) x))ここでのdefマクロは加評価（評価する側）で、
(fn (x) x)は被評価（評価される側）です。
そして例えば(fn {func-name} {body})が関数適用（加評価）のがわになる場合は、
展開は特には要請されません。
(def *x* 10)
((fn (x) (fn () (+ *x* x))) 1)
===
; ここで*x*を展開してもしなくてもしなくても、特には変わらない
(def *x* 10)
(fn () (+ *x* 1))備考2: 順序は問われない
さっきから
(def x 10)
(def y x)
(def f (fn () y))
===
(def x 10)
(def f (fn () x))
===
(def f (fn () 10))だったり
(def x 10)
(def y x)
(def f (fn () y))
===
(def y 10)
(def f (fn () y))
===
(def f (fn () 10))だったりしてますが、「展開」は ラムダ計算でいう（展開を適用とした）完全ベータ簡約だと思います。
何が便利なの？
クロージャを定義したときに、グローバル変数あたりにその場の環境をコピーするという、 もしかしたら一般的かもしれないアルゴリズムを考えたときに… 本記事のアルゴリズムはそれと比べ、簡素に済みます。
- グローバルへのコピーを引き起こさない
- = そのクロージャに関数適用がなされるタイミングで、グローバルへの参照が走らない
- グローバルへコピー/参照するアルゴリズムを実装する必要がない
- コピー/参照するアルゴリズムは例えば……
コピー時にクロージャごとにユニークなIDを振っておいて、
参照時にそれを鍵にしてグローバルから環境を引き出す。
……というものが考えられる
- コピー/参照するアルゴリズムは例えば……
コピー時にクロージャごとにユニークなIDを振っておいて、
それによって起こる注意点および未解決の問題
不変性を仮定する必要がある
処理系でsetqやdefなどによる、変数の再代入を許したときに、
作られたクロージャはそれに追随できません。
(def x 10)
(def f (fn () x))
(f) ; 10
(setq x 20) ; xを20に変更
(f) ; 10
; ↑ 20ではないなので不変性を仮定する必要があります。
具体的には、setqを定義しない。
defによる変数の再定義を禁止するか、名前の上書きと見做すということが必要になります。
上書きの見做し
(def x 10) ; A
(def x 20) ; B
; 以下、"x"というシンボルを用いたときは常にBが参照され、Aは参照できない。再帰関数をdefとfnの組み合わせで定義できない
関数定義を行うdefnマクロを考えます。
これは（僕のように）短絡的に考えると、defとfnの組み合わせで実現できそうです。
(defn f (x) (+ x 10))
===
(def f (fn (x) (+ x 10)))しかし同じように再帰関数を定義しようとすると、展開が必ず無限再帰します。
(defn f (x) (if (= x 0) 0 (+ 10 (f (- x 1)))))
===
; defとfnに分解
(def f (fn (x) (if (= x 0) 0 (+ 10 (f (- x 1))))))
===
; 浅いfを削除
(def f (fn (x) (if (= x 0) 0 (+ 10 ((fn (x) (if (= x 0) 0 (+ 10 (f (- x 1))))) (- x 1))))))
===
(def f (fn (x) (if (= x 0) 0 (+ 10 ((fn (x) (if (= x 0) 0 (+ 10 ((fn (x) (if (= x 0) 0 (+ 10 (f (- x 1))))) (- x 1))))) (- x 1))))))
===
(def f (fn (x) (if (= x 0) 0 (+ 10 ((fn (x) (if (= x 0) 0 (+ 10 ((fn (x) (if (= x 0) 0 (+ 10 ((fn (x) (if (= x 0) 0 (+ 10 (f (- x 1))))) (- x 1))))) (- x 1))))) (- x 1))))))
===
; 襲い来る無限再帰どうしようかね？
