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