ちょびっと Scheme

上記の広告は１ヶ月以上更新のないブログに表示されています。新しい記事を書く事で広告が消せます。

最近、仕事が忙しくてなかなか macro の実装に手をだせない
そういえば syntax-rules を cl で実装した mbe とかいうのがあるらしいんで読んで見る。

前回からの続きで syntax-case を実装しようとしているところだけど、syntax-case って何者なの？
bc-syntax-case.pdf（書籍 ビューティフルコード に日本語訳有） を読んだ限りではsyntax-case は syntax-object を受け取ってパターンマッチを行い、それぞれの要素に分解するっていう理解でいいのかな？

s式 => syntax-object => syntax-case => 分解 => syntax => 再構築 => syntax-object

見たいな感じ？違うかな。

まずは syntax-object の実装から srfi-9 の record を使ってみる。

(define-record-type syntax-object
  (make-syntax-object expr wrap) syntax-object?
  (expr syntax-object-expr)
  (wrap syntax-object-wrap))

syntax-case を実装するのに syntax-pair? syntax-car 等が必要になるらしいのでそれを定義、ついでにidentifier?も定義。

(define (syntax-predicate pred)
  (lambda (x) (pred (syntax-object-expr x))))

(define identifier?  (syntax-predicate symbol?))
(define syntax-null? (syntax-predicate null?))
(define syntax-pair? (syntax-predicate pair?))

(define (syntax-car x)
  (extend-wrap (syntax-object-wrap x) (car (syntax-object-expr x))))

(define (syntax-cdr x)
  (extend-wrap (syntax-object-wrap x) (cdr (syntax-object-expr x))))

それから wrap と env の操作を実装しているんだけど、どうも id -> label -> binding の関連付けが重要っぽい。
ちょっと考えをまとめてみよう。

なんとか byte-code を出力することが出来るようになった。

ついでにライブラリも揃えようとしたところ、今の compiler には let すらないことを思い出した。
本格的なプログラムを書くには let や cond, and, or 等々がやっぱり欲しい。

ということでマクロの実装について学んでみた。

r6rs のマクロの章を読み進めると identifier とか mark、wrap 等のワードがでてくる。これは何？
ってことで bc-syntax-case.pdf を読んでみる。
それにしても Kent Dybvig さんはスゴイな、よくこんな複雑なシステムをこれだけのページ数にまとめられるなー。
でもこれ syntax-case がないと実装できなくね！？
次は syntax-case の実装から始めてみますか。。。

archive/20081006.zip

literal と bytecode を保持する 順序付き集合 orderd-set を定義してみた。

(define (make-orderd-set)
  (cons 0 '()))

(define (orderd-set-lookup datum orderd-set)
  (cond
    ((assv datum (cdr orderd-set)) => cdr)
    (else
     (let ((c (car orderd-set)))
       (set-car! orderd-set (+ c 1))
       (set-cdr! orderd-set (cons (cons datum c) (cdr orderd-set)))
       c))))

(define (orderd-set->vector orderd-set)
  (let ((vec (make-vector (car orderd-set) #f)))
    (for-each (lambda (pair)
      (vector-set! vec (cdr pair) (car pair)))
      (cdr orderd-set))
  vec))

次のステップとして C で vm を書いてみることにする。

C で書かれた vm にコードを実行させるのに 今の symbol をオペレータにした list の体系では扱いづらいので、switch で判断できるようコードを変換するようにした。

具体的にはとりあえず byte-code を以下のような構造にしてみた。たぶんあまり効率はよくない。

'(#(op ...) #(bytecode ...) #(literal ...)) 

op は halt, refer ...とかのオペレータを数値に置き換えたもの。
bytecode は上記の構造そのもの。close オペレータで使用される。
literal は コード中の symbol string 等のインスタンスを集めたもの。

C での vm 関数(妄想)

void VM(scheme_vm *vm)
{
    for (;;)
    {
        switch (*vm->x++)
        {
            case HALT:
                return;
            case CONSTANT:
                vm->a = vm->literal[*vm->x++];
                break;
            ...
            case CLOSE:
                vm->a = close(vm->bytecode[*vm->x++]);
                break;
            ...
        }
    }
}

とりあえずこれで進めてみることにする。