■
この前のScheme or YARVが面白かったので、なんとなく楽しくなって、Toy Lispを作ってらっしゃる日記を検索して見て回ったりしてました。
リスト
2007-03-14 - HaskellでLispを書く日記 - haskell ではHaskellでLisp。ちゃんとしたS式パーザがとてもコンパクトに書かれていて、Parsec便利そうですねえ。そちらで
やっぱりlisp(LISt Processing)というからには、car,cdr,consが使えないと。
と書かれていて、これはその通りだと思ったので、真似してみることにしました。consセルは２要素の配列で表現しちゃうことにすると
def cons(a,d); [a,d]; end def car(lst); lst[0]; end def cdr(lst); lst[1]; end
これで完成。関数にしないで全部その場でコンパイルすることにすると
when :cons scm_compile arg[0]; scm_compile arg[1]; newarray 2 when :car scm_compile arg[0]; putobject 0; send :[], 1 when :cdr scm_compile arg[0]; putobject 1; send :[], 1 when :nil? scm_compile arg[0]; putnil; send :==, 1 when :list arg.each{|a| scm_compile a} putnil arg.each{|a| newarray 2}
こうですね。空リストはnilということにしました。
scheme <<EOS (define (sum x) (if (nil? x) 0 (+ (car x) (sum (cdr x))))) EOS p scheme("(list 1 2 3)") # ==> [1,[2,[3,nil]]] p scheme("(sum (list 1 2 3))") # ==> 6
末尾再帰
突然ですがRubyでSchemeのサブセットを実装します。継続と末尾再帰最適化ありの。その１：データ構造とパーサ - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥ という記事では
と書かれていて、これもまた実にその通りだと反省しました。
YARVにも末尾再帰の最適化は予定はされているらしく、VM_CALL_TAILCALL_BIT というフラグは定義されています。が、特に実装はされていません（たぶん）。というわけで、手製の超絶手抜き末尾再帰を自分で実装してみます。
まず、コンパイル時に関数の末尾かどうかを気にしながらコンパイルするようにします。
def scm_compile(s,tailpos=false)
関数を定義するときだけ、そのフラグをtrueにします。↓こんな感じ。
when :define mname, *mparam = arg[0] putnil definemethod mname, YASM.method(mname, mparam) { _ :method_head # <-- scm_compile arg[1], true # <-- leave } putnil
あと、末尾再帰するわけなので、メソッド先頭にジャンプで戻るためのラベルを置いておきました。
if文全体が末尾位置なら、そのthen部とelse部も末尾です。というわけでtailposフラグをスルーパス。
when :if scm_compile arg[0] branchunless :else_part scm_compile arg[1], tailpos #<-- jump :end _ :else_part scm_compile arg[2], tailpos #<-- _ :end
あとは、末尾の再帰呼び出しをジャンプへとコンパイルするだけです。
else
if tailpos && op.to_s==@name # <--
arg.each{|a| scm_compile a} # <--
@vars.reverse.each{|v| setlocal v} # <--
jump :method_head # <--
else
putnil
arg.each{|a| scm_compile a}
call op, arg.size
end
YASM::SimpleDataBuilderのインスタンス変数に触ってるのと、あとlet文作ってないので変数は引数しかないという手抜き仕様を大いに活用しているのがダメなところです。よい子のみんなは真似しないでね。
ま、ともかく、
scheme <<EOS (define (wa n) (if (== n 0) 0 (+ n (wa (- n 1))))) EOS p scheme("(wa 10000)"); # ==> stack level too deep (SystemStackError)
これは末尾再帰じゃないのでスタックがあふれますが。
scheme <<EOS (define (wa2 n a) (if (== n 0) a (wa2 (- n 1) (+ n a)))) EOS scheme <<EOS (define (wa3 n) (wa2 n 0)) EOS p scheme("(wa3 10000)") # ==> 50005000
これは末尾再帰なので無事計算できるようになりました。やった！
勢いでlambda
簡単な言語のインタプリタ/コンパイラを作るときに一番面倒なのは、変数などなどの名前の管理だと個人的には思っています。ここまでは、「ローカル変数を定義するlet文が無い」「変数とindexの対応関係はyasmが管理してくれている」という二つの理由で、この部分を思いっきり手抜きできていました。もし前回のScheme on YARVが簡潔に見えたとしたら、それが理由の99.9%です（たぶん）。
前置きはともかく、関数型言語ならlambdaとか高階関数くらい作れないとねー、と思いました。これをやると変数の範囲にスコープができたり色々一気に大変になります。が、ちゃんとしたものを作る気は最初からないので、ごまかせる範囲で適当に作ります。手抜きばんざいです。
(lambda (x y) (+ x y))
は
when :lambda putnil call :proc, 0, block(arg[0]) { scm_compile arg[1] leave }
無名関数はこんな感じでprocオブジェクトにするのが自然ですかね。
さてこうすると、ブロックローカル変数はgetlocalではなくgetdynamic命令でアクセスする必要があるので、変数アクセス式のコンパイルに手を加えないといけないです。
when Symbol if @type==:block && @vars.include?(s) getdynamic s else getlocal s end
変数の管理とか全然やってないので、yasmから即手に入る情報でごまかします。この実装だとネストしたブロックローカル変数にはさわれません。
あと、lambdaを入れる以上、関数を関数名以外で呼び出せないとダメですね。これも適当にごまかして
if Array===op || @vars.include?(op) scm_compile op arg.each{|a| scm_compile a} send :call, arg.size else if tailpos && op.to_s==@name ... else ... end end
こんな感じでProc#callにコンパイルします。
scheme <<EOS (define (map f x) (if (nil? x) (list) (cons (f (car x)) (map f (cdr x))))) EOS scheme "(p (map (lambda (x) (+ x 1)) (list 1 2 3)))" # ==> [2, [3, [4, nil]]]
こんなもんで。
