2015/01/30
クロージャの比較、あるいは「同じ」とはどういうことか
@SaitoAtsushi: R6RS では比較結果が未規定である事例として以下のような事例を挙げている。
(let ((p (lambda (x) x))) (eqv? p p))
未規定にすることで可能になるような最適化があったりする？ ざっと見た感じではどの R6RS 処理系も #t を返すっぽい。
この式そのもので#fを返すようにする意味はほとんど無いんだけれど、 もうちょい複雑になった場合にこの規則が意味を持つ可能性がある。
(define (foo a flag)
(let ((p (lambda (x) (+ x a))))
(bar (if flag identity p))))
上の式で、pは別の手続きに渡され得る(エスケープする可能性がある)から、
クロージャを作らざるを得ない。けれどもpがエスケープするのは
flagが真の場合だけなので、クロージャをアロケートしてから
flagが偽とわかったら無駄になる。
処理系としては次のような最適化をしてしまいたい。
(define (foo a flag) (bar (if flag identity (lambda (x) (+ x a)))))
この最適化自体は問題ない。
だが、コードがこうなったらどうだろう。
(define (foo a flag1 flag2)
(let ((p (lambda (x) (+ x a))))
(bar (if flag1 identity p)
(if flag2 identity p))))
同じ論理を適用するなら、こういう最適化が許されてほしい。
(define (foo a flag1 flag2)
(bar (if flag1 identity (lambda (x) (+ x a)))
(if flag2 identity (lambda (x) (+ x a)))))
しかしこの場合、二つのlambda式でクロージャの実体が別々に作られ得るので、 実体のアドレスで比較すると等しくならない可能性があるわけ。
もちろん、結果的に二つアロケートする羽目になるなら元コードに
比べて損するわけだけど、flag1とflag2が
共に#fになる確率が低い場合は必ずしも全体的に損だとは
言えないわけで、こういう最適化の可能性を切り捨ててしまうわけにはいかない。
このプログラム変換は特にクロージャに限った話ではない。
次のコードは複素数を「作って」それを条件的にbarに渡している:
(define (foo a flag1 flag2)
(let ((c (make-rectangular 1 a)))
(bar (if flag1 0 c)
(if flag2 1 c))))
これを次のように変換することには、何の問題もない:
(define (foo a flag1 flag2)
(bar (if flag1 0 (make-rectangular 1 a))
(if flag2 1 (make-rectangular 1 a))))
一般に、immutableなオブジェクトは、内容さえ同じなら、一度作ったものを使いまわそうが必要になる度に作ろうが関係ない(区別する必要がない)のだ。 (詳しくはHenry Bakerの"Equal Rights for Functional Objects or, The More Things Change, The More They Are the Same"参照)
そして、手続きというのはimmutableなオブジェクトである。 え、クロージャはmutableな状態を持ち得るじゃん、と思うかもしれないが、 mutableなのはクロージャが閉じ込んでいる環境の方で、手続きオブジェクト自体ではない。
struct procedure {
environment * const e;
const code * const c;
};
procedure->e の指してる先がmutableであっても、 構造体procedureはimmutableであって構わないわけ。
手続き自体がimmutableであるとしておくと、自由にコピーを作ったり、 あるいは中身が同じであるとわかる場合にひとつの実体にまとめてしまったり できるので、とても都合が良い。例えば次のコードであるが:
(define (foo a)
(let ((p (lambda (x) x)))
(bar p)))
pの実体はローカル環境を参照していないので、何度fooが呼ばれようが
全く同じ動作をする。従って次のように変換することで、fooを呼ぶ度に
手続きの実体をアロケートせずに済む。これはlambda liftingという変換の
基本的な場合で、Gaucheでもやっている。
(define G0 (lambda (x) x)) (define (foo a) (bar G0))
なお、「手続きオブジェクト」に色々な属性を後からつけられるようにしている 言語があるが、それをすると手続きはmutableなオブジェクトになってしまい、 多くのコンパイル時最適化手段が封じられてしまう。 一般的な実装では、手続きの定義箇所が実行される度に手続き実体をアロケート しなければならない。属性が変更され得るということは、「前回作られた手続き」 と「今回作られた手続き」が後から区別され得るということだから。
手続きに、ソースコード情報やら引数情報やらの属性を持たせるのはよくやることで、 処理系実装者としては「じゃあついでに任意の属性を後からでもつけられるように したら便利じゃね?」とかついつい考えがちなんだけど、そういう落とし穴もある。
閑話休題。
immutableなオブジェクトは実体がいくつあろうが関係ない、
というのは、オブジェクトの比較を実体のアドレスではなく内容で行うからだ。
Gaucheは複素数をヒープにアロケートするけれど、複素数の比較(eqv?)は
虚部と実部の等価性で判断するので、実体がメモリ上でもひとつなのか
別々なのかは気にする必要はないし、本来区別できない。
手続きがimmutableなら、手続きも内容で比較するのが正しい。はず、なのだけれど。
手続きの実体が上に書いたstruct procedureだと分かってるなら、
procedure->eとprocedure->cをそれぞれポインタ比較すれば
内容の比較になりそうだけれど、「言語仕様」としてはそこまで実装にべったりの
定義をしたくないわけだ。
クロージャの実装方法のバリエーションはいくらでもある。変更可能な 環境へのポインタを持つかわりに、環境のコピーを自分で持っておいて、 変更可能な部分だけをboxingしてあるかもしれない。 また、コード部分だって最適化の実装次第では「メモリ上では別の実体」 となっている可能性がある。実装の自由度を許容したまま「内容の等価性」を 定義することは非常に難しい。
かといって、実装に全く立ち入らずに「外から見て等しい動作をする手続きは等価である」 とするのも困る。「外から見て等しい動作をするかどうか」は 決定可能とは限らないからだ。
というわけで、手続きの等価性というのはかように面倒くさい問題で、 R6RSではそこそこ紛糾した結果として、「たとえ同じlambda式呼び出しで 作られたように見える手続きでも、等価かどうかは決めない」という選択をした。
ただねー、やっぱり
(let ((p (lambda (x) x))) (eqv? p p))
が未定義というのはどうも落ち着かない。 こういうコードを直接書くことはないにせよ、 pをハッシュテーブルやalistに入れて後で比較したりってことはあり得る。
そこでR7RSでは「コード上の起源が同じ手続きは同じ(eqv?)とする」とした。
上にあげたような最適化をやりたい場合は、
コード上のlambda式の評価で作られる手続きに実体の位置を示すtagを
つける、という考え方で説明できる。概念的にはこんな感じ:
(define (foo a flag1 flag2)
(let* ((tag (make-location-tag))
(p (lambda-with-tag tag (x) (+ x a))))
(bar (if flag1 identity p)
(if flag2 identity p))))
これで、同じtagを持てばeqv?である、ということにする。
これならlambda式自体が複製されても等価性は変わらない。
(define (foo a flag1 flag2)
(let ((tag (make-location-tag)))
(bar (if flag1 identity (lambda-with-tag tag (x) (+ x a)))
(if flag2 identity (lambda-with-tag tag (x) (+ x a)))))
但し、と大急ぎでつけたすけれど、R7RSでも(lambda (x) x)の
実体をシングルトンにして共有することは許されてるんで、
上のtagを使った形式はあくまで「実際に手続きの実体がアロケートされると
わかってから」の話である。「コード上の起源が同じなら等しい」は
保証されるが、「コード上の起源が別なら等しくない」は保証されないってこと。
Tags: Programming, Scheme, Gauche, R6RS, R7RS
2015/01/25
生物の分類
子供の宿題が難しい。"Protista"って何? "Eubacteria"って? と聞かれて 調べ始めたんだけど、なんか諸説入り乱れててわけがわからなくなりそうだ。
教材では次の6つに分類しているので、Woeseの六界説だな。
- Eubacteria (真正細菌)
- Archaea (古細菌)
- Protista (原生生物)
- Fungi (菌類)
- Plantae (植物)
- Animalia (動物)
落ち着いて考えてみたら自分らの時は確か五界説で、要は最初のふたつを 分けてなかっただけか? でも「モネラ界」なんて名前だったかなあ? (原核生物、と習ったような気もする。)
2015/01/23
入れ子のバッククオート
自分も良く迷うんだけど、一応簡単な指針がある。
まず、コンマのネストレベルとバッククオートのネストレベルを常に合わせるようにする。 次は良くない例：
``(list ,(+ 1 2))
これは(list ...)が2重のバッククオートの中にあるのに中でコンマを1重にしか使ってない。 規約上はバッククオートよりコンマのネストが少なければ動作はするけど、わかりづらくなるので避ける。
次に、「どのレベルのバッククオートで式を展開したいか」を考えて、 機械的に次の指針をあてはめる:
- 最初のレベル(外側)のバッククオートで式を展開したい場合はこうする:
,',式
- 最初のレベルでは展開せず、二番目(内側)のバッククオートで展開したい場合はこうする:
,,'式
ネストしたバッククオートが出てくる典型例はマクロ定義を生成するマクロだけれど、 その場合、最初のマクロ展開で埋め込みたい式は前者、生成されたマクロ定義の展開時に コンマとして機能させたい場合は後者を使う。
ちょっと手元に例として引けるコンパクトなコードがないので、わざとらしい例だけど、 例えば
(defmacro foo (x) `'(foo ,x))
みたいなマクロを名前を指定して生成するマクロ
(defmacro gen-defmacro (name) ...)
を考えよう。(gen-defmacro foo) とすると上の(defmacro foo ...)が生成される。(gen-defmacro bar)とするとこれが生成される：
(defmacro bar (x) `'(bar ,x))
まず、ここまではすぐ書けるだろう:
(defmacro gen-defmacro (name) `(defmacro ,name (x) `'(...)))
ここのnameはまだバッククオートが1重なので迷わない。問題はバッククオートがネストする...の部分だ。
- nameはgen-defmacroの展開時に埋め込みたい。つまり外側のバッククオートで展開
- xは生成されたdefmacroの展開時に埋め込む、つまり内側のバッククオートで展開
上の指針をあてはめればこの通り。
(defmacro gen-defmacro (name) `(defmacro ,name (x) `'(,',name ,,'x)))
実行例
[1]> (defmacro gen-defmacro (name)
`(defmacro ,name (x) `'(,',name ,,'x)))
GEN-DEFMACRO
[2]> (gen-defmacro foo)
FOO
[3]> (gen-defmacro bar)
BAR
[4]> (foo (a b c))
(FOO (A B C))
[5]> (bar (d e f)
(BAR (D E F))
3重以上のネストも基本的に同じ。ポイントは comma-quoteが互いにキャンセルするということ。後は右側から展開されてく。
,',',式 ; 一番外側のバッククオートで展開
,',,'式 ; 二番目のバッククオートで展開
,,','式 ; 三番目(最も内側)のバッククオートで展開
なお、バッククオートのネストレベルはコンマがあると下がるので、次のようなコードは ネストとは考えない：
`(list ,(list `(list ,x)))
外側のバッククオートはすぐ次のコンマと対応するんで、2番めのlistの式はネストレベルが0になる。
Tags: Programming, CommonLisp, Macro
2015/01/17
簡単で直交性の高い道具を組み合わせる
Explicit-renaming macroは何をやっているかが透明でわかりやすいのだけれど、 それだけでマクロを書くのは面倒だ。
Gaucheの低レベルマクロ機構で出したswap!マクロをもう一度取り上げてみよう。
まず、高レベルマクロのsyntax-rules版。
パターン置換だけで話が済むなら大抵はこれが一番簡潔。
(define-syntax swap!
(syntax-rules ()
[(_ a b)
(let ((tmp a))
(set! a b)
(set! b tmp))]))
swap!マクロならこれでいいんだけど、マクロ展開時にパターン置換だけではできない
計算をやろうとすると高レベルマクロでは限界がある。
syntax-case は高レベルマクロの「パターンマッチによる入力の分解機能(1)」および
「マクロ出力の組み立てで適切なリネーミングを行う機能(2)」をそのままに、
(1)と(2)の間に任意のScheme式による計算を入れることを可能にしたものだ。
(define-syntax swap!
(lambda (stx)
(syntax-case stx ()
[(_ a b)
(syntax
(let ((value a))
(set! a b)
(set! b value)))])))
この例では入力の分解と出力の組み立ての間にやる計算がないので あまり有難味はないけれど、必要なら取り出したaやbを使って複雑なことができる。
一方、ER macroは、hygienic macroに必要な最低限の機能、 つまり「環境を考慮した識別子の比較とリネーム」しか提供しない。 入力の分解と出力の組み立ては自分でやる必要があり、これはかなり面倒くさい。
(define-syntax swap!
(er-macro-transformer
(^[f r c]
(let ([a (cadr f)]
[b (caddr f)])
`(,(r'let) ([,(r'value) ,a])
(,(r'set!) ,a ,b)
(,(r'set!) ,b ,(r'value)))))))
けれども、入力の分解や出力の組み立てというのは、単なるS式の操作なのだから、 マクロシステムでわざわざ用意しなくても、一般のS式操作ライブラリを使えば良いともいえる。
パターンマッチによるS式の分解についてはGaucheはmatchを持っている。
出力の組み立てについては、「指定の式の識別子をリネームしつつ、必要な箇所に 計算結果を埋め込む」ようなマクロがあればよい。
(define-syntax quasirename-sub
(syntax-rules (unquote unquote-splicing)
[(_ rename ()) ()]
[(_ rename (unquote x)) x]
[(_ rename ((unquote-splicing x) unquote y)) (append x y)]
[(_ rename ((unquote-splicing x) . y)) (append x (quasirename-sub rename y))]
[(_ rename (x unquote y)) (cons (quasirename-sub rename x) y)]
[(_ rename (x . y)) (cons (quasirename-sub rename x)
(quasirename-sub rename y))]
[(_ rename x) (rename 'x)]))
(define-syntax quasirename
(syntax-rules ()
[(_ rename form)
(let ([xrename (lambda (x)
(if (or (symbol? x) (identifier? x))
(rename x)
x))])
(quasirename-sub xrename form))]))
これを使うと、ER macro版は次のとおり。
(define-syntax swap!
(er-macro-transformer
(^[f r c]
(match-let1 (_ a b) f
(quasirename r
(let ((tmp ,a))
(set! ,a ,b)
(set! ,b tmp)))))))
これで手間としてはsyntax-case版と変わらない。しかも、
- 入力の分解部分は普通のS式のパターンマッチャであり、 マクロ特有の事情を考慮する必要はない。 より強力なパターンマッチャを書けばそれを使うこともできる。
- 出力の構築部分はquasiquoteと同じセマンティクスである。 パターン変数が特別扱いされていないことに注目。aやbは単なるローカル変数束縛 なのだから、unquoteでその値が取り出せる、それだけである。 もちろんquasirename単独で使うこともできる。例えば識別子にプレフィクスを つけつつ、計算結果を埋め込みたい、とか。
syntax-caseやsyntax, quasisyntaxも裏では
似たようなことをやってるんだけど、マクロ特有のコンテキストを構文オブジェクトに
隠して持ち運んでいるので、応用が効かない。
(注: ここのquasirenameの定義だと、出力にunquoteやunquote-splicing
を含めるのが難しいので、unrenameとか別の名前を使った方が良いかもしれない。)
Tags: Programming, Gauche, Scheme, Macro
2015/01/12
Waldstein
アマチュアのピアノ愛好家有志による新年コンサートでヴァルトシュタインソナタを 弾かせてもらった。 これも子供の時から弾きたかった曲なのだ。
細かいところは相変わらずほつれているけど、 止まるとか余分な繰り返しみたいな大きな破綻は無かったかな。 (何か所か非常にやばい瞬間があるが…)
「芝居の時はあがらないのに演奏であがるのはなぜか」というのが ここ3～4年くらい考えていたテーマのひとつなんだけど、 今回また新たな知見が得られた。ような気がする。
舞台に立っている時の心理状態に、「入る」というのがある。 芝居が作り出す「場」に浸かっている状態。 マイズナーによる演技の定義は "Reacting truthfully to the imaginary circumstances" だが、 この "imaginary circumstances" が確固たるリアリティを持って 感じられている状態。この時はあがることがない。
舞台進行上、しかるべききっかけにしかるべき場所にいる、とか、 台詞を外さない、とかテクニカルに追わなくちゃならないことはたくさん あるんだけど、 場に対して素直に反応していれば演技が壊れることはないので、 そういうテクニカルな細々したものに振り回されることがなく、 むしろ余裕を持って対応できる。
(場に浸かっているからといって観客やら舞台装置やらが見えなくなるということはなく、 むしろそれらは明晰に見えていて、観客の反応や舞台装置の故障にも冷静に対応できる。)
芝居の訓練の多くは、必要なときに「入った」状態になるために 必要な準備の習得やそのための道具を揃えること、と言えるかもしれない。
演奏でも、音楽に「入る」状態があるようだ。出す音は全部意識してるんだけど、 何をどうすれば良いのかが自明な状態で、だから(脳からフィードフォワードで がちがちに制御するんではなく)出るべき音に身体をなるべく沿わせてやる感じ。
人前での演奏で上がりまくるというのは、うまく音楽「入る」ことができずに、 テクニカルなことを全て頭で制御しようとして、処理能力がパンクしているって ことかもしれないと思った。
今回も冒頭ではちゃんと入ってなくて、頭をフル回転させて制御しようとしてるんだけど、 第2主題の右手3連符のセクションに入るところの上行パッセージ(42小節目)、 処理が回らなくなってどの音を弾いてよいんだかわからなくなったことを覚えてる (んで、最後の拍は弾いてない)。 ただまあ、以前とは違って自分がそういう状態にあることは分かってたんで、 パニックにならずにどうにか前に進めたけど。
どこらへんかなあ、1楽章の展開部ではある程度入ってたのを覚えてる。 1楽章のコーダも間違いやすいんで普段は緊張するんだけど、 今回はかなり落ち着いてやれた。273小節1拍目の左手装飾音のAを外して、そのせいで 3拍目の左のスタート位置がわからなくなったんだけど、 ここは上のメロディさえ外さなければなんとなるだろ、と思いながら弾いてたり。
3楽章の難しいところで何度も抜けかけたけど、全体的に 鍵盤に大きな穴が開いてその向こうの世界に入り込む感覚がつかめつつあるので、 しばらくその感覚を追っかけてみよう。
Comments (0)