LoginSignup
1

More than 5 years have passed since last update.

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

Last updated at Posted at 2017-12-08

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

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

始まり

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

環境全てをキャプチャ?

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

ユーザ(プログラマ)の選択した変数のみをキャプチャ?

 今回僕が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))

展開?


※追記

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

知らなかった。

知らなかったので、ここでは「展開」と呼称するのを貫いていきます。

ほら、一貫性って大事ですよね。


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

(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を振っておいて、
        参照時にそれを鍵にしてグローバルから環境を引き出す。
        ……というものが考えられる

それによって起こる注意点および未解決の問題

不変性を仮定する必要がある

 処理系でsetqdefなどによる、変数の再代入を許したときに、
作られたクロージャはそれに追随できません。

(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マクロを考えます。
これは(僕のように)短絡的に考えると、deffnの組み合わせで実現できそうです。

(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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1