健全なマクロ展開 - 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 を簡便に…

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

Bawden 等の or-expander を今風に修正し、 それを使って手動でマクロ展開してみます。 (define (or-expander form expanding-syntactic-env defined-syntactic-env) (make-syntactic-closure defined-syntactic-env '() (let ((sc (lambda (form) (make-syn…

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

現代の健全なマクロ展開器は let-syntax 構文や letrec-syntax 構文を使ってソース木の部分木中のレキシカル・スコープで有効な局所マクロを定義して利用できるようになっています。 ところが、健全なマクロ展開の最初の実装例であった KFFD アルゴリズム (1…

健全なマクロ展開 - KFFD アルゴリズム

マクロ展開の健全性を提唱した E. Kohlbecker, D. Friedman, M. Felleisen, and B. Duba Hygienic Macro Expansion (1986)、 略して KFFD から 30 数年が過ぎました。 KFFD は最初の実装例だけあって、 素朴で単純でわかりやすく、 健全なマクロ展開の仕組み…

遅延評価の解釈系

「SICP 4.2.2 遅延評価の解釈系」をいじって遊んでみます。 まず、 apply に手を入れて、 手続きに primitive-lazy を追加します。 これはアプリケーションと同じで、 実引数の評価を必要が生じるまで遅延します。 なお、 ホスト処理系の eval と apply との…

3imp のスタック・ベースなフラット・クロージャ VM への letrec サポート組み込み

乗りかかった船、 ということでスタック・ベース VM に letrec サポートを加えてみます。⇒ gist: Stack-based Flat-Closure compile/VM from 3imp to Gauche 0.9.5まずは、 VM の動きを追っていきます。現在実行中の手続きのフラット・クロージャをレジスタ …

3imp のスタック・ベースなフラット・クロージャ VM

Dybvig Three Implementation Models for Scheme (1987 年。以下 3imp と略す) では、 PASCAL 系のスタック・マシンから出発して、 スタック・ベースなフラット・クロージャによるレキシカル・スコープ実装へ至る説明になっています。 それでは、 フラット・…

ヒープベースなフラット・クロージャでも letrec

フラット・クロージャ VM でも letrec をサポートしてみます。 方針はディスプレイ・クロージャと同じにします。 letrec のスコープの自由変数を集めたダミー・クロージャを作ります。 その際、 自由変数は実引数と本体の両方から求めます。 ダミー・クロー…

ヒープベースなディスプレイ・クロージャでも letrec

VM レベル letrec サポートをディスプレイ・クロージャのその 2 の方でやってみます。 その 2 はフラット・クロージャを真似て、 クロージャごとに自由変数部分のディスプレイをコピーして作り直していました。 このとき、 作り直すのはクロージャのトップレ…

3imp ヒープベース VM で Henderson スタイルの letrec

Henderson の SECD マシンで作られた遅延評価 LispKit Lisp のコンパイラ/VM では、 VM レベルで letrec をサポートしていました。 コンパイラは、 let の実引数を let 外の環境でコンパイルし、 letrec の実引数を letrec 内の環境でコンパイルします。 ; H…

ヒープベースなフラット・クロージャ VM (その2)

フラット・クロージャ方式では、 手続きを作るごとに自由変数を拾い上げて閉じ込めます。 そのため、 スコープが深くなっていく過程で同じグローバル定数を何度も閉じ込めていく無駄が生じます。 これを避けるにはグローバル定数を自由変数から区別するよう…

ヒープベースでフラット・クロージャ VM (その1)

R. Dybvig Three Implementation Models for Scheme (以下 3imp) 第 4 章のフラット・クロージャはスタックベース VM 用に作ってありますが、 フラット・クロージャ自体はヒープベース VM でも利用できる仕組みです。 ヒープベース VM でも、 クロージャ作成…

3imp ヒープベース VM をディスプレイ・クロージャで (その 2)

昨日は入れ子リストのクロージャをそのままディスプレイにしただけでした。 ディスプレイ・クロージャ版の VM の動作を追うと、 close 命令で環境をそのまま閉じ込めて、 apply 命令ごとにディスプレイを作成していました。 a (close n1 x1 x) e r s -> (n1 …

3imp ヒープベース VM をディスプレイ・クロージャで (その 1)

3imp では、 ヒープベース VM をディスプレイ・クロージャにする段階を飛ばして、 スタックベース VM へ進んでいきます。 ここでは、 ものは試しと、 ヒープベース VM をディスプレイ・クロージャに変更することにします。ディスプレイ・クロージャの元にな…

letrec と letrec*

R5RS 以前の letrec は実装に依存します。 R6RS でセマンティック・エラーになる書き方をしてみると…… (let ((a 4) (b 5)) (list (letrec ((a (begin (set! b 2) b)) (b (begin (set! a 3) a)) (f (lambda (t) (cons a b)))) (f #t)) (cons a b))) ;=> ((3 .…

3imp のフラット・クロージャ

R. K. Dybvig Three Implementation Models for Scheme (以後、 3imp と略す) でこってりと解説してある Chez Scheme 用フラット・クロージャについて。レキシカル・スコープの実装方法はいくつもあり、 Scheme 動作の説明で使われることが多い環境束縛モデ…

3imp ヒープベース compile/VM で階乗計算

春 の続きです。 3imp のヒープベース compile/VM にプリミティブ摘要を追加して階乗計算をやってみます。 ただし、 compile は式の並び対応に変更したものを使うことにします。 次のように、 環境を作成しておき、 fact を階乗計算の手続きに束縛します。 …

3imp ヒープベース compile/VM での begin 形式

Dybvig Three Implementation Models for Scheme (以下 3imp) では、 begin 形式と lambda 形式のボディを、 入れ子の lambda 形式へ変換してコンパイルするとあります。 それでも間違いではないのですが、 一つ注意点があって、 入れ子になっている lambda …

可読性を求めた quasiquote 展開

Scheme の quasiquote の処理には、 マクロ展開器の中に組み込む Alan Bawden Quasiquatation in Lisp の Appendix B のコードを使うのがてっとり早いのですけど、 このコードの出力する S 式は機械向けです。複雑になると人間には読めたものではないので、 …

「Beautiful Code 25章 構文の抽象化: syntax-case マクロ」の例題

2018 年 3 月 13 日追記あり 初稿には理解不足による間違いがあります。 R6RS Scheme のマクロ syntax-case の仕組みを単純化したコードで R. Kent Dybvig 御大自らが説明している「Beautiful Code 25章 構文の抽象化: syntax-case マクロ」(英語原本 PDF; …