続々 L2Lisp: マクロの健全化

2007.6.11 (2007.7.4 加筆訂正, 2010.8.11 リンク修正) (鈴)

1. はじめに

L2Lisp (Little Lambda Lisp) 2.0 版 のマクロには, 前回 §3 で説明したとおり,Common Lisp や Emacs Lisp と同じような マクロ引数の捕捉 が発生するきらいがある。 これを解決する普通の方法は gensym 関数の利用だが煩雑である。 より簡単な解決を可能にするため,L2Lisp 3.0 版ではダミー・シンボルを導入した。 このとき未インターン・シンボルと関数 make-symbol, gensym の存在理由の大半がなくなるから, 小さく手頃な処理系として,これらを廃止・削除した。 それによる非互換性が,これが 2.1 版ではなく 3.0 版である理由である。

実行速度は 2.0 版と同程度である。 前回 §1 と同じ環境での 10queens.l の実行時間は約 6.4 秒だった。

2. ダミー・シンボルによる変数捕捉の回避

第1引数が成立する限り,第2引数以降を実行するマクロ (while test body...) を考える。

素朴に書いた次の定義*1は一見すると正常に働くように見える。

(defmacro while (test &rest body)
  (list let '(a)
        (list setq 'a
              (list lambda ()
                    (list cond (cons test (append body '((a)))))))
        '(a)))

しかし,マクロ引数として a を含む式を与えると異常な振舞を示す。

> (let ((a 0))
    (while (/= a 5) 
      (print a)
      (setq a (+ a 1))))
(#<closure> (0 (…略…)))
number expected: (+ (#<arg> 1 0 . a) 1)
          (…以下 スタックの内容…)
#<error>

マクロ引数として与えた式 (/= a 5) と (print a) (setq a (+ a 1)) の中の a が, (let ((a 0)) …) の変数 a ではなく, マクロ展開された入れ子の let 式の末尾再帰関数 a と解釈されるため, その値 (#<closure> (0 (…略…))) を print したあと,(setq a (+ a 1)) で 1 を加算できずにエラーに終わる。

L2Lisp 2.0 版は,この問題を Common Lisp や Emacs Lisp と同じく gensym 関数で解決していた。

(defmacro while (test &rest body)
  (let ((a (gensym)))
    (list let (list a)
          (list setq a
                (list lambda ()
                      (list cond (cons test (append body (list (list a)))))))
          (list a))))

しかし,この場合, マクロ定義の中で a をクォートすることはできず,必ず評価しなければならない*2

そこで L2Lisp 3.0 版では gensym 関数とその背景にある作為的な未インターン・シンボルを廃止するかわりに, ダミー・シンボル を新しく導入した。 (macro …) を評価するとき,そこに字句的に含まれる $ で始まるシンボルは (クォート内でも) ダミー・シンボルとしてその (macro …) の中だけで同一視される。 マクロ展開のとき,マクロ引数由来の (外来の) シンボルは, たとえダミー・シンボルと同じ ($ で始まる) 名前であっても混同されない。 もちろん,その外来のシンボルが,たまたま他のマクロ式のダミー・シンボルであったとしても 混同されない。

ダミー・シンボルを利用すると,while マクロは次のように定義できる。 他のシンボルと同じくダミー・シンボルも自己評価的であることに注意されたい。

(defmacro while (test &rest body)
  (list let '($a)
        (list setq $a
              (list lambda () (list cond (cons test (append body '(($a)))))))
        '($a)))

ダミー・シンボルによって,マクロ定義は,再び素朴に書けるようになる。 マクロの中でローカルに定義したい変数名に $ を接頭するだけでよい。

*1: 前回 §3 でもそうでしたが,マクロ定義の本体で let や setq や lambda や cond をクォートしていません。 L2Lisp ではクォートしてもしなくても問題ありません。 クォートを省いたとき,L2Lisp は Lisp-1 ですから, let はその変数値であるマクロ式へと評価され,マクロ式が関数の位置に出現することになります。 字面上はマクロ式が長々と展開されて非効率そうに見えますが, 内部実装はどちらもポインタ1個にすぎません。 あらかじめ変数値の参照を済ませるわけですから,むしろ,わずかに効率が向上します。 setq, lambda, cond はもともと L2Lisp では自己評価的ですからクォートを省けます。
*2: 仮に Common Lisp と同様のバッククォートを導入しても事情は同じです。 シンボル a にカンマを接頭する必要があります。

「ダミー・シンボル」という呼称は,シンボルの名前に特に意味がなく, 数学の Σi のダミー変数などと同じく自由に変更可能であることにちなむ。 マクロの展開結果のなかで最終的にラムダ式の仮引数となるシンボルをダミー・シンボルとすることにより, ラムダ算法のアルファ変換が実現される。

ダミー・シンボルの内部表現は (#<dummy> . 元のシンボル) という形式のリストである。 元のシンボルからこの形式のリストへの変換は,(macro …) を評価するとき,最初に CompileLambda の内部手続き ReplaceDummyVariables が式内部を再帰的に走査して行う。 このとき同時に変換された同名のシンボルどうしだけが (組込み関数 eq で) 等しくなる。 したがって,実質的に gensym 関数と同じ効果が得られる。 組込み関数 atom はこの形式のリストに t を返すから, ダミー・シンボルが変数並びにあっても let マクロ は正常に動作する。

3. アナフォリック・マクロ

L2Lisp のマクロでフリーシンボルの捕捉は発生しない (前回 §2) が, マクロ引数の捕捉は発生する (前回 §3)。 今回導入したダミー・シンボルは一般に変数の捕捉を回避する。 では,ダミー・シンボルが自動的に使用されるようにして, マクロの変数捕捉を自動的に防止できないだろうか?

マクロ定義に含まれるシンボルを無差別にダミーにすると,他の変数や関数を参照できなくなる。 実用的にマクロの変数捕捉を防止するには, マクロ定義に含まれるシンボルが展開結果のどこにどう出現するかを解析し, 最終的にラムダ式の仮引数となるシンボルだけをダミーにする必要がある。 健全性を保つことを保証する Scheme の保健的 (hygienic) マクロのように, 何らかのマクロ専用言語を規定して自由度を制限するならばともかく, 一般には計算可能な任意の関数がマクロ展開時に使われ得るから,その完全で効率良い実現は困難である (一般に計算可能な任意の関数の振舞を,実際に計算せずに解析し尽くすことは不可能であり, 具体的な引数を与えて実際にマクロ展開する必要がある。 そして,引数由来のシンボルが影響を受けないように,展開前にさかのぼってダミー化し, 再展開する必要がある。 ダミー化によってマクロ展開が全く異なる結果になり得るから,再チェックが必要である。 もしも再チェックに合格しなかったマクロを病的であるとして単純にエラーにしても, 1回多く評価する必要がある)。 §4 で述べるように,防止対象を束縛変数に限れば, 自動的にマクロ引数が捕捉されないように処理系そのものを改造することが可能だが, 実用上は微妙で紛らわしい。

このように一般にマクロ引数の捕捉を自動防止することは困難である。 その一方,マクロ引数の捕捉には有用な用途がある。 結局,自動化するのではなく, マクロ定義で捕捉を発生させたくないシンボルに利用者が陽に $ を接頭して ダミー化する方法が,おそらく最も実用的であろう。

有用な用途の典型は On Lisp 14. で説明されているような アナフォリック (anaphoric) マクロである。 下記は Common Lisp,Emacs Lisp,L2Lisp で同じように動作する。

(defmacro awhen (test &rest body)
   (list 'let (list (list 'it test))
       (list 'cond (cons 'it body))))

第1引数の評価値が非 nil のとき,第2引数以降が順に評価されるが,そのとき (マクロ引数として与えた式の中に含まれる it が捕捉されることにより) 第1引数の評価値を it で参照できる。

> (awhen (+ 1 2 3 4)
     (print it))
10
10
> (awhen (= 1 2)
     (print it))
nil

it は見かけは大域変数のようにみえるが,実際は awhen 式にローカルである。入れ子にしても破綻しない。

> (awhen (+ 1 2 3 4)
     (awhen (+ 200 300)
        (print it))
     (print it))
500
10
10

it を陽に束縛しても,入れ子にした awhen 式の中では隠蔽される。 しかし,さらに入れ子にして束縛すれば,それが優先される。

> (let ((it 'hi))
     (awhen (+ 1 2 3)
        (print it)
        (let ((it 'hey))
           (print it))))
6
hey
hey

4. バリアント: 仮引数の名前解決によるマクロ引数捕捉の回避

前回 §3 で述べたように, 束縛変数,つまりラムダ式の仮引数についていえば, これを含む式をマクロ引数として渡しても変数捕捉が発生しないように処理系そのものを改造できる。 しかし,前回の予想と異なり,実際に実装したところ,あまり有用ではなかったため, 結局,この改造は採り入れないことにした。その理由は,

  1. 大域変数 (スペシャル変数) に対しては捕捉が発生する。この違いは微妙で紛らわしい。
  2. §2 のダミー・シンボルは,変数捕捉の回避方法として十分に簡単で分かりやすい。
  3. §3 のような有用なマクロ引数捕捉が,束縛変数に対して機能しなくなる。

下記がその実装例である。 仮引数の名前解決によるマクロ引数捕捉の回避を実装していることを除き, 元の 3.0 版と同一である。

以下,その概要を述べる。

ラムダ式をコンパイルするとき,仮引数 a の出現は (#<arg> level offset . a) に置換される。 level は最内のラムダ式の仮引数ならば 0 である。 offset は仮引数並びの順に 0 から割り振られる。例えば,

(lambda (a) a)
   ↓
(#<lambda> 1 (#<arg> 0 0 . a))

ラムダ式が入れ子ならば,内側のラムダ式をコンパイルするとき, 自由な (#<arg> level offset . a) の level を1だけ増やす。 これにより,環境リストから変数の実体を得るとき,1レベルだけ外側のフレームが参照される。

(lambda (a) (lambda (x b) a))
   ↓
(#<lambda> 1 (lambda (x b) (#<arg> 0 0 . a)))
   ↓
(#<lambda> 1 (#<lambda> 2 (#<arg> 1 0 . a)))

入れ子のラムダ式の内と外で同じ仮引数名ならば, 内側のラムダ式をコンパイルするとき, 外側で置換された仮引数を内側の仮引数として再解釈し,再置換する。

(lambda (a) (lambda (x a) a))
   ↓
(#<lambda> 1 (lambda (x (#<arg> 0 0 . a)) (#<arg> 0 0 . a)))    ; [1] 
   ↓
(#<lambda> 1 (#<lambda> 2 (#<arg> 0 1 . a)))

この再解釈のとき,これまでの実装では,内側のラムダ式に出現する (#<arg> 0 0 . a) の cdddr である a だけをみて,同じ仮引数かどうかを判定していた。 したがって,下記のようなマクロに対し,

(defmacro m (x)
    (list 'let '((a 4))
          (list 'if (list '< 'a x) (list 'print x))))

束縛変数 a をマクロ引数として与えると,その内部表現である (#<arg> 0 0 . a) と, マクロ展開されたばかりのシンボル a が同一視されて,変数捕捉が発生していた。 具体的に示せば,

(lambda (a) (m a))
   ↓
(#<lambda> 1 (m (#<arg> 0 0 . a)))
   ↓
(#<lambda> 1
  (let ((a 4))
     (if (< a (#<arg> 0 0 . a)) (print (#<arg> 0 0 . a)))))
   ↓
(#<lambda> 1
  ((#<lambda> 1 
    (cond ((< (#<arg> 0 0 . a) (#<arg> 0 0 . a)) (print (#<arg> 0 0 . a)))))
   4))

内側のラムダ式をコンパイルするとき,上記 [1] のように 仮引数並びと本体に出現する束縛変数が必ず同じように置換されている,という事実に注目すれば, この問題は解決できる。 置換されている (#<arg> 0 0 . a) の cdddr である a をみて 同じ仮引数かどうかを判定するのではなく,(#<arg> 0 0 . a) 全体をみて判定すればよい。 このとき,マクロ展開されたばかりのシンボルと束縛変数を区別できるから, マクロ引数の捕捉を回避できることになる。 実装上は,手続き Eval の内部手続き EvalTop の内部手続き CompileLambda がもつ内部手続き Scan と内部関数 ArgList を修正する。下記は修正後の実行例である。

> (defmacro m (x)
    (list 'let '((a 4))
          (list 'if (list '< 'a x) (list 'print x))))
m
> (m 10)
10
10
> (m 1)
nil
> (let ((a 10)) (m a))
10
10

ただし,修正後も,大域変数についてはマクロ引数の捕捉が発生する。

> (setq a 10)
10
> (m a)
nil

大域変数 (スペシャル変数) とシンボルは概念的に区別されているだけだから, この変数捕捉は不可避である。

5. おわりに

L2Lisp 3.0 版では,マクロの変数捕捉の有用性を維持しつつ, ダミー・シンボルを導入して利用者が意図しない変数捕捉を容易に防止できるようにした。 マクロ定義本体の関数が束縛変数の内部表現などに直接踏み込むことを禁止しているわけではないから, 病的なマクロを意図的に定義することは依然として可能だが, 通常の利用方法でマクロ展開の健全さを保つことは十分簡単になったといってよいだろう。 ダミー・シンボルのアイディアは著者自身によるものだが,十分に自明だから,調査をすれば おそらく Lisp その他のプログラミング言語の歴史の中に先行者を見つけることができると思われる (ダミー・シンボルは Scheme 等の保健的マクロの実装に有用であろう。逆にいえば, 保健的マクロの実装にダミー・シンボルと同じアイディアを使っているものがあると予想される)。

バリアントとして,ラムダ式の束縛変数の名前解決の方法を変更することによるマクロ引数の捕捉防止も実験した。 今回 L2Lisp 3.0 版には採り入れなかったが,変数とシンボルを完全に区別できるような 異なった状況,異なった言語仕様のもとでは問題の抜本的な解決策になる可能性がある。


次回へつづく


Copyright (c) 2007 OKI Software Co., Ltd.