兼雑記

■ sedlisp.sed 00:54

https://github.com/shinh/sedlisp

Lisp インタプリタを書きました。 sed で。

https://github.com/shinh/sedlisp/blob/master/sedlisp.sed

README に書いた通り、それなりにややこしいプログラムも動く気がします。具体的には eval.l として、 eval の無いところで eval を実装しました。で、その上で FizzBuzz なんかが動きます。これはつまり S 式のパースは省略した Lisp のインタプリタと言って良いので、 sed で書かれた Lisp の上で Lisp が動いて、その上で FizzBuzz が動いてることになります。ちなみにもう一段かますことはできませんでした。 Ruby で書いた実装でも動かないので、 eval.l がとりあえず循環できない作りになってしまってるみたいですが、デバッグできないので何が間違ってるのかよくわかってません… (追記: id:Irori さんがなおしてくれました! FizzBuzz on Lisp on Lisp on Lisp on sed が動く!)

正直疲れたんで s/// 以外の sed script 書くのやめようかと思いますね…なんか途中から ruby で等価なプログラムを書いてテストしはじめたのですが、 ruby の実装は 1 時間もかかってないのに対して、 sed の方は 40 時間くらいはかかってるんでないかなーと思います。

あとは実装について

加減乗除

加算減算は何度か書いたのでやるだけ作業です。動作の説明は

http://shinh.skr.jp/slide/mederu/048.html

などにあります。

乗除はめんどくさいので Lisp で組み込み関数として書きました。 neg? という関数だけ sed で実装して、割り算の実装に使っています。

次に実行する場所

関数しか無ければ、中から実行すればいいので、最左にある、その中に括弧の無い括弧の組を実行すれば良いです。正規表現で書くと ([^()]*)

大変なのは special form というやつです。 if とか defun とかは、中を先に実行しちゃまずくて、外から実行していく感じになります。これは最左の括弧の組を一旦 @ に変換しておいて、 @ より左に special form があれば、そっちを先に実行、という方式でやりました。

 (+ 2 (if t (+ 3 4) 5))

みたいな式があると、 (if t (+ 3 4) 5) だけを取り出す必要があるわけですが、これも正規表現ってやつはご存知の通りネストした括弧の組を取り出すとかできないので、かなりめんどくさいです。

具体的には (if の中の括弧の組を @ で取り出していって、 (if の中に括弧が無くなれば @ を復元、というようにやりました。

この方式では defmacro の実装はありえないくらいめんどくさいことになります。当然実装してません。

スタック

次に実行する場所を切り出せたら、切り出した以外の場所をスタックに保存しておかなければなりません。これは以前にもやったことがあって、切り出した部分を @ に置換しておいて、その @ を含んだ式をスタックに置いておきました。

さっきの if 文なら

 (+ 2 @)

のようなものがスタックに積まれて、 (if ...) の評価が終わると結果を @ と置換して実行を続けます。

sed にはスタックなどという便利なものは無いんで、ホールドスペースの末尾に一行ずつ書いていくことにしました。

define と defun

define で変数を定義すると、ホールドスペースの先頭の変数を置く空間に書きます。

 (define foo 42)

は

 ;foo;42;

などと定義されます。

変数の展開は、変数一覧をパターンスペースに持ってきてから、正規表現の後方参照でやります。

 s/^\([^\n]*[ ()]\)\?\(\S\+\)\([ ()\n].*\n;\2;\([^;]*\)\)/\1\4\3/

というような感じで…と言ってもなんのこっちゃわからんかもしれませんが、

$ echo '(func foo)@;foo;42;' | sed 's/^\([^@]*[ ()]\)\?\(\S\+\)\([ ()@].*@;\2;\([^;]*\)\)/\1\4\3/'

などとすると foo が 42 に置換されるので、そういうもんです。 (\n は @ に置換しておきました)

defun は単に define と lambda のシンタクスシュガーです。

quote と lambda

このコードの全域で値の区切りとして空白を使っているので、 quote や lambda にある空白は厄介、というかそのままでは全く取り扱えないです。あと括弧も残ってると絶望的です。

しょうがないので、内部的に括弧と空白を別な文字に置換して取り扱ってます。 (quote (4 5)) は [4,5] に、 {lambda_{n_m}_{+_n_m}}$ に置換してあります。 lambda の末尾についている $ は、 lambda を関数適用する時に lambda が引数として渡されたりすると大変なことになるので、ターミネータが必要だと気付いて足したものです。

lambda の適用は、特に引数の処理はだいたい変数の展開と同じです。

print 関数はこのへんをそのまま出力するので、

 (print (lambda (n m) (+ n m)))

などとすると内部表現が見られます。

まとめ

他にもいろいろハックでごまかしてる部分などがあって、大変でした。 evalify した sort とかよくうごいてるなーという感じ。