SECDV Schemeを実装する - VMとcore schemeコンパイラ

というわけで今月集中して取り組んでいるSECDV Schemeの制作。前回はVM命令セットを考えた( http://d.hatena.ne.jp/mjt/20170512/p1 )。

次回予告

とりあえずVMとcore scheme コンパイラが揃ったので、次は:

Alexpanderと統合してyuniのR6RS-lite形式プログラムを動かせるようにする
Scheme-on-Scheme構成でyuniのテストを一通り通す

のを目標に。GambitやMIT-Scheme向けにR5RS環境でyuniのプログラムを動かすのは一定の実績があり、R5RS構文の殆どはsyntax-rulesが有れば記述可能。手続きに関しては単純にホストのScheme手続きを呼び出せば良い。Alexpanderは信頼できるSyntax-rules実装で、syntax-rulesを使ったR5RSコードを限定的な構文のみを使用したSchemeに展開することができる。
(R6RS-lite形式とは、yuniが採用しているライブラリフォーマットで、要するに"必要最低限の変換でR7RS処理系でもロードできるR6RS形式ライブラリ"。R7RSのライブラリ形式には余計な機能が多いためR6RS形式を採用している。)
これらが完了したら以前考えた"BASICでも実装できるSchemeヒープ"( http://d.hatena.ne.jp/mjt/20160828/p1 )をScheme上で実装し、consとかcarのような手続きを実装したヒープ上で動作させるようにする。
重要なポイントは、yuniライブラリにSECDV VMとそのコンパイラを含めている点で、評価器に手を入れないと実現しづらい機構 -- 例えばカバレッジ計測ツールやデバッガ等 -- を移植性を保ったまま実装できると期待している。yuniは移植性ライブラリとして多くのScheme処理系をサポートしているが、意外と"Racketでないと再現しないバグ"みたいなのが多く、Racketのようにリッチなデバッガを持った処理系ならともかくとしてchibi-schemeのようなシンプルなSchemeではステップ実行やブレークポイントが処理できるだけでも便利、な、はず。。

VM

今回、VMはVM命令列を解釈するシーケンサと、レジスタを持ちVM命令を実際に実行するステートマシンに分割した。このようなフロントエンド/バックエンド分割はCPU設計などでも良く出てくるが、VM命令形式に依存しない部分を切り出すことで、VM命令形式ごとにVMを再実装する必要の無いように配慮している。

今のところ、ライブラリはTreeIRと呼んでいるS式形式のVM命令列だけをサポートしている。
ラベルの表現形式はちょっと悩みどころだが、

命令列を入れ子化可能な"ブロック"に分割する
ジャンプ命令の飛び先は、ブロック先頭へのジャンプ(enter)とブロックからの脱出(break)の2通りが指定可能
ブロック末尾では暗黙にブロックから脱出する (fallthrough挙動: ブロック末尾には暗黙の (JMP (break 現在のブロック)) 命令が置かれる)

という仕様にした。実際のジャンプを実装するためには、一度命令列全体をスキャンし、飛び先を格納したベクタを構築する必要がある。

https://github.com/okuoku/yuni/blob/8866b365d61e0743be654ab90dfa22a3bfddb49f/lib/yunivm/vm/seq-treeir.sls#L128

  ; IR Tree walk helper
  (define (walk ir parent cb-block)
    (unless (null? ir)
      (let ((code (car ir)))
        (when (and (pair? code) (eq? 'block (car code))) ;; (block ...)に出会ったらコールバックする
          (cb-block code parent (cdr ir))
          (walk (cddr code) (cadr code) cb-block))
       (walk (cdr ir) parent cb-block))))

  ;; Pass1: Scan for max-blockindex and allocate vector
  (let ((max-blockno 0))
   (walk ir #f
         (lambda (block parent next)
           (let ((no (cadr block))) ;; no = ブロック番号
            (when (< max-blockno no)
              (set! max-blockno no)))))
   (let ((blockcount (+ 1 max-blockno)))
    (set! block-enters (make-vector blockcount #f))
    (set! block-breaks (make-vector blockcount #f))
    (set! block-siblings (make-vector blockcount #f))))
  ;; Pass2: Fill block pointers
  (walk ir #f
        (lambda (block parent next)
          (let ((no (cadr block))) ;; no = ブロック番号
           (vector-set! block-enters no (cddr block))
           (vector-set! block-breaks no next)
           (vector-set! block-siblings no parent))))

個々のblockは整数で識別される仕様としたので、pass1で最大のブロックID値を導出し、ブロックIDを格納するのに十分な長さのベクタを確保し、pass2でインデックスを構築し以下の3情報にO(1)でアクセスできるようにする。

block-enters: ラベル (enter ブロックID) の飛び先
block-breaks: ラベル (break ブロックID) の飛び先
block-siblings: ブロックの最後の要素の次の要素を含むブロックID

block-siblingsの必要性はあまり自明ではないが、TreeIRの構成上、現在実行しているブロックのブロックIDを知らないと"次の命令"の場所を特定できないため入れている。
別解としては、blockからの暗黙のfallthrough自体を禁止して"block末尾は必ずJMPやRETのような分岐命令で終わる"と約束すれば現在ブロックIDをトラックをする必要は無くなる。ただ、linearIRにアセンブルしたときに消滅する命令は必要最低限にしたかったため、今回のような構成を採用した。

コンパイラ

コンパイラ( https://github.com/okuoku/yuni/blob/8866b365d61e0743be654ab90dfa22a3bfddb49f/lib/yunivm/compiler/compilercore.sls )は。。急いで書いているとは言え酷いコードなのでどうにかしたいところ。。せめて命令生成ループは末尾再帰にしようぜ。。
コンパイラは関連性高いコードを近所に生成するようにしている。つまり、lambdaは

;; (lambda (a b c) a b c)

(block 0
       (LDF  (enter 1))
       (JMP  (break 0)) ;; Lambda式のbody部分を飛ばす
       (block 1
              (RECV 3)  ;; Frame (a b c)
              (LD  0 0) ;; Load  a
              (LD  0 1) ;; Load  b
              (LD  0 2) ;; Load  c (as V)
              (RET)))