2010年4月12日月曜日

alambda

R5RS Schemeの衛生的マクロでアナフォリックマクロは書けません。
色んな意見があるとは思いますが、アナフォリックマクロが書けない時点でSchemeの衛生的マクロは設計としては失敗してる、と思います。
実際、R6RSの衛生的マクロ、syntax-caseでは書けるようになっている、と言う話なんですが、相当ややこしくなってる、との事です。またsyntax-caseに関してのまとまった文献なり入門、ってのも見たことないです(ビューティフルコードには載ってるっぽいんですが、どっちかと言うと論文っぽいんで、実用的にどうする、って話を読み取るのは難しいでしょう)。従って今のところ、syntax-caseは使いようがない。

ポール・グレアムのOn Lispalambdaと呼ばれるアナフォリックマクロが紹介されています。これはLET OVER LAMBDA Edition 1.0でも使われまくってるアナフォリックマクロの代表格です。定義は以下のようなものです。

CL-USER> (defmacro alambda (parms &body body)
`(labels ((self ,parms ,@body))
#'self))
ALAMBDA
CL-USER>

同書には次のような例が掲載されています。

CL-USER> (alambda (x) (if (zerop x) 1 (* x (self (1- x)))))
#<FUNCTION (LABELS SELF) {BB55A75}>
CL-USER>

ご覧の通り、alambdaは代名詞selfで束縛されたクロージャを返す。上のワンライナーは階乗の定義なんで、階乗を計算するクロージャですね。
続けてインタプリタに次のように入力します。

CL-USER> (funcall * 10)
3628800
CL-USER>

10の階乗がキチンと返ってきます。ちなみに、上の*は「掛け算」の意味ではなくって、CLのインタプリタ上では、その前の計算結果を参照する場合、*で参照出来ます。つまり、関数としての役割ではなくって、大域変数なんです。詳しくはこちらをご覧下さい。*を掛け算と解釈すると、上の入力は意味不明になります。
話を元に戻すと、最初の定義、

CL-USER> (defmacro alambda (parms &body body)
`(labels ((self ,parms ,@body))
#'self))
ALAMBDA
CL-USER>

に於いて、一見不用意にselfと言う変数名が挿入されているように見えます。これはマクロが展開される場所の外側からselfが指示されていたらそれを参照してもおかしくないんです。と言うか、前の例示の通り、明らかに参照している。
そのお陰で代名詞として役割を果たしてるんですね。上手い手です。そしてこれはSchemeで実現するのが難しい。と言うよりR5RSでは出来ません。

一見、R5RSマクロで次のような定義方法に翻訳出来て、それで良さそうに見えます。

;; この定義方法じゃ実はダメ。
(define-syntax alambda
(syntax-rules ()
((_ params body ...)
(letrec ((self
(lambda params
body ...)))
self))))

Schemeインタプリタで次のように走らせてみても、一見上手く動きそうに見えるのです。

> (alambda (n)
(if (zero? n)
'()
(cons
n
(self (- n 1)))))
#<procedure:self>
>

確かに手続きのクロージャselfが返ってるように見える。
ところが、これに実値を与えてみると、破綻している事が分かる。

> ((alambda (n)
(if (zero? n)
'()
(cons
n
(self (- n 1))))) 10)
reference to undefined identifier: self

=== context ===
/usr/lib/plt/collects/scheme/private/misc.ss:74:7

>

つまり、alambdaを用いたクロージャの定義で現れるselfは、alambda自体の定義で使われているselfとは別物だ、と認識されるのです。CLでのalambdaでは同一と見なされるものがR5RSでは同一と見做されない。変数衝突が起きない。これが衛生的と言われる所以です。

R5RSマクロは「letが変数束縛をする」ということを知っており、マクロが挿入する束縛変数とマクロの「外から来た」変数とを区別するのです。

-----<中略>-----

Schemeは、レキシカルクロージャを導入したのと同じ発想を、一段メタな領域に適用しようとしています。そこではもはやプログラムはS式そのものではありません。一度読み込まれて構文解析されたプログラムは「S式+環境」となり、マクロは「S式+環境」に対して作用します。


つまり、Schemeで翻訳を試みたalambdaの定義で使われているselfはクロージャによって守られていて、外側から中を参照する事が出来ません。コンテクストが外部定義からは切り離されているのです。故にアナフォリックマクロが定義出来ない。


Schemeではむしろ、束縛する変数を呼び出し環境から与えてやる書き方が推奨されます。


プログラミングGaucheの流儀に従うと、Schemeでのalambdaは次のように定義した方が無難だと言うことです。


(define-syntax alambda
(syntax-rules ()
((_ self params body ...)
(letrec ((self
(lambda params
body ...)))
self))))

つまり、外部からselfを与えてやるようにする。そうすると、

> (alambda self (n)
(if (zero? n)
'()
(cons
n
(self (- n 1)))))
#<procedure:self>
>

とクロージャselfが返るのは同じですが、引数を与えてやると、

> ((alambda self (n)
(if (zero? n)
'()
(cons
n
(self (- n 1))))) 10)
(10 9 8 7 6 5 4 3 2 1)
>

となります。
しかし、こうなると実際、アナフォリックマクロと言うよりクロージャを返すnamed-letの変種ですね。

こんな感じで、CLのマクロをSchemeに移植しようとすると、色んな障害が立ちはだかります。また、外部から変数を与えてPseudoなアナフォリックを狙っても、CLと違い、手続き定義に於いては味方の筈のクロージャが敵にまわり、同じ効果を出すには大きな障害として立ちふさがるのです。

4 件のコメント:

  1. はじめまして。
    syntax-case のまとまったチュートリアルとしては「プログラミング言語SCHEME (著:R.Kent Dybvig, 翻訳:村上雅章) 」が良いと思います。
    http://www.amazon.co.jp/dp/4894712261

    返信削除
  2. >> 斎藤さん

    どうも情報ありがとうございます。

    実は、プログラミング言語Schemeの第4版

    The Scheme Programming Language:
    http://www.scheme.com/tspl4/

    の日本語訳が出るのかどうか知らないんですけど(笑)、何か買い控えてるんですよね。将来的に出るならそっち買いたいよな、と(笑)。

    出ればいいんですけど。

    (余談ですけど、ピアソンって良い出版社だとは思うんですが、何か単発ものが多いですよね)

    返信削除
  3. syntax-case が正式に規格に入ったのは R6RS からですが、初出は意外に古いです。 その割には確かに文献が (日本語に限ればなおさら) 少ないと感じます。
    ウェブ上にあるものとしては IBM のサイトと leque 氏による srfi-93 の日本語訳が参考になると思います。
    http://www.katch.ne.jp/~leque/translations/srfi-93/srfi-93j.html
    http://www.ibm.com/developerworks/jp/linux/library/l-metaprog2/index.html

    CL では非衛生なマクロが基本にあって、衛生的にしようと思えばそのための記述 (gensym とか) をする必要があるわけです。 Scheme ではそれが逆になり基本は衛生的で、それを破りたければちょっと記述が追加になるという風に、結局はどちらを基点にするかの違いではないでしょうか。
    とは言え、比較すれば syntax-case は伝統的なマクロよりもややこしいのは事実でしょう。 私は CL を全然使っていないので細かい比較は出来ないのですが、 syntax-case がややこしく感じられるのは「構文オブジェクト」の概念を持ち込んでいるという点が大きいと思います。 伝統的なマクロは単なるリストの操作ですし、 syntax-rules もパターンマッチやら衝突回避やらを導入してはいるもののリスト操作の延長線上で考えることは出来ます。 そこに別の異質な概念が登場することでややこしく感じられるのではないかと。

    試しに alambda を syntax-case で定義してみました。

    (define-syntax alambda
    (lambda(x)
    (syntax-case x ()
    ((k params body ...)
    (with-syntax ((self (datum->syntax #'k 'self)))
    #'(letrec ((self (lambda params body ...))) self))))))

    (define (dec x) (- x 1))
    ((alambda (x) (if (zero? x) 1 (* x (self (dec x))))) 10)

    直接 syntax-case を使うのではなく、 syntax-case を用いて defmacro 相当の機能を実装するのも案外簡単です。

    (define-syntax defmacro
    (syntax-rules ()
    ((_ (macro . args) . body)
    (defmacro macro (lambda args . body)))
    ((_ macro transformer)
    (define-syntax macro
    (lambda(x2)
    (syntax-case x2 ()
    ((k . args)
    (datum->syntax #'k
    (apply transformer
    (syntax->datum #'args))))))))))

    これを使えば CL での場合とよく似た形式で alambda を定義できます。

    (defmacro (alambda parms . body)
    `(letrec ((self (lambda ,parms ,@body)))
    self))

    このように、考え易いように小さな単位でラッピングしてしまえばそれほどややこしくは感じないと思うのですが、結局は慣れなんですかね。

    返信削除
  4. >> 斎藤さん

    >syntax-case が正式に規格に入ったのは R6RS からですが、初出は意外に古いです。

    ある意味ring my bell、って感じではありますけれども。
    と言うのも、確か「衛生的マクロ」自体を学術的に研究してたのが、それこそchezの実装者であるKent Dybvigじゃなかったかしら?確かそうだったと思うんですけど……。
    実験的にChezで実装された衛生的マクロがRnRSに取り入れられて行った、って感じじゃないんですかね?多分。

    >試しに alambda を syntax-case で定義してみました。

    おお、これは嬉しいです。
    実際問題、syntax-caseで定義されたマクロってまず見た事が無いんですよ。
    これは意外と初顔合わせやもしれません。

    >結局は慣れなんですかね。

    でしょうね(笑)。
    まあ、先にも書いたんですが、「慣れる」以前に現物にお目にかからないわけです(苦笑)。
    ちょっとコード分析してみますね。

    返信削除