3imp のフラット・クロージャ

R. K. Dybvig Three Implementation Models for Scheme (以後、 3imp と略す) でこってりと解説してある Chez Scheme 用フラット・クロージャについて。

レキシカル・スコープの実装方法はいくつもあり、 Scheme 動作の説明で使われることが多い環境束縛モデルをここでは伝統的クロージャと呼び分けることにします。 ただ、 伝統というと誤解を与えるかもしれず、 実際にはフラット・クロージャの方が古い上に由緒正しく、 ラムダ算法のレキシカル・スコープの説明に黒板上で使われてきました。 一言で言えば、 スコープ中の自由変数の値をワンセットにするのがフラット・クロージャです。

フラット・クロージャも伝統的クロージャも同じ法則にしたがいます。 レキシカル・スコープでは、 あるレベルのスコープの束縛変数の集合 B と自由変数の集合 F が求まっている場合、 それより一段深いレベルのスコープの自由変数の集合 F1 は、 B ∪ F の部分集合です (F1 ⊆ B ∪ F)。 伝統的クロージャでは、 B の束縛変数が一段深いレベルで自由変数になるかどうかのチェックを省き、 自由変数になる可能性ありとして一段深いレベルの自由変数集合に問答無用に加えます。 フラット・クロージャでは、 自由変数かどうかの判定をおこなって自由変数集合を作ります。

(lambda (x1 x2)
 (lambda (y1 y2)
  (lambda (z1 z2) (f x1 y1 z1))))

伝統的クロージャの例:
  (function (x1 x2) (lambda (y1 y2) ..) E)
  (function (y1 y2) (lambda (z1 z2) ..) ((Vx1 Vx2) . E))
  (function (z1 z2) (f x1 y1 z1)        ((Vy1 Vy2) . ((Vx1 Vx2) . E))

現実的な伝統的クロージャの例:
  (function (x1 x2) (lambda (y1 y2) ..) #(E))
  (function (y1 y2) (lambda (z1 z2) ..) #(#(Vx1 Vx2) E))
  (function (z1 z2) (f x1 y1 z1)        #(#(Vy1 Vy2) #(Vx1 Vx2) E))

現実的なフラット・クロージャの例:
  (function (x1 x2) (lambda (y1 y2) ..) #(Vf))
  (function (y1 y2) (lambda (z1 z2) ..) #(Vx1 Vf))
  (function (z1 z2) (f x1 y1 z1)        #(Vy1 Vx1 Vf))

フラット・クロージャ作成に必要な自由変数探しを実行時におこなうとコストが高いため、 インタプリタ方式が主だった初期の 1962 年頃に伝統的クロージャが生まれ、 1970 年代を通して主流になりました。 それが、 1980 年代にコンパイラ利用が当たり前になり、 コンパイル時に自由変数をリストアップできるようになって、 今や多くの処理系や言語がフラット・クロージャを利用しています。 1980 年代初頭に、 Cardelli が VAX ML にとりいれ、 それを Dybvig が副作用を許すようアレンジして Chez Scheme に採用し Scheme の先例としました。

フラット・クロージャは実行時 VM の変数の扱いが単純になります。 束縛変数と自由変数の 2 つのフレームを使うだけで良くなります。 しかも、 コンパイル時に変数がどちらに属するのか決定できているので、 実行時はそれぞれのフレーム用の命令を実行するだけで済みます。 クロージャを作るときは、 束縛変数と自由変数の 2 つのフレームからクロージャの自由変数フレームへコピーします。 3imp では、 代入される束縛変数をコンパイル時にリストアップしておいて、 関数本体の実行時に代入対象の変数を間接参照に入れ替えます。 これで、 代入される変数はどのフレームからでも間接参照されるようになり、 VM 用に適切な間接参照の命令を生成することができます。

ラムダ形式の例です。 束縛変数集合 bind、 代入対象の束縛変数集合 sets、 そして、 自由変数集合 free をラムダ形式ごとにリストアップしてあります。

(lambda (a b c x y)  ; -------- bind=(a b c x y)    sets=(a x)      free=(cons)
 (set! a
  (lambda (z) (cons x y)))  ; - bind=(z)            sets=()         free=(x y cons)
 (set! x b)
 (c x y))

(lambda (a b c x y)  ; -------- bind=(a b c x y)    sets=(a x)      free=(cons)
 ((lambda (t)  ; -------------- bind=(t)            sets=()         free=(b c x y)
   ((lambda (t)  ; ------------ bind=(t)            sets=()         free=(c x y)
     (c x y))
    (set! x b)))
  (set! a
   (lambda (z) (cons x y))))) ; bind=(z)            sets=()         free=(x y cons)

(lambda (a b c d e f)  ; ------ bind=(a b c d e f)  sets=(a b c)    free=(g h i)
 (lambda (t)  ; --------------- bind=(t)            sets=()         free=(c)
  (set! c 'assign))
 (lambda (t)  ; --------------- bind=(t)            sets=()         free=(b)
  (lambda (t)  ; -------------- bind=(t)            sets=()         free=(b)
   (set! b 'assign)))
 (set! a 'assign)
 (set! i 0)
 (lambda (d e)  ; ------------- bind=(d e)          sets=(d)        free=(c g)
  (set! d 1)
  (g c d))
 (lambda (t)  ; --------------- bind=(t)            sets=()         free=(f)
  (f t)
  (lambda (u)  ; -------------- bind=(u)            sets=()         free=(f t)
   (f t)))
 (lambda (t)  ; --------------- bind=(t)            sets=()         free=(h)
  (lambda (u)  ; -------------- bind=(u)            sets=()         free=(h t)
   (h t))))

ラムダ形式の body と vars を対象に、 スコープ内の自由変数集合を求める find-free 手続きを SRFI 113 の set を使って書き直しました。 ラムダ形式の body は式の並び、 さらに begin 形式も扱えるように修正済みです。

(use srfi-1)
(use srfi-113)
(use util.match)

; (match '(lambda (x y) (set! x y) (set! z y))
;  (('lambda vars . body) (find-free body vars)))
; => (z)

(define (find-free body vars)
 (define phi (set eq-comparator))

 (define (find body binds)
  (fold (lambda (exp u)
    (set-union u
     (match exp
      ((? symbol? var) (if (set-contains? binds var) phi (set-adjoin phi var)))
      (('quote obj) phi)
      (('lambda vars . body) (find body (set-union (apply set-adjoin binds vars) binds)))
      (((or 'set! 'if 'call/cc 'begin) . body) (find body binds))
      ((fn . args) (find exp binds))
      (_ phi))))
   phi body))

 (set->list (find body (apply set-adjoin phi vars))))

同様に set! されている束縛変数の集合を求める find-sets 手続きも式の並びを受け付けるように書き直しておきます。

(use srfi-1)
(use srfi-113)
(use util.match)

; (match '(lambda (x y) (set! x y) (set! z y))
;  (('lambda vars . body) (find-sets body vars)))
; => (x)

(define (find-sets body vars)
 (define phi (set eq-comparator))

 (define (find body sets)
  (if (set-empty? sets)
   phi
   (fold (lambda (exp u)
    (set-union u
     (match exp
      ((? symbol? var) phi)
      (('quote obj) phi)
      (('lambda vars . body) (find body (set-difference sets (apply set-adjoin phi vars))))
      (('set! var . body) (if (set-contains? sets var) (set-adjoin (find body sets) var) (find body sets)))
      (((or 'if 'call/cc 'begin) . body) (find body sets))
      ((fn . args) (find exp sets))
      (_ phi))))
    phi body)))

 (set->list (find body (apply set-adjoin phi vars))))