alexpanderを読む

nmosh

expanderのインターフェースを検討するために、既存のexpanderを改造してライブラリ対応にしてみることにした。
nmoshのbootstrapにはR5RSが必要なので、alexpanderを使用している。

alexpanderは、マクロを使用せずにR5RSのexpander(要するにsyntax-rulesとかquasiquote等)を実装していて、これがnmoshのexpanderをexpandするのに十分な機能を持っている。
今回は、これを改造してR6RSのライブラリシステムを乗せてみることにする。

ロードと実行

まずは、素のalexpanderをロードしてみる。nmoshのREPLにはloadがあるのでそれを使用する。

oku@cage ~/alexpander
$ nmosh
nmosh top program
nmosh> (load "alexpander.scm")
#<unspecified>

ここでロードするalexpanderはnmoshのものでないといけない。元の配布( http://petrofsky.org/src/alexpander.scm )は余計な定義があるので失敗する。
試しにalexpander自身をexpandしてみる。alexpanderはこのために使用できるexpand-program手続きを定義する。

nmosh> (import (mosh pp) (yuni util files))
nmosh> (pp (expand-program (file->sexp-list "alexpander.scm")))
((define _eqv?_17 eqv?)
 (define _cons_31 cons)
 (define _append_32 append)
 (define _list_33 list)
 (define _vector_34 vector)
 (define _list->vector_35 list->vector)
 (define _map_36 map)
 (define
   ERROR
   (lambda e (error "err from alexpander" e)))
 (define
   sid?
   (lambda
     (sexp)
     ((lambda (x) (if x x (renamed-sid? sexp)))
      (symbol? sexp))))

alexpanderの要素

alexpanderのコア言語はbuiltinと呼ばれ、(begin define define-syntax if lambda quote set! delay let-syntax syntax-rules)の10定義が存在する。
expanderの実装する言語要素は"null-environment"と呼ばれる。これはR5RSがそう呼んでいるからで、nullといっても一切定義が無いというわけではない。null-environmentは純粋にsyntax-rulesで書かれているか、alexpanderの内部構造を利用して書かれていることも有る。
alexpanderにおける名前空間はstoreと呼ばれる。library対応にあたっては、このstoreの入出力がキモとなる。

nmosh> (import (mosh pp))
nmosh> (pp builtins-store)
((syntax-rules . syntax-rules) ;; builtinsは単純なシンボル→シンボルマップとなる
 (let-syntax . let-syntax)
  :
nmosh> (pp null-store)
((quasiquote
   (syntax-rules
     ()
     ((_ template) (let () (qq template () template))))
   ((qq . 39) (let . 30)))
 (36 . #(map 36))
 (35 . #(list->vector 35)) ;; rename後の名前はintegerになる
 (34 . #(vector 34))
 (33 . #(list 33))
 (32 . #(append 32))
 (31 . #(cons 31))
 (37
  (syntax-rules
    ()
    ((_ template) (let () (qq template () template))))
  ((qq . 39) (let . 30)))
 :

コア言語はbuiltins-storeに格納され、R5RS null environmentはnull-storeに格納される。これらは、現状のalexpanderではexpandの際にimplicitにimportされる。
これらのフォーマットは、alexpander.scmに説明がある

;; env: ((id . local-location) ...)
;; store: ((location . val) ...)
;; location: toplevel-location | local-location ;; a.k.a. symloc and intloc.
;; toplevel-location: symbol
;; local-location: integer
;; val: variable | syntax | code
;; variable: #(toplevel-location) | #(symbol local-location)
;; code: (output) ; output is the expanded code for an expression.
;; syntax: builtin | transformer
;; builtin: symbol
;; transformer: (synrules env)
;; synrules: the unaltered sexp of the syntax-rules form.

alexpanderはR5RSなので、transformerにはsyntax-rulesしか存在しない。

ライブラリをexpandするために

プログラムのexpandとライブラリのexpandで異なるのは、ライブラリのexpandではマクロのexpand結果も必要という点になる。プログラムをexpandする場合は、そのプログラム中で定義されたマクロは捨ててしまって構わない。alexpanderでこれを実現するためには、expand後のstoreの内容をキャプチャする必要がある。alexpanderは、builtins-storeからnull-storeを作るために既にこれを行っているので、これを行うAPIを提供すれば良い。

;; null-prog is the preamble that defines all the standard macros that
;; are in the null-store. (The "null-" name prefix was chosen to
;; correspond to the name of r5rs's null-environment procedure, even
;; though the null-store is far from empty.)
(define null-prog
  '((define-syntax letrec-syntax
      (let-syntax ((let-syntax let-syntax) (define-syntax define-syntax))
        (syntax-rules ()
         ((_ ((kw init) ...) . body)
         (let-syntax ()
         (define-syntax kw init) ... (let-syntax () . body))))))
- snip -
;; ここのexpand-top-level-formsでbuiltins-storeをimportしてnull-stuffを作る。
(define null-stuff (expand-top-level-forms null-prog builtins-store 0 list))
(define null-output (car null-stuff))
(define null-store (cadr null-stuff))
(define null-loc-n (caddr null-stuff))