2009-09-15

Lisp相当のマクロが使えるように変更

今回の連載の最終回です。
Lisp相当のマクロを実装します。

マクロの定義はmac(変換前の式)変換後の式と書くことにします。

例)

mac(mul('a,'b))a*b

上のようにマクロを定義しておき、

mul(2,3)

とすると2*3が計算されて6が返されます。

		switch(a) {
		case op(l, tag, r):
			if(tag=="Smac()"){// マクロ取り出し
				macros.push(a);
				return nil;
			} else
			if(symStr(l)=="add" && tag=="M()") {
				var rr:Exp = r;
				switch(rr) {
				case op(aa, tag2, bb):
					if(tag2=="L,") {
						return op(macroExpand(aa,e),"L+",macroExpand(bb,e));
					}
				default:
				}
			}
			return op(macroExpand(l, e),tag,macroExpand(r,e));
		case fun(prm, body, env): return fun(macroExpand(prm,e), macroExpand(body,e), env);
		default: return a;
		}

以上のようにaddシンタックスシュガーの手前に処理を追加します。
macros.push(a)としてmacrosにmacro定義の式を保存します。

次に展開する処理を作成します。

		switch(e.get("macros")){
		case stk(stack): macros = stack;
			for(i in stack) {
				switch(i){
				case op(prms, tag, body):
					var back = env1;
					var m = new Hash<Exp>();
					m.set("parent", env(e));
					env1 = m;
					var rc = macroMatch(prms, a);

					if(rc) {
						var r= execute(body);
						env1 = back;
						return r;
					}
					env1 = back;
				default:
				}
			}
		default:
		}

以上のようにmacroExpand関数の最初にmacroの配列からマクロを取得して式とマッチングします。
マッチしたら式を実行して返します。

次にmacroMatch関数を作成します。この関数では、式全体を再帰的にたどって、aの式とbの式のマッチングを行います。１箇所でもマッチしないところがあればすぐにfalseを返します。

	function macroMatch(a:Exp, b:Exp):Bool {
		switch(a) {
		case ssym(n): env1.set(n,b); return true;
		case op(a1,a2,a3):
			switch(b){
			case op(b1,b2,b3): return (a2==b2)&&macroMatch(a1,b1)&&macroMatch(a3,b3);
			default: return false;
			}
		case nil:
			switch(b){
			case nil: return true;
			default: return false;
			}
		case vid:
			switch(b){
			case vid: return true;
			default: return false;
			}
		case num(n): 
			switch(b){
			case num(nb): return n == nb;
			default: return false;
			}
		case sym(s):
			switch(b){
			case sym(sb): return s == sb;
			default: return false;
			}
		case str(s):
			switch(b){
			case str(sb): return s == sb;
			default: return false;
			}
		default: return false;
		}
	}

これでLisp相当のマクロを実現できます。

まとめ

このように式をベースとするとマッチングのプログラムを小さく書くことができます。
結果的に簡単に強力なマクロを実現できます。

式をベースとした言語はHaskell,SML,Ocaml,Clean等と他にもありますが、
ポピュラーなC言語風の言語の多くは式をベースとしてません。
そのため、LISP級のマクロの導入は困難です。

現在の一般的な言語は、文字列からすぐに巨大な文法に則って構文解析を行います。
これは高速である反面、プログラムでプログラムを扱おうとした場合には規則が複雑なためプログラムも巨大になってしまうのです。

たとえば、Rubyの構文木を作成するプログラムがありますが、どれだけの人が利用しているでしょう？
ほとんど利用されていないのではないでしょうか？
その理由は、文法の巨大さにあるのです。

プログラミング言語の美しさの観点は個人によって違うと思います。
しかし、表現力が高く、プログラムをデータとして扱うことができて、実装が簡単であることが美しさの尺度であるとするなら、美しい言語が作れたのではないかと思います。

以上で、今回のお話はおしまいです。

参考リンク

epp http://staff.aist.go.jp/y-ichisugi/doc/newjdoc/index.html
1. JavaのプリプロセッサでJavaをS式に変換し、操作した後、Javaに戻す仕組み
次世代プログラミング言語開発室 http://www.sun-inet.or.jp/~yaneurao/intensive/newlang/chap0000.html
1. 非常に影響を受けた言語
10分で書ける、お手軽パーザー http://fxp.hp.infoseek.co.jp/arti/parser.html
1. プログラミング言語の基本中の基本の作り方
JavaScript で数式パーサを書いてみた。 http://d.hatena.ne.jp/amachang/20070829/1188400850
1. 演算子順位法の考え方がわかりやすい
Top Down Operator Precedence http://javascript.crockford.com/tdop/tdop.html
1. 演算子順位法について
ビューティフルコード http://www.amazon.co.jp/ビューティフルコード-Brian-Kernighan/dp/4873113636
1. 上記 Top Down Operator Precedenceの和訳があります
Clean Book 第六章インタプリタ http://sky.zero.ad.jp/~zaa54437/programming/clean/CleanBook/part2/Chap6.html
1. 関数型言語Cleanによる演算子順位法を使った式言語ベースでインタプリタを作成している例。
記号のパターンマッチング http://www.geocities.jp/m_hiroi/xyzzy_lisp/abclisp22.html
1. マクロのマッチングで使っているの考え方
D-Expressions: Lisp Power, Dylan Style http://people.csail.mit.edu/jrb/Projects/dexprs.pdf
1. Appleの強力なマクロのある言語、Dylanのマクロ導入のためのD式
生け垣オートマトン: XML スキーマの形式的モデル http://www.xml.gr.jp/relax/hedge_nice_ja.html
1. S式やC式は生垣だよなという
[relax-users-j 01519] 二分木オートマトンによるRELAX Core の検証について http://www2.xml.gr.jp/log.html?MLID=relax-users-j&N=1519
1. 2分木の文法のバリデーション方法を応用して式に適用すると楽に検証できそう
Macro Tree Transducers and Their Complexity http://www.kmonos.net/pub/Presen/tohoku.ppt
1. バリデーションだけじゃなくて、式を変換したりコンパイルしたりするにはMTTをつかうといいみたい

以下プログラムソースです。

Scala で TAPLを勉強しつつ LLVM コンパイラを作る日記

haXeで作るプログラミング言語(14)