M. Adams 等の R6RS equal? の find 手続き

M. D. Adams, R. K. Dybvig, Efficient Nondestructive Equality Checking for Trees and Graphs, 2008 (以下、 ADAMS2008 と略す) の find 手続きについて。 結論は先送りで、 気になった点を備忘録として残しておきます。SRFI-85 で提案されて、 R6RS Sche…

健全なマクロ展開 - 変換世代マーク・リスト

ybvig syntax-case で識別子の意味を探すときに、 ラップから抜き出した変換世代マークのリストを使います。 このやりかたを明示リネーミング・マクロに利用するとどうなるのか興味を覚えたので、 試しに Hanson-Bawden に変換世代マークを取り入れてみます…

健全なマクロ展開 - syntax-rules (その 5)

前回の syntax-rules マクロは、 Hanson-Bawden 構文クロージャ展開器で利用することを想定して作っています。⇒ Gist rsc-rules.scm ⇒ Gist rsc-expand.scmまず、 so-rules.scm から so-syntax-rules-macro をテキスト・ファイルに抜き出します。 そして、 …

健全なマクロ展開 - syntax-rules (その 4)

syntax-rules のパターンの省略記号は、 R6RS 以後、 正規リストとドッテッド・リストの両方の途中に導出可能になっています。 SRFI 149 の参考実装に採用している Chibi Scheme のものでは、 パターンの途中に省略記号があると、 パターンと比較対象式の両…

健全なマクロ展開 - 構文オブジェクト (その11)

syntax-case は、 シンボルに構文環境がくっついた識別子を使うことで健全性を実現します。 識別子を使って変換結果を作るのはマクロ変換子の役目で、 展開器が識別子に変換世代を区別する印を追加してくれます。 マクロ変換子が使う識別子はマクロの定義式…

健全なマクロ展開 - 構文オブジェクト (その10)

