C#でSchemeを作ってみた

S式をコンパイルしてVMで実行するタイプ。末尾再帰最適化あり。call/ccあり。syntax-rulesあり（一部。もちろんhygienic
）。これも去年ごろ製作したものを諸般の事情により公開。
評価機はhttp://www.cs.indiana.edu/~dyb/papers/3imp.pdfを参考にした。

できること

(+ 1 2)
 => 3

(define (add x y) (+ x y))
(add 10 20)
 => 30

(define x "global")
(define f  (let ((x "local"))(lambda () x))))
(f)
 => "local"

(let ((counter 0)) (set! incr (lambda () (set! counter (+ 1 counter)) counter)))
(incr)
 => 1
(incr)
 => 2

(+ 10 (call/cc (lambda (c) (set! cont c) 10)))
 => 20
(cont 10)
 => 20

(define (tarai x y z)
    (if (<= x y)
      y
      (tarai (tarai (- x 1) y z)
         (tarai (- y 1) z x)
         (tarai (- z 1) x y))))
(tarai 10 5 0)
 => 10 ;;遅い

;;syntax-rules
(define-syntax cond
         (syntax-rules (else =>)
               ((cond (else result1 result2 ...))
                (begin result1 result2 ...))
               ((cond (test => result))
                (let ((temp test))
                (if temp (result temp))))
               ((cond (test => result) clause1 clause2 ...)
                (let ((temp test))
                (if temp
                  (result temp)
                  (cond clause1 clause2 ...))))
               ((cond (test)) test)
               ((cond (test) clause1 clause2 ...)
                (let ((temp test))
                (if temp
                  temp
                  (cond clause1 clause2 ...))))
               ((cond (test result1 result2 ...))
                (if test (begin result1 result2 ...)))
               ((cond (test result1 result2 ...) clause1 clause2 ...)
                (if test
                  (begin result1 result2 ...)
                (cond clause1 clause2 ...)))))
(define-syntax
 let (syntax-rules ()
           ((_ ((var val) ...) body ...)
             ((lambda (var ...) body ...) val ...))
           ((_ name ((var val) ...) body ...)
          ((letrec ((name (lambda (var ...) body ...))) name)
           val ...)))) 
;;とかが通る。

VMのコードはこんなかんじ

;;x
(refer-global x)
(halt)

;;(f 1 2 3)
(new-frame) {
  (const 3)
  (push-param)
  (const 2)
  (push-param)
  (const 1)
  (push-param)
  (refer-global f)
  (apply)
}
(halt)

評価の過程はやや複雑で、S式→マクロを展開しながらパースして中間言語に変換→さらにそれをコンパイルしてVMの命令列を得るようになっています。今思えば中間表現もS式で済む話だったのだけれど。

コンソールに出力されているのは中間表現。display-assemblyプロシージャでVMの命令列が見えます。

> (define (f x) (let ((hoge 1)) (+ x hoge)))
expand-macro result:
define f Lambda ( x) {
    Apply {
        target:
        Lambda ( hoge) {
            Apply {
                target:
                GlobalBinding +
                params:
                LocalBinding x(level:0,index:0)
                LocalBinding hoge(level:1,index:0)
            }
        }
        params:
        Const 1
    }
}


eval result:
#<closure>

> (display-assembly '(define (f x) (let ((hoge 1)) (+ x hoge))))
expand-macro result:
Apply {
    target:
    GlobalBinding display-assembly
    params:
    Const (define (f x) (let ((hoge 1)) (+ x hoge)))
}

eval result:
(create-closure ( x) <
(clear-args)
(const 1)
(push-param)
(create-closure ( hoge) <
(clear-args)
(refer-local hoge(1 0) )
(push-param)
(refer-local x(0 0) )
(push-param)
(refer-global +)
(apply)
>)
(apply)
>)
(define f)
(halt)

ダウンロード

現在ファイルサーバが死亡しています。近日中にソースをcodereposにupする予定はあります。(2008.02.18)
→ソースを紛失しました、なんてこったい。おれの青春が…… (20090506)
jsで実装したSchemeというのもつくりました、興味があるかたはどうぞ。