ギリギリまでsyntax-rulesを使ってexpanderを書けないか問題

nmosh

追記: $quoteの定義を修正。($quote syms ...) => (syms ...)だとシンボル単体のquoteができない。なので($quote (syms ...)) => (syms ...)。

目的

目下、R6RS/R7RSライブラリであるyuni( https://github.com/okuoku/yuni )をR5RSであるGambitに移植しようとしている。なので用語のマッピングは以下のようになる:

  • フロントエンド、expander = R6RS/R7RSで書かれた、R6RS/R7RS → R5RSプログラムへのトランスレータ(R5RSにはモジュールシステムが無いため、複数のライブラリファイルを1本のプログラムに合成する必要がある。前回参照。)
  • バックエンド、コンパイラ = Gambit

もっとも、yuniにおいて移植性は非常に重要なので、Gambit以外へのリターゲットが容易であることを重視している。

処理系実装におけるマクロの利用

Schemeのバックエンド、要するにコンパイラは、だいたい低レベルマクロシステムの上に構築されている。例えば、vanilla-moshではwhenのような構文は

(case (car form) 
      ...
      [(when)
       (match sexp
         [('when pred body . more)
          ($src (pass1/expand `(cond (,pred ,body ,@more))) sexp)]
         [else
          (syntax-error "malformed when")])])

のように、低レベルマクロによってcondに変換されている。
上記のような単純なwhen → cond変換であれば、syntax-rulesを使って、

(define-syntax when
  (syntax-rules ()
    ((_ pred body . more)
     (cond (pred body . more)))))

のように書ける。
このような変換を積み重ねていくことで、バックエンドとなるSchemeコンパイラがサポートしなければならない構文をギリギリまで減らすことができる。例えば、let構文は

(define-syntax let
  (syntax-rules ()
    ((_ ((var frm) ...) body ...)
     ((lambda (var ...) body ...) frm ...))))

のようにすればSchemeコンパイラはletの実装をサボることができる。(ただし、これはいわゆる"名前付きlet"をサポートしていない。もっと完全なものは R7RSの7.3節に沢山載っている。)
これを突きつめて、Scheme処理系の可能な限り多くの部分をsyntax-rulesによって記述するために必要なプリミティブは何かというのを考察したい。これができれば、文法チェックの殆どをsyntax-rulesのルールとして行うことができ、expanderをコンパイラの実装者がカスタマイズする上でも読みやすいものになるのではないだろうか。

課題: コンパイラのサポートするscheme構文をexpanderに持ち込むにはどうすれば良いか？

上記のletのように、letをlambdaに変換してしまうとSchemeコンパイラによっては非効率なコードを生成してしまう可能性がある。letは本来クロージャを生成する必要は無いが、lambdaはクロージャを生成してしまうため、余計なオブジェクトを生成する余地がある。
このため、expanderが効率的なコードを生成するためにはコンパイラのサポートするScheme構文を可能な限り多く"expanderの世界"に持ち込む必要がある。

低レベルビルディングブロック: $inject 構文と $extend-env 補助構文

まず、バックエンドのサポートするScheme構文は必ず元の名前で出力する必要がある。これを示すために$inject構文を導入する。例えば、バックエンドがwhenをサポートしている場合、フロントエンドでのwhenの宣言は以下のように行える:

;; ($inject <SYMBOL> body ...)
;;   => (<SYMBOL> body ...)

(define-syntax when
  (syntax-rules ()
    ((_ arg body ...)
     ($inject when arg body ...))))

$injectでは、指定されたシンボルはそのままバックエンドに出力されるが、残り(上記の例ではarg body ...)はsyntax-rulesの置換の影響を受ける。
lambdaのように、変数を定義することで環境を"拡張"する構文は、expanderにそれを伝える必要がある。この目的のために、$injectの補助構文$extend-envを導入する。

;; $extend-envは環境を拡張し、bodyをspliceする
;; ($extend-env (var ...) body ...)
;;   => body ... ただしvar ...を既知の変数として展開する
(define-syntax lambda
  (syntax-rules ()
    ((_ frm body ...)
     ($inject lambda
              ($extend-env frm body ...)))))

可視タイミングの制御: $bind-variable補助構文

$injectと$extend-envを導入することで、letrecは以下のように宣言できる:

(define-syntax letrec
  (syntax-rules ()
    ((_ ((var frm) ...) body ...)
     ($inject letrec
              ($extend-env (var ...)
                           ((var frm) ...)
                           body ...)))))

しかし、let構文は$extend-envを使用して宣言できない:

;; エラーのあるlet
(let ((a 10)
      (b (+ a 10))) ;; ← エラー！ aはこの行では不可視のはず
 b)

;; ↓ 先のletrecの定義を使用して$injectに展開
($inject let
         ($extend-env (a b) ;; ← ここで a b を可視に
                      ((a 10)
                       (b (+ a 10))) ;; ← a b 共に可視なのでエラーに見えない！
                      b))

このため、可視タイミングを制御する$bind-variable補助構文を導入する。

;; ($bind-variable var)
;;  => var ただし、環境に変数を追加するが、後続の$extend-envまで不可視状態にする
(define-syntax let
  (syntax-rules ()
    ((_ ((var frm) ...) body ...)
     ($inject let
              ((($bind-variable var) frm) ...)
              ($extend-env (var ...)
                           body ...)))))

;; ↓先程の例を$injectに展開
($inject let
         ((($bind-variable a) 10)
          (($bind-variable b) (+ a 10))) ;; ← ここでは a は不可視。エラー。
         ($extend-env (a b)
                      b))

$bind-variableされていない変数が$extend-envに表われた場合は、暗黙に$bind-variableし直後に可視状態にする。

defineへの対応: $bind-definition補助構文

今迄の例は全て変数のスコープが$inject記述に閉じていたが、Schemeのdefine構文では特殊なスコープを持つ変数を宣言することができる。このため、専用の補助構文を用意して対応する必要がある。

;; ($bind-definition var)
;;  => var ただし、変数にdefine相当のスコープを与える
(define-syntax define
  (syntax-rules ()
    ((_ nam obj)
     ($inject define
              ($bind-definition nam)
              ($extend-env nam obj)))))

$bind-definitionでは、それが書かれた$injectの親をスコープとする変数を定義する。宣言された変数はそれが書かれた$injectを抜けると可視となる。

低レベル補助構文: $quote

今迄の補助構文でR7RS schemeのbinding constructsは大体対応できるが、それ以外の構文の中には対応できないものもある。
例えば、case構文の宣言には、ソースに書かれたdatumをそのまま挿入する$quote補助構文が必要となる。

(define-syntax case
  (syntax-rules (else)
    ((_ ((syms ...) body ...) ... (else else-body ...))
     ($inject case
              (($quote (syms ...)) body ...) ;; ← 仮にsymsが既知の変数と一致したとしてもリネームしてはいけない
              ...
              (else else-body ...)))
    ((_ ((syms ...) body ...) ...)
     ($inject case
              (($quote (syms ...)) body ...)
              ...))))

例えばバックエンドのdefine-record-typeを直接活用したいようなケースでは他にも追加の考察が必要になるかもしれない。

既存の低レベルマクロとの比較

今回の$injectはexpanderの保持している環境を直接制御することを目的としているため、既存の低レベルマクロシステムとは良く対応しない。この表における"なし"は不要の意味とも言える。

今回の$injectマクロ syntax-case er-macro
$inject datum→syntax rename
$extend-env なし なし
$bind-variable なし なし
$bind-definition なし なし
$quote syntax→datum なし

hookポイントとして考えると興味深いかもしれない。つまり、expanderによってリネームされる可能性のあるシンボルは全て$bind-*か$extend-envで囲まれていることになるため、これらの出現箇所を記録することでプログラム中に宣言された変数を収集することができる。
explicit renaming macroなど構造を持たない低レベルマクロシステムで書かれたマクロを$injectを使ってアノテートすることで、マクロがどのような変数をbindしたのかを明示的に示すことができる。例えばドキュメンテーション用のstubや構文強調のためのメタデータとして使用できるかもしれない。