Abstract
マクロは、構文拡張により言語の高い次元の抽象化を行うことができる、Lisp 特有の機能です。マクロは、S式をコンパイルするとき、そのheadがマクロをもつシンボルであったならば、対応する macro-function を呼び出して式を変形させるという動作をします。コンパイルは構文木のrootから順に行われます。
この記事では、マクロ一般の能力ではなく、 現在の Common Lisp におけるマクロシステム について、それが制限を持っているということを示します。また、この制限を克服できる新たなマクロシステムを提案します。
マクロとは
(略)
マクロに関係するマクロ、関数、変数は以下です。
(defmacro name lambda-list &body body)
(macrolet bindigs &body body)
(eval form)
(compile name definition)
(macroexpand form &optional env)
(macroexpand-1 form &optional env)
*macroexpand-hook*
また、環境に関してcltl2で提供される関数も示します。
AUGMENT-ENVIRONMENT
COMPILER-LET
DECLARATION-INFORMATION
DEFINE-DECLARATION
ENCLOSE
FUNCTION-INFORMATION
PARSE-MACRO
VARIABLE-INFORMATION
マクロの基本的な使用方法とその動作
マクロの基本はリスト操作, defmacro , macroexpand-1 です。
defmacro は、ほとんど defun と同じですが、その関数をマクロ展開関数(macro-function)として保存します。
macroexpand-1 は引数にリストを取り、リストの head (最初の要素) にあるシンボルをみて、そのシンボルに macro-function が束縛されているかを見ます。束縛されている場合、defmacroによって定義された関数を呼び出して、その関数が返した新たなフォームを返します。なお、macroexpand-1 は *macroexpand-hook* を通してmacro-functionを呼び出します。二つめの返り値は、マクロ展開が行われたかどうかのbooleanを返します。
マクロ関数が束縛されていない場合、つまりシンボルがタダの関数かスペシャルフォームである場合、何も行いません。下の *form* の例では、そのhead は let 、つまりスペシャルフォームの名前なので、何も展開しません。
(defmacro my-unless (condition &body body)
`(when (not ,condition)
,@body))
(defparameter *form*
`(let ((x 5))
(my-unless (plusp x)
(print :minus))))
(macroexpand-1 *form*)
; -->
; (LET ((X 5))
; (MY-UNLESS (PLUSP X)
; (PRINT :MINUS)))
; NIL
次の場合はどうでしょうか。
(defparameter *form2*
`(my-unless (plusp x)
(print :minus)))
この場合、 my-unless は今回作ったマクロですから、展開されます。
(macroexpand-1 *form2*)
;; -->
;; (WHEN (NOT (PLUSP X)) (PRINT :MINUS))
;; T
展開されると、 my-unless で定義されているとおり、 when が現れます。二つめの返り値は、マクロ展開が行われたかどうかですから、 T が返ります。さて、 CLHS によれば、 when もまたマクロです。そのため、もう何度か macroexpand-1 を噛ませると、こうなります:
(macroexpand-1 (macroexpand-1 *form2*))
;; ->
;; (IF (NOT (PLUSP X))
;; (PROGN (PRINT :MINUS))
;; NIL)
;; T
(macroexpand-1 (macroexpand-1 (macroexpand-1 *form2*)))
;; ->
;; (IF (NOT (PLUSP X)) ; 変化なし
;; (PROGN (PRINT :MINUS))
;; NIL)
;; NIL
if は special operator で、マクロではありませんから、1番目のケースと同じでこれ以上は展開されません。そのため、二つめの返り値はNILになります。
macroexpand はこの２つ目の返り値を見ながら繰り返し展開します。２つ目の返り値がNILになるまで展開し続けるわけです。
(macroexpand *form2*)
;; -->
;; (IF (NOT (PLUSP X))
;; (PROGN (PRINT :MINUS))
;; NIL)
;; T
ここで重要なのは、 macroexpand が展開するのはあくまで 与えられた構文木(フォーム)の一番上の部分だけ であるという事です。
(macroexpand *form*)
;; -->
;; (LET ((X 5))
;; (MY-UNLESS (PLUSP X)
;; (PRINT :MINUS)))
;; NIL
なんど展開しようが LET は LET のままです。マクロ展開を内側まで行うことはありません。
実際にプログラムを動かす時は?
さて、前の章では、 「 macroexpand はすべてのマクロを展開するわけではない」ということを示しました。それが展開するのはトップレベルのマクロだけなわけです。では、内側のマクロはいつ、誰がどのように展開するのでしょうか？
この動作を調べるのには、インタプリタの eval のコードを読むことが助けになります。今私たちはマクロ変換のみに注目したいので、考えるのはインタプリタ評価における動作で十分です。(そうでないと、例えば自分の使っているsbclの場合、ネイティブコードへの変換するコードがまざってきます。)
インタプリタは、マクロを展開しながら逐次動作します。「コンパイルをしないのがインタプリタ」と考えがちですが、実際にはマクロ展開という意味でのコンパイルは行います。
では、実際に sbcl のインタプリタのコードを見てみましょう。sbclは通常、evalをするときでも一旦ネイティブコンパイルして実行しますが、最近のsbclの eval は、 sb-eval:*evaluator-mode* という変数を:interpret にセットすることで、 本当の インタプリタとして動きます。
CL-USER> (setf *evaluator-mode* :interpret)
; --> :INTERPRET
さて、実際のコードです。(一部分、いらないところは削除してあります)
(defun eval (original-exp)
(eval-in-lexenv original-exp (make-null-lexenv)))
;; ↓
(defun eval-in-lexenv (exp lexenv)
(if (eq *evaluator-mode* :compile)
...
(sb!eval:eval-in-native-environment exp lexenv)))
;; ↓
(defun eval-in-native-environment (form lexenv)
(handler-bind
((sb!impl::eval-error ...))
...
(%eval form env)))
;; ↓
(defun %eval (exp env)
...
(%%eval exp env))
;; ↓
長かった。いよいよですね。
(defun %%eval (exp env)
(cond
((symbolp exp)
;; CLHS 3.1.2.1.1 Symbols as Forms
(multiple-value-bind (value kind) (get-variable exp env)
(ecase kind
(:variable value)
(:expansion (%eval value env)))))
;; CLHS 3.1.2.1.3 Self-Evaluating Objects
((atom exp) exp)
;; CLHS 3.1.2.1.2 Conses as Forms
((consp exp)
(case (car exp)
;; CLHS 3.1.2.1.2.1 Special Forms
((block) (eval-block (cdr exp) env))
((catch) (eval-catch (cdr exp) env))
;; special form が20個ぐらい続く
;;
;; (略)
(t
(let ((dispatcher (getf *eval-dispatch-functions* (car exp))))
(cond
(dispatcher ; cltl2:compiler-let のための処理
(funcall dispatcher exp env))
;; CLHS 3.1.2.1.2.4 Lambda Forms
((and (consp (car exp)) (eq (caar exp) 'lambda))
(interpreted-apply (eval-function (list (car exp)) env)
(eval-args (cdr exp) env)))
(t
(multiple-value-bind (function kind) (get-function (car exp) env)
(ecase kind
;; CLHS 3.1.2.1.2.3 Function Forms
(:function (%apply function (eval-args (cdr exp) env)))
;; CLHS 3.1.2.1.2.2 Macro Forms
(:macro
;; **ここからがキモ**
;; **ここからがキモ**
)))))))))))
ネストが深いので、キモだけを抜き出してみました。
(let ((hook *macroexpand-hook*))
(%eval (funcall hook ; 展開
function
exp
(env-native-lexenv env))
env))
と、いうことで、やはり、1レベルだけ展開して、またeval するわけですね。なお、 *macroexpand-hook* は通常 funcall に束縛されています。
スタックの動き
上のコードを見ながら、はじめに扱ったコードを インタプリタがどのように実行するのか、考えてみましょう。すると、展開や評価におけるコールスタックの動き方が下の図のようなものだとわかります。
;; eval するコード
(let ((x 5))
(my-unless (plusp x)
(print :minus)))
;; 展開してできるコード
(let ((x 5))
(IF (NOT (PLUSP X))
(PROGN (PRINT :MINUS))
NIL))
;; コールスタック
(eval ; let
(eval ; my-unless
(macroexpand) ; my-unless -> when -> if
(eval ; if
(eval (eval)) ; (not (plusp x))
(eval)))) ; (progn ...) か NIL
evalのコールの途中に macroexpand が混じっている感じですね。もし展開するコードが２つ以上のマクロ展開を含んでいたらどうなるでしょうか。
;; eval するコード
(my-unless (plusp x)
(my-unless (minusp x)
(print :zero)))
;; 展開してできるコード
(IF (NOT (PLUSP X))
(PROGN
(IF (NOT (MINUSP X))
(PROGN (PRINT :ZERO))
NIL))
NIL)
;; コールスタック
(eval ; my-unless
(macroexpand) ; my-unless -> when -> if
(eval ; if
(eval ; (not (plusp))
(eval ; my-unless
(macroexpand) ; my-unless -> when -> if
(eval ...))))) ; (not (minusp))
ここで掲げたい重要事項が、各々のマクロ展開は独立しているということです。上のマクロ展開は、下のマクロ展開の時に、スタック上に残っていない。カッコでいって上にあるコードがどのようなものだったかという情報は、綺麗サッパリ消えてしまっています。コールスタックに残っていないからです。
局所マクロ -- macrolet で作ってみる --
上の仕様は、「賢い」局所マクロを実装する上の障害になります。局所マクロを実装する方法はすでにあるだろう、と思われるかもしれません。macrolet のことですね。でも、それではいけないのです。
わかりやすい説明をするために、LOOPのような機能をもつ有名なユーティリティ iterate の簡易版を実装してみましょう。私が実装する簡易版 iterate は、だいたい以下のような構文を持ちます。
;; iterate の簡易バージョン
;; iter の中にいるばあい、
;; while は 引数が true の時だけ実行を次の節に続けます。
;; collect はその引数を内部的な変数に集め、iterの返り値にします。
;; iter の外で使われた時は、for と collect はエラーを投げます。
(let ((i 0))
(iter (while (< i 5))
(incf i)
(collect (+ 3 (* 4 i)))))
これを macrolet だけで実装してみましょう。ざっとこんな感じ。
(define-condition compile-error (simple-error)
((message :initarg :message :accessor message))
(:report (lambda (c s)
(princ (message c) s))))
(defmacro collect (x)
(declare (ignore x))
(error 'compile-error
:message "`collect' must be used under `iter'"))
(defmacro while (x)
(declare (ignore x))
(error 'compile-error
:message "`while' must be used under `iter'"))
(require :alexandria)
(use-package :alexandria)
(defmacro iter (&body body)
(with-gensyms (iter-block accumulate start)
`(block ,iter-block
(let ((,accumulate nil))
(macrolet ((while (condition)
`(unless ,condition
(return-from ,',iter-block
(nreverse ,',accumulate))))
(collect (thing)
`(push ,thing ,',accumulate)))
(tagbody
,start
,@body
(go ,start)))))))
(let ((i 0))
(iter (while (< i 5))
(incf i)
(collect (+ 3 (* 4 i)))))
;; --> (7 11 15 19 23)
うん、まあうまく行ってますね。なんだ、やはり macrolet だけで十分じゃないかと。
では、それと同じ感じで 本来の iterate にある(collect x into acc) の機能を作ってみましょう。これは、モノが蓄積される場所を明示的に指定できる機能です。
(let ((i 0))
(iter (while (< i 5))
(incf i)
(print acc) ; <--
(collect (+ 3 (* 4 i)) :into acc))) ; <--
・・・できますか？ macroletだけで？ できないはずです。
何らかの場所を明示的に指定するためには、その場所を束縛するように、ループ全体を let で囲まなくてはいけません。 でも、collect節が展開されるのは、iterが展開された後なのです。この点こそが致命的な弱点です。
Macros in Common Lisp are still restricted
lisp以外の言語の使用者からすれば「はぁ、そうですか」となるかもしれませんが、まあど〜せそういった人々は対象ではありません。私が考える common lisp のマクロの致命的な弱点はこの点です。
マクロ展開が再帰的でない
マクロ展開は、 繰り返し によって行われます。CLHSですら、こう書いています。
macroexpand repeatedly expands form until it is no longer a macro
form. In effect, macroexpand calls macroexpand-1 repeatedly until the
secondary value it returns is nil. -- CLHS Function MACROEXPAND, MACROEXPAND-1
展開が再帰的で、上の展開がスタックに残っていれば、たとえば先ほど示した例に対応する collect の実装は、以下のように書くことができます。
(collect (thing &key into)
(if into
(error 'accumulate-target :name into) ; コンパイルやり直し！
`(push ,thing ,',accumulate)))
そして、 iter 展開時のハンドラでこのシグナルをキャッチするのです。たとえば、以下のような実装はどうでしょうか。&continuation cont としてクロージャが与えられ、これを funcall を通して呼ぶことで、下層の macroexpand を呼ぶことができると考えましょう。スタックの下から登ってきた condition を、上のハンドラが受け取って、マクロ展開をやり直せます。
(defmacro iter (&body body &continuation cont)
(with-gensyms (iter-block accumulate start)
(handler-case
(funcall #'cont
`(block ,iter-block
(let ((,accumulate nil))
(macrolet ((while (condition)
`(unless ,condition
(return-from ,',iter-block
(nreverse ,',accumulate))))
(collect (thing &key into)
(if into
(signal 'accumulate-target :name into)
`(push ,thing ,',accumulate))))
(tagbody
,start
,@body
(go ,start))))))
;; handler
(accumulate-target (c)
(setf accumulate (name c))
(funcall #'cont
`(block ,iter-block
(let ((,accumulate nil))
(macrolet ((while (condition)
`(unless ,condition
(return-from ,',iter-block
(nreverse ,',accumulate))))
(collect (thing &key into)
`(push ,thing ,',accumulate)))
(tagbody
,start
,@body
(go ,start))))))))))
Related Works
本物の iterate では、このようなことが行えないため、code walker を用いて (collect ... into ...) 節を検出しています。code walker がどう賢くないかというと、 collect などの節がマクロの中に現れてしまった時に困るという点です。
;; 一階層隠蔽する
(defmacro my-collect (&rest args)
`(collect ,@args))
(let ((i 0))
(iter (while (< i 5))
(incf i)
(print acc)
(my-collect (+ 3 (* 4 i)) into acc)))
iterate の code walker は、すべての collect 節を漏らさず検出するために、 iter 以下のすべてのマクロを展開する必要があります。しかし、それには限界があります。iterateは、iter節の中に現れた macrolet を展開できません。つまり、 macrolet の中にある while や collect は code walker に見過ごされます。
(require :iterate)
(in-package :iterate)
(let ((i 0))
(iter (while (< i 5))
(incf i)
(print acc)
(macrolet ((my-collect (&rest args)
`(collect ,@args)))
(my-collect (+ 3 (* 4 i)) into acc))))
; in: LET ((I 0)) ...
;
; caught WARNING:
; Iterate:
; Iterate does not know how to handle
; the special form (MACROLET ...)
; It will not be walked, which means that Iterate clauses
; inside it will not be seen.
;
; compilation unit finished
; Undefined function:
; COLLECT
; Undefined variables:
; ACC INTO
これは、実質的には ANSI CLの問題です。実は、cltl2 の augment-environment を使えば、macrolet を認識して展開することができます。
[Function] augment-environment env &key
:variable :symbol-macro :function :macro :declare
:macro
The argument is a list of local macro definitions, each of the form (name definition). Note that the argument is not in the same format as the cadr of a macrolet special form. Each definition must be a function of two arguments (a form and an environment). The new environment will have local macro bindings of each name to the corresponding expander function, which will be returned by macro-function and used by macroexpand.
これによって、
(defmacro iter (... &environment env)
...
(walk-code ... env))
(defun walk-code (form env)
...
(when (eq 'macrolet (car form))
(destructuring-bind (car macros . body) form
(declare (ignore car))
(walk-code
`(progn ,@body)
(augment-environment
env
:macro (make-macro-functions macros))))))
と、まあこのように、macrolet を 普通のマクロと同じように展開できるはずです。ただしもう一度ですが、これは cltl2 に頼ることになります。
しかしそもそも、 walk-code は、letやtagbody、blockやcatch など、スペシャルフォームを認識して、すべて理解し直さなくてはなりません。それってすっっっっごく頭が悪いと思いませんか?Common Lisp にはもとからevalやcompileなど、スペシャルフォームをネイティブコードまたはバイトコードに変換してくれる便利な関数が存在しています。なぜ、二度同じものを書きなおさなくてはならないのでしょうか?
それに、結局このwalk-codeは以下のmacroexpand の中で行われるわけです。つまり、そのあとのevalが、展開したスペシャルフォームと関数フォームをもう一度解析し直す -- つまり、マクロの有無をもう一度確認するわけです。これはとても非効率ではないでしょうか？
(eval ; let
(eval ; iter
(macroexpand) ; iterを展開 (中でwalk-codeを呼ぶ)
(eval))) ; 展開したコードをまた読み込み直す -- マクロのチェックもする
また、その他の例もあります。たとえば以下のような例。
(let ((x 0))
(let ((y x))
(declare (fixnum y))
...))
letは実際にはマクロではありませんが、仮にマクロだと考えてください。この例では、yの方がfixnumであると言われています。しかし、yはxから直接コピーしたものです。マクロ展開をバックトラックして、 xの型も fixnumであると宣言したくなりませんか？
似たような応用例はいろいろと考えられます。上に挙げた例は、ソースコードの最適化という操作に大きな効果をもたらすわけですが、これを一般化すると、「ソースコード(カッコ)の内側から、より大域的な環境に制約(=型情報など)を伝播させることができる」というわけです。今までのマクロシステムではそのようなことはできませんでした。そのため、この種の最適化は処理系独自の拡張 (sbclならば deftransform など)によってしか不可能だったのではないかと思います。
結論
現状のマクロ展開は、
macroexpand -> eval -...-> eval -> macroexpand -...->
のように、一部を展開しては次へ評価するという形をとります。その途中で、「以前にmacroexpandを行った」という情報はスタックから消えてしまうため、コンディションシステムを用いてマクロ展開前の状態に戻ることはできなくなります。これは、マクロの可能性をかなり制限します。
この記事では、より良いマクロシステムの設計として、「展開自体は最初に再帰的にすべて行ってしまい、展開しつくしたコードを評価ないしバイトコード・ネイティブコードコンパイルする」といった形式を提唱しました。また、そのようなマクロシステムを使えば、処理系の特殊な実装に頼ることなく、局所的なコードからより大域的な制約を推論することができることを示しました。
以上、反応をお待ちしています。