不変性を仮定した、環境をキャプチャしないクロージャ生成アルゴリズムとその問題

　この記事は[言語実装 Advent Calendar 2017](https://qiita.com/advent-calendar/2017/lang_dev)の、
12月1日の記事です。

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

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

環境全てをキャプチャ？

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

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

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


# 備考
　この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`に束縛します。

（以下、`===`は展開を表します）

```lisp
(def f (fn (a) x))
===
; xを削除（置き換え）
(def f (fn (a) 10))
```


## 展開？

- - -

※追記

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

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

- [定数伝播（定数畳み込み） - Wikipedia](https://ja.wikipedia.org/wiki/定数畳み込み#.E5.AE.9A.E6.95.B0.E4.BC.9D.E6.92.AD)

- - -

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

```lisp
(def x 10)
(def f (fn (a) x))
===
; xを削除
(def f (fn (a) 10))
```

「展開」は仮引数の変数を展開しません。

```lisp
(def x 10)
(def f (fn (a) (do
    x
    a)))
===
; aを削除しない
(def f (fn (a) (do
    10
    a)))
```

「展開」は`+ - * /`などの基本的なシンボルとマクロのシンボルを展開しません。  
（ここで「基本的な」とは、
実体がS式でない、これ以上は他のS式に展開できないことを表しますこと（実装がネイティブ実装である）
ことを表します。）

```lisp
(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は展開されない
```

「展開」は再帰的に行われます。

```lisp
(def x 10)
(def y x)
(def f (fn (a) y))
===
(def f (fn (a) x))
===
(def f (fn (a) 10))
```

「展開」は（いわゆる）評価を行いません。

```lisp
(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式が被評価される際に実行されます。

例えば

```lisp
(def f (fn (x) x))
```

ここでの`def`マクロは加評価（評価する側）で、
`(fn (x) x)`は被評価（評価される側）です。

　そして例えば`(fn {func-name} {body})`が関数適用（加評価）のがわになる場合は、
展開は特には要請されません。

```haskell
(def *x* 10)
((fn (x) (fn () (+ *x* x))) 1)
===
; ここで*x*を展開してもしなくてもしなくても、特には変わらない
(def *x* 10)
(fn () (+ *x* 1))
```


## 備考2: 順序は問われない
　さっきから

```lisp
(def x 10)
(def y x)
(def f (fn () y))
===
(def x 10)
(def f (fn () x))
===
(def f (fn () 10))
```

だったり

```lisp
(def x 10)
(def y x)
(def f (fn () y))
===
(def y 10)
(def f (fn () y))
===
(def f (fn () 10))
```

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

- [評価戦略（完全β-簡約） - Wikipedia](https://ja.wikipedia.org/wiki/評価戦略#.E5.AE.8C.E5.85.A8.CE.B2-.E7.B0.A1.E7.B4.84)


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

- グローバルへのコピーを引き起こさない
    - = そのクロージャに関数適用がなされるタイミングで、グローバルへの参照が走らない
    - グローバルへコピー/参照するアルゴリズムを実装する必要がない
        - コピー/参照するアルゴリズムは例えば……
          コピー時にクロージャごとにユニークなIDを振っておいて、  
          参照時にそれを鍵にしてグローバルから環境を引き出す。  
          ……というものが考えられる


# それによって起こる注意点および未解決の問題
## 不変性を仮定する必要がある
　処理系で`setq`や`def`などによる、変数の再代入を許したときに、
作られたクロージャはそれに追随できません。

```lisp
(def x 10)
(def f (fn () x))
(f) ; 10
(setq x 20) ; xを20に変更
(f) ; 10
; ↑ 20ではない
```

なので不変性を仮定する必要があります。

具体的には、`setq`を定義しない。
`def`による変数の再定義を禁止するか、名前の上書きと見做すということが必要になります。

上書きの見做し

```lisp
(def x 10) ; A
(def x 20) ; B
; 以下、"x"というシンボルを用いたときは常にBが参照され、Aは参照できない。
```

## 再帰関数をdefとfnの組み合わせで定義できない
　関数定義を行う`defn`マクロを考えます。
これは（僕のように）短絡的に考えると、`def`と`fn`の組み合わせで実現できそうです。

```lisp
(defn f (x) (+ x 10))
===
(def f (fn (x) (+ x 10)))
```

しかし同じように再帰関数を定義しようとすると、展開が必ず無限再帰します。

```lisp
(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))))))
===
; 襲い来る無限再帰
```

どうしようかね？


# 参考ページ

- [これの実装](https://github.com/aiya000/hs-zuramaru/blob/0b71e01c12e10b39276560f7ad622f1f3ca12af8/src/Maru/Eval.hs#L345)
    - [aiya000/hs-zuramaru: An experience of Make-A-Lisp ずら〜 - GitHub](https://github.com/aiya000/hs-zuramaru)
- [kanaka/mal - Make a Lisp - GitHub](https://github.com/kanaka/mal/blob/master/process/guide.md)


# Thanks

- [keenさん](https://twitter.com/blackenedgold)