構文環境をくっつけてある式を展開する so-expand-form は Clinger-Rees のものと同じです。 Hieb-Dybvig の方がチェックが厳しく作ってあって、 ペアの構文オブジェクトか識別子でないときは、 空リストか、 定数であることをチェックします。 (define (so-…

健全なマクロ展開 - 構文オブジェクト (その9)

これまで書いてきた展開器を流用しつつ、 Hieb-Dybvig を参考にした展開器を書いてみます。 Gauche 0.95 で動くことを目標にします。 以下、 Beutiful Code 25 章の Dybvig 「構造の抽象化: syntax-case マクロ」(英語版 PDF) と照らし合わせることを考慮し…

健全なマクロ展開 - 構文オブジェクト (その8)

今度は syntax-case の構文オブジェクトが局所マクロの再帰定義をどう扱うかを調べます。 例にするのは、 syntax-rules に free-identifier=? の真似ごとをさせるマクロとします。 (let-syntax ((freeid=? (syntax-rules () ((_ a b) (let-syntax ((test (sy…

健全なマクロ展開 - 構文オブジェクト (その7)

前回までは syntax-case の構文オブジェクトが局所マクロの再帰展開をどう扱うかを見てみました。 今度はλ構文と局所マクロが識別子をどのように扱うかを調べます。 そのために、 R4RS 以後、 健全性の例の一つとして利用されている次のマクロ展開をとりあげ…

健全なマクロ展開 - 構文オブジェクト (その6)

いつもの or 構文の展開も試してみます。 これまで同様、 構文環境フレーム E1 とマーク M0 をすべてのシンボルにくっつけてから展開を始めます。 syntax-quasiquote 構文はここで独自にでっちあげた構文で、 quasiquote 構文と一点を除いて同じです。 その…

健全なマクロ展開 - 構文オブジェクト (その5)

その4 までの構文オブジェクトによる展開器は、 Hanson-Bawden の構文クロージャによる展開器を元にしていたため、 いびつなところが残っていました。 Hanson-Bawden で明示リネーミングの対象になるのは構文情報がくっついていないシンボルなのに対して、 …

quasiquote の展開

1年前の「可読性を求めた quasiquote 展開」は、 Alan Bawden Quasiquatation in Lisp の Appendix B のコードを元にしていました。 このコードは、 とても良く似ている 2 つの内部定義手続き qq-expand と qq-expand-list を使って書いてあります。 手続き…

健全なマクロ展開 - 構文オブジェクト (その4)

構文オブジェクト (その 3) 展開器では、 Hanson-Bawden の名残りでマクロ定義時構文環境から拡張した変換世代マークだけを式にくっつけていました。 その結果、 identifier=? しか利用できなくなり、 識別子の意味一致判定のためマクロ変換手続きに展開時構…

健全なマクロ展開 - syntax-rules (その 3)

SRFI 149 は syntax-rules のパターン言語のテンプレートに新しい機能を追加しています。 従来のテンプレートは、 サブテンプレートにつけることができる省略記号は 1 つだけだったのを、 2 つ以上も許し、 2 つ以上のときは余分な省略記号の分、 リストの a…

健全なマクロ展開 - syntax-rules (その 2)

構文オブジェクト (その 3) 展開器で syntax-rules を使えるようにします。今回の syntax-rules はそれ自身が低レベル・マクロです。 このマクロは syntax-rules 構文で記述してある展開対象式を低レベル・マクロの展開対象式へと変換します。 パターン言語…

Chibi-Scheme のsyntax-quote 構文

SRFI 149 のサンプル実装で使われている Chibi Scheme の独自機能は、 length* だけではありません。 もうひとつ、 syntax-quote という見慣れないキーワードが使われています。 syntax-quote の別名が使われている重要な場所は 2 ヶ所あります。 一つは、 …

健全なマクロ展開 - syntax-rules (その 1)

現在の syntax-rules 規格は、 互換性がない R6RS と SRFI 149 の 2 つが存在しています。 互換性が崩れている箇所は、 パターンとテンプレートで省略記号 (3 ドット) の段数に違いがあるときの扱いです。 違いが現れる典型的なマクロは、 パターン変数 a の…

健全なマクロ展開 - 構文オブジェクト (その3)

Hanson-Bawden 展開器を元に、 別名を構文オブジェクトへ置き換えて低レベル・マクロ展開器を作っていきます。マクロ変換ごとに挿入されていくシンボルの変換世代を自動的に区別する目的で、 今度の展開器は展開前の展開対象式のシンボルにも変換世代マーク…

健全なマクロ展開 - 構文オブジェクト (その2)

構文オブジェクトを採用すると、 KFFD のようにマクロ変換子が新しく挿入したシンボルを自動認識させることができるようになりました。 前回の例は、 マクロは大域だけで局所マクロを使わなかったので、 構文オブジェクトを使って展開対称式をマークしておく…

Chibi-Scheme の length* 手続き

SRFI-149 の実装例、 Chibi-Scheme の syntax-rules 構文の定義中に使われている length* 手続きは、 Chibi 独自のもので、 C 言語の関数 sexp_length_op を登録してあります。 ./opcodes.c:156:_FN1(_I(SEXP_FIXNUM), SEXP_NULL, "length*", 0, sexp_length…

健全なマクロ展開 - 構文オブジェクト (その 1)

最初の健全なマクロ展開手法 KFFD (1986) では、変換世代ごとに挿入されるシンボルを自動認識して、 それらを別物として区別します。 あらかじめ変数に変換世代番号がつけてあり、 変換するごとに世代番号なしの変数を探して、 新しい変数を認識していました…

マクロではないパターン・マッチング手続き

Andrew Wright のパターン・マッチング言語のサブセットを使う 200 行以下の小規模なパターン・マッチング手続きです。 対象はリスト限定で、 ベクタやレコードへのマッチングは省略してあります。 擬似クォート・パターンも省略しています。 set! と get! …

Andrew Wright のパターン・マッチングのリストのコピー

Scheme で親しまれている Andrew Wright のパターン・マッチング・マクロのパターンは ... を使ってリストに一致させることができます。 この場合、 次のようにリストを作成してパターン変数に結びつける機能の副産物で、 リストのコピーを生じることがあり…

健全なマクロ展開 - dotted-list の展開

ここまで書いてきた展開器は、 λ構文の仮引数が正規リストに限っていました。 Scheme のλ構文の仮引数部はドッテッド・リストであっても良く、 束縛変数を可変長の実引数のリストに束縛できるようになっています。 ((lambda x (apply + x)) 2 3 4 5) ;=> 14 …

健全なマクロ展開 - reversed syntactic closures (その3)

Clinger-Rees 展開器に構文クロージャを加え、 rename denotation を取り除いて Hanson-Bawden の展開器を作ってみました。 ⇒ Gist tociyuki/rsc-expand.scm展開器のトップで symbol? を sc-identifier? に変更し、 構文クロージャの展開処理を追加します。 …

健全なマクロ展開 - reversed syntactic closures (その2)

Hanson は、 定義時構文環境とシンボルを閉じ込めた構文クロージャをシンボルの別名とし、 シンボルと同格に扱えるように Bawden の syntactic closures を改良しました。 別名と意味を結びつける束縛対を構文環境に置くことができるようになり、 (その1) の…

健全なマクロ展開 - reversed syntactic closures (その1)

明示的リネーミング・マクロの元になった Clinger-Rees (1991) の記載によると、 R4RS Scheme (1991) を目指して 1988 年から始まった議論の中で、 Bawden-Rees の syntax-closures (1988) を改良することで syntax-rules の実装に利用する方法を C. Hanson …

健全なマクロ展開 - Clinger-Rees の明示リネーミング・マクロ (その2)

W. Clinger、 J. Rees、 Macros That Work (1991) のアルゴリズムになるべく沿って展開器を書いてみます。 明示リネーミング・マクロとしては W. Clinger, Hygienic Macros Through Explicit Renaming (1991) に沿います。 相変わらず、 Gauche 0.9.5 にべっ…

健全なマクロ展開 - Clinger-Rees の明示リネーミング・マクロ (その1)

健全なマクロ展開は 1986 年に発見されて KFFD アルゴリズムが生まれました。 これはグローバルなマクロ定義を使い、 O(n^2) の計算時間がかかります。 続く 1988 年に Bawden 等によって、 展開器の構文環境と構文クロージャが発見され、 それらを巧みに利…

健全なマクロ展開 - syntactic-closures (その 3)

変換子のレキスカル・スコープ問題を無視して、 Bawden 等の実装を真似た展開器を書いてみます。 今回も Gauche 0.9.5 に依存したコードになっています。⇒ Gist tociyuki/sc-expand.scmオリジナルの構文環境のデータ構造から変更し、 letrec-syntax を簡便に…