alexpander

alexpander*1が、r5rsのsyntax-rulesを展開する*2らしいので、組み込んでみた。

let alexpand sexps =
  let defs = parseDefs (sexps_from "lib/alexpander.scm")
  and primis = ge Eval.eval_apply in
  let env = Eval.extendletrec primis defs in
  let expandproc = List.assoc "expand-program" defs in
  let expand = ApplyExp (expandproc, [QuoteExp (List sexps)]) in
  let x = Eval.evalExp env expand in
  match val_to_sexp x with
    List s -> s

対話環境でテストする。

# let ae = alexpand (sparse_top 
"(let-syntax ((when (syntax-rules ()
                     ((when test stmt1 stmt2 ...)
                      (if test (begin stmt1 stmt2 ...))))))
    (when 'x 'a 'b 'c))");;
val ae : Syntax.sexp list =
  [List [Id "define"; Id "_eqv?_17"; Id "eqv?"];
   List [Id "define"; Id "_cons_31"; Id "cons"];
   List [Id "define"; Id "_append_32"; Id "append"];
   List [Id "define"; Id "_list_33"; Id "list"];
   List [Id "define"; Id "_vector_34"; Id "vector"];
   List [Id "define"; Id "_list->vector_35"; Id "list->vector"];
   List [Id "define"; Id "_map_36"; Id "map"];
   List
    [Id "if"; List [Id "quote"; Id "x"];
     List
      [Id "begin"; List [Id "quote"; Id "a"]; List [Id "quote"; Id "b"];
       List [Id "quote"; Id "c"]]]]
# eval_body (parseBody ae);;
- : Parser.exp Valtype.valtype = SymbolV "c"

自身の評価器でalexpanderのexpand-programを評価してs式を展開させ、展開されたs式を評価する。

caseとlet*

case syntaxとlet* syntaxに対応した。
パーサにparseLetstarとparseCaseを追加した。
対話環境でテストしてみる。

# let e1 = parse "(case (* 2 3)
     ((2 3 5 7) 'prime)
     ((1 4 6 8 9) 'composit))";;
val e1 : Parser.exp =
  IfExp
   (ApplyExp (VarExp "memv",
     [ApplyExp (VarExp "*", [SelfEvalExp (Int 2); SelfEvalExp (Int 3)]);
      QuoteExp (List [Int 2; Int 3; Int 5; Int 7])]),
   QuoteExp (Id "prime"),
   IfExp
    (ApplyExp (VarExp "memv",
      [ApplyExp (VarExp "*", [SelfEvalExp (Int 2); SelfEvalExp (Int 3)]);
       QuoteExp (List [Int 1; Int 4; Int 6; Int 8; Int 9])]),
    QuoteExp (Id "composit"), UnspecifiedExp))
# evalExp env e1;;
- : Parser.exp Valtype.valtype = SymbolV "composit"

# let e2 = parse "(let* ((x 7) (z (+ x 3)))
    (* z x))";;
val e2 : Parser.exp =
  ApplyExp
   (LambdaExp (["x"], Fixed,
     ApplyExp
      (LambdaExp (["z"], Fixed,
        ApplyExp
         (LambdaExp ([], Fixed,
           ApplyExp (VarExp "*", [VarExp "z"; VarExp "x"])),
         [])),
      [ApplyExp (VarExp "+", [VarExp "x"; SelfEvalExp (Int 3)])])),
   [SelfEvalExp (Int 7)])
# evalExp env e2;;
- : Parser.exp Valtype.valtype = IntV 70

展開していて結果もそれなりであるが、caseでは (* 2 3) が何回も評価されている。r7rsの else => にも未対応。
伝統的なマクロが動くのでschemeで書いてもいいのだが、外部ファイルを読み込むデザインは保留しているので、当面はパーサにOCamlでハードコードする。

ベクタリテラル、文字リテラル

今まで対応していなかった、ベクタと文字のリテラルに対応した。
s式パーサとレキサを修正。r7rsによると、`#( は、トークンである。

sparser.mly

Sexp :

  | CHARV { Char $1 }

  | SHARPLPAREN Sexplist RPAREN { Vector $2 }

対話環境でテストしてみる。

# let a = sparse "#\\a";;
val a : Syntax.sexp = Char 'a'
# evalExp [] (parseExp a);;
- : Parser.exp Valtype.valtype = CharV 'a'
# let asd = sparse "#(a s d)";;
val asd : Syntax.sexp = Vector [Id "a"; Id "s"; Id "d"]
# evalExp [] (parseExp asd);;
- : Parser.exp Valtype.valtype =
VectorV [|SymbolV "a"; SymbolV "s"; SymbolV "d"|]

ベクタはs式としてはOCamlのリストで表現しているが、評価後の値の型はOCamlの配列を使っている。
文字のヘキサ表現、文字名表現には対応できていない。

ベクタ関連のライブラリ関数も追加した。

伝統的マクロ

quasiquoteが動いたので、伝統的マクロを実装してみた。展開して評価できるところまで動いた。

evalExpのパターンマッチにMacroAppExp節を追加。

let rec evalExp env = function

  | MacroAppExp (id, sexps) ->
     let args = List.map evalQuote sexps
     and m = !(lookup id env) in
     let s = eval_apply m args in
     evalExp env (parseExp (val_to_sexp s))

マクロの中のマクロ呼び出しは、evalExpの中で再帰的に展開している。
マクロ展開は一回だけ実行するように変更するには、パーサと評価部や環境との依存関係にかなり影響がありそうである。

quasiquote続き

やはりテストケースに漏れがあった。ネストとdotted list表記の組み合わせでおかしな結果になっていた。

(define (qq7-6 name1)
  `(a b . `,,name1))

(qq7-6 'x)  =>  (a b a b quasiquote ,x)

では期待結果はなにか、ということで調べてみると、微妙なことになっている。

Gauche
gosh> `(a b . `,,'x)
*** ERROR: Compile Error: unquote appeared outside quasiquote: ,'x

Racket
> `(a b . `,,'x)
(a b quasiquote ,x)

果たして外なのか、内なのか。
これは

(quasiquote (a b quasiquote (unquote (unquote (quote x)))))

なので、2番目のリストの先頭ではないquasiquoteをどう解釈するか、ネストレベルを増やすか、そのままかの違いだと思われる。
unquoteについては、リストの先頭でないunquoteもリストの先頭のunquoteと同様に機能して、ネストレベルが減少するようである。R7RSではサンプルで

`((foo ,(- 10 3)) ,@(cdr '(c)) . ,(car '(cons)))  =>  ((foo 7) . cons) 

と記述している。quasiquoteも同じように解釈せよとうことかしらん。

quasiquote

quasiquoteがなんとか動いた。

quasiquoteのネストレベルの増減をどう追跡すべきかは初期段階で明白ではなかった。

dot表記が混じった場合、

`((foo ,(- 10 3)) ,@(cdr '(c)) . ,(car '(cons)))

現状のs式パーサが (a b . (unquote x)) を (a b unquote x) (OCaml的には、[a; b; unquote; x])としてしまうため、unquoteがリストの先頭にあるパターンではマッチしなかった。

unquote-splicingがリストの最後の場合、xがリストに評価されなくてもエラーではない。*1

> (define (qq13 x)
  `(foo ,@x))
> (qq13 '(a b c))
(foo a b c)
> (qq13 'a)
(foo . a)

> (define (qq14 x)
  `(,@x))
> (qq14 '(a b c))
(a b c)
> (qq14 'a)
a

これをfixするのに手間取った。

quasiquoteは派生で定義できるようなので、調査するかな。

*1:Racketのドキュメントに記述とサンプルがある http://docs.racket-lang.org/reference/quasiquote.html?q=quasiquote

最近の変更点

勉強を再開してからの主な変更点

sicp 4.1.7のanalyze評価器
valtype/envがeval評価器とanalyze評価器それぞれに存在したのを共通化 *
primitiveを、新しいvaltype/envに対応させて、個別に存在したのを共通化 
S式コメント (srfi 62)
delay/force primitiveな実装
dotted list notation対応
その帰結として、可変長引数対応
自動テスト
do syntax
内部定義をletrecの派生とする

* 修正のためバリアントのtype定義に型変数を入れたところコンパイルできなくなった。

 This expression has type
         'a proctype = 'a Valtype.env -> 'a Valtype.valtype
       but an expression was expected of type 'a
       The type variable 'a occurs inside
       'a Valtype.env -> 'a Valtype.valtype

検索してみると、 -rectypesオプションがあるらしく、回避できた。
なぜ回避できたかは追及していないが..