オレ処理系の[Nendo]についての開発メモ。

chibi-schemeのsyntax-rulesをポーティングした時のメモ。 [Nendo] 0.5.1時点での実装を解説となっている。 以下の実装で、chibi-scheme 0.3のsyntax-rules関連のテストケースが通り、さらに、match.scmも修正無しでテストケースをパスしている。

背景

[Nendo]はRubyで書かれたScheme処理系である。サブセットではあるが。 syntax-rulesの処理は複雑で、自分で新しくコードを書くのはメンテが大変なので、できれば別の処理系で書かれたポータブルな実装を使いたい。 探した結果、chibi-schemeのsyntax-rulesがScheme自身で書かれたいて、機能的にもGaucheのライブラリを動かすのに十分であったため採用した。 ただ、ポータブルなSchemeで書かれているため、マクロ展開が重いという課題もあるが、[Nendo]ではマクロ展開の処理速度には重きを置かない方針なので、とにかく動かすことを最優先とした。

chibi-scheme 0.3のsyntax-rulesについて

chibi-schemeのsyntax-rulesは、explicit macro transformerを使って書かれている

(define-syntax syntax-rules
  (er-macro-transformer
   (lambda (expr rename compare)
     (let ((ellipsis-specified? (identifier? (cadr expr)))
           (count 0)
           (_er-macro-transformer (rename 'er-macro-transformer))
 .
 (略)
 .
 .

従って、er-macro-transformerが正しく動くことが必須となる。 但し、syntax-rulesが使われる場所は、define-syntaxとlet-syntaxのルール記述部分になるので、処理系には大域的syntaxと局所的syntaxのマクロ展開の機能が必要になる。 [Nendo]は伝統的マクロの展開とあわせて3種類のマクロ展開をサポートしている。 [Nendo]のマクロ展開エンジンはRubyで書かかれている。

syntaxのサポート

syntaxは、マクロ展開フェーズで実行される特別なプロシジャである。 処理系の都合で、lambdaで定義されたプロシジャとは別の特別な型が使われることが多いようだ。 Gaucheでは #という型が使われる。ユーザ定義関数は #となる。

$ gosh
gosh> if
#<syntax if>
gosh> (define (func1) #t)
func1
gosh> func1
#<closure func1>

Nendo(0.5.1)でも、それぞれ以下のように、それぞれNendo::LispSyntaxとProcという型が使われる。

$ nendo
nendo> syntax-rules
#<Nendo::LispSyntax:0x8d9b608@/usr/local/stow/..(略)../nendo.rb:23500>
nendo> (define (func1) #t)
#<Proc:0x8adf6e4@(stdin):9>
nendo> func1
#<Proc:0x8adf6e4@(stdin):9>

chibi-schemeでは、syntaxは構文エラーになってしまうがprocedureとは別ものとして扱われていることにはかわりない。

$ chibi-scheme
> if
ERROR: invalid use of syntax as value: if
> (define (func1) #t)
> func1
#<procedure func1>

これを実現するために、[Nendo]ではLispSyntaxという型をProcから継承して実装した。中身は空。

  class LispSyntax < Proc
  end

大域的syntaxのサポート

大域的syntaxはレキシカルスコープを意識しなくていいので、マクロ展開は非常に簡単だ。 例:

(define-syntax cut
  (syntax-rules () ((cut args ...) (%cut #f () () args ...))))

上のように cut というシンタックスが定義された場合、マクロ展開される時は常にトップレベル環境を使って展開すればいいので、レキシカル環境は気にしなくていい。

局所的syntaxのサポート

一方、let-syntaxを使って定義される局所的syntaxは、定義されたレキシカル環境の中でマクロ展開される必要がある。 R5RS日本語訳(PDF) 4.3.1. 構文キーワードのための束縛コンストラクト

(let-syntax <束縛部> <本体>) 構文: <束縛部> は次の形式をとること。 ((<キーワード> <変換子仕様>) … ) 各<キーワード> は識別子である。各<変換子仕様> はsyntax-rules のインス タンスである。<本体> は１個以上の式からなる列であること。束縛されるキー ワードの並びの中に一つの<キーワード> が複数回現れることはエラーである。 意味: let-syntax 式の構文環境をマクロで拡張することによって得られる構 文環境の中で，<本体> が展開される。ただし，それらのマクロはそれぞれ<キー ワード=""> をキーワードとし，仕様が規定する変換子に束縛されている。各<キー ワード=""> の束縛は<本体> をその領域とする。

(let-syntax ((when (syntax-rules ()
                     ((when test stmt1 stmt2 ...)
                      (if test
                          (begin stmt1
                                 stmt2 ...))))))
  (let ((if #t))
    (when if (set! if 'now))
    if))

=> now

(let ((x 'outer))
  (let-syntax ((m (syntax-rules () ((m) x))))
    (let ((x 'inner))
      (m))))

=> outer ※ これがinnerとなっては駄目

これを実現するには、let-syntax された syntax は let で束縛された変数も考慮した環境を保持する必要がある。

マクロ展開に求められる要件

上記の仕様を満たすマクロをRubyのようなレキシカル変数を持った言語にトランスレートするには次の要件を満たす必要がある。

• 要件 局所的syntaxが展開される場所でも、let-syntaxで定義された場所のレキシカル環境を擬似的に復元する必要がある。

• [Nendo]での実現方法とそのメリット マクロ展開エンジンはletとletrecで束縛されたレキシカル変数を全て抜き出しておいて、syntaxがRubyのメソッドとしてコンパイルされる時に、 レキシカル変数の環境をRubyのレキシカル変数の環境として復元する。

[Nendo]

(let ((x 'outer))
  (let-syntax ((m (syntax-rules () ((m) x))))
    (let ((x 'inner))
      (m))))

↓

Rubyでのマクロ展開中イメージ(説明のためかなり簡略化している)

# 新しいS式に変換するマクロ m
m = LispSyntax.new {|expr,use_env,mac_env|
  # let-syntaxの定義環境で expr の式を展開して返す
  # 外部の環境が m の内部の x に影響を与えない。
  _tmp = lambda {|x|   # マクロ定義の環境を再現(start)
    x
  } ; tmp( :outer )    # マクロ定義の環境を再現(end)
}

# マクロ展開フェーズで、callProcedure部分が展開される
_tmp = lambda {|x|
  _tmp = lambda {x|
    callProcedure ( m,
      Cell.new,    # mの引数
      [].to_list,  # use_envは常に空
      # mac_envはグローバル変数、ローカル変数の全シンボルリスト
      (global_variables() + local_variables()).to_list
    )
  }
  _tmp( :inner )
}
_tmp( :outer )

Rubyへのマクロ展開結果(説明のためかなり簡略化している)

マクロ展開フェーズで、callProcedure部分が展開される

_tmp = lambda {|x|
  _tmp = lambda {x|
    :outer
  }
  _tmp( :inner )
}
_tmp( :outer )

=> 結果S式評価結果は outerとなる。

[Nendo]ではLispのlambdaをRubyのlambdaで置きかえる方式のため、上記のような方法でレキシカル環境をマクロ展開する場所に埋めこむ。 もし、VMのバイトコードに変換する方式を採用した場合は、環境フレームを処理系が管理するやりかたが恐らく一般的だろう。(chibi-schemeもそうなっている) [Nendo]では最大限Rubyとの親和性を担保しやすいこと、環境フレームを管理することの実行時オーバヘッドを軽減するという観点から、VM方式は採用していない。

• デメリット 処理系が環境フレームを管理しない場合のデメリットは次の通り。 複数の場所で局所的syntaxが使われた時は、それぞれが別の環境になる。 環境フレームを自前で管理する方式では、同一のフレームは一つのインスタンスを共有することができるが、[Nendo]のようにマクロ展開する場所に環境を復元するコードを埋めこんでいく方式では、全て別々のインスタンスとなる。

これは、局所的syntaxが使われる回数によっては、展開後コードが肥大化するというデメリットがある。

• 注意点 マクロ展開の結果、let-syntaxを含むS式が変革される場合は注意が必要となる。 さらには、let-syntaxで定義したsyntax-rulesの<本体>部分でlet-syntaxで束縛したsyntaxを(再帰的に)使用している場合を考慮すると、環境復元コードも再帰的に展開されることになる。 そのため、環境復元コードの中に同一の変数が見つかったものをリダクションする必要がある。

いいかえると、結局のところ必要に応じて環境フレームの共有(融合)を行う必要がある。

er-macro-transformer(hygienic explicit renaming transformer)に必要な関数

chibi-scheme 0.3のREADMEに記載されているように、以下の関数を実装する必要がある。

SYNTAX-RULES macros are provided by default, with the extensions from SRFI-46. In addition, low-level hygienic macros are provided with a syntactic-closures interface, including SC-MACRO-TRANSFORMER, RSC-MACRO-TRANSFORMER, and ER-MACRO-TRANSFORMER. A good introduction to syntactic-closures can be found at:

http://community.schemewiki.org/?syntactic-closures

IDENTIFIER?, IDENTIFIER->SYMBOL, IDENTIFIER=?, and MAKE-SYNTACTIC-CLOSURE and STRIP-SYNTACTIC-CLOSURES are provided.

[Nendo]で実装した関数と、その解説を行う。 VM方式のLisp処理系とは違った考慮が入っている可能性がある。そのため、VM方式を採用しているLisp処理系にはそぐわない可能性があることに注意すること。

• er-macro-transformer chibi-scheme 0.3のコードは全てlambda式で書かれており、意味が汲み取りにくい。 読みやすいように改変してはいるが、本質的な意味においては chibi-scheme 0.3のコードから改変なし。

  ;; readable code for nendo. (original code is chibi-scheme-0.3)
  (define er-macro-transformer
  (lambda (f)
    (%syntax (expr use-env mac-env)
      (define (expander-main rename compare)
        (f expr rename compare))
      (define (_rename renames)
        (lambda (identifier)
          (let (*cell (assq identifier renames)*)
            (if cell
                (cdr cell)
                ((lambda (name)
                   (set! renames (cons (cons identifier name) renames))
                   name)
                 (make-syntactic-closure mac-env '() identifier))))))
      (define (_compare x y)
        (identifier=? use-env x use-env y))
        
      (expander-main
       (_rename '())
       _compare))))
  

• identifier? シンボルとidentifierの区別は不要。

  (define (identifier? x)
  (symbol? x))
  

• identifier? シンボルとidentifierの区別は不要なので、無変換。 別の型が入ってきたことに気づけるようにエラーチェックを入れているのみ。

  (define (identifier->symbol id)
  (when (not (symbol? id))
    (error "Error: identifier->symbol requires only symbol"))
  id)
  

• identifier=? シンボルとidentifierの区別は無いため、シンボル同士のeq?でOK。

  (define (identifier=? use-env-x x use-env-y y)
  (eq? x y))
  

• make-syntactic-closure Rubyで実装している。 リストは (syntax-quote …) しか許さず、 シンボルで、マクロ環境で束縛された変数なら、その束縛を含むレキシカルフレームのラップ 「(let (let (let …)))」 で包んで返し、 シンボルで、マクロ環境で束縛された変数でないなら、SyntacticClosureを返す。 上記以外の式は許さない。(型エラー) これにより、chibi-schemeのsyntax-rulesでrenameされるシンボルはマクロ環境の束縛状態においてidentifierの健全性が保たれる。

    def _make_MIMARKsyntactic_MIMARKclosure( mac_env, use_env, identifier )
      if _pair_QUMARK( identifier )
        if :"syntax-quote" == identifier.car
          identifier
        else
          raise TypeError, "make-syntactic-closure requires symbol or (syntax-quote sexp) only. but got: " + write_to_string( identifier )
        end
      elsif _symbol_QUMARK( identifier )
        if mac_env.to_arr.include?( identifier.intern )
          found = @lexicalVars.find { |x| identifier == x*0* }
          if found
            lexvars = @lexicalVars.clone
            __wrapNestedLet( identifier, lexvars )
          else
            identifier
          end
        else
          SyntacticClosure.new( identifier, (toRubySymbol( identifier ) + _gensym( ).to_s).intern )
        end
      else
        raise TypeError, "make-syntactic-closure requires symbol or (syntax-quote sexp) type."
      end
    end
  

ちなみに、SyntacticClosureは次のように定義され、[Nendo]独特のトリックが使われてる。 SyntacticClosureはリネーム前のシンボルと、リネーム後のシンボルが保持されており、 マクロ展開後に、quoteされたSyntacticClosureは、originalSymbol側が使用され、quoteされずに変数名として使用されるとgensymでリネームされた(健全性が保たれた)ほうが使用される。

  class SyntacticClosure
    def initialize( originalSymbol, renamedSymbol )
      @originalSymbol = originalSymbol
      @renamedSymbol  = renamedSymbol
    end

    def to_s
      @renamedSymbol.to_s
    end

    def intern
      @renamedSymbol
    end

    attr_reader :originalSymbol, :renamedSymbol
  end

• strip-syntactic-closure Rubyで実装している。 リストをトラバースしてSyntacticClosure型が見つかったら、sexp.internでリネームされた側のSymbolに変換する。

    def _strip_MIMARKsyntactic_MIMARKclosures( sexp )
      case sexp
      when Cell
        if _null_QUMARK( sexp )
          sexp
        else
          Cell.new(
                 _strip_MIMARKsyntactic_MIMARKclosures( sexp.car ),
                 _strip_MIMARKsyntactic_MIMARKclosures( sexp.cdr ))
        end
      else
        if sexp.is_a? SyntacticClosure
          sexp.intern
        else
          sexp
        end
      end
    end
  

再帰的にマクロ展開する箇所

マクロ展開エンジンで下記の箇所を再帰的にマクロ展開しなければならない。 (let-syntax ((<シンタックス1> (syntax-rules (ellipse) ((<マッチングルール1-1> <展開テンプレート1-1>) (<マッチングルール1-2> <展開テンプレート1-2>)) ...)) (<シンタックス2> (syntax-rules (ellipse) ((<マッチングルール2-1> <展開テンプレート2-1>) (<マッチングルール2-2> <展開テンプレート2-2>)) ...)))