SRFI 67: Compare Procedures

This SRFI is currently in ``final'' status. To see an explanation of each status that a SRFI can hold, see here. To provide input on this SRFI, please email mailto:srfi-67@srfi.schemers.org. See instructions here to subscribe to the list. You can access the discussion via the archive of the mailing list. You can access post-finalization messages via the archive of the mailing list.

• Received: 2005/04/01
• Revised: 2005/05/24
• Revised: 2005/08/18
• Final: 2005/09/11

August 18, 2005

目次

• 1 概要と論理的根拠
• 2 はじめに
• 3 用語と慣習
• 4 仕様
  • 4.1 アトムの比較
  • 4.2 リスト、ベクタの比較
  • 4.3 ペア、非真正リストの比較
  • 4.4 デフォルトの比較手続き
  • 4.5 比較手続きを作る
  • 4.6 比較手続きを使う
• 5 比較手続きの理論
• 6 設計原理
• 7 関連研究
• 8 リファレンス実装

Copyright (c) 2005 Sebastian Egner and Jens Axel Søgaard.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the ``Software''), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED ``AS IS'', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

1 概要と論理的根拠

この SRFI は R⁵RS 標準の述語 =, <, char<? 等の拡張、もしくは置き換えとさえ言えるかもしれない。 この SRFI の設計の主要な特徴は、全順序の表現と その使用の分離である。 順序の表現法として、我々は真の三元比較をを選択した。 これを使うために、多数の操作を提供した。 これらの操作はそれぞれ比較のための関数を受け取る。 比較手続きは大抵省略可能であるため、組み込みの型の比較は R⁵RS と同等、もしくは時にはより使い勝手がよくなっている。 例えば、整数の添え時 i が {0, ..., n - 1} の範囲にあるかどうか、というテストは (<=/<? 0 i n) と書くことができるが、 これは暗默に default-compare を呼び出す。

新しい全順序が必要になった場合には、 スクラッチからそのような全順序をつくるよりも、 この SRFI で提供される仕組みを使う方が はるかに便利で、大抵の場合より効率的である。

また、Scheme ユーザーや実装者がこの仕組みを便利だと思い採用すれば、 データ構造の全順序関係の統一的なインタフェースをもつ利点が 明白になるだろう。いちばん具体的な例を挙げると、この SRFI の精神にもとづいたソート手続きは、 (my-sort [ compare ] xs) のようになっていて、compare が省略された場合には default-compare を使うようなインタフェースになるであろう。そして、 my-sort はこの SRFI ので提供される仕組み （例えば、効率のよい二項・三項分岐、関係連鎖のテスト、ペア単位の不等、 最大値・最小値、一般統計）をつかって定義できるのである。

2 はじめに

この SRFI は Scheme の値を全順序[1] （線型順序）で比較する仕組みを定義する。 提供される操作は以下の通りである。

1. 組み込みオブジェクトの比較
2. プログラム中で現れる全順序の利用
3. 新たな全順序を定義する仕組み

続いて、これらの側面について詳しく説明する。

Scheme では伝統的に全順序関係を < や char<? のような順序述語で表現していたが、 この SRFI では全順序関係を手続きで表現する。 この手続きは引き数をふたつとり、ひとつめの方が小さい場合、 等しい場合、より大きい場合にそれぞれ -1、0、1 を返す。 このような比較手続きとしては、例えば実数を比較する (lambda (x y) (sign (- x y))) や、 任意のオブジェクトを比較する (lambda (x y) 0) などがある。 Revised⁵ Report on the Algorithmic Language Scheme （R⁵RS , [3]） のほとんどの組み込み型を比較する手続きは、この SRFI の 4.1 節、4.2 節、4.3 節に規定されている。 比較手続きの公理的定義は 5 節で与えられる。

（二値の）順序述語の代わりに三値の比較手続きを使う第一の理由は、 効率である。比較操作の計算量が大きい場合、三値比較一度で済むところで 述語を二回呼ぶのは無駄である。この点については 6 節でさらに詳しく議論する。

