LispBuilderを作ったよ(Groovy DSLによるLisp風言語のパーサ?+インタプリタ)

LispBuilderというものを作ったのでgithubに公開しておきます。

これは何かというと、GroovyのBuilderとして作ったlisp風のDSLであり、実行もできます。言ってみるとGroovy上に構築したLisp風言語のインタプリタです。実験的なものですが、以下のようなコードが書けます。

フィボナッチ数の計算

def bx = new LispBuilder()

assert bx.build{progn
                ${defun; fib; ${n}
                  ${IF; ${or; ${equal; n; $1}; ${equal; n; $2}}
                    $1
                    ${add; ${fib; ${add; n; $(-1)}}
                      ${fib; ${add; n; $(-2)}}}}}

                ${fib; $10}

}.eval() == 55

ニュートン法による平方根の計算

def env = new Env()

env.eval{progn
         ${defun; improve; ${y; x}
           ${average; y; ${div; x; y}}}

         ${defun; good_enoughp; ${y; x}
           ${le; ${abs; ${sub; ${mul; y; y}; x}}; $(0.000001)}}

         ${defun; sqrt_iter; ${y; x}
           ${IF; ${good_enoughp; y; x}
             y
             ${sqrt_iter; ${improve; y; x}
               x}}}

         ${defun; sqrt; ${x}
           ${sqrt_iter; $(1.0); x}}}

assert env.eval{sqrt; $(3.0)} == 1.73205081

(参考)

前者はLispBuilderを明示的に使って、S式の生成(build)と評価(eval)を２段階で行っています。Envクラスというのはシンボルのバインド環境を表していて、前者では明示的には渡していませんが.eval()時に新規生成されています。後者はEnvを最初に明示的に生成して、直接eval()メソッドを呼んでいます。内部的にはLispBuilderが作られて呼ばれています。

Lispコード(s式)をGroovy DSLとして表記するための留意点

Lispといっても、Groovy DSLで表現するためにちょっと癖がありまして、以下のような点に留意する必要があります。

丸括弧の代わりに「$+中括弧」を使う。(例：(a) → ${a})
要素はセミコロン(';')で区切る(例: (a b c) → ${a;b;c})。ただし改行前はセミコロン省略可能。
文字列定数には$をつける。(例: "ABC" → $"ABC")
正の整数の数値定数には$をつける。(例: 123 → $123)
その他の数値定数は$()で括る。(例: $(-3), $(1.25))
Groovyの予約語と重なる場合は大文字で指定。(例: IF, TRUE, FALSE)。
プラスやマイナス記号など、記号のatomは使えない。(例: (+ a b) → ${add; a; b})
シンボルにGroovy/Javaクラス名が衝突してはならない。(例: fib.groovyではfibというシンボルは使えない。なぜならそれはクラス名と扱われるから)

「ちょっと癖がある」どころじゃないって。わっはっは。心の目で見ると$と;がすーっと薄くな・・らなかったらシンタックスハイライト設定でどうぞ。詳しいところはサンプルをどうぞ。

Lispとしての特徴

Lispとしては動的スコープの比較的伝統的なものですが、以下の点に留意。

falseとnilは違う
クオート(')記法はない(明示的に(quote ..)と書く)
lambdaのbodyに暗黙のprognはない（さぼり）
リスト評価に遅延評価がある。Lispレベルだけではできないんですけども・・。
大文字小文字の区別はあり

組み込み関数・既定義関数

以下は組み込み関数および既定義の関数の一覧。基本的にサンプルを動かすための機能しかないのです。

組み込み関数	eq IF quote TRUE FALSE nil car cdr cons setq and or progn equal lt le gt ge add sub mul div defun call print println
既定義関数	not neq nullp append reverse

その他

任意のGroovyコードやJavaコードを呼ぶこともできる(swing.groovy参照)。

感想

前に遅延評価記事を書いてたときに思いついて作り始めてみましたが、文法をそれらしく作るためだけでも結構工夫がいりますね。Groovyの場合、DSL実現手段が様々に用意されている(MOP,closure, category,..)のが救いではありますが、それぞれの要素実現にどの手段を選べばいいか、には試行錯誤が必要でした。とはいえ限界や制約も多く、苦労した割りに自然な表記にはなってないかもしれませんが、とりあえずこんなもんかという線には到達できた気がします。さらにAST変換を組み合わせるともうちょっとは自然な文法にできそうな気もしますが焼け石に水な気もします($123、$"abc"、${}の$を取るぐらいはできそう)。

周知

LispBuilderについて、作りや工夫、具体的に苦労した点などについて、7/22のg*work shop（@横浜CIJ)でライトニングトークとして発表したいと思います。よろしくお願い致します。(追記: g*ws 4thの日付を間違えていたので修整しました。大変申し訳ありません(誤)7/11→(正)7/22)

uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかReactとかFregeとかJavaとか -