IQ1でもASTがいじりたい
この記事はIQ1の2まいめっ Advent Calendar 2018 8日目の記事です。
最近lispを書いていなくて寂しくなって来たのでlispのマクロのことでも思い出していきたいと思います。
Common Lispが中心です。
S式について
lisp系の言語はS式と呼ばれるフォーマットで記述されます。リストの先頭を手続き、残りを引数としてプログラムのASTを記述するのがS式です。
> (* 3 (- 5 2))
9面白いのは、S式がlispのデータ構造であるリストであり、プログラムから操作可能であるという点です。S式とはASTのリストによる表現であり、このリストをプログラムから作ってしまう機構こそがlispのマクロです。ASTベースのマクロは今や珍しくない気がしますが、これをリスト操作でやってのけるのが面白くて好きな部分です。
マクロの定義
Common Lispにおいてはマクロは以下のように定義されます。以下の例はシンボルvarをnil（nullのようなもの）に束縛するマクロの定義です。
(defmacro nil! (var)
(list 'setq var nil))マクロの呼び出しは通常の関数のように行われます。
(nil! hoge)
マクロが呼び出されると、定義中のシンボルが引数に束縛されてリストが作られます。この例ではvarがhogeというシンボルに束縛されて、
(setq hoge nil)という式が作られます。マクロ定義中にあるquote(')は式の評価を止めることを指示するための構文で、setqというシンボルは評価されることなくそのまま残ります。与えられた引数から式が作られ（展開）、生成された式が評価されるという流れでマクロ呼び出しは評価されます。
マクロ定義に便利な構文
Common Lispのものを紹介しますが、他の方言にも同じ機構はあると思います。
quasiquote
上に出て来たクォートの変種としてquasiquote(`)が存在します。式の評価をやめさせるのがquoteですが、その効果をunquote(,)で打ち消せるのがquasiquoteです。
;; a,b,cがそれぞれ1,2,3に束縛されているとき、
> `(a ,b c) ;; bだけ評価される
(A 2 C)
> `(a (,b c)) ;; 同じくbだけ評価される
(A (2 C))
> `(a ,(+ b c)) ;; (+ b c)は評価される
(A 5)quasiquoteを使うと、展開先が想像しやすい形でマクロを定義することができます。
(defmacro nil! (var) `(setq ,var nil))unquote-splicing
上のunquoteの変種となるのがunquote-splicing(,@)です。これは評価結果がリストになるような式に対して使うことができ、評価したリストの中身をその場に埋め込むような動作をします。
> `(a ,@(list 1 2 3))
(A 1 2 3)
;; hogeに(1 2 3)が束縛されているとき
> `(a ,@hoge)
(A 1 2 3)これを使うと可変長引数をとるマクロの定義が楽になります。
条件を満たした時のみ逐次評価を行うwhenという制御構造を自作してみます。
(defmacro our-when (test &body body)
`(if ,test
(progn ,@body)))このマクロは以下のように呼び出して使うことができます。
(our-when (test obj)
(do-hoge)
(do-fuga))この時、testは(test obj)に束縛され、bodyは&bodyというキーワードによって残りの引数をリストにまとめたものである((do-hoge) (do-fuga))に束縛されます。定義中のtestとbodyのみが評価されて埋め込まれることによって次のような式が出来上がります。
(if (test obj)
(progn
(do-hoge)
(do-fuga)))制御構造のためのマクロのbody部は可変長引数の機構を用いて処理することが多いのでよくお世話になります。
macroexpand-1
macroexpand-1という関数でマクロ展開を一段階進めた結果を見ることができます。展開したいマクロ呼び出しにquoteをつけたものを渡して呼び出します。マクロのデバッグに必須です。
> (macroexpand-1 '(our-when (test obj)
(do-hoge)
(do-fuga)))
(IF (TEST OBJ)
(PROGN (DO-HOGE) (DO-FUGA)))
T変数捕捉
マクロのつらい話の一つが変数捕捉です。マクロ展開の際にマクロ定義中のシンボルが他のシンボルと衝突してしまうバグのことを変数捕捉と呼びます。典型的なのはswapなどローカルに変数を用意する例です。
(defmacro swap (sym1 sym2)
`(let ((tmp ,sym1))
(setq ,sym1 ,sym2
,sym2, tmp)))これは以下のような呼び出しに対してうまく動作しません。
> (macroexpand-1 '(swap tmp v))
(LET ((TMP TMP))
(SETQ TMP V
V TMP))
Tマクロシステムの中には、これを回避してくれる衛生的マクロと呼ばれるようなものもあります。しかし、Common Lispのマクロシステムは非衛生的なので自分で回避する必要があります。gensymという、衝突しないシンボルを生成する関数を利用することで、マクロ内の変数が他のシンボルと衝突するのを回避します。
(defmacro swap (sym1 sym2)
(let ((gtmp (gensym))) ;; gtmpは生成したシンボルに束縛される
`(let ((,gtmp ,sym1)) ;; 評価して生成したシンボルに置き換える
(setq ,sym1 ,sym2
,sym2 ,gtmp))))> (macroexpand-1 '(swap hoge fuga))
(LET ((#:G522 HOGE))
(SETQ HOGE FUGA
FUGA #:G522))
Tなお、gensymで回避できるのはswapのようにマクロ側が変数を上書きしてしまうタイプの変数捕捉だけです。マクロ呼び出し外部でsetqなどが他の値に束縛されてしまう場合の回避などには意味がないです。
実例
マクロについてｻｯとおさらいしたところで、マクロの実例を並べていきたいと思います。
if-not
thenとelseを入れ替えるだけの単純なマクロです。Clojureには用意されていたりします。
(defmacro if-not (test &body body)
`(if ,test ,else ,then))くだらないように見えますが、例外を先に弾きたいみたいなケースではじわじわ効いて来ます。
alambda
変数捕捉はやっかいな問題ですが、それを利用したマクロが存在しています。マクロ中で特定のシンボルを値の参照に使うアナフォリックマクロと呼ばれるタイプのマクロです。「アナフォリック」というのは「前方照応的」という意味で、「アレ」とか「コレ」みたいなものです。
alambdaは再帰可能な無名関数を書きやすくするためのマクロで、selfというシンボルで自身を参照することができます。
;; 階乗をalambdaで定義して適用
> (funcall (alambda (x) (if (= x 0) 1 (* x (self (1- x))))) 5)
120定義ではalambdaの定義をselfという局所関数定義に変換してselfを返すということをしています。
(defmacro alambda (params &body body)
`(labels ((self ,params ,@body))
#'self))使い捨ての再帰関数というのは多いもので、渡されたリストを走査したい場合などで頻出します。便利です。
with-gensyms
「マクロを書くためのマクロ」というのが存在していたりします。その一つにwith-gensymsという有名なマクロがあります。これはgensymでシンボルを生成するのを楽にするためのマクロです。
(defmacro swap (sym1 sym2)
(with-gensyms (gtmp)
`(let ((,gtmp ,sym1))
(setq ,sym1 ,sym2
,sym2 ,gtmp))))> (macroexpand-1 '(with-gensyms (gtmp)
`(let ((,gtmp ,sym1))
(setq ,sym1 ,sym2
,sym2 ,gtmp))))
(LET ((GTMP (GENSYM)))
`(LET ((,GTMP ,SYM1))
(SETQ ,SYM1 ,SYM2
,SYM2 ,GTMP)))定義では渡されたシンボルをgensymで生成したシンボルに束縛するためのletをmapcarで作っています。mapcarはいわゆるmapで、シンボルのリストから(<symbol> (gensym))のリストを作っています。高階関数とかループ処理が入るとASTからASTを作る実感が湧いて来て楽しいですね！
(defmacro with-gensyms (syms &body body)
`(let ,(mapcar #'(lambda (s) `(,s (gensym)))
syms)
,@body))valid?->
卒研の言語処理系はClojureで書いていました。簡単な型検査が必要になったのですが、
- 部分木の型検査に失敗したらその場でエラーを返して抜けたい
- AST全体の型検査には部分木の型検査の結果を使いたい
などが組み合わさると記述が結構煩雑になりました。結果以下のようなマクロが生まれました。
(valid?-> sym-1 type-check-expr-1
sym-2 type-check-expr-2
...
sym-n type-check-expr-n
expr-return)動作としては
- 上から順に
type-check_expr-iを評価する type-check-expr-iが成功したら結果をsym-iに束縛して次へ進むtype-check-expr-iが失敗したらその場で失敗の内容を返して抜ける- 最後までたどり着いたら
expr-returnを評価して結果として返す
みたいな感じです。例えばifの型検査は（Common Lisp風に翻訳すると）以下みたいに書けます。
(defun check-type-if (ast)
(valid?-> res-test <test部の型検査>
res-then <then部の型検査>
res-else <else部の型検査>
<if全体の型検査>))実装の詳細は伏せますが、再帰的なマクロとして素直に書けました。
書いているプログラムに合わせて構文を作るのは楽しいです。
おわりに
コードに共通の構造を見つけてまとめるというのはパズルのような面白さがあって僕は好きです。関数で済むなら関数をつかってまとめるべきで、マクロは濫用すべきものではないですが、制御構造を弄るなどマクロでしか出来ないことも多いです。また、ASTをリスト操作で弄るlispのマクロには、ASTを直接操作するような独特の面白さがあると思います。興味が湧いた人はぜひ一度試してみてはどうでしょうか。