しかし、三値比較をアプリケーションプログラムで直接扱うのは 不便であるし、書き手の意図を曖昧がなってしまう。 例えば、x < y かどうかをテストするのに (eqv? (compare x y) -1) のように書かなければならなくなってしまうのだ。 そのため、<? という操作を提供し、同じテストを (<? compare x y) と書けるようにした。 これは、比較操作のみっつの出力値をふたつの真理値 {#f, #t} に写像する例である。 <? は全順序関係を明示的に引き数としてとるため、 それぞれの全順序関係すべてについて簡単にテスト用の道具箱を 用意することができる（4.6 節）。 これは、操作が = , <, >, ≤, ≥ のいつつだけで、 real/number、char、 char-ci、string のそれぞれの全順序関係にこれらの操作を提供するという R⁵RS のアプローチとは大きくことなることになる。

しかし、それでもまだ、<? に比較手続きを毎回明示的に渡さなければならないというのは 使い勝手がわるいだろう。そこで、この SRFI では compare パラメータを大抵の場合に省略できるようにし、 比較手続きが明示的に渡されなければ default-compare 手続きが使われることにした。default-compare （4.4 節）は、R⁵RS の組み込み型に妥当な全順序関係を定義している。

この SRFI の第三の特徴、比較手続きの定義のためには、 特別な制御構造（マクロ）が提供されている。 これらの制御構造は（潜在的に再帰的な）比較手続きの定義に使うことができる。 これについては例をあげて説明するのがいちばんわかりやすいだろう。

例

物理的な長さをあらわす型 length があるとしよう。 この型には長さをメートル単位の実数で返す meters というアクセサ手続きがある。そして長さの比較手続きは real-compare （4.1 節参照）を使うと下のように定義できる。

(define (length-compare length1 length2)
  (real-compare (meters length1) (meters length2)))

そして、(<? length-compare x y) は、長さ x が y よりも短いかどうかをテストする。同様に、 (<=/<? length-compare a x b) は、x が長さ a 以上で b 未満かどうかをテストする。(min-compare length-compare x y z) は、長さ x、y、z のうちいちばん短いものを返す。 さらに、(chain<? length-compare x1 x2 x3 x4) は、長さ x1、x2、x3、x4 が正確に増加しているかどうかをテストする （以下 4.6 節を参照）。

また、ここで、box という箱をあらわす型について考えよう。 この型には width、height、depth という寸法を length として返す手続きがある。 箱の比較手続きは、まず幅で比較し、次に高さ、その次に奥行きで比較する。 この手続きは 4.5 節の refine-compare という制御構造を使うと以下のように定義できる。

(define (box-compare box1 box2)
  (refine-compare
   (length-compare (width box1) (width box2))
   (length-compare (height box1) (height box2))
   (length-compare (depth box1) (depth box2))))

このとき、(<? box-compare b1 b2) は箱 b1 が箱 b2 よりも、 定義した順序にもとづいて小さいかをテストする。 もちろん、ほかの述語や、最小値・最大値といったものも同様に 使用可能である。

最後に複雑な例として、 radius（length を返す）、open? （真理値を返す）というアクセサのある bowl 型について考えよう。 ボウルはまず、開いているか閉じているかで比較され、次に半径で比較される。 さらに、ボウルと箱を互いに比較する必要がある場合、 ボウルは箱よりも「小さい」とする（box?、 bowl? という型検査述語があるものとする）。 4.5 節の select-compare という制御構造を使うと、次のように書くことができる。

(define (container-compare c1 c2)
  (select-compare c1 c2
                  (bowl? (boolean-compare (open? c1) (open? c2))
                         (length-compare (radius c1) (radius c2)))
                  (box? (box-compare c1 c2))
                  (else "neither bowls nor boxes" c1 c2)))
    

これは、5 節で説明する 比較手続きの「階層型拡張」の例である。 bowl? の場合に暗默に refine-compare が使われていることにも気をつけてほしい。

ここまでの例で、この SRFI の主だった機能を説明した。 これ以外の例については 4.4 節とリファレンス実装に含まれる examples.scm を参照のこと。

3 用語と慣習

比較手続き は引き数をふたつとり、 何らかの全順序関係に従って有効な入力値を順序づけ、 正確な整数 { -1, 0, 1 } を返す Scheme 手続きをいう。 比較手続きとそれに適用可能な Scheme 値を合わせたものは 5 節で定義する比較関数に相当する。

比較 はふたつの値に比較手続きを適用すること、 もしくはそのような式の結果をいう（訳注: 原文 comparison。 訳文では適宜「比較操作」、「比較結果」と言い換えたところがある）。

それぞれの操作（マクロないし手続き）は比較操作の値が実際に { -1, 0, 1} に含まれるかをチェックし、これを満たさない場合は エラーを通知する。

特定の型を期待する比較手続きは、引き数がその型でない場合には エラーを通知する。この SRFI で規定されているほとんどの比較手続きは このようなふるまいをする必要がある。 比較手続き compare は、必要であれば、 (compare x x) のようにして x の型を検査することができる。 これは、chain<? のように、 それぞれの引き数を無条件にチェックするような手続きで便利である。

4 仕様

4.1 アトムの比較

この節では R⁵RS のアトム型のほとんど — 真理値、文字、文字列、シンボル、数値 — に対する比較手続きを定義する。

一般的な命名規則として、 type-compare-order という名前の手続きは、type 型のオブジェクトふたつを order について全順序で比較する。 order はニーモニックヒントである（例えば、 -ci は case insensitive である）。もちろん、ひと通りの順序しかない場合や、順序が明白な場合には -order がないこともある。 特定の型のオブジェクトを受けつける手続きを別の型のオブジェクトを 引き数にして呼び出すとエラーになる。

procedure: (boolean-compare bool1 bool2)

真理値を比較する。 #f < #t である。

注: #f 以外の値であっても真とは解釈しない。 そのような値を渡すとエラーが通知される。

procedure: (char-compare char1 char2)

procedure: (char-compare-ci char1 char2)

それぞれ、文字を char<=?、 char-ci<=? のように比較する。-ci は "case-insensitive" の謂である。

procedure: (string-compare string1 string2)

procedure: (string-compare-ci string1 string2)

それぞれ、文字列を string<=?、 string-ci<=? のように比較する。-ci は "case-insensitive" の謂である。

注: compare-string は以下のように定義できる。

(define (string-compare string1 string2)
  (vector-compare-as-list char-compare
                          string1 string2
                          string-length string-ref))

procedure: (symbol-compare symbol1 symbol2)

シンボルを、symbol->string の返した名前を string<= で比較したように比較する。

procedure: (integer-compare x y)

procedure: (rational-compare x y)

procedure: (real-compare x y)

procedure: (complex-compare x y)

procedure: (number-compare x y)

ふたつの数値を比較する。 引き数の型が手続きの名前で指定されたものでなかった場合は エラーを通知する。

複素数は (re, im) のペアの辞書順で比較される。実数をあらわす型については sign(x - y) で計算される。 real? ないし complex? を満たしながら、 実数ないし複素数を表現しない値については、 — それが規定されていないということは別にしておいて — R⁵RS の = と < と整合性のある順序にならなければならない。

数値の比較手続きは R⁵RS の数値型の階層と 互換性がある。つまり、S が数値型 T の下位型で、x、y が S、T 両方で表現可能なら、 compare-S と compare-T は同じ結果を返す。

注: 浮動小数点形式は普通、実数で簡単には表せないシンボル値を含んでいる。 例えば、IEEE 754 標準では -0、-Inf、+Inf、NaN （not a number） といったものを、エラー状態の存在するもとで計算を続けるために 定義している。このような特別なシンボルが引き数の場合の 数値の比較操作のふるまいは未定義である。

警告: 不正確性の伝播は驚くべき結果をもたらすことがある。 ある Scheme システム（例えば、PLT Scheme version 208）では 複素数の不正確性の伝播により次のような結果が得られる。

(complex-compare (make-rectangular (/ 1 3) 1.)
                 (make-rectangular (/ 1 3) -1))
 ===> -1

一見したところでは、それぞれの実部は等しく、 ひとつめの虚部 1. はふたつめの虚部 -1 よりも大きいため、ひとつめの複素数の方が大きいと思うだろう。 だが、よく見ると、複素数の構築時に 虚部の小数点によりひとつめの複素数の実部は不正確な数になる、 さらに実装の使っている浮動小数点フォーマットでは (exact->inexact (/ 1 3)) が (/ 1 3) よりも小さくなるため、この実部からこのふたつの複素数の比較結果が 決まることがわかる。

4.2 リスト、ベクタの比較

この節では Scheme のリストとベクタ、さらにリストやベクタのように アクセスできるオブジェクトの比較手続きを定義する。

オブジェクト x について、手続き size、ref が定義されてい、 (size x) が要素数をあらわす負でない整数 n を返し、(ref x i) （i ∈ {0, ..., n - 1}）が x の i 番目の要素を返す場合、 x はベクタのようにアクセスできるという。

オブジェクト x が（真正）リストのようにアクセスできる というのは、手続き empty?、head、tail があり、(empty? x) が x に要素がないかどうかをあらわす真理値を返し、 (head x) が x の最初の要素、 (tail x) が残りの要素を表すオブジェクトを 返すような場合をいう。デフォルトのリストアクセス手続きは null?、car、cdr である。

要素のアクセス方が異なるため、 ベクタとリストとでは自然な順序関係が異なっている。 より短いシーケンスが小さく、同じサイズの場合には辞書式に 比較される場合、そのシーケンスはベクタ風に比較されるという。 空のシーケンスがもっとも小さく、ふたつのシーケンスが空ではない場合、 それぞれの先頭の要素を比較し、その要素が等しくない場合にだけ 再帰的に残りの要素を比較するような場合、そのシーケンスは リスト風に比較されるという。

procedure: (vector-compare [ compare ] x y [ size ref ])

procedure: (vector-compare-as-list [ compare ] x y [ size ref ])

procedure: (list-compare [ compare ] x y [ empty? head tail ])

procedure: (list-compare-as-vector [ compare ] x y [ empty? head tail ])

ふたつのシーケンス x、y を比較する。 要素の比較には compare を用いる。 結果は { -1, 0, 1} のいずれかである。 compare が省略された場合には default-compare が使われる。

access-compare-as-order という名前の手続きは、オブジェクトを access のようにアクセスし、order で与えられた順序に従って 比較を行う。type-compare という名前は type-compare-as-type の略である。

例:

(list-compare '(2) '(1 2))             ===>  1
(list-compare-as-vector '(2) '(1 2))   ===> -1
(vector-compare '#(2) '#(1 2))         ===> -1
(vector-compare-as-list '#(2) '#(1 2)) ===>  1

4.3 ペア、非真正リストの比較

この節では Scheme のペア、非真正（の可能性のある）リストの 比較手続きを定義する。

procedure: (pair-compare-car compare)

procedure: (pair-compare-cdr compare)

ペアの car（cdr） だけを使い、 cdr（car）を無視するような 比較手続きを作成する。この手続きは以下のように定義できる。

(define (pair-compare-car compare)
  (lambda (x y) (compare (car x) (car y))))

論理的根拠: pair-compare-car は探索用のデータ構造 （例えばヒープ）を辞書に変換するのに使うことができる。例えば、 (key . value) のペアを格納し、 (pair-compare-car compare-key) で比較する等。

procedure: (pair-compare compare-car compare-cdr pair1 pair2)

procedure: (pair-compare [ compare ] obj1 obj2)

ペアないしは（非真正リストである可能性のある）リストを比較する。

4 引き数の形式は pair₁、pair₂ それぞれの car を compare-car で比較し、 car が等しければ compare-cdr を使って cdr を比較する。

3 引き数の形式は null < pair < neither-null-nor-pair という型の順序にしたがって比較を行い、 neither-null-nor-pair 型のオブジェクト同士は compare で比較される。ペア同士の場合は car を compare で比較し、 car が等しい場合には再帰的に cdr を比較する。

2 引き数の形式は compare として default-compare を用いる。

(pair-compare '() 'foo)   ===> -1
(pair-compare '() '(1 . 2))) ===> -1
(pair-compare '(1 . 2) 'foo) ===> -1
(pair-compare 3 4)      ===> -1

4.4 デフォルトの比較手続き

組み込み型を簡単に比較できる比較手続きがあると便利である。

procedure: (default-compare obj1 obj2)

引き数は以下の型の順序付けにしたがい比較される。

null < pair < boolean < char < string < symbol < number < vector < other

同じ type 型のオブジェクトは type-compare のような手続きがあれば、 その手続きがするのと同じような方法で比較される。 null 型は空リスト '() で構成される。other 型のオブジェクトを比較したり、 （リストやベクタによりできる）循環構造を比較した場合の動作は 未定義である（実装側は構造体や正規表現など、 他の組み込み型の比較操作を追加してもよい）。

原理: default-compare は neither-null-nor-pair を分割し pair-compare を洗練する。

注: default-compare は以下のように定義できる（条件の順序に注意）。

(define (default-compare x y)
  (select-compare x y
                  (null?  0)
                  (pair?  (default-compare (car x) (car y))
                          (default-compare (cdr x) (cdr y)))
                  (boolean? (boolean-compare x y))
                  (char?  (char-compare  x y))
                  (string? (string-compare x y))
                  (symbol? (symbol-compare x y))
                  (number? (number-compare x y))
                  (vector? (vector-compare default-compare x y))
                  (else (error "unrecognized types" x y))))

4.5 比較手続きを作る

この SRFI の重大な目標は、あたらしい比較手続きをできるだけ 手軽に定義できる仕組みを提供することである。 この節で定義する構文拡張はそれを実現するための基礎的な道具である。

syntax: (refine-compare <c1> ...)

構文: <c_i> は式である。

意味: 0 でない値が見つかるか、評価する引き数がなくなるまで、 引き数 <c₁> ... を 左から右へ評価する。0 でない値が見つかった場合には その値を返し、見つからなければ 0 を返す。引き数はなしでもかまわない。

注: このマクロは別の手続きを洗練して比較手続きを定義するのに 好ましい方法である（5 節を参照）。

例:

(define (compare-rectangle r s)
  (refine-compare
   (compare-length (width r) (width s))
   (compare-length (height r) (height s))))

syntax: (select-compare <x1> <x2> <clause1> ...)

構文: 各 <clause> は (<type?> <c1> ...) という形式である。ここで、 <type?> は評価すると述語手続きになる式で、 <c_i> は評価すると { -1, 0, 1} のいずれかを返す式である。また、最後の <clause> は (else <c1> ...) という形式の「else 節」でもよい。

意味: select-compare は比較手続きを階層的に拡張・洗練 するための条件文である（5 節参照）。 <x₁>、<x₂> について、順に型検査を行い、マッチした場合は refine-compare を暗默に適用する。

より詳しく言うと、評価は以下のような手順ですすむ。 まず最初に、 <x₁> と <x₂> が評価される （このときの評価順序は規定されていない）。 この結果の値を順に x₁、 x₂ とする。 次に、それぞれの clause が左から右にひとつひとつ評価される。

(<type?> <c1> ...) という節について、まず <type?> が評価され、述語手続き type? になる。次に (type? x1) と (type? x2) が評価され、真理値が得られる。この真理値が両方とも真であった場合、 全体の値は (refine-compare <c1> ...) になる。 はじめの方だけが真であった場合、評価結果は -1 になり、 ふたつめだけが真の場合の場合は 1 になる。 どちらも真でない場合は次の clause を考える。 else 節はどちらのテストも真であったとして扱われる。 残りの clause がなくなった場合、評価結果は 0 になる。

select-compare は clause がひとつもない場合でも <x₁> と <x₂> を確実に一回だけ評価する。 そして、それぞれの <type?> は高々 1 回評価され、評価結果の type? は最大 2 回評価される。

注: select-compare の例は、上の default-compare 定義を参照のこと。

syntax: (cond-compare <clause1> ...)

構文: 各 <clause> は ((<t1> <t2>) <c1> ...) という形式である。ここで、 <t₁> と <t₂> は、評価すると真理値になる式で、 <c_i> は { -1, 0, 1} のいずれかになる式である。 最後の <clause> は (else <c1> ...) という形式の「else 節」でもよい。

構文: cond-compare は、比較手続きを階層的に拡張・洗練する もうひとつの条件文である（5 節参照）。

評価は以下のように進む。 clause は左から右へひとつひとつ評価される。そして、 ((<t1> <t2>) <c1> ...) という clause について、まず <t₁> と <t₂> を評価し真理値を得る。 この真理値がどちらも真であれば、全体の値は (refine-compare <c1> ...) になる。はじめの方だけが真の場合、評価結果は -1 になり、 ふたつめの方だけが真の場合には 1 になる。 どちらも真でない場合には次の clause を考える。else 節は両方が真の場合として扱われる。 残りの節がないか節がまったくない場合、評価結果は 0 になる。

cond-compare はすべての式を最大 1 回評価する。

原理: cond-compare と select-compare 型検査の指定の仕方だけが異なる。どちらの方法も等価で、 場合によって、どちらかの方が便利なことがある。

4.6 比較手続きを使う

この節では、アプリケーションであらわれる様々な状況で、 （引き数として渡した）比較手続きを使う仕組みを提供する小道具を定義する。

syntax: (if3 <c> <less> <equal> <greater>)

構文: <c>、<less>、<equal> <greater> は式である。

意味: if3 は比較用の三項条件分岐である。 最初に <c> を評価し、値 c を得る。 c の値は { -1, 0, 1} のいずれかでなければならず、 そうでない場合はエラーが通知される。 c = -1 ならば、if3 の値は <less> を評価したものになる。 c = 0 ならば <equal>、 c = 1 ならば <greater> が評価される。

注: 例として、以下のような手続きを考える。 この手続きは、ソート済みのリスト s に x を挿入し、同値な要素があれば それを置き換える。

(define (insert compare x s)
  (if (null? s)
      (list x)
      (if3 (compare x (car s))
           (cons x s)
           (cons x (cdr s)) ; 置き換え
           (cons (car s) (insert compare x (cdr s))))))

原理: if3 は比較操作の結果を使う分岐で、みっつの分岐すべてが 異なるような場合に便利である。

syntax: (if=? <c> <consequent> [ <alternate> ])

syntax: (if<? <c> <consequent> [ <alternate> ])

syntax: (if>? <c> <consequent> [ <alternate> ])

syntax: (if<=? <c> <consequent> [ <alternate> ])

syntax: (if>=? <c> <consequent> [ <alternate> ])

syntax: (if-not=? <c> <consequent> [ <alternate> ])

構文: <c>、<consequent>、 <alternate> は式である。 <alternate> は、省略された場合には (if #f #f) が使われる。

意味: これらむっつのマクロは比較操作に対する二項条件分岐である。 最初に <c> を評価し、結果の値 c を得る。c の値は { -1, 0, 1} のいずれかでなければならず、さもなくはエラーが通知される。 その次に、c の値とマクロに名前にしたがって、 <consequence> か <alternate> のどちらかが評価され、その値が条件式の値になる。

分岐先は下の表にしたがって選ばれる。

	<consequent>	<alternate>
if=?	c = 0	c ∈ { -1, 1}
if<?	c = -1	c ∈ {0, 1}
if>?	c = 1	c ∈ { -1, 0}
if<=?	c ∈ { -1, 0}	c = 1
if>=?	c ∈ {0, 1}	c = -1
if-not=?	c ∈ { -1, 1}	c = 0

注: if<=? 等は比較操作の結果にもとづいて 二項分岐を行うのに便利なマクロである。

procedure: (=? [ compare ] [ x y ])

procedure: (<? [ compare ] [ x y ])

procedure: (>? [ compare ] [ x y ])

procedure: (<=? [ compare ] [ x y ])

procedure: (>=? [ compare ] [ x y ])

procedure: (not=? [ compare ] [ x y ])

x、y が与えられた場合には、 比較手続き compare にもとづき x、y が手続きの名前 rel? で指定される関係にあるかどうかをテストし、 それ以外の場合は述語手続きを生成する。

(rel? [ compare ] x y), の形式では、 (compare x y) の結果にもとづき x、y が （if<? 等と同様に） rel? を満たすかどうかを調べ真理値を返す。 compare を省略した場合には default-compare が使われる。

(rel? [ compare ]), という形式では (lambda (x y) (rel? compare x y)) という述語手続きが生成される。この場合も、 compare が省略されると代わりに default-compare が使われる。

説明のためにいくつか例を挙げる。

(>? "laugh" "LOUD")                   ===> #t
(<? string-compare-ci "laugh" "LOUD") ===> #t
(define char<=? (<=? char-compare))
(sort-by-less '(1 a "b") (<?))        ===> '("b" a 1)
(sort-by-less '(1 a "b") (>?))        ===> '(1 a "b")

注: よくある間違いは、(<=/<=? x y z) のつもりで (<=? x y z) と書く、というものである。たぶん、式 (x y z) が評価されたところで、これに気づくことになるだろう。

procedure: (</<? [ compare ] [ x y z ])

procedure: (</<=? [ compare ] [ x y z ])

procedure: (<=/<? [ compare ] [ x y z ])

procedure: (<=/<=? [ compare ] [ x y z ])

procedure: (>/>? [ compare ] [ x y z ])

procedure: (>/>=? [ compare ] [ x y z ])

procedure: (>=/>? [ compare ] [ x y z ])

procedure: (>=/>=? [ compare ] [ x y z ])

x、y、z が、比較手続き compare について、手続きの名前 rel1/rel2? で指定される二関係でつながっているかどうかを テストする。

compare が省略された場合には default-compare が使われる。 x、y、z が省略された場合には、三引き数の述語手続きが生成される。 値の比較順序は規定されていないが、それぞれの値は少くとも 一回は比較される。

注: (<=/<? real-compare 0 x 1) は x が実数で、半開区間 [0,1) 内にあるかどうかをテストする。

procedure: (chain=? compare x1 ...)

procedure: (chain<? compare x1 ...)

procedure: (chain>? compare x1 ...)

procedure: (chain<=? compare x1 ...)

procedure: (chain>=? compare x1 ...)

比較手続き compare について、（0 個以上の）x₁ ... が手続きの名前で指定される関係でつながっているかどうかをテストする。 戻り値は真理値である。 値の比較順序は規定されていないが、それぞれの値は最低一度は 比較される（1 回だけのこともある）。

関係 rel? について、値 x₁, ..., x_n がつながっている、というのは、 すべての 1 ≤ i < j ≤ n について (rel? compare xi xj) が成り立つことをいう。これは特に、 n ∈ {0,1} の場合である。

= , <, >, ≤, and ≥ は推移的なので、 1 ≤ i < n なる i について (rel? compare xi xi+1) を評価すれば十分である。

注: 各 x_i が最低一回は評価されるのは型検査のためである。 すべての値がつながっているかどうかをテストすれば、 これらの値は compare で比較可能な型といえるからである。 これは引き数の数や、引き数がつながっているかどうかに 関係なく成立する。

procedure: (pairwise-not=? compare x1 ...)

比較手続き compare について、（0 個以上の） x₁ ... がペア単位で等しくないかどうかをテストする。 戻り値は真理値である。 値の比較順序は規定されていないが、それぞれ最低一回は比較される （一度だけのこともある）。

すべての i ≠ j について (not=? compare xi xj) なるとき、 x₁, ..., x_n はペア単位で等しくない、という。 これは特に、n ∈ {0,1} の場合である。

compare は全順序関係を定義するので、ペア単位の不等性は O(n log n) でチェックできる。実装側はこれを満たさなければならない （例えば、最初に整列し、隣接する要素を比較する等）。

procedure: (min-compare compare x1 x2 ...)

procedure: (max-compare compare x1 x2 ...)

比較手続き compare について、（1 個以上の） x₁ x₂ ... の最小値・最大値を求める。

戻り値は最初の最小値（最大値）である。 値の比較順序は定まっていないが、各値は最低一度は比較される （一度だけのこともある）。

procedure: (kth-largest compare k x0 x1 ...)

比較手続き compare について、（1 個以上の） x₀ x₁ ... の k 番目に大きい値を返す。

より精確に言うと、 (kth-largest compare k x0 ... xn-1) は (x₀ ... x_n-1) を安定なソートでならべかえたシーケンスの (modulo k n) 番目の要素を返す（安定なソートアルゴリズムというのは 等しい要素、つまり compare について同値な要素の順序を保存するソートアルゴリズムをいう）。

引き数 k は 正確な整数で、n ≥ 1 である。 x_i が比較される順序は不定であるが、 どの要素も最低一度は比較される（一度だけの場合もある）。

注: 0 番目に大きな要素は最小値であり、-1 番目に大きな要素は最大値である。 n が奇数の場合、中間値は (n - 1)/2 番目に大きな値であり、n が偶数の場合、 n/2 - 1 番目に大きな値と n/2 番目に大きな値の平均値が中間値になる。

procedure: (compare-by< lt-pred [ x y ])

procedure: (compare-by> gt-pred [ x y ])

procedure: (compare-by<= le-pred [ x y ])

procedure: (compare-by>= ge-pred [ x y ])

procedure: (compare-by=/< eq-pred lt-pred [ x y ])

procedure: (compare-by=/> eq-pred gt-pred [ x y ])

x、y が指定された場合、 与えられた述語により定義された全順序で x、y を比較し、{ -1,0,1} のいずれかを返す。 省略された場合引き数をふたつとり比較する手続きを生成して返す。

述語手続きの意味は以下の通りである。 (lt-pred x y) は x < y かどうかをテストする。 le-pred は ≤、 gt-pred は >、 ge-pred は ≥、 eq-pred は x と y が同値かどうかをテストする。述語手続きの返した値は Scheme の真理値として解釈される（すなわち、 #f が偽で、#f でない値は真になる）。

compare-bypredicate(s) は順序述語と、可能ならばさらに加えて同値述語から、 比較手続きを生成するためのものである。 同値述語 eq-pred が与えられた場合、 これは順序述語の前に呼び出される。 これは、同値関係というのは全順序よりも粗く、 計算量が少ないかもしれないからである。

注: char<=? を使って char-compare を以下のように定義することができる。

(define char-compare (compare-by<= char<=?))

procedure: (debug-compare compare)

compare の呼び出しをデバッグ用のコードでラップした、 compare と等価な比較手続きを返す。 デバッグ用のコードは比較手続きの公理がおかされていることを 検知すると、エラーを通知する。このため、compare には副作用がないことを仮定している。

具体的に言うと、 (debug-compare compare) を評価すると、渡された引き数にもとづいて compare の反射性、反対称性、推移性を チェックする比較手続き compare₁ になる。 compare₁ は compare に渡されるすべての引き数について反射性をチェックし、 引き数の組すべてについて反対称性を、 現在のふたつの引き数と、以前呼ばれたときの引き数からランダムに 選ばれた値との三つ組について推移性をチェックする。

原理: テストのカバー範囲は不完全でランダムに選ばれたものだが、 compare₁ の実行時間は compare の実行時間の定数倍にしかならない。

5 比較手続きの理論

この節では「比較関数」という概念に理論的正当性を与える。 まず、比較関数の公理的定義を与え、その次に、比較関数が単に 同値類上に全順序を定義する型破りな方法に過ぎず、また、 これが比較関数について数学的に言うべきことすべてであることを証明する。

この段階で、数学者はまず第一にどうして比較関数などというものを 導入するのかといぶかしむかもしれないが、それには、 そうすると全順序を使うプログラムを書くのに便利だから、 と答えておく。

この SRFI をできるかぎり利用しやすくするため、 これがどんなに自明であるにしても、我々はこの定理と証明を明確にしておく。

定義:

集合 X 上の 比較関数とは すべての x, y, z ∈ X について以下の条件を満たす関数 c : X × X である。

• (R) c(x, x) = 0
• (A) c(x, y) + c(y, x) = 0
• (T) c(x, y) ≤ 0 and c(y, z) ≤ 0 ⇒ c(x, z) ≤ 0.

これらの性質を (R) 反射性、 (A) 反対称性、 (T) 推移性 と呼ぶ。 ∎

典型的な比較関数は以下のようなものである。

• c_ℝ : ℝ × ℝ → {-1, 0, 1}
• (x, y) ↦ sign(x, y);

この関数は実数を標準の順序で比較する。 明らかに x < y のとき、かつそのときに限り c(x, y) < 0 である。 ここで、c が文脈から明らかな場合、 「c(x, y) < 0」と書く代わりに、簡単に 「x < y」と書くことにする（同様に、 ≤、=、≥、> にもこれを拡張する）。

ひとつめの定理は、それぞれの比較関数から自然なかたちで 同値関係が得られることを示す。

定理:

c を X 上の比較関数とすると、 x, y ∈ X について、以下のように定義される 関係 ∼ は X 上の同値関係である。

証明:

同値関係とは、反射的で対称的で推移的な関係である [2]。以下それぞれを確認する。

「反射性」: x ∈ X について考える。このとき、(R) c(x, x) = 0 から x ∼ x である。

「対称性」: x ∼ y なる x, y ∈ X について考える。まず、∼ の定義から c(x, y) = 0。さらに (A) から c(y, x) = -c(x, y) = 0。 よって、y ∼ x。

「推移性」: x ∼ y かつ y ∼ z なる x, y, z ∈ X について考える。このとき、 c(x, y) = c(y, z) = 0。 これと (T) より、c(x, z) ≤ 0。 さらに、対称性から c(y, x) = c(z, y) = 0 が得られる。これと (T) から c(z, x) ≤ 0。 したがって、c(x, z) = 0。 よって x ∼ y。 ∎

次の定理は、比較関数により定義される同値類は自然な順序をもつことを示す。

定理:

c を X 上の比較関数、 ∼ を先の定理の同値関係とし、 x を含む同値類を [x] と書くことにする。つまり、 [x] = { y ∈ X | c(x, y) = 0 } である。このとき、下のように定義される x, y ∈ X に関する関係 ≤ は、 {[x] | x ∈ X} の同値類の集合上の同値類である。

[x] ≤ [y] :⇔ c(x, y) ≤ 0,

証明:

全順序関係は、反射的で、（弱く）反対称的、推移的で、 かつ、すべての要素が比較可能である。よって先と同様にして、

「反射性」: x ∈ X について考える。このとき、 (R) より c(x, x) = 0、 したがって、すべての x ∈ X について [x] ≤ [x]。

「反対称性」: [x] ≤ [y] かつ [y] ≤ [x] なる x, y ∈ X について考える。このとき、≤ の定義から c(x, y) ≤ 0、また、 (A) から c(y, x) = -c(x, x) ≤ 0。 よって、c(x, x) = 0。 従って、[x] = [y]。

「推移性」: [x] ≤ [y] かつ [y] ≤ [z] なる x,y,z ∈ X について考える。≤ の定義から c(x, y) ≤ 0 かつ c(y, z) ≤ 0。 また、(T) から c(y, z) ≤ 0。 よって、[x] ≤ [z]。

「比較可能」: c を比較関数としたとき x,y ∈ X について c(y, z) ∈ {-1, 0, 1} である。 したがって、(A) より、 c(x, y) ≤ 0 ならば [x] ≤ [y]、 c(x, y) ≥ 0 ならば [y] ≤ [x] である。 ∎

最後の定理では、前のふたつの逆、 つまり、同値類上の集合に対する全順序には、 一意に定まる比較関数があることを示す。

定理:

X を集合、 ∼ を X 上の同値関係とし、≤ を ∼ による同値類の集合上の全順序とする。 このとき、

のように定義される関数 c: X × X は X 上の比較関数であり、関係 ≤ と 同値関係 ∼ から定義される。

証明:

まず最初に、 [x] ≤ [y] and [y] ≤ [x] から [x] = [y] (i.e. x ∼ y) が導かれる、という具合に、 c は関数として明確に定義されていることに注目する。 ここで、比較関数の公理を確認する。

(R): ∼ の反射性から すべての x ∈ X について c(x, x) = 0。

(A): x, y ∈ X について考える。 x と y は ≤ により比較可能なことから、 [x] ≤ [y]、または [y] ≤ [x]。 この両方が成りたつとき、すなわち x ∼ y であり、したがって、c(x, y) = c(y, x) = 0。さもなくは、 c(x, y) = -1 かつ c(y, x) = 1、または c(x, y) = 1 かつ c(y, x) = -1。 いずれの場合も、 c(x, y) + c(y, x) = 0 である。

(T): c(x, y) かつ c(y,z) ≤ 0 なる x, y, z ∈ X について考える。このとき c の定義から [x] ≤ [y] かつ [y] ≤ [z]。 ≤ の推移性から、[x] ≤ [y]、つまり c(x, z) ≤ 0。 ∎

この時点で比較関数の数学はおわりである。 しかし、古い比較関数から新しいものを作る方法を検討するのは有益である。

符号反転:

c を X 上の比較関数とする。 このとき (x, y) ↦ -c(x, y) もまた X 上の比較関数である。これは (x, y) ↦ c(y, x) と同一である。

偶然にも、c がひとつの場合、 (x, y) ↦ f(c(x, y)) が比較関数であり、{ -1, 0, 1 } をそれ自身に写像するような関数 f はふたつしかない。すなわち、 f(γ) = 0 と f(γ) = -γ である。

引き数変換:

c を X 上の比較関数とし、 関数 φ: U → X を考える。このとき、

(u, v) ↦ c(φ(u), φ(v))

は集合 U 上の比較関数である。

φ ≠ ψ ときの c(φ(u), ψ(v)) を考えたい向きもあろうが、この結果は c、φ、ψ が密接に関係している場合にだけ比較関数になる（i.e. (R), (A), (T) が保たれる）。

洗練:

c_coarse、c_fine を同一の集合 X 上の比較関数とする。 このとき、

は比較関数である。帰納法より、この構築は有限回の繰り返しになる。 すなわち、もっとも粗い比較関数 (x, y) ↦ 0 から始まる。

階層型拡張:

X, Y を互いに素な集合とし、 c_X、 c_Y をそれぞれ X、Y 上の比較関数とする。このとき、

は X ∪ Y 上の比較関数である。 X 上の c_X と Y 上の c_Y をそれぞれ使い、 X < Y を洗練する。これは、互いに素な領域上の比較関数の 任意のあつまり（選択公理に注意）に一般化することができる。

Scheme 上では、この SRFI は洗練、階層型拡張、引き数変換、符号反転 のための便利で効率のよう方法として refine-compare、select-compare、 cond-compare マクロを定義している。

6 設計原理

この節では、我々がこの SRFI の設計を決定したうらにある理由を紹介する。 我々はこの点をあきらかにしておきたい。 これは、設計というのは決定の結果としてあるものではなく、 ほかに考えた選択肢のなかにあると考えるからである。 この節は Q&A リストにしてある。

（二値）順序述語と三値比較のどっちがいいの？

数学では伝統的に「等しいかより小さい」（≤）という関係で 全順序関係を規定します。これは、<= 述語関数というかたちでプログラミング言語にもあらわれています。

しかし、全順序関係にもとづけば、x、y という要素には本質的に、x < y、 x = y、x > y という みっつの関係があり得るのです （半順序関係ではよっつめの関係として x と y が比較できない、というのがあります）。これは、（≤、=、< 等といった）二値操作にもとづいた仕組みでは、 要素ふたつの関係を特定するのに、式をふたつ 評価しなければならないことがある、ということです。

実際に、比較操作の計算量が大きい場合にこれが問題になります。 この例としては、要素の順序が相対的な位置関係で決まるように 定義してある場合があります（同形型でグラフを比較する場合を考えてください）。 この場合、それぞれの順序述語は比較手続きと同程度にコストがかかります。 つまり、三項分岐は二項分岐をふたつならべるのよりも倍速いということです。 従って、純粋に比較操作のインタフェースだけによって、 潜在的に性能にかなりのロスが出てくるのです。

しかし、三値比較をそのまま使うのは、第一に、使う場合にも 定義する場合にも、不便なことがあります。 幸運にも、この問題はScheme の構文（マクロ）と手続きによる抽象化で、 十分に解決することができます（4.5 節、 4.6 節参照）。

みっつの場合の表し方は？

我々は比較結果を表現するのに次のような方法を考えました。

1. 正確な整数 -1、0、1（この SRFI の方法）
2. 正確な即値整数の符号
3. real? を満足するすべての Scheme の数値の符号
4. ことなるみっつのシンボル（例えば '<、 '=、'>）
5. 三要素からなる列挙型
6. それ自身に評価される特別な組み込み定数（例えば #<、#=、#>）

比較結果の表現は、オブジェクトを比較するプログラムと、 その比較結果を使うプログラムとの内部インタフェースです。

みっつの値だけを使う利点は、それぞれの場合を一意に定義できる ということです。これにより、if の代わりに case を使えるようになり、 さらにポータビリティも保証されます。R⁵RS の範囲では、不完全指定や不正確な数のこともあり、 数値のポータビリティにはいくつか問題があります。

一意でない（数値）表現を使う利点は、「#f でない値が真になる」仕様のように、計算の結果をそのまま 条件分岐で使えることがある、ということです。 しかし、4.6 節の操作を使うと、この利点はほとんど役に立たなくなります。 さらに、「#f でない値が真になる」仕様は、 それ自身が思いがけないプログラムのふるまいの原因になることが よくあります。

シンボルをみっつ使うのではなく、{ -1, 0, 1} を使うと、例えば、そのまま添え字の計算に使うといった、 追加の操作がサポートされるという利点があります。 特に便利なのは、 (* sign (compare x y)) のようにして、sign（-1 か 1）に応じて順序関係を 反転させられるということです。さらに、整数値は一意です。 比較結果を整数値で返せば、どの数値かはすぐにわかります。 また、Scheme システムは普通、小さな整数を boxing されない値として扱うし、また整数がそれ自身に評価されるリテラルである、 という考えも片隅にあります。

みっつのシンボルを使う方法には、よりわかりやすいものを 選べるようになるという利点があります。例えば、 (symbol-compare 'foo 'bar) が 'greater になる方が 1 になる方がわかりやすいでしょう。しかし、不幸なことに、 このみっつのシンボルの名前の選び方に自明なものはありません。 無難なものとしては 'less 'equal 'greater や 'lt 'eq 'gt、 '< '= '> があります。シンボルを使うと不便な点は、 Scheme のシンボル自体にも順序があり、その順序が このみっつの場合にとって好ましい順序と異なるかもしれないという点です。

いくつかの Scheme 実装では列挙型を定義するため仕組みが提供されています。 例えば Scheme 48 の define-enumerated-type を使えば、lt、eq、gt のみっつのオブジェクトから成る comparison 型を定義することができます。また、 SRFI 9 (Defining Record Types) [10] を使って、インスタンスをひとつしか持たない構造体型をみっつ定義して、 （直接）列挙型を定義することもできます。我々は、この方法は みっつのシンボルを使う方法よりもよいと考えます。 なぜなら、比較結果は独自の型を持ち、十分によくできたコンパイラなら、 この情報を使って冗長な型検査をはぶくことができるからです。

この方向から一歩進んで、以下のような設計の選択肢を考えました。 comparison 型はプログラミングにとって基礎的なものであることを 考えると、これを Scheme のコアに組み込む価値があるかもしれません。 これは以下のようなかたちになるでしょう。 例えば、 #< #= #> のようなそれ自身に評価される定数があり、これらは comparison 型の唯一のインスタンスである。 この型は comparison? と comparison-compare のふたつの操作をサポートする。さらに比較結果の値を区別するのに eq?、eqv?、equal? が必要になる。— 言い換えると、boolean のあとに comparison がある、ということです。 しかし、このように言語に密接に比較操作を組み込むことで、 どちらの問題が解決するのかは不明瞭です。

このような状況で、我々は { -1, 0, 1} を選択しました。整数値を直接扱うので、 これらを便利に扱うための道具が必要になることはほとんどありません。

複素数の順序はどうあるべき？

数学的には代数構造や位相構造に互換な複素数の全順序は存在しません。 にもかかわらず、プログラミング目的では複素数に何らかの 手軽に使える全順序関係があると便利ことがあります。

少なくとも実数の自然な順序づけと互換性のある複素数の全順序関係は いくつかあります。このうちで、いちばん驚きの少ないのが (re, im) の辞書式順です。

浮動小数点数の特殊シンボルはどう順序づけるべき？

浮動小数点フォーマットは実数を表すだけでなく、 +Inf、-Inf、NaN （Not a number）、-0 のような特殊なシンボル用に拡張されていることがよくあります。 これらのシンボルは他の普通の数値に対してどのように順序づけられる べきでしょうか、こういったもの同士ではどうでしょうか （msg00010 から始まる議論のアーカイブを参照して下さい）。

これらの特殊シンボルの目的を簡単に確認しておきましょう。 浮動小数点フォーマットにこのような特殊シンボルを導入するのは、 データにまつわるエラーが起こった場合でも計算を続けるためです。 これは、エラーが起こった場合でも、計算結果について、 意味のある情報がいくらか残っているためです。 +Inf や -Inf といったシンボルは計算により、値が表現可能な範囲を 越えてしまったことを示します。そして -0 は、表現不可能なほど 小さな絶対値の値が生成されたということを示し、さらに負の数側で アンダーフロウが起こったという情報を持っています（そうでなければ +0 になります）。このような情報は枝刈りに使えます。 最後に、NaN は値についての情報がまったくなくなってしまったことを 示します（例えば -Inf + Inf）。NaN は例外を挙げずに他の部分の計算結果を使って計算を続けるためにあります。 様々な NaN があることにも気をとめておくべきでしょう。 例えば、IEEE 754 標準では（解釈はどうであれ） NaN を表すビットパターンが多数あります。

+Inf と -Inf は極値を表すために設計されているため、 これらの実数に対する順序は明らかです。符号付き零に対しても同様です。 しかし、ふたつの零（あるいは -0、0、+0 のみっつ）の概念は 実数の算術構造と互換ではありません。したがって、ほとんどの場合、 計算結果の情報が破棄されてしまうとしても、 すべての零は等しいものとしてあつかわれます。 しかし、浮動小数点数のなかのすべての情報が 保存される状況で意味をもつような設計の選択肢もあるでしょう。

NaN となると、話はもっと曖昧になります。 NaN は他の浮動小数点数との間の自然な順序関係すらありません。 ひとつの選択肢として、NaN が比較操作のなかに現れた場合には エラーが起こるというのがあります。「制御フローが NaN に依存していたら、どちらにしろ困ることになるだろう」という論法です。 別の選択肢として、強引に何らかの順序を定義してしまうというのもあります。 こちらは「オブジェクトが real? を満足するのなら、 real-compare? で比較できるべきだ」という論法です。 どちらの方法がよいか一概には断言できません。

このような場合を考え、R⁵RS のアプローチにならい、real-compare のなかで浮動小数点の特殊シンボルを使った場合の結果は未定義のままに しておいきました。この点については、Scheme 自体の浮動小数点数の表現や数値計算についての部分が明確になったら 変わるかもしれません。

default-compare をどのように定義すべき？

default-compare の目的は、任意の Scheme の値ふたつを 比較する何らかの明確な方法を提供することです。 例えば、全順序の実態が実際に問題にならない場合など、 利用者が明示的に比較手続きを定義したくない場合に default-compare が使えます。

整数の集合の集合をあつかう場合を考えてみましょう。 この場合、集合を表すのに重複のないソート済みリストを使い、 default-conmpare が既に提供する全順序を使うことができます。

しかし、default-compare の定義には制限があります。例えば、 default-compare がオブジェクトのポインタ表現から来るハッシュコードにもとづくというのは、 ガーベッジコレクションの仕組みに密接に依存してしまうため 簡単にはいかないでしょう。我々もやはり、default-compare は型や構造にもとづいた方がアプリケーションにとって 便利だと思います。

しかし困ったことに、 ポータブルなリファレンス実装を考えようとすると、これによって default-compare で比較できるオブジェクトに制限を課すことになってしまいます。 特に、循環構造をあつかうポータブルな方法というのは 過度のコストがかかってしまうのです。

もちろん、その型をどのように順序づけるべきか、という疑問も 自然と湧いてくるでしょう。この問いに対しては、 boolean-compare と pair-compare の両方を理解するのが役に立ちます。どちらも（少なくとも建て前上は） すべての値について全順序を定義しています。 従って、default-compare はこの一方を洗練します。 しかし、残念ながら（#f と '() がそれぞれ最小値と最大値である場合を除いて）両方を洗練することはありません。 pair-compare の方が boolean-compare よりもよく使われるため、我々は pair-compare を default-compare の基礎にすることにしました。 他のポータブルで比較可能な型については、 複雑さが増していく方向に順序づけをしました。 このあたりは完全に独断的なものです。

「辞書式順序」って何？

辞書式順序は要素の並び順からシーケンスの順序を定義する 一般的な方法です。辞書式順序では、空のシーケンスが最小のシーケンスで、 ふたつの空でないシーケンスはまず最初の要素を比較し、これが等しい場合にだけ 残りの要素が再帰的に比較されます。

辞書式順序は、辞書で使われていることからこの名前がきています。例えば、 fun < funloving < jolly になります。

リストやベクタの「自然な順序」って何？

ある抽象データ型の「自然な順序」といった場合、そのデータ型で サポートされた基本操作に合致するように定義された全順序を意味します。

Scheme のリストに定数時間で実行できる基本的なアクセス操作は null?、car、cdr です。 これが、ふたつのシーケンスを辞書式順序で比較するのにちょうど必要な操作です。

Scheme のベクタの定数時間アクセス操作は vector-length（サイズ） と vector-ref（参照）です。 ベクタの基本的な順序づけでは、これらの操作をつかい、 まず最初にサイズで比較しサイズが等しい場合にかぎり 要素を辞書式順序で比較します。

ベクタはどうして辞書式順序にならないの？

この SRFI では、リストと文字列はデフォルトで辞書式順序（LEX）で 順序づけされます。例えば、"12" < "2" です。これに対して、ベクタは最初に サイズで比較され、その次に辞書式順序で順序づけられます（LENGTH-LEX）。 例えば #(2) < #(1 2) になります。 この代わりに、ベクタも純粋に辞書式順序にすることもできました。 極論して、リストや文字列、ベクタを、具体的な表現にしばられずに、 "12" = (#\1 #\2) = #(#\1 #\2) のように、ただシーケンスとみなして順序を決めることもできました。

この選択の影響を受けるのは vector-compare、 default-compare と順序づけの概念的な解釈のされ方です。 この SRFI ではさらに、シーケンスに順序をつける基本的な方法（LEX と LENGTH-LEX）を言うのに、「リスト風に順序づける」、「ベクタ風に順序づける」 という用語を導入しました。 この選択は、コンテナデータ型を導入するほかのすべての SRFI（例えば、 SRFI 66 や SRFI 74）で、著者がこの SRFI と互換性のあるデフォルトの比較手続きを指定したいと思った場合に 備えてのものです。

このことについての議論を大別すると、主にみっつの主張があるようです。

1. 概念的にはベクタやリストはシーケンスの表現型であり、 順序づけをひとつ選ぶのなら、それは LEX であるべきである
2. 定数時間のサイズを求める操作をサポートする方については LENGTH-LEX の方がより基本的で効率的である
3. 概念的には文字列は「文字のベクタ」であり、 文字列は普通デフォルトで辞書式順序になるのだから、 潜在的な混乱をできるだけ避けるためにも、 ベクタは LEX で順序づけするべきだ。

（詳しくは議論のアーカイブを参照して下さい。特に msg00054。）

我々は、数学的な自然さから 2. をいちばん重要と考え、 続いて、実装を単純化できる点から 1. を次に重要と考えました。 このことについては議論の余地がありますが、我々は、 異なるデータ側には異なる順序づけを導入すべきであり、 それぞれの順序はシーケンスに対する唯一のものから導き出すべきではない と考えました。最後に 3. ですが、我々は、文字列の順序はもともと歴史的に、 自然言語の（小文字で）書かれた単語の順序に由来するものであることから、 論拠としては弱いと考えました。

SRFI 66 や SRFI 74 で導入されたベクタ風のデータ型については、 我々はその型について最も自然に見えるデフォルトの順序を定義することを おすすめします。手続きの名前は便利のために type-as-ordering としておくとよいでしょう。順序づけがあまり重要でない場合は、 この SRFI と互換性のあるようにしておくのをおすすめします。

どうしてこんなに高階構築子が少ないの？

制御構造（マクロ）を使う代わりに refine-compare や select-compare、cond-compare を比較手続きを生成する高階関数にすることもできました。

しかし、我々は単純さの面から高階手続きの代わりに制御構造を 使うことにしました。これは、上で定義した default-compare のような、再帰的な比較手続きを定義する場合に歴然としてきます。 select-compare を使うと、default-compare はいくつかの分岐先で自分自身を呼び出す程度の単純なものとして 定義できました（4.4 の例参照）。 高階手続きを使った方法では、定義途中の手続きを自身を アプリケーションの指定した引き数で呼び出すことができなければなりません。 これを柔軟な高階手続きで表現しようとすると、より一層遠回しな 表現になってしまいます。

<?、<=? とかは何のためにあるの？

プログラムを書くには二項分岐と三項分岐の両方が必要です。 三項分岐のためには if3 が提供されています。

二項分岐をするには、比較操作の結果である { -1, 0, 1 } を { #f, #t } に写像しなければなりません。 この写像を行う関数がやっつあります。むっつの非定数関数は =? や <? 等として提供されています。

単調な関数いつつは値の並びに対して一般化することができます。 普通の比較操作で比較手続きを省略できるようにするために、値の並びに対して chain<? や chain< のような別の手続きを定義しました。六番目の not=? については、ペア単位の不等という一般化として pairwise-not? を定義しました。この手続きは、比較手続きによって 全順序関係が定義されているので、効率よく実装することができます。

みっつの値の比較はプログラム中にもよく現れ（0 ≤ i < n といった境界チェックを考えてください）、異なる関係演算子が 組み合わされることもあるので、みっつの値に対する特別な操作を用意しました （</<?、</<=? 等）。

利便性のために、比較手続きはできるだけ省略可能にしてあります。 しかし、困ったことに、これは落とし穴にもなっています。 例えば、(<=/<=? x y z) のつもりで (<=? x y z) と書いてしまうというものです。 しかし、幸いにも、(x y z) が評価されたところで、このまちがいはすぐに明らかになります。

<? とかが手続きで、マクロじゃないのはどうして？

<? や </<?、chain<? といった手続きはマクロにすることもできました。 そうすることで「短絡評価」を使うことができるようになるという利点も あります（短絡評価というのは、比較操作のひとつが失敗した時点で 中断して、残りの式と比較操作を評価しない方法です）。 場合によってはこれが効率的な場合があります。

その一方で、手続きには、それが Scheme の「第一級市民」である という利点があります。これは、関数の引き数として渡すことができ、 高階手続きの戻り値にできるということです。

このアプローチをもう一歩進めると、比較結果がすでにわかっている場合でも、 比較関数に引き数の型チェックをさせることができます。 これは R⁵RS の 6.2.5 節で = や < の「推移性」と呼ばれているもののことです。 例えば、(< 0 x y) は最初に x が正であるかをテストし、それが成り立ったとき、 (< x y) をテストします。しかし、x が正でなかった場合でも y が実際に real であるかを確認し、さもなくはエラーが起こります。 これに対して、「短絡評価」では、x が真でなければ、y は任意の Scheme の値でかまいません。

「推移性」テストには明らかにオーバーヘッドがあります。 これをすることによって、冗長な可能性のある型チェックを行う必要が出てきます。 さらに悪いことに、引き数の型が比較手続きだけにわかっている場合には、 型検査を行う唯一の方法が比較すること—時にはそれ自身と比較すること （比較手続きの定義のよれば、この場合の結果は 0 になります）—になってしまうことになります。

「推移的」な比較の利点は、自動的に型についての表明が入ることです。 例えば、(chain<? integer-compare x y z) を評価したあとには、結果の如何によらず、x、y、 z は整数であることがわかります。我々はこの利点には 対価を支払うだけの価値があると考えました。

compare-by< とかはどうしてあるの？

比較関数を書くよりも、順序述語と、それとは別に同値述語を 定義した方が簡単だということがよくあります。 compare-by< 等々は、このような場合に 対応する比較関数を簡便かつロバストに定義する方法を提供します。

リファレンス実装を書いてわかったことですが、これらの手続きというのは、 どれも数行の些細なコードであるにもかかわらず、 面白いほどバグが入りやすいのです。

同値関係だけから比較関数を定義するにはどうすればいいの？

やめておいた方が無難です。

比較関数は同値類の上の全順序を定義し、逆もまた同様です （5 節を参照）。 従って、比較手続き compare は (=? compare x y) のようにして同値性をテストするのにつかうことができます。

逆に、x ∼ y ならば c(x, y) = 0、 さもなくは、c(x, y) = 1 ということを利用し、∼ だけから比較手続き c を定義してみたくなる人があるかもしれません。 しかし、（すべてのオブジェクトが等価である場合、すなわち すべての x、y について c(x,y) = 0 の場合を除いて） c は反対称ではありません。従って、比較関数ではないのです。 実際に、同値類上の全順序を回避することはできないのです。

このことは、全順序にもとづいた効率のよい（log オーダーの）探索用の データ構造が存在し、同値関係だけにもとづいたデータ構造では非効率的な （最悪では線型時間かかる）データ構造しかない、という事実にも あらわれています。下のプログラムは、使用する同値類の数を h とすると、O(h) の時間と空間をとります。

(define (equal->compare equal)
  (let ((reps '()) (length-reps 0))
    (define (index x)
      (let loop ((i (- length-reps 1)) (rs reps))
        (if (null? rs)
            (let ((i length-reps))
              (set! reps (cons x reps))
              (set! length-reps (+ length-reps 1))
              i)
            (if (equal x (car rs))
                i
                (loop (- i 1) (cdr rs))))))
    (lambda (x y)
      (integer-compare (index x) (index y)))))

equal が同値述語であれば（すなわち、反射的で対称的で 推移的であれば）、(equal->compare equal) は equal で比較可能なオブジェクトに対する比較手続きになります。 ここで定義された全順序は（呼び出し順序に依存して） 不定になります。

同値述語 equal はunion-find データ構造 を使って定義されているかもしれないことに気をつけてください。 また、equal で表される同値関係は (equal->compare equal) を使っている間変更されないことも 覚えておいてください。したがって、union find データ構造は一体のクラスでなければなりません。

R⁵RS からこの SRFI への切り換えはどうすればいいの？

この SRFI は偶然にも R⁵RS にある 25 の順序述語と完全な互換性があるので、いちばん簡単な方法は R⁵RS にある操作を、この SRFI で規定された操作で書きすことでしょう。対応する Scheme コードは r5rs-to-srfi.scm を見て下さい。

もうひとつの方法として、R⁵RS の順序述語を参照する式をそれぞれ、この SRFI を使った等価な式に変換することもできます。 それでも、この変換を行うにはその式の文脈、特に変数の束縛やマクロ定義、 eval の使用についての理解が必要なことは覚えておいて下さい。

これによって、式の意味は変わったとしても、たいてい型安全性を増したり、 わかりやすくしたりすることができます。例として、次の (and (<= 0 i) (< i n)) を置き換えの可能性を考えてみましょう。

(and (<=? real-compare 0 i) (<? real-compare i n))
(<=/<? real-compare 0 i n)        ; 常に n と比較する
(<=/<? integer-compare 0 i n)     ; i、n は整数
(<=/<? 0 i n)                     ; default-compare を使う

最初のものだけがもともとのものと等価な式です。 しかし、ほかのものも目的によっては便利かもしれません。

どうして型まわりがこんなに厳密なの？

この SRFI の手続きとマクロのほとんどは引き数が特定の型でないと エラーを通知することになっています。 特に、比較結果の値は正確な整数でどんなときも { -1, 0, 1 } のいずれかでなければなりません。代わりに、手続きやマクロは 意味のある範囲で一般的な値を受けつけるようにすることもできました。

しかし、我々はこういった言語の基礎的な部分で型に厳密なのは すぐに見返りが得られると信じています。特に、デバッグが単純になります。 さらに、プログラムを静的に解析で、より多くの変数の型がわかり、 値を unbox したり、効率よくコンパイルされたコードが得られるようになります （もちろん、これを書いている時点では理屈の域を出ません）。

この SRFI を使うと性能は悪くなる？

はい、そして、いいえ。

リファレンス実装では正確さとポータビリティに主眼を置きました。 そのため、内部的な手続き呼び出しや型検査のオーバーヘッドで、 性能はかんばしくなくなっているでしょう。

しかし、SRFI という言葉のいうとおり、この文書は「実装への要求（ request for inplementation）であり、 我々としては、特定 Scheme システムの実装に熟練した人がこの SRFI を効率よく実装して欲しいと思っています。実際に、ここで定義した 操作は、すべてではないにしろ、ほとんどがネイティブでサポートされています。

このような場合、この SRFI を使っても性能上の問題はありません。 それよりもむしろ、この SRFI を使えば、明示的な三項分岐や型付けにより 性能があがることさえあるかもしれません。

どうして省略可能な引き数が先にあるの？

いくつかの操作では、最初の引き数が省略可能になっていますが、 これは、省略不可な引き数のあとに省略可能な引き数を置くという Scheme の慣習には反しています。

前の方にある省略可能な引き数はいつも、使用する全順序を示す compare 引き数です。これが省略された場合には default-compare が使われます。

compare を省略可能にしたのは、 (<? default-compare x y) の代わりに (<? x y) 書ける、というような簡潔さのためです。 省略可能にすることが混乱の種にもなりますが （例えば (<? x y z) と (</<? x y z)）、 我々は、こうするのが対話的に使う場合や使い勝手のよいプログラムには 重要な機能だと考えました（例えば (do ((i 0 (+ i 1))) ((=? i n))) で使うような場合）。

compare を省略可能にすると決めたとき、 この引き数をどうやって渡すのかという疑問が挙がってきました。 省略可能引き数について、ほかに広く受け入れられている方法がないため、 我々は引き数リストの長さを変えるだけにした。歴史的な理由により、（SRFI 16 の case-lambda 以前は）解析を簡単にするために 省略可能引き数は引き数リストの最後に指定されるようになっていました。 その一方で、(<? x y compare) よりも (<? compare x y) の方がこの SRFI のほかの部分と一貫性があります。

しかし、ここで取った選択は妥協案であり、議論の余地も残っています （詳しくは議論のアーカイブを見て下さい。特に msg00051）。 我々は一般的な場合の表記上の便利さ（省略可能な compare）と この SRFI での一貫性（先行する省略可能引き数）を選ぶことにしました。

chain<? とかは何のためにあるの？ 述語のパラメータじゃいけないの？

この SRFI では chain=?、chain<?、 chain>?、chain<=?、chain>=? のいつつの述語を規定しています。代わりに順序をパラメータとしてとる 述語をひとつ定義することもできました（ msg00012 から始まる議論のアーカイブを参照）。

我々がいつつの述語を定義するのを選んだのは、 述語手続きでなく、順序をあらわす比較手続きを使うことに決めたからです。 テストの連鎖が意味をもつ順序関係述語はいつつあります （六番目の =? は推移的ではありません。そのため、ペア単位の テストが必要になったのです）。このいつつは明確に定義でき、 効率的に実装することができます。主なオーバーヘッドというと 比較手続きの呼び出しになります。

どうしてもっと沢山高階手続きがないの？

この SRFI では、min-compare は、最初の引き数として比較手続きをとり、残りの引き数リスト全体に 最小値を求める操作を適用するようになっています。この代わりに、 （省略可能な）比較手続きだけをとり、（その比較手続きに従って） 引き数全体の最小値を計算する手続きを返すようにすることもできました。 これと同様にして、ほかの手続きを高階手続きとして定義することもできました。

しかし、この SRFI では単純さと効率のために高階手続きを 避けることにしました。繰り返し言ってきたように、 比較手続きというのは、順序関係を、定義されたところから それを使うところまで届けるための主な媒体なのです。 さらに、この SRFI で使用可能になったほとんどの操作は プログラム中にはまずめったに現れないので、 どちらにしても得るところはすくないでしょう。 最後に、高階手続きを使うと、より沢山の括弧を書くことになるし、 単純志向の Scheme システムでは短命なクロージャが沢山 できることになる、などということもあります。

<? とかにはどうしてこんなに省略可能な引き数があるの？

=?, <? といった手続きでは、比較手続きだけでなく、比較対象も省略可能になっています。 これにより、別々の機能ごとに様々な比較手続きを指定したり、 場合によっては指定しなかったりすることで、プログラムをわかりやすくする ことができます。

<? といった操作は比較手続きを使うための 基本的な仕組みです。そのため、多用途に使えて簡潔でなければならないのです。

我々のもともとの設計では比較対象に関する引き数は省略できず、 比較手続きだけが省略可能でした。すなわち、(<? compare x y) というかたちでふたつのオブジェクトのパラメトリック比較を提供していたのです。 そのとき、Amir Livne Bar-On が高階関数スタイルのプログラミングを よりよくサポートすべきだという問題を提起しました。 ((<? compare) x y) という形式を提案したのです （msg00012 を参照）。

しかし、Scheme では Haskell や ML といったカリー化の行われる プログラミング言語に比べて、高階関数スタイルはあまり便利ではありません。 実際、これはすぐに明らかになりました。いちばん基本的でよく現れる、 デフォルトの順序にしたがったオブジェクトの比較が ((<=?) x y) のようになるのです。 括弧がふたつ少なくなると最適です。

ありがたいことに、Dave Mason が、パラメトリックテストと 高階関数スタイルをわかりやすく使い分ける構文を提案してくれました （msg00014 参照）。 こうしてふたつの機能をひとつの手続きに合わせることにより、利用者は 好きなスタイルを選べるようになったのです。

7 関連研究

比較手続きを使うのは別段新しいことではない。 しかし、これらを効率よくあつかうために （if3, select-compare といった）制御構造を定義するというのは目新しいかもしれない （少なくとも、我々は今までに見たことがない）。

R⁵RS では全順序は <=、char<=? といった、型付きの順序述語で表現されている。 「大きいか等しい」述語があれば全順序関係は定義できるが、 R⁵RS では便利さや読みやすさのために、比較述語がすべて （すなわち =、<、>、≤、≥）定義されている。 R⁵RS には全順序にかかわる述語が全部で 25 個ある。 これらは (=|<|>|<=|>=) や (char|string)[-ci](=|<|>|<=|>=)? といった名前をしている。

Scheme では伝統的に同値関係（ふたつの値が等しいと扱われるか）は eq?、eqv?、equal? で表されてきた。歴史的に、この方法ではポインタ単位の比較をするだけで、 再帰的な構造はあつかわないことにしてきた。この SRFI では任意の同値関係を一般化し、この同値類に全順序を与える。

Ruby [4] では、この SRFI の比較手続きにあたる <=> というメソッドが提供されている。 このメソッドを（再）定義すると、あるクラスのインスタンスについて、 他のオブジェクトと比較したときの全順序を定義することができる。 二値比較はすべて <=> を基本にするようになっているが、 Ruby では原則的にそれぞれのメソッドはオーバーロードされる可能性がある。

Haskell 98 [6] 順序述語と比較関数の両方が存在している。Ordering 型 [6, Sect 6.1.8] は LT, EQ, GT のみっつの記号定数からなる列挙型である。 Ord という型クラス [6, Sect 6.3.2] は、その型に全順序があることを示し、Eq という型クラス [6, Sect 6.3.1] は、その型に同値関係が存在することを示している。 compare メソッドはデフォルトで == と <= を使って定義されてい、逆に == や <= は compare を使って定義されている。このため、使用パターンに影響せずに、 簡単に全順序の提供の仕方を選ぶことができる。

C 言語の "string.h" にある strcmp 関数 [7] は、戻り値の符号だけを考慮するという違いはあるものの、 この SRFI の比較手続のようなふるまいをする。 Python [5] には cmp という組み込み関数がある。これも、この SRFI でいうところの比較手続きである。

SRFI-32 (Sort libraries) [13] では「より小さい」で表される全順序を使って整列を行っている。 この SRFI についての議論のアーカイブ [13] に、ソートアルゴリズムの改良という側面での三値比較の使用について 議論しているスレッドがある。

Galore.plt という PLT Scheme のデータ構造ライブラリでは、 (define-signature order^ (elm= elm< elm<=)) のようなシグネチャ定義で全順序を表現する。

8 リファレンス実装

リファレンス実装は compare.scm にある。これは R⁵RS（hygienic macro 込み）と SRFI-16 (case-lambda) [9]、 SRFI-23 (error) [11]、 SRFI-27 (random-integer) [12] で実装されている。

テストコードとサンプルコードは examples.scm にある。こちらは SRFI-42 (comprehensions) [14] が必要になる。リファレンス実装とテストコードは PLT/DrScheme 208p1 [15]、 Scheme 48 1.1 [16]、 Chicken 1.70 [17] で開発し実行した。

この SRFI を使って R⁵RS の順序述語を定義したものが r5rs-to-srfi.scm にある。

参考文献