　この記事は言語実装 Advent Calendar 2017の、
12月1日の記事です。

ファーストバッターやっていき

始まり

　皆さんは常々クロージャを作っていると思うのですが、
どのように作ってらっしゃるのでしょうか。

環境全てをキャプチャ？

包含される変数のみをキャプチャ？

ユーザ（プログラマ）の選択した変数のみをキャプチャ？

　今回僕がLisp処理系を作るに当たって、
不変性を仮定した場合に（多分）マクロでない（副作用のない）変数を
任意のタイミングで簡約できるということを利用した、
クロージャ生成アルゴリズムを採用しました。

備考

　このLisp処理系の評価戦略は値呼びで、
スコープはレキシカルスコープです。

どんなアルゴリズム？

　以下のようなとても基本的なクロージャを考えます。

(def x 10)
(def f (fn (a) x))
(f 0)
; 10

defマクロは、渡された式を評価し、その結果をグローバル変数に束縛します。
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))

展開？

※追記

　これは一般的に「定数伝播」と呼ばれるらしいです。
知らなかった。

知らなかったので、ここでは「展開」と呼称するのを貫いていきます。
ほら、一貫性って大事ですよね。

定数伝播（定数畳み込み） - Wikipedia

　「展開」は、外部環境の変数をその変数の値で（再帰的に）置き換えます。

(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))

だったりしてますが、「展開」は
ラムダ計算でいう（展開を適用とした）完全ベータ簡約だと思います。

評価戦略（完全β-簡約） - Wikipedia

何が便利なの？

　クロージャを定義したときに、グローバル変数あたりにその場の環境をコピーするという、
もしかしたら一般的かもしれないアルゴリズムを考えたときに…
本記事のアルゴリズムはそれと比べ、簡素に済みます。

グローバルへのコピーを引き起こさない
- = そのクロージャに関数適用がなされるタイミングで、グローバルへの参照が走らない
- グローバルへコピー/参照するアルゴリズムを実装する必要がない
  - コピー/参照するアルゴリズムは例えば……
    コピー時にクロージャごとにユニークな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))))))
===
; 襲い来る無限再帰

どうしようかね？

参考ページ

Thanks

keenさん