define-macroのみ備える処理系のsyntax-rulesサポートは可能か？

nmosh

追記: Redditの投稿 https://www.reddit.com/r/lisp_ja/comments/8kttfy で、Common Lispでの実装 http://www.ccs.neu.edu/home/dorai/mbe/mbe-lsp.html に言及がある。
追記: (最後の段はあんまり正しくない。 __ でgensymする場合、単一のsyntax-rulesテンプレート中に2回以上 __ が出現した場合は同じシンボルを出力するように出力をキャッシュする必要がある。こういう感じに: https://github.com/okuoku/yuni/blob/e03dc40e14389f9b1b63fd07fbb63ffbfe3fd228/lib-runtime/generic/synrules.scm#L40 )
yuniで提供されるライブラリの殆どはFFIを経由したCライブラリのwrapperになると考えられる。このため、ライブラリはマクロや補助構文をexportしないことが殆どになると言える。この要件の元でなら、define-macro(伝統的マクロ)しか備えない処理系でも自前のマクロ展開器を実装せずにR7RSライブラリやsyntax-rulesを実装できるのではないか。
(以前書いたように、マクロをエクスポートする場合は他のバインディングもグローバルにbindするという制約が必要になる http://d.hatena.ne.jp/mjt/20160825/p1 )

各種define-macro処理系

ここでのdefine-macroはScheme処理系にたまに見られるマクロ機構で、特定シンボルに"変換器"となる手続きをバインドし、ソースコードを実行前に変形することができる。

通常のシチュエーションでは、ランダムなシンボルを生成するgensym手続きとセットで提供される。Gambitやs7では、シンボルがgensymで生成されたものかどうかを判別することが可能だが、BiwaSchemeやbiglooではそうではない。
gensymが追加のオブジェクトを取れるかどうかにも微妙な差異がある。

define-macroでsyntax-rules(もどき)を実現するための制約

s7のように自由に環境クエリが可能なものを除くと、define-macroによる伝統的なマクロは、

  1. Scheme手続きによる式の変形
  2. gensymによる他と衝突しないシンボルの生成

のみが可能となっている。このため、syntax-rulesによるマクロが本来備えている"自動的な健全性"はどうやっても実現できない。なので何らかの現実的な制約を加えてどうにかdefine-macroでも実装可能なレベルに落としてやる必要が生じる。
... これがなかなか難しい。というか、制約として存在して困るケースが全然思いつかないので、何がダメになるのかが分からない。
define-macro処理系ではマクロの定義にdefineだけが使える。つまり、let-syntaxやletrec-syntaxに相当する構文が存在しないということになる。ただ、let-syntaxは通常のletとdefine-syntaxに開くことができるし(たぶん)、letrec-syntaxはそもそもdefine-syntaxでエミュレートできる(letrec*をdefineでエミュレートできるのと同じ)。
健全なマクロの例によく出てくる有名な例としては、"elseのような補助構文を別の意味にbindした場合に正常に動作しない"というケースだろう。でも個人的にはこれを真剣にやりたいケースに遭遇したことが無い(Cとかだと有るんだけど)。define-macroでsyntax-rulesを実現する上では、補助構文(syntax-rulesで与えたリテラル)は字面上での一致しか見ることができないため、補助構文をマスクするような記述はできないことになる。

(define-syntax checkelse
  (syntax-rules (else)
    ((_ else) (display "Is Else\n"))
    ((_ otherwise) (display "Is NOT Else\n"))))

(checkelse else) ;; => "Is Else" が出力される
(checkelse if) ;; => "Is NOT Else" が出力される
(let ((else #t))
 (checkelse else)) ;; => define-macroではこちらも "Is Else" になる。通常の処理系では "Is NOT Else"。


というわけで、健全性は一切気にしない方向でsyntax-rulesを実装してBiwaSchemeで実行させてみた。https://gist.github.com/okuoku/968caa7fa751beb029398a20838fbb24 今回は、chibi-schemeのexplicit renamingマクロで実装されたsyntax-rulesを適当にwrapしている。
(BiwaSchemeはnpmに収録されているので"npm install biwascheme -g"とすることでコマンドライン版biwasがインストールできる。)
要するに、syntax-rulesが単にテンプレートに従った式変形ツールになったとして、現実的な問題で困ることができるだろうか？他のポイントとしては、syntax-rulesのテンプレート内のシンボルはそのまま展開されるため、:

  1. マクロを定義した場所の環境 == マクロを使用した場所の環境 となっている必要がある。つまり、マクロを使用して変数をライブラリからimplicitに持ち出すことはできなくなる。...これは実はChickenのような通常のScheme処理系でもできないことが有るため、移植性という意味ではそこまで大きな問題では無い気がしている。
  2. "束縛されていないものに関してはマクロ展開のたびに異なる識別子が挿入される"要件を満たすことができない。R6RSで言うところの generate-temporaries https://practical-scheme.net/wiliki/wiliki.cgi?R6RS%3A%E7%BF%BB%E8%A8%B3%3AStandard%20Libraries%3A12.7%20Generating%20lists%20of%20temporaries が実装できないということになる。

逆に、generate-temporariesを専用の構文として分けてしまえば十分かもしれない。
例えば、R7RSの例として載っているletrec実装は、define-macroで書かれたsyntax-rulesでは正常に動作しない。

- (10 20)が正解
これは途中のダンプ結果に現われているように、変数"newtemp"が2回のsyntax-rules展開で被ってしまっているため出力結果が間違っている。本来syntax-rulesでは、マクロの展開結果が未知の識別子を挿入する場合は、その挿入した識別子は他のsyntax-rules展開で挿入されるものと絶対に被らないことを保証しなければならない。通常のdefine-macroでは、挿入しようとしている識別子が未知かどうかを知る手段が存在しないため、この制約を良く実装することができない。
もっとも頭の悪い解法は、適当なidentifier-macroを定義してそれをgensymの意味で使うことだろう。つまり、↑の実装でシンボルフィルタとして渡している baselib 手続を

(define (yuni/synrule-baselib sym)
  (case sym
    ((__) (yuni/gensym))
    (else sym)))

のように、ある適当なシンボル(ここではアンダースコア2つ)をgensymの意味になるように設定し、

     (letrec0 "generate temp names" (y ...)
       (__ temp ...)
       ((var1 init1) ...)
       body ...)

のように、新しい識別子が必要な場所で明示的に使うことで、マクロ手続き側で環境の知識を持っていなくても適切にgensymに誘導するようにできる。
これで、letrecも期待通り動作するようになった。


正直ここまでして処理系のマクロ展開器を使いつづける意義ってのが有るのかどうか微妙な線になってきたが、とにかく今のところは受け入れ可能な制約でdefine-macro処理系にyuniを実装することができる気がしている。