`(Hello ,world)

ツッコミ、添削大歓迎です。いろいろ教えてください。

2008-04-09

クロージャが参照する値

00:38

NekoVM のドキュメントを読んでいて、Function Scope に、ローカルスコープで参照する変数の値は関数が定義された時点での値になる、なので定義された後に変数を書き換えても値は変わらない、と書いてある。あれ?Lispもそうなの?と思ってテスト:

(let ((x 3))
  (let ((f (lambda ()
             (print x))))
    (setq x 4)
    (funcall f)))

4 
4

やっぱり違うよな。Nekoだと変数の値がコピーされてしまうので、クロージャ内から外の環境の変数を書き換えることはできない、ってことかな?

継続フェスタ

09:08

no title

この豪華メンバーで、この内容で、しかも無料と聞いては、行かざるをえない。

バイトコンパイル

08:46

Lisp のソースをVM形式にコンパイルしたいんだけど、既存のソースは大きくて読むのがおっかない…SECDの説明をみてもさっぱりわからん…。そんな軟弱な俺の唯一のよりどころ、RubyでSchemeを作ってみたよ今度こそ。 - <s>gnarl,</s>技術メモ”’<marquee><textarea>¥を見て作り始めてみた。

コンパイル本体
(defun compile (s nxt)
  (cond ((consp s)   (comp-list s nxt))
        ((symbolp s) (comp-symbol s nxt))
        (t           (comp-const s nxt))))

nxt には続く処理をバイトコンパイルしたものを渡します。継続みたいなもん。

定数
(defun comp-const (s nxt)
  (append `(:const ,s) nxt))

「:const 値」の形

シンボル
(defun comp-symbol (s nxt)
  (append `(:refer ,s) nxt))

「:refer シンボル」の形。環境の何番目の値か、というインデクスには畳んでないです。

リストのコンパイル
(defun comp-list (s nxt)
  (case (car s)
    ; スペシャルフォーム
    (if        (comp-if s nxt))
    (quote     (comp-quote s nxt))
    ; 普通の関数呼び出し
    (otherwise (comp-apply s nxt))))

関数呼び出し/マクロ/スペシャルフォームを埋め込みでコンパイルしてます。するつもりです。

if式
(defun comp-if (s nxt)
  (let ((pred (cadr s))
        (th (compile (caddr s) nxt))
        (el (compile (cadddr s) nxt)))
    (compile pred (list :test th el))))

条件式が真の場合と偽の場合のコードを生成して、条件式により分岐するコード「:test th el」を生成。else 節になにも与えなかった場合、(compile nil nxt) → (:refer nil) になります。

クォート式
(defun comp-quote (s nxt)
  (append `(:const ,(cadr s)) nxt))

定数と同じ。

関数呼び出し

未実装

(defun comp-apply (s nxt)
  "not implemented")

とりあえずここまで。テストしてみる:

> (compile '(if 1 'hello 'world) nil)
(:const 1 :test (:const hello) (:const world))

こんな感じで、バイトコードがS式で吐き出される。


VM実装

S, E, C, D を与えてもらって、一命令実行して、次の状態を返す。

(defun step-vm (stack env code dump)
  (case (car code)
    (:const (let ((v (cadr code)))
              (values (cons v stack) env (cddr code) dump)))
    (:refer (let ((v (lookup (cadr code) env)))
              (values (cons v stack) env (cddr code) dump)))
    (:test  (let ((pred (car stack))
                  (th (cadr code))
                  (el (caddr code)))
              (values (cdr stack) env (if pred th el) dump)))
    ))
シンボルの参照
(defun lookup (symb env)
  (let ((a (assoc symb env)))
    (if (null a)
        nil
      (cdr a))))

環境は、とりあえず単一の alist としてます。親環境をたどるのはまたあとで。

実行
(defun run-vm (code)
  (let ((stack '())
        (env   '())
        (dump  '()))
    (while (not (null code))
      (print code)
      (multiple-value-setq (stack env code dump)
        (step-vm stack env code dump)))
    (car stack)))

ひとまずテストでコードの内容を表示してます。step-vm からの多値の戻り値を multiple-value-setq で受け取る。コードが空になったらスタックの先頭を返す。副作用上等。

実行結果
> (run-vm
   (compile '(if 1 'hello 'world) nil))

(:const 1 :test (:const hello) (:const world)) 
(:test (:const hello) (:const world)) 
(:const hello) 
hello
トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20080409