識別子が束縛を持つか判定する

目的

プログラミング言語 Scheme (R6RS) において、ある識別子が束縛を持つかどうかを判定する方法を考えました。

つまり、たとえば以下のような挙動をするマクロ bound? を定義しようとするものです。

#!r6rs
(import (rnrs)
        (binding))

(define bar #t)

(display (bound? foo))    ;; foo は定義されていないので #f
(display (bound? bar))    ;; bar は定義されているので #t
(display (bound? lambda)) ;; lambda は定義されているので #t
(display (bound? bound?)) ;; bound? は定義されているので #t

実装

以下のようなものが出来上がりました。

#!r6rs
(library (binding)
  (export bound?)
  (import
   (for (only (rnrs base) list not quote lambda eqv? unquote quasiquote) expand)
   (for (only (rnrs base) define-syntax) run)
   (for (only (rnrs lists) exists) expand)
   (for (only (rnrs syntax-case)
              syntax-case syntax free-identifier=? syntax->datum datum->syntax)
        expand)
   (for (only (rnrs eval) eval environment) expand))

  (define-syntax bound?
    (lambda(ctx)
      (syntax-case ctx ()
        ((_ id)
         (exists (lambda(x)(free-identifier=? #'id x))
                 (list #'syntax #'quote #'syntax->datum #'datum->syntax))
         #t)
        ((_ id)
         (not (free-identifier=?
               (eval `(datum->syntax #'k ',(syntax->datum #'id))
                     (environment '(only (rnrs)
                                         datum->syntax
                                         syntax->datum
                                         syntax
                                         quote
                                         )))
               #'id))))))
  )

解説

上記の実装がどのような仕組みで識別子を判定するのか順を追って解説します。

識別子の等しさ

さて、識別子を比較するにあたって free-identifier=? を用いていますが、 free-identifier=? によって定義される識別子が等しいというのは「ふたつが同一の束縛に帰着する場合のみ。 ただし、同名の識別子がどちらも未束縛の場合は同一の束縛に帰着したものとする」ということになっています。

ですから逆に言えば同名の識別子であってもことなる束縛を持つならひとしくない識別子であるということになります。

(let ((lambda 1))
  ;; この中では lambda は (rnrs) の lambda と等しくない
  )

束縛を持つか？

以上を踏まえてある識別子が束縛を持つかどうかは、その識別子と同名で束縛を持たない識別子と比較すればよいと考えました。 比較の結果が異なるならば束縛を持ち、比較の結果が一致するなら元から束縛を持たない識別子であったのだと判定することができます。

同名で束縛を持たない識別子の生成

入力された識別子と同名で束縛を持たない識別子を生成するにあたって syntax->datum を用いて入力された識別子から文脈情報をはがした上で datum->syntax を用いて bound? マクロ定義時の文脈に付け替えています。

同名で束縛を持たない識別子の生成が出来ない場合

同名で束縛を持たない識別子の生成をするにあたって単純に datum->syntax を使うだけでは bound? マクロ定義時の文脈に存在するいくつかの識別子についてはその束縛を持った識別子が生成されてしまいます。 なので eval を用いることで最小限の語彙しかない環境で処理することにしました。 更にそれでも残ってしまう語彙については条件分岐して別途対応するという処置をしています。

動作試験

私は R6RS の範囲内で正しく実装したつもりではいますが、処理系によっては期待通りに動作しませんでした。

処理系名	バージョン	動作
Sagittarius	0.9.7	期待とは異なる判定をする場合がある。 処理系の作者の言によれば Sagittarius はフェイズの分離をしない実装方針であることが影響しているのではないかとのこと。
Racket CS	7.8	必要以上にメタレベルの指定を入れる必要があったがその処置をすれば期待通り動作した。 標準のライブラリが提供する語彙のほとんどは仕様上はエクスポートレベル 0 と 1 で公開されているべきだが、エクスポートレベル 0 のみで公開されている様子。
Chez Scheme	9.5.3	期待通り動作した。
Larceny	1.3	期待通り動作した。

修正版

大きな見落としをしていたのをコメントで指摘してもらいました。 syntax などが束縛を持つ場合は場合分けしていたのに束縛を持たない場合について考慮しておらず、結果的に間違った判定をしていました。

それらを修正した上で多少の整理をした修正版を示します。

#!r6rs
(library (binding)
  (export bound?)
  (import
   (for (rnrs) run expand)
   (for (rnrs eval) expand))

  (define-syntax bound?
    (lambda(ctx)
      (syntax-case ctx (syntax quote datum->syntax)
        ((_ syntax) #t)
        ((_ quote) #t)
        ((_ datum->syntax) #t)
        ((_ id)
         (free-identifier=?
          (eval `(datum->syntax #'k ',(syntax->datum #'id))
                (environment '(only (rnrs) datum->syntax syntax quote)))
          #'id)
         #f)
        ((_ id)
         (memq (syntax->datum #'id) '(datum->syntax syntax quote))
         #f)
        ((_ id)
         #t))))
  )

移植性

R6RS では実行時とマクロ展開時の環境を分離するフェイズという考え方が導入された。 マクロ展開時に用いるマクロを展開するならそのときの環境も、更にその中でのマクロ展開も……といったように多段の構成でも環境をどう分けるかというのが整理されている。

ただ、この仕組みは言語仕様上はだいぶん緩い仕組みで、あまりしっかり環境を分けない実装を許している。 ライブラリの実体 (インスタンス) を異なるフェイズで共有しても良いし、参照する側でも区別してもしなくてもよい旨は R6RS の 7.2 に書かれている。

一例として以下のような場合を考えてみよう。 名前 foo を実行フェイズでは bar としてインポートし、展開フェイズでは baz としてインポートしている。 このとき bar と baz を比較した結果はどうなるだろうか。

#!r6rs
(library (lib)
  (export foo)
  (import (rnrs))

  (define-syntax foo (syntax-rules ()))
  )

#!r6rs
(import (rnrs)
        (for (rename (lib) (foo bar)) run)
        (for (rename (lib) (foo baz)) expand))

(let-syntax ((qux (lambda(ctx)
                    (syntax-case ctx ()
                      ((_ x y)
                       (free-identifier=? #'x #'y))))))
  (display (qux bar baz)))

ありえる可能性を考えると以下のみっつが思いつくだろう。

• baz はこのフェイズにおいて束縛されていないのだから束縛されていない識別子として扱われる。 (上の例の結果は #f になる)
• 別のフェイズで使われるべき識別子が現れたのだからエラーである。
• 起源が同じなのだから等しい識別子である。 (上の例での結果は #t になる)

理念通りに考えるのであれば一番目の選択肢が妥当だと私には思えるが、実際はどれも許されている。 どれかになることを期待すると移植性を損なうことはわざわざ明記されている。

Thus, a library whose meaning depends on whether the instances of a library are distinguished or shared across phases or library expansions may be unportable.

eval が返す構文オブジェクトがフェイズでいうとどういう扱いになるのかも仕様上ははっきりしないし、移植性の高い方法ではないようだ。