6.2.1 等価

Schemeには等価性を判定する汎用的な述語が3つあります。 また、これらの他に、いくつかの型はその型同士で使える比較手続きを持っています。

Function: eq? obj1 obj2 ¶

[R7RS base] 最も高速で、細かい区別ができる述語です。 obj1とobj2が同一(identical)のオブジェクト、 すなわち、メモリ上の同じオブジェクトを表している場合に#tを返します。 特に、二つのシンボルもしくは二つのキーワードが同一かどうかを比較するのにeq?が使えます。 ヒープアロケートされるオブジェクトに対しては、ポインタ比較と考えても良いでしょう。

真偽値もeq?で比較できますが、文字と数値はたとえ値が同じオブジェクトであっても 互いにeq?になるかどうかはわかりません。 同一性比較で文字や数値も扱う必要がある場合は、下のeqv?を使いましょう。

(eq? #t #t)               ⇒ #t
(eq? #t #f)               ⇒ #f
(eq? 'a 'a)               ⇒ #t
(eq? 'a 'b)               ⇒ #f
(eq? (list 'a) (list 'a)) ⇒ #f
(let ((x (list 'a)))
  (eq? x x))              ⇒ #t

Function: eqv? obj1 obj2 ¶

[R7RS base] obj1とobj2がともに正確な数値、もしくはともに (NaN、-0.0以外の)非正確な数値である場合、 (= obj1 obj2)が真であれば#tが、偽であれば#fが 返されます。 -0.0は-0.0とだけeqv?です。

obj1とobj2がともに文字である場合、 (char=? obj1 obj2)が真であれば#tが、偽であれば#fが 返されます。 それ以外の場合は、Gaucheではeqv?はeq?と同じです。

(eqv? #\a #\a)             ⇒ #t
(eqv? #\a #\b)             ⇒ #f
(eqv? 1.0 1.0)             ⇒ #t
(eqv? 1 1)                 ⇒ #t
(eqv? 1 1.0)               ⇒ #f
(eqv? (list 'a) (list 'a)) ⇒ #f
(let ((x (list 'a)))
  (eqv? x x))              ⇒ #t

NaNの比較には少々奇妙なところがあります。数値比較は、引数に一つでもNaNが 含まれていれば失敗します。したがって(= +nan.0 +nan.0)は常に#fと なります。けれども、(eq? +nan.0 +nan.0) や (eqv? +nan.0 +nan.0)は#tを返すことがあるかもしれません。

Function: equal? obj1 obj2 ¶

[R7RS+ base] obj1とobj2がリストやベクタなどの複合型である場合、 equal?は再帰的に対応する要素同士をequal?で比較してゆきます。 そうでなければ、equal?はeqv?と同じようにふるまいます。

もしobj1とobj2が互いにeqv?でなく、 組み込み型でもなく、かつ両者のクラスが等しい場合、equal?は ジェネリックファンクションobject-equal?を呼びます。 object-equal?にメソッドを定義することにより、 ユーザ定義のデータ型に対するequal?の振るまいを拡張することができます。

(equal? (list 1 2) (list 1 2)) ⇒ #t
(equal? "abc" "abc")           ⇒ #t
(equal? 100 100)               ⇒ #t
(equal? 100 100.0)             ⇒ #f

;; 0.0と-0.0は数値としては等しい(=)ですが、eqv?は区別し、したがってequal?も区別します。
(equal? 0.0 -0.0)              ⇒ #f

註: この手続きは、obj1とobj2がともにペアやベクタを介した 循環構造を持っている場合もR6RSやR7RSに規定されるように値を返します。 ただし、循環構造がユーザ定義データ型を間に挟んでいる場合は 終了しない可能性があります。

Generic Function: object-equal? obj1 obj2 ¶

equal?が未知のオブジェクトに対して呼ばれた場合、 このジェネリックファンクションが呼ばれます。自分で定義したクラスに対して このメソッドを定義することにより、equal?で等価判定が行えるように なります。メソッドは、obj1とobj2が等価ならば#tを、 そうでなければ#fを返さねばなりません。 オブジェクトの各要素に対して再帰的に等価判定を行いたい場合は、 object-equal?を直接呼ぶのではなく、equal?を各要素に対して 呼ぶようにして下さい。

(define-class <foo> ()
  ((x :init-keyword :x)
   (y :init-keyword :y)))

(define-method object-equal? ((a <foo>) (b <foo>))
  (and (equal? (slot-ref a 'x) (slot-ref b 'x))
       (equal? (slot-ref a 'y) (slot-ref b 'y))))

(equal? (make <foo> :x 1 :y (list 'a 'b))
        (make <foo> :x 1 :y (list 'a 'b)))
  ⇒ #t

(equal? (make <foo> :x 1 :y (make <foo> :x 3 :y 4))
        (make <foo> :x 1 :y (make <foo> :x 3 :y 4)))
  ⇒ #t

Method: object-equal? (obj1 <top>) (obj2 <top>) ¶

このメソッドは、ユーザ定義クラスの2つのインスタンスがequal?であるかを 調べる際に、そのクラスに特殊化したメソッドが無かった場合を捕まえるものです。

このメソッドが呼ばれると、まず登録されたデフォルト比較器の中にobj1と obj2を共に処理できるものがあるかどうかを調べ、 あればその比較器の等価述語を使って比較します。デフォルト比較器が引数を処理できなければ #fを返します。デフォルト比較器については 用意されている比較器を参照してください。特に default-comparatorとcomparator-register-default!の 項目を見てください。

註: もし、このメソッドと全く同じスペシャライザを 指定してobject-equal?メソッドを定義すると、それはこのメソッドを 置き換えることになり、default-comparatorの動作が壊れることになります。 将来のGaucheのバージョンではそのような再定義は禁止される予定です。 うっかりそういう再定義を行わないように気をつけてください。

しばしば、ふたつの複合型オブジェクトに関して、両者がトポロジー的に等しいこと、 すなわち一方が共有する部分構造を持っている場合にもう一方も同じように部分構造を 共有しているかどうかを調べたいことがあります。equal?はその目的には 使えません。モジュールutil.isomorphの提供するisomorphic?が その目的に使えます。(util.isomorph - 同型判定参照)。

---

6.2.2 比較

等価性はオブジェクトが等しいかどうかしか判断しませんが、しばしば オブジェクトの順序関係を調べたい場合もあります。 ここでも、唯一の「万能順序」があるわけではありません。例えばある複素数が 別の複素数より大きいか小さいかというのは数学的には意味をなしませんが、 数値を含むオブジェクトのリストをソートして一貫性のある結果を得たい場合は 何らかの適当な順序づけを決めておくことは役に立ちます。

Function: compare obj1 obj2 ¶

一般的な比較手続きです。obj1がobj2より小さければ-1を、 等しければ0を、大きければ1を返します。

obj1とobj2が比較できない場合はエラーとなりますが、 compareは多くのSchemeオブジェクト間に全順序を定義しているので、 様々なオブジェクトの比較に使うことができます。この全順序は、 SRFI-114で定義されているものの上位互換です。

組み込みオブジェクトのうち、自然な順序が定義されているものはそれに従って順序づけられます (例えば実数はその数値の大小で、文字はchar<等を使って比較されます)。 また便宜上、通常の意味で大小が定義されないオブジェクトについても ある程度表面的な順序が定義されます。例えば複素数は、まず実部の大小によって 順序づけられ、次に虚部の大小によって順序づけられます。 すなわち、1+i、2-i、2、2+iはこの順番に並びます。

#fは#tより前に来ます。

リストは辞書順で比較されます。すなわち、まず共通のプリフィクスを除きます。 一方が()でもう一方がそうでなければ、()である方が先にきます。 どちらの尾部も空でなければ、尾部の先頭要素同士を比べます。 (この定義により、空リストは全てのリストの「最小」のものになります)。

(ユニフォームベクタを含む)ベクタは、まず長さで比較され、 長さが同じ場合は要素同士が左から比較されます。 リストや文字列とは異なることに注意。

(compare '(1 2 3) '(1 3))
  ⇒ -1  ; (1 2 3) is smaller
(compare '#(1 2 3) '#(1 3))
  ⇒ 1   ; #(1 3) is smaller
(compare "123" "13")
  ⇒ -1  ; "123" is smaller

二つのオブジェクトがともに<object>のサブクラスであれば、 ジェネリックファンクションobject-compareが呼ばれます。

二つのオブジェクトが異なる型で、少なくとも一方が<object>でない時は、 両者の型により順序が決まります。SRFI-114は組み込み型について 次の順序を定めています。

1. Empty list.
2. Pairs.
3. Booleans.
4. Characters.
5. Strings.
6. Symbols.
7. Numbers.
8. Vectors.
9. Uniform vectors (u8 < s8 < u16 < s16 < u32 < s32 < u64 < s64 < f16 < f32 < f64)
10. 他のオブジェクトすべて

Generic Function: object-compare obj1 obj2 ¶

このジェネリックファンクションを特殊化することで compare手続きをユーザ定義クラスに対して動作するように拡張できます。

このメソッドは以下のいずれかの値を返さねばなりません。 -1 (obj1はobj2より前)、 0 (obj1とobj2は等しい)、 1 (obj1はobj2より後)、 #f (obj1とobj2は順序づけできない)。

Method: object-compare (obj1 <top>) (obj2 <top>) ¶

このメソッドは、ユーザ定義クラスの2つのインスタンスをcompareする 際に、そのクラスに特殊化したメソッドが無かった場合を捕まえるものです。

このメソッドが呼ばれると、まず登録されたデフォルト比較器の中にobj1と obj2を共に処理できるものがあるかどうかを調べ、 あればその比較器の比較手続きを使って両者の順序を判定します。 デフォルト比較器が引数を処理できなければ #f(「比較できない」)を返します。デフォルト比較器については 用意されている比較器を参照してください。特に default-comparatorとcomparator-register-default!の 項目を見てください。

註: もし、このメソッドと全く同じスペシャライザを 指定してobject-compareメソッドを定義すると、それはこのメソッドを 置き換えることになり、default-comparatorの動作が壊れることになります。 将来のGaucheのバージョンではそのような再定義は禁止される予定です。 うっかりそういう再定義を行わないように気をつけてください。

Function: eq-compare obj1 obj2 ¶

とある全順序に従ってobj1とobj2を比較し、前者が小さければ-1、 等しければ0、前者が大きければ1を返します。obj1とobj2は どんなSchemeオブジェクトでも良く、また型が違っていても構いません。 次の二つの性質が保証されます。

• (eq? x y)が#tなら、そしてその時に限り、 (eq-compare x y)は0。
• 結果は、一回のプロセスの実行中で一貫している (ただし、別のプロセスの実行では異なる結果を返すかもしれない)。

これらの性質以外には、順序についていかなる意味もありません。

この手続きは、任意のSchemeオブジェクトをとにかく順序づけたい (一貫してさえいれば、実際の順序は何でも良い)、という場合に使います。

---

6.2.3 ハッシュ

ハッシュ関数は等価判定述語と関係が深いので、ここで説明します。

Function: eq-hash obj ¶

Function: eqv-hash obj ¶

この2つはそれぞれeq?および eqv?と一緒に使うのに適した ハッシュ関数です。返り値のハッシュ値は、 システムおよびプロセスに依存する値です。動作しているプロセスの境界を 超えてもちまわることはできません。

注意: eq-hash をつかって、数をハッシュしてはいけません。 2つの数はたとえその値が等しくても eq? であることは保証されて いません。

Function: default-hash obj ¶

[R7RS+ comparator] equal?と一緒に使うのに適したハッシュ関数です。 R7RSでは、scheme.comparatorライブラリで定義されています (元はsrfi.128)。

obj が、数値、真理値、文字、シンボル、キーワード、文字列、リスト、 ベクタ、ユニフォームベクタのいずれかならば、そのハッシュ値を求めるのには内部ハッシュ関数を 使います。 obj が、それ以外であれば、 hash は総称関数 object-hash を呼んで、そのハッシュ値を計算します。

返されるハッシュ値はhash-saltの値にも依存します。hash-salt はプロセスが走る度に異なる値をとります。

Function: portable-hash obj salt ¶

時に、「ポータブル」なハッシュ値が必要になることがあります。ここでポータブルとは、 プロセスを何度実行しても、また異なるプラットフォームで実行しても、同じオブジェクト に対して常に同じ値となることです。そのようなハッシュ値は、 プロセスの外に保存したり他のプロセスと共有するオブジェクトと一緒に使えます。

この手続きはobjについてその性質を持つハッシュ値を計算して返します。 つまり、同じオブジェクトと同じソルト値が渡されれば同じハッシュ値となる、ということです。 ここで、「同じオブジェクト」とは、だいたい外部表現が同じになるものと 考えて構いません。equal?であるもの同士は同じです。 また、オブジェクトをwriteで書き出してreadで読み込んだものは 元のオブジェクトと同じになります。

このことから、read/write不変性をもたないオブジェクトはportable-hash では扱えません。objがそのようなオブジェクトを含まないことは 呼び出し側で保証する必要があります。

saltは非負のfixnumで、ハッシュ関数に変化をつけます。一貫した結果を 得るには同じソルト値を使わなければなりません。

objが数値、真理値、文字、シンボル、キーワード、文字列、リスト、 ベクタ、ユニフォームベクタのいずれでもない場合、ハッシュ値を計算するのに 総称関数 object-hashが呼ばれます。

Function: legacy-hash obj ¶

バージョン0.9.4まで、Gaucheではhashと呼ばれるハッシュ関数が equal?ハッシュテーブル用のハッシュ計算と ポータブルなハッシュ値の計算の両方を兼ねていました。 しかしそれには問題がありました。

1. ハッシュ関数にソルトを与えることができなかったため、 外部からのデータによる衝突攻撃が可能だった
2. ハッシュ関数自体があまり良くなかった(特に浮動小数点数)
3. 多倍長整数と浮動小数点数のハッシュ値計算で、 異なるアーキテクチャで異なる値を返してしまうバグがあった。

既にhashで計算されたハッシュ値を利用しているデータがあるため、 以前のhashで提供していたハッシュ関数をlegacy-hashとして 保存することにしました。古いデータにアクセスする場合に使ってください。 (hash関数自体もデフォルトでは legacy-hashと同様に振る舞いますが、ちょっとした仕掛けがあります。 下の説明を参照)。

新たに書くコードでポータブルなハッシュ値が必要なら portable-hashを使ってください。

Generic Function: object-hash obj rec-hash ¶

この総称関数に対するメソッドを定義することにより、ユーザ定義された 型のオブジェクトはハッシュ値を持つことができ、equal?型のハッシュ テーブルで利用できるようになります。

メソッドは正確な非負整数を返さなければなりません。また、 互いにequal?であるオブジェクト同士に対しては同じハッシュ値を 返さなければなりません。 さらに、objがポータブル(「ポータブル」の意味については 上のportable-hashの説明を参照)の場合には、 ハッシュ値は実行中のプラットフォームやプロセスの状態に依存してはなりません。

メソッドが obj の要素のハッシュ値を必要とする場合には、 それらに対して、rec-hashを呼び出してください。そうすれば 適切なハッシュ関数が再帰的に呼び出されます。例えばobject-hashが portable-hash経由で呼び出されている場合、 rec-hashを呼べば同じソルト値でポータブルなハッシュ値が計算されます。

objがいくつかの要素を持っている場合、各要素のハッシュ値を まとめるにはcombine-hash-valueを呼びます。

(define-class <myclass> () (x y))

;; user-defined equality function
(define-method object-equal? ((a <myclass>) (b <myclass>))
  (and (equal? (ref a 'x) (ref b 'x))
       (= (abs (ref a 'y)) (abs (ref b 'y)))))

;; user-defined hash function
(define-method object-hash ((a <myclass>) rec-hash)
  (combine-hash-value (rec-hash (ref a 'x))
                      (rec-hash (abs (ref a 'y)))))

註: object-hashのベースメソッドは、どんな引数に対しても 単一の値を返します (具体的な値は、object-hashが default-hashから呼ばれた場合はhash-saltに依存します。 それ以外の場合は固定値です)。 これは、オブジェクトの等価性が自由に設定できるからで、 等価性を知らずに意味のあるハッシュ値を計算できないあらです。

この振る舞いは最後の安全ネットと考えるべきで、一般には自分で定義したクラスのインスタンスが ハッシュされる可能性があるなら、必ずobject-hashメソッドを定義するように してください。

Method: object-hash (obj <top>) rec-hash ¶

Method: object-hash (obj <top>) ¶

これら二つのメソッドはシステムで定義されており、 後方互換性およびdefault-comparatorの正しい振る舞いを保証しています。 全く同じスペシャライザを持つメソッドを定義することでこれらを置き換えてしまわないように 注意してください。将来のバージョンでは、これらのメソッドを置き換えるのは エラーになる予定です。

Function: combine-hash-value ha hb ¶

二つのハッシュ値haとhbを組み合わせたハッシュ値を返します。 次の性質が保証されます：(= ha1 ha2) かつ (= hb1 hb2) ならば (= (combine-hash-value ha1 hb1) (combine-hash-value ha2 hb2))。 これはユーザ定義のobject-hashメソッドを書くのに便利です。

Function: hash obj ¶

この関数は非推奨となりました。

equal?ハッシュとして使える、objのハッシュ値を返します。 デフォルトでは、この関数はlegacy-hashと同じ値を返します。 しかし、この関数がdefault-hashかportable-hashから (object-hashを経由して)呼ばれた場合は、呼び出したハッシュ関数へと 再帰します。

この振る舞いは既存のコードを動かすためのものです。0.9.5より前は、 hashが、ポータブルなハッシュ値にもequal?ハッシュテーブルにも 使えるハッシュ値を計算する唯一の関数でした。object-hashメソッドは ハッシュ値を計算したいオブジェクトだけを引数に取り、もしそのオブジェクトが 指す他のオブジェクトのハッシュ値が欲しいなら、hashを再帰呼び出ししていました。

0.9.5から、object-hashはいくつかのハッシュ関数から呼び出されるようになり、 第2引数に再帰すべきハッシュ関数を取るようになりました。 けれども既存のコードを動かなくしてしまうわけにはいきません。そこで、 object-hashのデフォルトメソッド(2引数でマッチするメソッドが 無い場合に呼ばれるもの)が、1引数のobject-hashを呼び出すように 定義されています。既存のobject-hashがhashを呼び出していれば、 正しいハッシュ関数へと再帰するというわけです。 新たに書くコードはこの振る舞いに依存してはいけません。 2引数のobject-hashメソッドを定義してください。

Function: boolean-hash bool ¶

Function: char-hash char ¶

Function: char-ci-hash char ¶

Function: string-hash str ¶

Function: string-ci-hash str ¶

Function: symbol-hash sym ¶

Function: number-hash num ¶

[R7RS comparator] これらは、R7RSのscheme.comparatorで定義された、 特定の型のオブジェクト専用のハッシュ関数です。 Gaucheでは、これらの関数は単に引数の型チェックをして(必要なら大文字小文字の 区別をなくした後)、組み込みのdefault-hashを呼び出しているだけです。 これらはscheme.comparatorで定義されているために提供されていますが、 特にポータビリティが必要でなければdefault-hash (あるいは、等価述語によってはeq-hashや eqv-hash)を呼んでしまう方が簡単だし高速です。

大文字小文字を区別しない、char-ci-hashおよびstring-ci-hashは、 引数にそれぞれchar-foldcaseとstring-foldcaseを適用してから hashに渡します。 (char-foldcaseについては文字を、 string-foldcaseについてはフルセットの大文字小文字変換を 参照してください。)

Function: hash-bound ¶

Function: hash-salt ¶

[R7RS comparator] どちらも、正確な非負整数へと展開されます。R7RSでは、 scheme.comparatorライブラリで定義されています。

(註: scheme.comparatorはこれらをマクロと定義しています。処理系が ランタイムオーバヘッドを避けられるようにするためです。 Gaucheでは、呼び出しのオーバヘッドはそれほど問題にならないという 立場から、どちらも手続きにしています。)

ユーザ定義のハッシュ関数は、 結果を0と(hash-bound)の間に限定してもハッシュの質を落とさないことが 保証されます。(ユーザ定義のハッシュ関数は(hash-bound)を気にする 必要はありません。ハッシュテーブルが必要な時にモジュロを取ります)。

ユーザ定義のハッシュ関数はまた、(hash-salt)を計算に組み入れることが できます。展開されるソルト値は、Schemeプロセスの実行ごとに異なる値を 取ったり、ハッシュテーブルごとに異なる値を取るかもしれません。 これは、コリジョン攻撃を回避するためのものです。 組み込みのハッシュ関数は既にソルト値を考慮しているので、 ユーザ定義ハッシュ関数がプリミティブ型のハッシュ値を組み合わせるだけの 場合は、ソルト値を気にする必要はありません。

---

6.2.4 基本的な比較器

等価性判定と大小比較は色々なデータ構造のパラメータになっています。 treemapはキーの大小を比較します。ハッシュテーブルはキーが等しいかどうかを調べ、 またハッシュ関数と等価性判定に一貫性が無ければなりません。

ジェネリックなデータ構造を作りたければ、こういった比較についてのバリエーションを 抽象化する必要があります。そのために導入されたのが比較器(comparator)です。 これは、比較について関係の深いいくつかの手続きをまとめた構造体です。

比較器を定義したSRFIは二つあります。SRFI-128と呼ばれていた規格は R7RS largeに取り込まれ、scheme.comparatorになりました。 新しいコードではそちらを使うべきです。 Gaucheはscheme.comparatorのAPIを全て組み込みで提供します。 古く、より複雑なのがSRFI-114で、Gaucheはそちらは主に後方互換性のために サポートしています。重要なのは、Gaucheの組み込みの<comparator>オブジェクトは scheme.comparatorの比較器としても SRFI-114の比較器としても使えるということです。

• 比較器クラスとコンストラクタ:
• 比較器にまつわる述語とアクセサ:
• 用意されている比較器:
• 比較器を組み合わせる:

---