目次へ 最終更新 : 2003/7/21
第4章 型の力
訳者注：一意性の多相性(4.3.7)の所で、記号が正しく印字されない場合（Adobe Acrobat Reader 5.05で閲覧）がありましたので、私なりに補充しました（一応確認しました）。従って、そこに関しては正確でないかもしれないのでご了承下さい。
CLEANは、強く型付けされた言語である。これは、言語内のあらゆる式が型付けされており、プログラム実行前にコンパイラが型の正当性を検査できるということを意味している。間違って型付けされたプログラムは認められない。この型システムのおかげで、多くのエラーをコンパイル時に発見し報告することができる。ソフトウェア開発プロセスの早期の段階でプログラミングエラーを発見することは重要である。後でエラーを直すことは、遥かに多くの努力を必要とし、相当量の金銭がかかる場合もある。型システムは可及的に大規模なエラーを発見するのに確実に役立つ。しかし、型システムは、一貫していない使用によるプログラミングエラーを発見するのみである。例えば、それは論理エラーを発見できない。CLEANの型システムは非常に柔軟だが、型の正当性を静的に決定できるようにいくつかの制限がある。このことは、ある稀な場合には、プログラムが正当であるにもかかわらずコンパイラがそれを拒絶するということを示している。我々は、型の正当性を静的に決定できることの非常に強力な利点の為に、この対価を喜んで支払う。
型システムはまた、言語の表現力を増大するのにも使用できる。本章では、型システムに関連する多くの言語上の特徴を説明する。第1に、類種の動作を行う異なった関数に同一の関数名を使用できるようにする、CLEANの多重定義機構を説明する。これは、使用されている実際のデータ構造を、設計の後の方の段階で選択できるという方法で、プログラム（の一部）を書くのに使用できる（セクション4.1）。どのようにして、存在量化されたデータ型を使って、異なった型のオブジェクトを、リストのような再帰的データ構造に保存することができるのかを説明する。この方法で、オブジェクト指向スタイルのプログラミングを達成できる（セクション4.2）。最後に、CLEANの重要な特徴を取り扱う。つまり、一意性型システムである（セクション4.3）。これによって、言語の純粋関数型の意味を壊すことなく、配列及びファイルのようなデータ構造を破壊的に更新することが可能となる。
4.1 型クラス
新しい関数を定義する場合、同一通用範囲内に定義された他の全ての関数とは異なった新しい（意味のある）名前を、その関数に与えなければならない。しかし、既存の名前を再利用することが非常に便利であり得る場合が時々ある。明確な例は、関数'+'である。整数についての'+'、実数についての'+'等々を有したいと思うだろう。従って、異なった型に付いて類種の事を行う異なった関数に同一の名前を使うことで、可読性を増大することができることがある。そのような関数を定義することを認めているメカニズムは、多重定義又はアドホック多相性と呼ばれる。多重定義は、同一名を持ついくつかの関数が同一通用範囲内で定義される場合に出現する。しかし、これらの関数の各々は、（少し）異なった型を持つ。従って、あるものとそれと同一の（多重定義された）関数名（例、+）は、異なった演算（Int加算、Real加算等々）の集まりに関連付けられている。各々具体的な型に対して同一方法で動作する、型の範囲を越えて定義されているただ1つの関数に過ぎないmapのような多相関数との違いに注意。
多重定義された関数の定義は、2つの部分からなる。
- 多重定義された関数のシグニチャ、つまり、その多重定義された関数が共通して持っている名前と全体の型。
- （型依存の）具体的実体化たるインスタンスの集合。
柔軟性の理由から、これらの部分は（例えば、異なったモジュール内で）別々に指定できる。CLEANでは、クラス宣言によってシグニチャが導入される。このクラス宣言は、その名前を持つ多くの関数が出現し得るということを示している。これら全ての関数が十分似ていることを保証する為に、これらの関数の型は、シグニチャ内で与えられる共通の型のインスタンスでなければならない。このシグニチャは、全ての具体的インスタンスが従わなければならない青写真と見ることができる。そのようなシグニチャの例は、いくつかの共通した多重定義演算子を導入している以下の（定義済み）クラス宣言である。
class (+) infixl 6 a :: a a -> a
class (-) infixl 6 a :: a a -> a
class zero a :: a
class (*) infixl 7 a :: a a -> a
class (/) infix 7 a :: a a -> a
class one a :: a
class (==) infix 2 a :: a a -> Bool
class (<) infix 2 a :: a a -> Bool
各クラス宣言では、シグニチャに現れている型変数の1つが明示的に表される。このクラス変数は、多重定義演算子の型を、そのインスタンスの全ての型に関連付けるのに使用される。後者は、インスタンス宣言によって導入される。インスタンス宣言は、関数本体を具体的なインスタンス型に関連付ける。この関数の型は、インスタンス型を、それに対応するシグニチャ内のクラス変数と置き換えることによって決められる。例えば、以下のように、文字列に対する多重定義演算子'+'のインスタンスを定義できる。
instance + {#Char}
where
(+) s1 s2 = s1 +++ s2
型シノニムに対するインスタンスを定義することは認められていないので、文字列に対するのではなく{#Char}に対するインスタンスを定義しなければならない。型シノニムのインスタンスを認めれば、実際にはそれと同一型のインスタンスである、ある多重定義関数の複数の様々なインスタンスを持つことが可能になるだろう。CLEANシステムは、これらのインスタンスのどれが適用されるべきなのかを識別することができない。
'+'のシグニチャ内で、aに代えて{#Char}を置き換えることによって、新しく定義される演算子の型を獲得し、{#Char} {#Char} -> {#Char}であると認識する。CLEANでは、この指定された型が上記置換えを経由して獲得された型と全く同じであるならば、明示的にインスタンスの型を指定することが認められている。とりわけ、このことは、以下のインスタンス宣言も有効であることを意味している。
instance + {#Char}
where
(+) :: {#Char} {#Char} -> {#Char}
(+) s1 s2 = s1 +++ s2
多くの、基本型とデータ型に対するこれら演算子とインスタンスが、StdEnvに定義されている。標準ライブラリのサイズを限定するため、最も有用であると考えられる演算子が定義されている。標準関数と演算子それ自体のいくつかのインスタンスを定義しなければならないことが起こるかもしれない。我々が多重定義関数と呼んでいるものは通常の意味での本当の関数ではないということに注目してほしい。つまり、多重定義関数は実際には関数の族全体をあらわしている。従って、もし多重定義関数があるコンテクストで適用されるならば、型システムは、どの具体的インスタンスが使用されなければならないかを決める。例えば、以下のように定義すると、
increment n = n + 1
このInt加算は、'+'にこれのInt版を置換えることを導くものと意味されることは明確である。しかし、適用されるコンテクストによっては、多重定義関数の具体的バージョンを導出することはしばしば不可能である。以下の定義を考える。
double n = n + n
ここでは、'+'のどのインスタンスが意味されているのかをコンテクストから決めることはできない。実際、関数doubleはそれ自体多重定義されており、このことは以下の型の中に反映されている。
double :: a -> a | + a
型定義内に現れる型コンテクスト+は、doubleが'+'で操作できるオブジェクトに関してのみ定義されるという制限を示している。
他のいくつかの例は以下のものである。
instance + (a,b) | + a & + b
where
(+) (x1,y1) (x2,y2) = (x1+x2,y1+y2)
instance == (a,b) | == a & == b
where
(==) (x1,y1) (x2,y2) = x1 == x2 && y1 == y2
一般に、形式C aの型コンテクストは、aのインスタンス化を、Cのインスタンス宣言が存在している型に制限する。もしaの型コンテクストが複数のクラス適用を保持しているならば、aは、これら全てのクラスが共通して持っているインスタンスの型から選ばれると想定される。
勿論、関数doubleに対しては、より特定した型を使用することはできる。例えば、
double :: Int -> Int
double n = n + n
明らかなことだが、doubleはこれ以上多重定義されない。つまり、追加的な型情報によって、使用する'+'のインスタンスを今決めることができるのである。
もし複数の異なった多重定義関数が1つの関数本体内で使用されると、型コンテクストは全く複雑なものになる。例えば、2次方程式を解く関数determinantを考える。
determinant a b c = b * b - (fromInt 4) * a * c
determinantの型は以下のものである。
determinant ::: a a a -> a | *, -, fromInt a
可読性を拡大する為に、既存の多重定義関数の集合に新しい（クラス）名前を関連付けることが可能である。例えば、
class Determinant a | *, -, fromInt a
クラスDeterminantは、多重定義関数'*'、'-'及びfromIntからなる。determinantの型内で新しいクラスを使用することは、以下の型宣言を導く。
determinant :: a a a -> a | Determinant a
関数determinantとクラスDeterminantの間の違いに注意。クラスDeterminantは、単に型の制限の集合の為の短い記法である。このような型クラスの名前は大文字の記号から始まるべきである。関数determinantは、その関数の型に関するいくつかの制限を定義するコンパクトな方法としてクラスDeterminantを使用する関数に過ぎない。CLEANシステムに関する限り、これらの名前が非常に似ていると思ったとしても偶然の一致である。
C1はクラスC2を保持する新しいクラスであるとする。すると、C2は、いわゆるC1のサブクラスである。サブクラスであるということは、クラスに関して推移的な関係である。つまり、今度はC1がC3のサブクラスであるならば、C2もC3のサブクラスである。
クラス定義はまた、いわゆるクラスのメンバたる新しい多重定義関数を保持することができる。例えば、クラスPlusMinは、以下のように定義できる。
class PlusMin a
where
(+) infixl 6 :: a a -> a
(-) infixl 6 :: a a -> a
zero :: a
PlusMinをインスタンス化するには、メンバの各々のインスタンスを指定しなければならない。例えば、CharのPlusMinのインスタンスは、以下のように見えるかもしれない。
instance PlusMin Char
where
(+) x y = toChar ((toInt x) + (toInt y))
(-) x y = toChar ((toInt x) - (toInt y))
zero = toChar 0
読者の中には、多重定義関数の定義が、単一メンバからなるクラスの定義と本質的に同じであると気づいた人もいるだろう。実際に、クラスと多重定義演算子は1つであり同じ概念である。演算子は単に2つの引数を持つ関数に過ぎないので、通常の関数と同じ方法で型クラス内の演算子を使用することができる。
前に述べたように、クラス定義は実際には、同一名を持つ関数の族を定義している。多重定義関数（クラスメンバ）に対しては、各型インスタンスの為に別々の関数が定義されなければならない。各型に対して唯1つのインスタンスだけが定義されていることを保証する為、型シノニムに対するインスタンスを定義することは認められていない。適用される多重定義関数のインスタンスの選択は、型情報に基づいてCLEANシステムが行う。可能な限りいつでも、コンパイル時にこの選択を行う。ただ、コンパイル時にこの選択を行うことができない場合が時々ある。そのような状況では、その選択は実行時になされる。適用されるクラスメンバの選択が実行時になされる場合でさえ、静的型システムは依然として完全な型の一貫性を保証している。
CLEANでは、クラス定義の一般形式は、以上に議論したバリアントの組合せである。つまり、新しいクラスは、新しいメンバ集合で拡張された既存のクラスの集合からなる。その上、そのようなクラスは、実際のインスタンスを決定できない1つ以上のメンバを使用するあらゆる関数の型コンテクストで現れるだろう。例えば、（個別のクラス'+'、'-'とzeroではなく）PlusMinクラスを使用すると、doubleとdeterminantの型は以下のようになる。
double :: a -> a | PlusMin a
determinant :: a a a -> a | *, PlusMin, fromInt a
CLEANシステムそれ自体は、クラス制限を待つこの種の型を導出できる。
標準環境(StdClass)に定義されているクラスPlusMinは、本セクションで示される定義とは少し異なっている。標準環境の定義は以下のものである。
class PlusMin a | +, -, zero a
クラスPlusMinを使用する場合には、両者の定義の間には違いがない。しかし、そのクラスの新しいインスタンスを定義する場合には、クラスの実際の定義を意識しなければならない。クラスがメンバを保持している場合、ここで示したようにクラスの全メンバのインスタンスを生成しなければならない。StdClassのPlusMinのように、クラスコンテクストによって定義されるクラスについては、そのコンテクストにリストされる全クラスのインスタンスを定義することで、1つのインスタンスを定義する。次のセクションでは、このクラスのインスタンスの定義の1例を示す。
4.1.2 有理数クラス
3.4.1章では、有理数を表現する型Qを導入した。これらの数は双方が型Intである分子と分母フィールドからなるレコードである。
:: Q = { num :: Int
, den :: Int
}
対応する型クラスのインスタンスとしてQに関する通常の算術演算を定義する。例えば、
instance + Q
where
(+) x y = mkQ (x.num * y.den + x.den * y.num) (x.den * y.den)
instance - Q
where
(-) x y = mkQ (x.num * y.den - x.den * y.num) (x.den * y.den)
instance fromInt Q
where
fromInt i = mkQ i 1
instance zero Q
where
zero = fromInt 0
以下のものを使用する。
mkQ :: x x -> Q | toInt x
mkQ n d = simplify {num = toInt n, den = toInt d}
simplify :: Q -> Q
simplify {num=n,den=d}
| d == 0 = abort "denominator of Q is 0!"
| d < 0 = {num = ~n / g, den = ~d / g}
| otherwise = {num = n / g, den = d / g}
where
g = gcd n d
最初に見た時には、例えば、'+'のインスタンスの定義は、'+'の適用がこのインスタンスの本体内に現れているので、再帰的であるかのように見える。しかし、そのコンテクストからするとすぐに、意味される実際の演算は型Intの値に対する'+'であるという結論になる。
新しいデータ型が導入される場合、このデータ型の文字列表現が利用可能であるならば、それはしばしば便利である。とりわけ、この表現は、画面上にその型の具体的値を印字するのに使用できる。このため、クラスtoStringが標準環境に導入されている。
class toString a :: a -> String
それに対応するQのtoStringのインスタンスは以下のように見えるだろう。
instance toString Q
where toString q
| sq.den==1 = toString sq.num
| otherwise = toString sq.num +++ "/" +++ toString sq.den
where
sq = simplify q
Qを抽象データ型にすることで、この関数のqの簡約化を省略できる。このような抽象データ型によって、抽象データ型の関数が、生成された有理数を常に簡約化する場合には、全ての有理数が簡約化されることが保証される。
型Qに対してクラスEnumのインスタンスを定義することで、ドット-ドット式を使用して有理数のリストを生成することさえできる。関数'+'、'-'、zeroやoneとは別に、クラスEnumは順序演算子'<'を保持している。Qに対する'<'の適切なインスタンス宣言は以下のものである。
instance < Q
where
(<) x y = x.num * y.den < x.den * y.num
以下のようなプログラムは、
Start :: [String]
Start = [toString q \\ q <- [zero, mkQ 1 3 .. mkQ 3 2]]
型正当である。これの実行によって以下のものが出力される。
["0","1/3","2/3","1","4/3"]
4.1.3 内部多重定義
以下のプログラムの実行によって、
Start :: String
Start = toString sum
where
sum :: Q
sum = zero + zero
文字列"0"が出る。
以下のように書いたとしても違いはないかのように見える。
Start = toString (zero + zero)
しかし、この状況では、zero、'+'とtoStringの使用インスタンスを一意に決定することはできない。つまり、適用することのできる複数の具体的インスタンスがある。この問題は、式toString (zero + zero)が内部的に多重定義されているということである。つまり、（単純なStringである）それの結果型は、この多重定義を反映していない。このような式によって、コンパイラは以下のエラーメッセージを生成してしまうだろう。
Type error [...]: "zero" (internal) overloading is insolvable
例えば、zeroのインスタンスのどれを使用すべきかが分かると、'+'とtoStringの具体的インスタンスを推論できる。内部多重定義は常に、（上述例のsum関数のように）明示的に型付けされた補助的局所定義を導入することで、解決できる。
曖昧性を解決するもう1つの方法は、デフォルトインスタンスとして、クラスのインスタンスの1つを指定することである。多重定義を解決できない全ての状況では、このデフォルトインスタンスが使用される。例えば、以下のように書くことで、クラスzeroのデフォルトとして、型Qのインスタンスを定義できる。
instance zero Q default
where
zero = mkQ 0 1
この場合には以下のように書くことが認められる。
Start = toString (zero + zero)
このコンテクストは依然として、どのzeroがここで使用されるかを決めはしないが、ここではCLEANシステムはデフォルトのもの、つまり、型Qのzeroを採用する。
4.1.4 派生クラスメンバ
クラスのメンバが、本当は新しい関数ではなくて、（同一クラスかサブクラスの）他のメンバによって定義されているということが時々ある。例えば、標準環境は、以下の方法で、（既にStdOverLoadedでクラスとして定義されている）比較演算子==と<>を保持するクラスEqを導入している。
class Eq a | == a
where
(<>) infix 2 :: a a -> Bool | Eq a
(<>) x y :== not (x == y)
<>演算子は、いわゆる派生クラスメンバの1例である。このメンバは、本体がクラス定義それ自身の中に含まれている。HaskellやGoferのような他の関数型言語とは対称的に、CLEANでは、派生クラスのインスタンスは決して指定できない。つまり、それらは、使用される演算子（上の例の==）に対応するクラスから継承される。
同様のスタイルで、'<'を基にした順序演算子の完全なセットを定義できる。
class Ord a | < a
where
(>) infix 2 :: a a -> Bool | Ord a
(>) x y :== y < x
(<=) infix 2 :: a a -> Bool | Ord a
(<=) x y :== not (y<x)
(>=) infix 2 :: a a -> Bool | Ord a
(>=) x y :== not (x<y)
実際には、等値演算子==も、例えば以下のように指定することで、派生メンバとして定義できる。
class Eq a | < a
where
(==) infix 2 :: a a -> Bool | Eq a
(==) x y :== x <= y && x >= y
(<>) infix 2 :: a a -> Bool | Eq a
(<>) x y :== not (x == y)
このメカニズムにより、ある型に対する'<'のインスタンスを定義するだけで、その型に対する全ての順序演算子を得る。効率性の理由から、これはCLEANの標準環境ではなされない。ある型Tに関する全てのあり得る比較を可能にする為には、'<'と"=="のインスタンスを定義すべきである。
多相的なデータ構造に作用する関数のインスタンスを定義する場合、以下の例に示されるように、これらのインスタンスはそれ自身しばしば多重定義されている。
instance < [a] | < a
where
(<) :: [a] [a] -> Bool | < a
(<) _ [] = False
(<) [] _ = True
(<) [x:xs] [y:ys] = x < y || x == y && xs < ys
インスタンス型[a]を、インスタンス本体内で'<'演算子がリスト要素に適用されるということを反映する型コンテクストに与える。その指定した型は、[a] | < aをクラス変数に代わって置換後'<'のシグニチャから取得した型と、いつものように同じであることに注目して欲しい。
この例は明確に型クラスの表現力を示している。ある型Tのインスタンス'<'が利用可能であるとする。たった１つのインスタンス定義によって、型[T]、型[[T]]等のオブジェクトを比較することが可能となるのである。
4.1.5 型構成子クラス
いままで各型構成子は、その数を示す固定長の要素数を持っており、その型構成子の型引数、適用もそれを持っていると想定してきた。例えば、リスト構成子[]は、要素数1を持ち、3つ組の構成子(,,)は、要素数3を持つ等々である。引数の実際の数が使用している構成子の要素数より少ない場合の型構成子適用を認めることで、高階型を得る。CLEANでは、そのような高階型に及ぶクラス変数を持つクラスを定義することができる。このことは、いわゆる型構成子クラスを導く。型構成子クラスは、多重定義高階関数の集合を定義するのに使用できる。この考えを説明するのに、通常定義されているmap関数を考える。
map :: (a -> b) [a] -> [b]
map f [] = []
map f [x:xs] = [f x:map f xs]
経験あるプログラマならば、類似の関数が幅広い範囲の他の大抵の多相型データ構造にしばしば使用されていることを認識するだろう。例えば、
:: Tree a = Node a [Tree a]
mapTree :: (a -> b) (Tree a) -> Tree b
mapTree f (Node el ls) = Node (f el) (map (MapTree f) ls)
:: MayBe a = Just a | Nothing
MapMayBe :: (a -> b) (MayBe a) -> MayBe b
MapMayBe f (Just a) = Just (f a)
MapMayBe f Nothing = Nothing
これらmapのバリアントの全ては同種の動作をもっているので、単一の多重定義map関数のインスタンスとしてそれらを定義することは魅力的に見える。不幸なことに、今までに示した多重定義機構はこのケースを扱うのに十分なパワーを持っていない。というのも、適切なクラス定義は、（少なくとも）以下の型仕様を処理できるべきだからである。
(a -> b) [a] -> [b]
(a -> b) (Tree a) -> Tree b
(a -> b) (MayBe a) -> MayBe b
適切なインスタンス型で単一のクラス変数を置き換えることによって、これら全ての型仕様を取得可能であるような、mapの型シグニチャは不可能である、ということを知るのは容易である。しかし、一階型ではなく高階型でクラス変数を初期化することを認めることで、以下のクラス定義に示されるように、そのような型シグニチャを発見することはできる。
class map t :: (a -> b) (t a) -> t b
ここでは、通常の型変数aとbは一階型に及ぶが、一方でクラス変数tは高階型に及ぶ。より詳細には、tに代わって置換え可能な具体的インスタンス型は、少なすぎる1引数を持つ（高階）型である。mapの様々なバージョンに対応するインスタンス宣言は今では以下のように指定できる。
instance map []
where
map f l = [f e \\ e <- l]
instance map Tree
where
map f (Node el ls) = Node (f el) (map (map f) ls)
instance map MayBe
where
map f (Just a) = Just (f a)
map f Nothing = Nothing
mapに対する以下のインスタンス宣言も有効である。
instance map (,) a
where
map :: (a -> b) (c,a) -> (c,b)
map f (x,y) = (x,f y)
ここで(,) aは、型変数aに適用される2つ組の型構成子を表す。型(,)のインスタンス（つまり、同一の型構成子だが、今では型引数を持たない）は不可能であることに注目してほしい。
4.2 存在型
多相的代数データ構造は、新しいデータ構造を構築する場合に多大な柔軟性を提供する。例えば、リスト構造は以下のように定義できる。
:: List a = Cons a (List a) | Nil
この型定義は、整数リスト、文字リスト又は何かのリストのリストさえ生成するのに使用できる。しかし、この型定義によれば、リストに保存されているリスト要素の型は全て等しくなければならない。例えば、リストは整数と文字の両方を保持できない。勿論、例えば、以下の補助型を導入することで、この問題をアドホックに解決することはできる。
:: OneOf a b = A a | B b
実際、型List (OneOf Int Char)のリストは、文字と整数の両方を保持しているかもしれないが、この場合でもその選択は制限される。実際には、その自由の量は、データ型定義に現れる型変数の数によって決められる。勿論、これは、有限数の型、例えば、List (OneOf (OneOf Int (List Int)) (OneOf Char (Char -> Int)))に拡張できる。
適用可能性を拡大する為に、CLEANは、いわゆる存在量化された型変数（又は短く存在型変数）を代数データ定義内に使用する可能性を拡張した。存在型変数は、関数の型仕様内では認められていないので、データ構成子は、これら特別の型変数が現れることのできる型仕様を持つ唯一の記号である。以下の例では、様々な型の要素を保存できるリストデータ構造を定義することで、存在変数の使用法を例解する。
:: List = E.a: Cons a List | Nil
aのE接頭語は、aが存在型変数であることを示す。通常の多相的な（又は時々全称量化されたと呼ばれる）型変数とは対照的に、問題になっているある具体型のデータオブジェクトが生成される場合にのみ、存在型変数をその型でインスタンス化できる。例えば、以下の関数を考える。
newlist = Cons 1 Nil
ここでは、構成子Consの変数aはIntでインスタンス化される。一度そのデータ構造が生成されると、その結果型(List)内に反映されるこの具体型の情報は、しかし、失われる。この型によって、我々はCons 1 (Cons 'a' Nil)のような構造を構築することが認められる。
しかし、存在量化された型変数のインスタンス化であるデータ構造に、例えば、関数のパターン照合内でアクセスする場合、これ以上その具体型を導出できない。従って、リストの頭部要素を出力する以下の関数Hdは、
Hd :: List -> ???? // この関数は静的に型付けできない
Hd (Cons x xs) = x
無効である。というのも、返されるリスト要素の実際の型が何であるかについて分からないからである。それはどの型でもあり得るのである。リストに保存されているリスト要素の型が失われるので、関数結果として未知の型のリスト要素を出力することは認められない。というのも、型チェッカはこれ以上型の正当性を保証できないからである。関数Hdは、型システムにより拒絶される。しかし、例えば以下を定義することで、上のリストの尾部にアクセスすることは、
Tl :: List -> List
Tl (Cons x xs) = xs
認められている。つまり、誰も型の安全性を混乱させるかもしれないTlの結果について何もできないのである。
存在型は余り有用ではないと結論するかもしれない。以下に示すように、それは違う。
存在型を使用してオブジェクトを生成
存在量化された部分を持つデータ型は、保存されるオブジェクトにアクセスする方法が存在しないならば余り有用ではないことは明確である。この為、大抵は、インターフェース、つまり、隠蔽されたオブジェクトの情報を変更及び/又は取得する関数の集まりを持つデータ構造を提供する。従って、これらのデータ構造の一般形式は以下のものである。
:: Object = E.a: { state :: a
, method_1 :: ... a ... -> ...
, method_2 :: ... -> ...a...
, ...
}
このトリックは、データ構造生成に際して、型検査器が、状態の内部的型一貫性及び、生成されるデータ構造に一緒に保存されているこの状態に作用するメソッドを、検査することができるということである。一度生成されると、存在量化された型変数に関連付けられた具体型は失われるが、具体型がなんであるかに関わらず、保存されたメソッドは、それに対応する保存された状態に安全に適用できるということを常に保証することが可能である。
オブジェクト指向プログラミングに精通した人ならば、オブジェクト指向データ抽象の概念とCLEANの存在量化されたデータ構造との間の類似性に気がつくだろう。
drawableオブジェクトを以下のように表現する例の助力によって、存在量化されたデータ構造の使用法を例解する。
:: Drawable = E.a: { state :: a
, move :: Point a -> a
, draw :: a Picture -> Picture
}
Drawableは、stateフィールド（つまり、点、線、円等の表現）と、各々画面上にオブジェクトを移動及び表示する2つの関数move及びdrawを保持する。モジュールPictureの標準I/Oライブラリに定義されている多くのグラフィカルデータ構造を使用する。絵を描くことは、Ⅱ部でより詳細に説明する。
:: Point :== (Int, Int)
:: Line :== (Point, Point)
:: Rectangle :== (Point, Point) // 境界上の点
:: Oval :== Rectangle // 境界上の矩形
:: Curve :== (Oval, Int, Int) // startとend角を持つOval
第1に、基本オブジェクトLineとCurveを生成する2つの補助関数を定義する。対応する描画ルーチンは、標準I/OライブラリPictureから取る。移動は直接に定義される。moveの定義では、以下のように定義される組に対する'+'を使用する。
instance + (x,y) | + x & + y
where (+) (x1,y1) (x2,y2) = (x1+x2,y1+y2)
MakeLine :: Line -> Drawable
MakeLine line = { state = curve
, move = \dist line -> line + (dist,dist)
, draw = DrawLine
}
MakeCurve :: Curve -> Drawable
MakeCurve curve = { state = curve
, move = \dist (oval,a1,a2) -> (oval + (dist,dist),a1,a2)
, draw = DrawCurve
}
これらのオブジェクトの構成を例解する為に、4つの線からなる合成構造としてRectangleを定義し、一方で、Wedgeは、2つの線と1つの曲線からなる。
MakeRectangle :: Rectangle -> Drawable
MakeRectangle ((x1,y1),(x2,y2))
= { state = [ MakeLine ((x1,y1),(x1,y2)), MakeLine ((x1,y2),(x2,y2))
, MakeLine ((x2,y2),(x2,y1)), MakeLine ((x2,y1),(x1,y1))
]
, draw = \s p -> foldl (\pict {state,draw} -> draw state pict) p s
, move = \d -> map (MoveDrawable d)
}
MakeWedge :: Curve -> Drawable
MakeWedge curve =: ((begp,endp), a1, a2)
= { state = [ MakeLine (mid,mid+ epc1), MakeLine (mid,mid+ epc2)
, MakeCurve curve
]
, draw = \s p -> foldl (\pict {state,draw} -> draw state pict) p s
, move = \d -> map (MoveDrawable d)
}
where
mid = (begp+endp)/(2,2)
(epc1,epc2) = EndPointsOfCurve curve
EndPointsOfCurveの適切な実装を使用すると、
MoveDrawable :: Point Drawable -> Drawable
MoveDrawable p d =: {state,move} = {d & state = move p state}
両方の合成オブジェクトの移動と描画は同様の方法でなされることに注目。更に、（可能な限り異なった）Drawableは、（このようなオブジェクトの状態は隠されているので）1つのリスト内に保存できるという事実により、これらの演算を行うmapとfoldlのような標準リスト操作関数を使用することができる。勿論、Drawableの型が本当に有用である為には余りにシンプルである。つまり、他の関数は、drawableの内外に、例えば、与えられた点が境界線上にあるかを検査する述語を加えなければならない。そのような拡張は取るに足らないこととはいえないかもしれないが、しかし、存在量化されたデータ構造に基づくこの方法の優雅さは維持される。フルフレッジな型Drawableは、本書のⅡ部で開発する。
存在型VS代数データ型
存在量化されたデータ構造を使用する代わりに、通常の代数データ構造を使用することも可能である。
:: AlgDrawable = Line Line
| Curve Curve
| Rect [Line]
| Wedge [AlgDrawable]
ここでは、drawableオブジェクトの操作は、別個に定義された関数によってなされなければならない。これらの関数は、代数データ型AlgDrawalbleの様々な代替部を正確に構築することについての詳細な知識を使用する。幸運なことに、AlgDrawableの代替部の1つをたまたま省略した場合、コンパイラは警告(Function may fail)を生成する。
move :: Point AlgDrawable -> AlgDrawable
move p object = case object of
Line line -> Line (line + (p,p))
Curve (rect,a1,a2) -> Curve (rect + (p,p),a1,a2)
Rect lines -> Rect [line + (p,p) \\ line <- lines]
Wedges parts -> Wedge (map (move p) parts)
draw :: AlgDrawable -> (Picture -> Picture)
draw object = case object of
Line line -> DrawLine line
Curve curve -> DrawCurve curve
Rect lines -> seq (map DrawLine lines)
Wedge parts -> seq (map draw parts)
これは複数の異なった種類で登場するオブジェクト操作方法であるが、いくつかの欠点を持つ。第1の欠点は、drawableオブジェクトの属性と操作が多くの関数に配布されてしまうということである。多くの関数が操作する複雑な型に対して、そのオブジェクトの全ての情報を集めることは不確実になる。代数データ型を使用することの第2の欠点は、コードを維持することが難しくなるということである。Ovalのような付加的なオブジェクトが導入されると、対応する全ての関数を、矩形操作のために更新するのを保証することは難しい。コンパイラは、新しい種類のオブジェクトを操作することのできない関数は失敗するだろうという警告を作り出すことができるが、これは、いかなるものも保証しない。しかし、これらの警告は、プログラマがオフに切替えるか又は無視することができる。そのような欠如した代替部が実行時に必要とされるような場合には、実行時エラーが生成される（かまたは、デフォルトの代替部が適用される）だろう。
データ型を変更する
心を変えて、境界線上の点によって矩形を保存したいと思う場合、これは、オブジェクト指向的アプローチでは非常に局所的な変化である。関数MakeRectangleのみが変更されればよい。
MakeNewRectangle :: Rectangle -> Drawable
MakeNewRectangle rect = { state = rect
, move = \p r -> r + (p,p)
, draw = DrawRectangle
}
代数データ型AlgDrawableを使用して、drawableオブジェクトを表現し、同等の変化を実装したい場合、そのデータ型に対応する操作関数を変更しなければならない。
:: AlgDrawable = Line Line
| Curve Curve
| Rect Rectangle // 変更
| Wedge [AlgDrawable]
move :: Point NewAlgDrawable -> NewAlgDrawable
move p object = case object of
Line line -> Line (line + (p,p))
Curve (rect,a1,a2) -> Curve (rect + (p,p),a1,a2)
Rect rect -> Rect (rect + (p,p)) // 変更
Wedge parts -> Wedge (map (move p) parts)
draw :: NewAlgDrawable -> Picture -> Picture
draw object = case object of
Line Line -> DrawLine line
Curve curve -> DrawCurve curve
Rect rect -> DrawRectangle rect // 変更
Wedge parts -> seq (map draw parts)
一方で、全く新しい操作関数を加えることは、代数データ型にとってはより容易である。その新しい関数のみを定義すればよい。オブジェクト指向アプローチでは、各オブジェクト生成関数をそれに従って変更しなければならない。
例として、drawableオブジェクトの境界上の矩形を決める演算を加える。代数データ型アプローチについて、以下の関数を定義する。
bounds :: AlgDrawable -> Rectangle
bounds object = case object of
Line line -> normalize line
Curve curve -> curveBounds curve
Rect rect -> normalize rect
Wedge parts -> foldl combine_bounds (map bounds parts)
where
foldl1 :: (a a -> a) [a] -> a
foldl1 f [x:xs] = foldl f x xs
combine_bounds :: Rectangle Rectangle -> Rectangle
combine_bounds ((tl1x,tl1y),(br1x,br1y)) ((tl2x,tl2y),(br2x,br2y))
= ((min tl1x tl2x,miin tl1y tl2y),(max br1x br2x,max br1y br2y))
normalise :: Rectangle -> Rectangle
normalise ((x1,y1),(x2,y2))=((min x1 x2, min y1 y2), (max x1 x2, max y1 y2))
オブジェクト指向的アプローチについては、Drawableとこの型のオブジェクトを生成する全ての関数定義を変更しなければならない。上と同一の補助関数を使用する。
:: Drawable = E.a: { state :: a
, move :: Point a -> a
, draw :: \dist line -> line + (dist,dist)
, bounds :: a -> Rectangle // 新規
}
MakeLine :: Line -> Drawable
MakeLine line = { state = curve
, move = \dist line -> line + (dist,dist)
, draw = DrawLine
, bounds = \l -> normalise l // 新規
}
MakeCurve :: Curve -> Drawable
MakeCurve curve = { state = curve
, move = \dist (rect,a1,a2) -> (rect + (dist,dist),a1,a2)
, draw = DrawCurve
, bounds = \c -> curveBounds c // 新規
}
MakeRectangle :: Rectangle -> Rectangle
MakeReatangle ((x1,y2),(x2,y2))
= { state = [ MakeLine ((x1,y1),(x1,y2)), MakeLine ((x1,y2),(x2,y2))
, MakeLine ((x2,y2),(x2,y1)), MakeLine ((x2,y1),(x1,y1))
]
, draw = \s p -> foldl (\pict {state,draw} -> draw state pict) p s
, move = \d -> map (MoveDrawable d)
, bounds = \parts -> foldl1 combine_bounds // 新規
(map (\{state,bounds} -> bounds state) parts)
}
MakeWedge :: Curve -> Drawable
MakeWedge curve =:((tl,br), a1, a2)
= { state = [ MakeLine (mid, mid+epc1)
, MakeLine (mid, mid+epc2)
, MakeCurve curve
]
, draw = \s p -> foldl (\pict {state,draw} -> draw state pict) p s
, move = \d -> map (MoveDrawable d)
, bounds = \parts -> foldl1 combine_bounds // 新規
(map (\{state,bounds} -> bounds state) parts)
}
where
mid = (tl + br)/ (2,2)
(epc1,epc2) = EndPointsOfCurve curve
代数データ型の忘れられた代替部とは対照的に、存在型アプローチを使用したdrawableの１つの省略された更新は、型エラーを結果する。代数データ型に関連したあり得る実行時エラーよりも、これらの型エラーの方が望ましい。
オブジェクト指向的アプローチ又は代数データ型アプローチのどちらかをいつ使用すべきかの一般規則を与えることはできない。上の例が示すように、両方のアプローチには利点と欠点がある。新しいオブジェクト型を加え、又は、特定のオブジェクト型を変更することは、オブジェクト指向的アプローチにおいては非常に容易で局所的である。一方で、新しい操作関数、メソッドを加えることは、代数データ型アプローチには容易で遥かに局所的である。その決定は、当該データ型に予想される使用及び変更に基づくべきである。幸運なことに、その選択のどちらも大抵の場合実際に間違っている。それは単に簡便性の問題に過ぎない。
関数のパイプライン
存在量化されたデータ構造は、以下の問題を解決するのにも使用できる。一連の関数を、与えられた引数に適用する関数seqを考える（5章も参照）。
seq :: [t->t] t -> t
seq [] s = s
seq [f:fs] s = seq fs (f s)
リストの全要素は同一型を持たなければならないので、seqは、関数の（非常に）限られた列だけを構成できる。一般に、seq [h,g,f]とf o g o hを置き換えることはできない。全ての中間結果の型だけでなく、引数と最終結果の型も全て異なっているかもしれない。しかし、seq関数を適用することで、全ての型は同一になる。
存在型によって、以下の型定義に示されるように、全ての中間結果の実際の型を隠すことができる。
:: Pipe a b = Direct (a->b)
| E.via: Indirect (a->via) (Pipe via b)
このPipeデータ型を使用すると、実際のパイプライン方式で任意の関数を構成することができる。唯一の制限は、2つの連続的な関数の型が照合しなければならないということである。一連の関数をある初期値に適用する関数ApplyPipeは、以下のように定義される。
ApplyPipe :: (Pipe a b) a -> b
ApplyPipe (Direct f) x = f x
ApplyPipe (Indirect f pipe) x = ApplyPipe pipe (f x)
以下のプログラムは、
Start :: Int
Start = ApplyPipe (Indirect toReal (Indirect exp (Direct toInt))) 7
有効である。この結果は、1097である。
4.3 一意型
関数型プログラムについて論じ、分析する為に非常に重要な特性は、参照透明性(referencial transparency)である。関数は、同一の引数で呼出された場合常に同一の結果を返す。参照透明性により、その定義の各引数に代わって、その対応する適用の引数が単一に置換えられる関数定義に、引数を持つ関数適用を置き換えることにより、プログラムの評価について論じることができる。この高校数学から親しむ単一置換（代入）(uniform substitution)の原則は、関数型プログラムを論じるには重要である。
C、C++やPascalのような命令型言語は、データが破壊的に更新されることを認めている。この特徴は、効率性の理由（データ用に確保されるメモリは再利用される）にとって重要であるだけではない。データを破壊的に書き直すことができるということは、あらゆるコンピュータに関するキー概念である。例えば、データベース又はファイルの内容に保存されているレコードを非常に変更したいであろう。この可能性がないならば、重要なプログラムを書くことはできない。関数型プログラムの参照透明的な性質を破壊することなくして破壊的更新を組み込むことは、いくらか努力を要する。
我々が命令型言語に払わなければならない対価は、参照透明性がないことである。つまり、関数適用の値は、以前に評価されたプログラムの一部の効果に依存し得る。これらの副作用は、命令型言語を論じることを非常に複雑にしている。一意型は、参照透明性と破壊的更新を組み合わせる1つの可能性である。
4.3.1 グラフ簡約
今まで、関数型言語CLEANで使用される計算モデルについて余り正確ではなかった。式への参照数は、その式が一意であるかどうかを決めるのに重要なので、もう少し特定しなければならない。
実行の基本成分、いわゆる簡約を論じた。我々が見てきた最初の原則は、単一置換である。引数を持つ関数適用は、定義内の各引数をそれに対応する適用の引数で単一に置き換える関数定義によって置き換えられる。第2の原則は、遅延評価である。式は、最初の式を計算するのにその値が必要な場合のみ評価される。
ここで、グラフ簡約(graph reduction)の原則を加える。変数の全ての出現は、単一置換中に、1つで同一の式に置換えられる。その変数は、仮引数か又は局所定義として導入された式である。これは、式が決してコピーされず、従って、式はせいぜい一回だけしか評価されないということを示している。それに対応する変数は、計算結果を共有することができる。これは、参照透明性によって、行うに健全なものである。つまり、式の値は、評価されるコンテクストから独立している。参照透明性のおかげで、コピーによる場合と共有による場合の単一置換の間には意味論的な違いはない。共有可能な式の簡約はグラフ簡約と呼ぶことができる。グラフ簡約は一般に、通常の簡約よりも効率的である。というのも、それは式の再計算を回避するからである。
グラフ簡約を以下の例によって例解する。簡約ステップは、記号→により示され、一連の簡約ステップは、→*により示される。有用だと分かるときにはいつでも、redex（可約式）に下線を引く。つまり、その式は書換えられる。局所定義は共有を示すのに使用される。
Start = 3*7 + 3*7 | Start = x + x where x = 3*7
|
Start | Start
→ 3*7 + 3*7 | → x + x where x = 3*7
→ 3*7 + 21 | → x + x where x = 21
→ 21 + 21 | → 42
→ 42
最右のプログラムで導入されている共有はある仕事を節約することに注意。これらの簡約列は以下にように描写できる。
図4.1 上に示した簡約列の図的表現
ある仕事が共有されているもう1つの例は、なじみのある累乗関数である。
power :: Int Int -> Int
power x 0 = 1
power x n = x * power x (n-1)
Start :: Int
Start = power (3+4) 2
このプログラムは以下の簡約ステップの列によって実行される。
Start
→ power (3+4) 2
→ x * power x (2-1) where x = 3+4
→ x * power x 1 where x = 3+4
→ x * x * power x (1-1) where x = 3+4
→ x * x * power x 0 where x = 3+4
→ x * x * 1 where x = 3+4
→ x * x * 1 where x = 7
→ x * 7 where x = 7
→ 49
式の参照数は通常参照カウントと呼ばれる。この例からは、その参照カウントが動的に変化し得ることが明らかである。最初には、式3+4のカウントは1である。このノードの最大参照カウントは3である。式3+4、7の結果、つまり簡約物は、2つの場所で使用される。
4.3.2 破壊的更新
ファイルを表現する特別なデータ構造を考える。このデータ構造は、（通常は）破壊的に更新されなければならないディスク上の構造を表現しているので、特別である。従って、そのようなデータ構造を操作するプログラムは、プログラム内部の構造を操作するだけではなく、外の世界の構造（例えば、ファイル）をも操作している。CLEANの実行時システムは、実世界のオブジェクトと貴方のプログラムの内部構造を最新にし続けることに気をつけている。そのプログラムでは、貴方は単にデータ構造を操作するに過ぎないのである。
呼出されているコンテクストから独立している既存ファイルに文字を追加し、修正ファイルを返す関数fwritecを持っているとする。つまり、この関数の意図される結果は、余分な文字が入ったファイルである。
fwritec :: Char File -> File
このような関数は、他の関数によって使用できる。
AppendA :: File -> File
AppendA file = fwritec 'a' file
実際には、Fileは、セクション3.7で紹介したstackに似た抽象データ型である。そのスタックに'a'をプッシュする関数は以下のものである。
pushA :: (Stack Char) -> Stack Char
pushA stack = push 'a' stack
以下のものによって、スタックに2つの文字をプッシュすることができる。
pushAandB :: File -> File
pushAandB stack = push 'b' (push 'a' stack)
ちょうど同じ方法で、ファイルに2つの文字を書き込むことができる。
AppendAandB :: File -> File
AppendAandB file = fwritec 'b' (fwritec 'a' file)
破壊的更新に関する問題
抽象データ型Fileがディスク上のファイルに対応付けられているという事実により、特別な注意が必要である。以下の関数AppendABは、関数型言語で定義できると考えよう。
AppendAB :: File -> (File, File)
AppendAB file = (fileA, fileB)
where
fileA = fwritec 'a' file
fileB = fwritec 'b' file
すると、結果の組(fileA, fileB)のファイル内容はなんであるはずなのか？そこには、両者ともが求めていない属性を持つたった2つの解決法しかないように見える。
第1の解決法は、fwritecが、（命令型言語のように）文字を追加することで、最初のファイルを破壊的に変更していると想定することである。しかしそうなると、AppendABの結果の組の値はその評価順序に依存するだろう。もしfileBがfileAの前に評価されるならば、'b'は'a'の前にファイルに追加される。fileAがfileBの前に評価されるならば、'a'は'b'の前に書きこまれるだろう。このことは、関数プログラミング言語の参照透明性規則を破る。参照透明性を緩めることは、プログラムを分析し論じることを非常に複雑にしてしまうので、単なるファイルの書換えは拒絶される。
第2の解決法は、参照透明性に従って、その結果は2つのファイルを持つ組であるということであろう。つまり、一方のファイルは、文字'a'で拡張され、もう一方は、文字'b'で拡張される。このことは、参照透明性を破らない。というのも、関数呼出しAppendA fileとAppendB fileの結果は、そのコンテクストに影響されないからである。このことは、各関数呼出しfwritecをその'クリーンな'ファイル上で適用しなければならないだろうということを意味している。そして、今度は、関数呼出しAppendABに対しては、ファイルの2つのコピーを生成しなければならないということも意味する。最初のコピーに対して文字'a'が加えられ、第2のコピーに対して文字'b'が加えられる。もしファイルのオリジナルが他のどのコンテクストにも使用されないならば、それをゴミとして捨てることができる。
スタックを使うことでそのようなファイルを実装できる。例えば、以下の関数は、
pushAB :: (Stack Char) -> (Stach Char, Stack Char)
pushAB stack = (push 'b' stack, push 'a' stack)
2つのスタックの組を出力する。これらのスタックは部分的に共有されるかもしれないにもかかわらず、ここでは概念的には2つのスタックがある。'b'を持つものは一方のトップに、'a'を持つものももう一方のトップにある。
しかし、この第2の解決法は、OSの実際の動作の方法に対応していない。これはかなり非実用的である。このことは、画面上のウィンドウに書込みたいと思う場合に遥かに明確になる。つまり、既存ウィンドウに出力を出すことができるようにしたいであろう。この第2の解決法に従うと、各出力コマンドによって新しいウィンドウを構築しなければならないだろう。
従って、参照透明性を破ることなく、ファイル等を破壊的に書換える方法があるならば、それはよいものであろう。我々は、全ての式の結果がよく定義されていることを必要としているし、しかも、不必要なコピーをすることなくファイルやウィンドウを更新したいのである。
4.3.3 一意性情報
この問題を処理する道は、言語設計者の以下のような考え方に典型的かもしれない。つまり、もしそれがいやなら、あなたはそれを行えない。従って、実世界のオブジェクトの参照が2つ以上ある場合にはそれを表わすデータ構造を更新することは認められないだろう。上記AppendABの定義は、従って、コンパイラにより拒絶されるはずである。
fwritecのファイル引数の参照カウントが常にただの1つであることを保証できると仮定する。そのような引数は、一意である(unique)という。ここで、そのような一意なファイルにfwritecを適用すると、以下のことを観察できる。意味的には、新しいファイルを作り出すべきである。しかし、他のどの式も古いファイルを参照できないということを知っている。つまり、fwritecのみがそれの参照を持っている。従って、新しいファイルを構築するのにfwritecの引数として渡される古いファイルを何故再利用しないのか？換言すると、古いファイルが一意である場合、それをfwritecが簡単に破壊的に更新できる結果、意図する効率的で安全な方法で新しいファイルを作り出すのである。
上に示したAppendABの定義は禁止されているが、以下のものを書き下すことは認められる。
WriteAB :: File -> File
WriteAB file = fileAB
where
fileA = fwritec 'a' file
fileAB = fwritec 'b' fileA
ここでは、データ依存関係は、文字がファイルに追加される順序（最初は'a'で次は'b'）を決めるのに使用される。この解決法は、上に導入した関数AppendAandBに意味的には等しい。このプログラミングスタイルは、従来からの命令型スタイルに非常に似ている。そこでは、文字が、連続したプログラムステートメントによって追加されるからである。しかし、文字が追加されるファイルが、ある特定の関数定義から他のものに、引数として明示的に渡されることに注意。この引数を渡す技術は、環境渡しと呼ばれている。その関数は、状態遷移(state transition)関数と呼ばれる。というのも、渡される環境は、渡される間に変化するかもしれない状態と見ることができるからである。
4.3.4 一意性型付け
勿論、どうにかして適切に、つまり必要な更新ができる方法で、その環境が渡されることが保証（及び指定）されなければならない。この為、一意性(uniqueness property)を導出する型システムが設計される。関数は、評価時に引数へのただ1つの参照しか存在しない場合に、一意型(unique type)の引数を持つといわれる。この性質により、関数が適切な時に、引数の消費するメモリを再利用することが安全になる。
図4.1では、左側の例の全ての部分が一意である。右側では、式3*7は、一意ではない。というのも、加算の両側の引数が共有しているからである。いくつかの画を描くことによって、上に紹介した関数WriteABが一意のファイルを使用している一方で、AppendABでは、ファイルの参照カウントは2であることがすぐに明確である。従って、関数AppendABは、コンパイラにより拒絶される。
図4.2 WriteAB fileの結果
図4.3 AppendAB fileの結果
関数fwritecは、（上書きできるようにするために）一意型である第2引数のファイルを要求し、結果として、WriteABも一意な引数を持たなければならないことが導出される。その型の中でこの一意性は、従来の型に属性として添付されている'*'で表現される。この'*'は、コンパイラにより使用される。つまり、その型は、関数が実行される場合において、それに対応する引数の参照カウントがちょうど1つであることを決めることができる場合にのみ、コンパイラによって承認されるのである。
fwritec :: Char *File -> *File
WriteAB :: *File -> *File
一意性型システムは、従来の型システムに加えられた拡張である。関数の型仕様において引数が一意な型属性(*)に属性付けられる場合、関数評価の際には、その関数がこの特定の引数に対するプライベートな（一意な）アクセスを持つということを型システムが保証する。
一意性の型の正当性は、（正格性情報以外の）他の全ての型情報の場合のように、コンパイラが検査する。ここで、プログラマが以下のように関数AppendABを定義したとする。
AppendAB :: File -> (File, File)
AppendAB file = (fileA, fileB)
where
fileA = fwritec 'a' file
fileB = fwritec 'b' file
コンパイラは、以下のエラーメッセージでこの定義を拒絶する。
<conflicting uniqueness information due to argument 2 of fwritec>
この定義のこの拒絶は、2つの局所定義の引数ファイルを非一意に使用することで引き起こされている（型fwritec :: Char *File -> *Fileであるとする）。
この特定のアクセス発生前にそのオブジェクトの参照が多く存在し得るということを知ることは重要である。例えば、以下の関数定義は、その引数ファイルに2つの参照があるにもかかわらず、型システムが承認するだろう。しかし、fwritecが呼出されると、その参照は一意である。
AppendAorB :: Bool *File -> *File
AppendAorB cond file
| cond = fwritec 'a' file
| otherwise = fwritec 'b' file
従って、一意性型付け(uniqueness typing)の概念は、引数に、関数の局所性の要件を指定する方法として使用できる。つまり、もし関数、つまり、Fの引数の型が一意であるならば、Fの全ての具体的適用において、実引数は参照カウント1を持つので、Fは実の所それに対するプライベートなアクセスを所有する。これは、ファイルに文字を書きこむ関数fwritecのような（固有の）破壊的作用を定義するのに使用できる。
結果型の一意性も指定可能で、fwritecの適用結果を、例えば、別のfwritecの呼出しに渡すことが認められるということに注目してほしい。そのような一意性型付けと明示的環境渡しの組合せは、評価中のどの時点でも、実際のファイルが参照カウント1を持ち、ファイルの全ての更新を適当な位置で安全に行うことができるということを保証する。もし一意属性を引数の型に指定しないならば（例えば、fwritecのChar引数）、対応する実引数の参照カウントは一般に、実行時には分からない。従って、その引数の局所性に関して前提を作ることはできない。つまり、それは非一意(non-unique)とみなされる。
関数が非一意な引数を必要とする場合に、一意な引数を提供することは、安全である。より技術的には、一意なオブジェクトは非一意なものに型変換(coerce)できるという。例えば、関数freadcとfwritesが以下の後者の適用において、前者の型を持つとする。
freadc :: File -> (Bool, Char, File) // 論理値は成功又は失敗を示す
fwrites :: String *File -> *File
readwrite :: String *File -> (Bool, Char, File)
readwrite s f = freadc (fwrites s f)
fwritesの（一意な）結果Fileは、freadcに渡される前に、非一意なものに型変換される。
勿論、関数が一意なオブジェクトを必要とする場合に、非一意なオブジェクトを提供するすることは常に失敗する。というのも、非一意なオブジェクトは、可能な限り共有され、破壊的更新をよく定義しないからである。オブジェクトは、一意性がそのコンテクストによって必要とされるからだけではなく、共有の理由からもその一意性を失うかもしれないことに注意。例えば、このことは、（一意な結果型の為に）fwritecそれ自体の適用が常に一意であるにもかかわらず、もし複数の参照が存在するならば、それは非一意であるとみなされるということを意味する。まとめると、（引数の）提供する型は、最外の適用の結果型とその引数の参照カウントによって決められるのである。
いままで、参照カウント1のオブジェクトと、より大きな参照カウントのオブジェクトを区別してきた。つまり、前者のみが一意であリ得る（オブジェクト型それ自身に依存するが）。上の例で分かるように、参照カウントは、各右側で別々に計算される。ガード内に、一意なオブジェクトを必要とする式がある場合には、これを考慮しなければならない。これは、我々が以下のように書かなければならない理由である。
AppendAorB :: *File -> *File
AppendAorB file
| fc == 'a' = fwritec 'a' nf
| otherwise = fwritec 'b' nf
where
(_,fc,nf) = sfreadc file
関数sfwritecは、一意なファイルから文字を読みこみ、一意なファイルを出力する。
sfreadc :: *File -> (Bool, Char, *File)
ここで、ファイルから文字を読み込むことが常に成功すると仮定する。AppendAorBの右側が評価されると、そのガードがまず決定され（従って、sfreadcからfileへの結果アクセスは非一意である）、その結果、その代替部の1つが選択され評価される。条件節fc == 'a'如何によって、nfへのfwritecの最初の適用の参照か又はその次の適用の参照のどちらか一方が、未使用のままにされるので、従って、その結果は一意である。予想するかもしれないが、関数AppendAorBの右側で、nfの代わりにfileを使うことは認められない。ファイル操作は、5章でより詳細に説明する。
4.3.5 入れ子通用範囲スタイル
環境を渡す関数を組み合わせるのに便利な記法は、（let又は#が示す）let-before定義の入れ子された通用範囲を使用することである。このスタイルでは、WriteABは以下のように書くことができる。
WriteAB :: File -> File
WriteAB file
# fileA = fwritec 'a' file
# fileAB = fwritec 'b' fileA
= fileAB
let-before式は、命令型プログラミングの外見を持つ特別な通用範囲規則を持つ。これらの定義の左側の変数は、その定義の右側の通用範囲には現れないが、それに続く他の定義の通用範囲には現れる（root式は含み、whereブロックの局所定義は除く）。このことは図4.4で示される。
図4.4 let-before式の通用範囲
let-before式の変数の通用範囲は、代替部のwhere式の定義には及ばないということに注意。しかし、その逆は真である。つまり、where式の定義は、let-before式内で使用できる。
let-beforeの通用範囲の入れ子により、WriteABの定義は、以下のように書くことができる。
WriteAB :: File -> File
WriteAB file
# file = fwritec 'a' file
# file = fwritec 'b' file
= file
従って、中間のファイル(fileA,fileAB)に新しい名前を発明することはなく、名前fileを再利用できる。入れ子通用範囲記法は、非常に良く簡潔だが、通用範囲の常として、危険でもあり得る。つまり、同一名fileの意味が常に同じとは限らない一方で、それは異なったスポットで使用される（定義から定義まで変化する通用範囲を考慮しなければならない）。しかし、同一名の再利用は、一意型のスレッド化された引数に使用される場合にはかなり安全である。そのような引数が正確にシングルスレッドな方法で使用されない場合、型システムはそれを見付け（そしてそれを拒絶す）るだろう。他のケースに命令型プログラミングスタイルを採用する為に、let-before式を使用することは確実に勧められない。
'#'定義の導入する変数の通用範囲は、'#'に続く関数の右側の部分である。右側の'#'定義とwhere定義は、この通用範囲から外される。'#'定義の右側を外す理由は、上の例から明白である。'#'定義の本体が通用範囲の一部である場合、変数fileは循環的な定義であろう。where定義を外す理由は、幾分トリッキーである。where定義の通用範囲は、関数代替部の右側全体である。これは、'#'定義を含む。このことは、WriteABのwhere定義で変数fileを使用する場合には、それは最初の関数引数であるべきだということを示している。これは、直観の反対であり、fileは最後のfreadcの結果であると予想するだろう。そのような関数の本体の1つにローカル定義が必要な場合、let又はwithを使用すべきである。様々な局所定義のより念の入った議論については言語マニュアルと6章を参照。
4.3.6 一意性の伝播
パターン照合は、関数が単一の参照を経由してではなく、データパスを経由してより深い引数にアクセスできることをもたらす関数プログラミング言語の本質的側面である。例えば、以下のように定義されるリストのhead関数は、
head :: [a] -> a
head [x:xs] = x
xとxsの両方に対する（間接的な）アクセスを持つ。このより深いアクセスは、いわゆる間接共有をもたらす。つまり、オブジェクト自身は参照カウント1を持つにもかかわらず、複数の関数が（中間のデータ構成子を経由して）その同一オブジェクトをアクセスする。例えば、以下のように定義される関数headsを考える。
heads list = (head list, head list)
headsの右側では、headの両方の適用が、同一のリスト構成子を経由してその結果を取得する。以下のプログラムでは、
Start = heads [1,2]
整数1は、それが参照カウント1を持つにもかかわらず、一意であリ続けられない。この例では、共有は、listが参照カウント2を持つという事実によって示される。共有は、以下の場合のように更に隠蔽することができる。
heads list =: [x:_] = (head list, x)
もし、例えば、headの頭部引数に関する一意性の要件を明確化したいならば、対応する'*'を持つ型変数aを属性付けることでは十分ではない。つまり、周囲のリストそれ自体も一意になるべきである。リスト要素の一意性は外に伝播する(propagate outwards)ということができる。つまり、もしリストが一意な要素を保持するならば、リストそれ自体も一意であるべきである。この伝播条件がなければ、オブジェクトの局所性をこれ以上保証できないということは容易に理解できる。例えば、headに対する以下の型を認めてみるとする。
head :: [*a] -> *a
すると、headsの定義は型付け可能である。というのも、2つのhead適用の直接の引数には一意性の要件がないからである。headsの型は以下のものである。
heads :: [*a] -> (*a,*a)
これは明らかに正しくない。というのも、同一オブジェクトが2回出力されているからである。しかし、一意性伝播規則を適用することは、以下の型を導く。
head :: *[*a] -> *a
実際、これは、headの全ての適用においてリスト引数の共有を排除するので、headsの定義は最早有効ではない。これこそが我々の必要とするものである。
一般に、伝播規則は、もし一意なオブジェクトがより大きいデータ構造に保存されるならば、そのデータ構造も一意であるべきだという考えを反映している。これは、以下のようにも定式化できる。あるデータ構造内に保存されるオブジェクトは、そのデータ構造それ自体も一意である場合にのみ一意であり得る。
しかし、実際には、その評価順序が考慮される場合、もっと自由でいることができる。その趣旨は、もしオブジェクトの破壊的アクセス時には参照のただ1つだけが存在しているに過ぎないということを知っているならば、（一意な）オブジェクトの多数の参照は無害であるということである。例えば、コンパイラは、定義済み条件関数ifでは、ただ1つの枝のみが使用されるということを知っている。このことは、以下の関数が正しいことを示している。
transform :: (Int -> Int) *{#Int} -> *{#Int}
transform f s
| size s == 0 = s
| otherwise = if (s.[0] == 0)
{f i \\ i <-: s}
{f i \\ _ <-: s & i <- [s.[0]..]}
この例は、オブジェクトの一意性がファイルやウィンドウに制限されないということも示している。配列は通常は大きいので、CLEANでは、一意な配列を更新することのみが認められている。古い配列のスペースを使用すると、そのような更新を非常に効率的に行うことができる。
4.3.7 一意性の多相性
関数が引数の一意性を変化させないでいることを示すために、（一意）属性変数を使用することができる。最もシンプルな例は、以下のように型付けできる恒等関数である。
id :: u:a -> u:a
ここでは、aは通常の型変数だが、uは属性変数である。もしidが一意なオブジェクトに適用されると、その結果も一意である（その場合には、uは具体的な属性'*'にインスタンス化される）。勿論、もしidが非一意なオブジェクトに適用されれば、その結果も非一意なままである。CLEANには非一意に対する表記が存在しないにもかかわらず、その属性を暗黙に想定していることに注意。
次の例は、型変数と属性変数は区別する必要があるということを示している。
tup :: a -> (a, a)
tup x = (x, x)
tupの引数が一意であっても、結果では、この式は共有される。
より興味深い例は、以下のように型付けされる関数freadcである。
freadc :: u:File -> (Bool, Char, u:File)
ここでも、freadcは一意及び非一意なファイルの両方に適用できる。最初の場合には、結果のファイルも一意であり、例えば、書込みだけでなく更には読込みにも使用できる。第2の場合には、結果のファイルも非一意であるので、書込みアクセスは認められない。
いわゆる強制型変換ステートメント(coercion statement)を加えることにより、関数の型仕様の中に現れる属性変数間の関係を指示することもできる。これらのステートメントは、形式u <= vの属性不等式からなる。この趣旨は、その結果の属性不等式が、有効である、つまり、以下の形の等式に帰結しない場合にのみ、属性置換（代入）が認められるということである。
'非一意 ≤ 一意'
強制型変換ステートメントの使用法は、よく知られた追加演算子"++"の一意性を示す次の例によって例解される。
(++) infixr 5 :: v:[u:a] w:[u:a] -> x:[u:a], [v w x<=u, w<=x]
最初の強制型変換ステートメントは、リストに対する一意性の伝播を表現している。つまり、もしその要素が（uに'*'を選択することで）一意であるならば、これらのステートメントは、v、wとxも'*'によってインスタンス化されることを強制する。もしu = *ならば、u <= *であることに注意。後者のステートメントw<=xは、追加結果のスパイン(spine)の一意性が、第2引数のスパインの属性wにのみ依存しているということを表現している。これは、追加の操作的な動作を反映している。つまり、結果リストを取得する為に、最初のリスト引数を完全にコピーし、その後で最末尾のポインタを第2リスト引数にリダイレクトする。
(++) [x:xs] list = [x: xs ++ list]
(++) _ list = list
CLEANでは、伝播属性から発生する属性変数と属性不等式を省略することが認められている。つまり、それらは型システムが自動的に追加する。結果として、++に対する以下の型仕様も有効である。
(++) infixr 5 :: [u:a] w:[u:a] -> x:[u:a], [w<=x]
勿論、（型及び/又は属性変数をインスタンス化することにより）更に特定した型を使用することは常に認められている。以下に与えられる全ての型は++に対して有効な型である。
(++) infixr 5 :: [u:a] x:[u:a] -> x:[u:a]
(++) infixr 5 :: *[*Int] *[Int] -> *[*Int]
(++) infixr 5 :: [a] *[a] -> *[a]
型の可読性をより高める為に、CLEANは、実際の名前が本質的ではない属性変数の略記として、無名(anonymous)属性変数を使用する可能性を提供している。無名な属性を使用すると、++は以下のように型付けできる。
(++) infixr 5 :: [.a] w:[.a] -> x:[.a], [w<=v]
これは、コンパイラが導出した型である。CLEANの型システムは、本当の属性変数を無名のものに置換える。各'.'は、型変数に付いているドットを除いて新しい属性変数を引き起こす。つまり、型変数は、同一型変数の全ての出現が同一属性を獲得するという意味で、一意に属性付けされる。上の例では、このことは、全ての'.'が1つでありしかも同一の（新しい）属性変数によって置換されるということを意味している。
最後に、通常のリストが予想される場合には一意なリストを常に使用することができる。従って、以下の型を追加演算子に指定することで十分である。
(++) infixr 5 :: [.a] u:[.a] -> u:[.a]
正格性記法とは別に、これは、標準環境のモジュールStdListの追加演算子に指定されている型である。
4.3.8 属性付けられるデータ型
第1に、データ構成子の型は、プログラマによって指定されるのではなく、それに対応するデータ型定義から導出されるということを忘れないでほしい。例えば、List型の（古典的な）定義は、
:: List a = Cons a (List a) | Nil
以下のデータ構成子の型を導く。
Cons :: a (List a) -> List a
Nil :: List a
データ型の一意なインスタンスを生成できるようにする為に、プログラマは、それに対応するデータ型定義それ自体を変更しない。つまり、CLEANの型システムは、全データ構成子の（古典的な）型の適切な一意のバリアントを自動的に生成する。そのような一意のバリアントは、データ型定義に現れる全ての型及び部分型を一貫性を持って属性付けることで得られる。例えば、Consに対しては、この属性付けは以下の型を出力する。
Cons :: u:a v:(List u:a) -> v:List u:a, [v<=u]
これの全ての詳細に付いてその属性付け機構を説明することは、本書の範囲を越えている。つまり、その手続はリファレンスマニュアルと[Barendsen 93]に見つけることができる。その主たる性質は、全ての型変数及び定義した型構成子（つまりT）の全出現は、属性変数を受け取るということである。またこれは、単一の方法でなされる。つまり、等しい変数は等しい属性を受け取り、Tの出現も等しく属性付けられる。その上、属性変数は、もしそれが対応する型構成子の伝播性によって必要とされるならば、不可変な位置で加えられる（以下の例参照）。強制型変換ステートメントは、通常のように、伝播規則によって決められる。例として、以下のTree定義を考える。
:: Tree a = Node a [Tree a]
データ構成子Nodeの型は以下のものである。
Node :: u:a w:[v:Tree u:a] -> v:Tree u:a, [v<=u, w<=v]
リスト型がその要素のv属性を伝播するので、一意性変数wと強制型変換ステートメント[w<=v]が付加されるということに注目して欲しい。
データ型定義の一部は、定義された型構成子（つまり、T）それ自体と同じ属性を受け取らなければならないと指定することもできる。この為に、無名の(.)属性変数が予約されている。そして、それはTの定義の右側のあらゆる（部分）型に付けることができる。その趣旨は、'.'属性が、Tの出現に割り当てられるものと同一の属性を表しているということである。これは、もし関数をデータ構造に保存したいならば部分的に有用である。つまり、高階一意性型付けに関する次のセクションも見て欲しい。例えば、Treeの以下の定義は、
:: Tree2 = Node2 .Int [Tree2]
データ構成子Nodeの型が以下のものに拡張されるということをもたらす。
Node2 :: u:Int v:[u:Tree2] -> u:Tree2, [v<=u]
不幸なことに、型属性vは、構成子Nodeの結果では使用されない。従って、その型にNodeの引数の一意性を保存する方法はない。従って、型Listとは対照的に、型Treeの一意なインスタンスを構築することはできない。このことは、以下の事を示す。つまり、木を逆にする関数
swap (Node a leafs) = Node a [swap leaf \\ leaf <- rev leafs]
rev :: [.a] -> [.a]
rev list = rev_ list []
where rev_ [x:xs] list = rev_ xs [x:list]
rev_ [] list = list
は、以下の型を獲得する。
swap :: (Tree a) -> Tree a
以下のものではなくて。
swap :: u:(Tree .a) -> u:(Tree .a)
このことは、一意な木が、この関数swapによって交換される場合にその一意性を緩めるということを意味している。上に紹介した略記により、最後の型は以下のようにも書くことができる。
swap :: u:(Tree .a) -> (Tree .a)
型Treeの一意なインスタンスを必要とする場合、ある節の内側の木のリストは、その節全体と同一である一意型属性を持つということを示さなければならない。
:: Tree a = Node a .[Tree a]
ここでは、コンパイラは、一意な木の交換は一意な木を出力する、ということを示す型、つまり、swap :: (Tree .a) -> (Tree .a)を導出し、認めるだろう。
全ての木が一意であるべき場合は、以下のように定義すべきである。
:: *Tree a = Node a [Tree a]
これに対応する関数swapの型は以下のものである。
swap :: *(Tree .a) -> *Tree .a
実際には、定義済みの属性付けスキームは、余りに制限的であるように見える。まず第1に、もしデータ構造のある部分が常に一意であると指示することが認められているならば、便利である。例えば、型Filesの（一意な）ファイルシステムを保持する、5章で定義されている型Progstateを考える。
:: *ProgState = {files :: Files}
上記の属性付け機構によれば、Filesは非一意であっただろう。この問題を欺く為に、Progstateを多相的にすることができる。つまり、定義Progstateは以下のようになる。
:: Progstate file_system = {files :: file_system}
すると、Progstate *FilesによってProgstateの全ての使用を置き換えることができる。勿論、これは、すこし骨の折れることであり、従って、データ型定義それ自体の中に'*'属性を含めることが認められている。従って、Progstateの定義は実際に有効である。'*'属性が外へ伝播するので、Progstateそれ自体は一意になっていることに注意。このことは、Progstate定義の左側の'*'を説明する。
4.3.9 高階一意性型付け
高階関数は、（データ構成子だけでなく関数の）部分（しばしばカリー化と呼ばれる）適用をもたらす。つまり、引数の実際の数がそれに対応する記号の要素数より少ない場合の適用である。もしこれらの部分適用が一意な部分式を保持しているならば、気を付けなければならない。例えば、適用(fwritec unifile)において、型fwritec :: *File Char -> *Fileを持つ以下の関数fwritecを考える（unifileは一意なファイルを返すものとする）。この適用の型が形式o:(Char -> *File)であることは明白である。疑問は、どの種の属性がoなのか？ということである。それは、変数なのか'*'なのか、それとも非一意であるのか？決める前に、上の適用を共有することを認めるのは危険であるということを例解しよう。例えば、(fwritec unifile)が以下の関数に渡される場合、
WriteAB write_fun = (write_fun 'a', write_fun 'b')
fwritecの引数は、2つの書込み作用が出現した時点で最早一意ではない。明らかに、(fwritec unifile)式は、本質的に一意である。つまり、その参照は1より大きくなるべきでは決してない。そのような本質的に一意な式がコピーされることを防止する為に、一意性型システムは、特別に'*'属性と組み合わせて"->"型構成子を考慮する。つまり、その一意性を無視することは許されない。ここで、属性oについての疑問に答えることができる。つまり、それは'*'に設定される。もしWriteABが以下のように型付けされるならば、
WriteAB :: (Char -> u:File) -> (u:File, u:File)
WriteAB write_fun = (write_fun 'a', write_fun 'b')
式WriteAB (fwritec unifile)は、型システムによって拒絶される。というのも、それは、型*(Char -> *File)の実引数が(Char -> u:File)に型変換されることを許さないからである。その式が型付け可能になる方法で、WriteABを型付けすることはできないことが容易に分かる。これはちょうど我々がファイルに対して求めているものである。
カリー化適用を保持するデータ構造を定義するには、（無名の）ドット属性を使用することがしばしば便利である。例えば、
:: Object a b = { state :: a
, fun :: .(b->a)
}
new :: *Object *File Char
new = {state = unifile, fun = fwritec unifile}
newは本質的に一意な式を保持しているので、それ自身本質的に一意な式になる。従って、newの結果は、保持しているどんなnewにおいても、コンテクストの求める属性型は一意でなければならないということを示す一意なオブジェクトに型変換できるに過ぎない。
関数の型が具体的属性ではなく属性変数を保持している場合には、関数（又はデータ構成子）のカリー化適用の型を決定することは、いくらか込み入っている。大抵は、これらの変数は、以下の例に見られるように追加的な強制型変換ステートメントをもたらす。
Prepend :: u:[.a] [.a] -> v:[.a], [u<=v]
Prepend a b = Append b a
PrependList :: u:[.a] -> w:([.] -> v:[.a]), [u<=v, w<=u]
PrependList a = Prepend
以下の説明が適している。式PrependList some_listは、もう1つのリスト、つまり、other_listに適用されると、other_listとsome_listの結合からなる新しいリストを出す関数を出力する。これを最終結果new_listと呼ぶ。もしnew_listが一意であるならば（つまり、vが*になる）、型変換ステートメントu<=vにより、属性uも*になる。しかし、もしu = *ならば、w = *にもなる。というのも、w<=uだからである。このことは、オリジナルの式PrependList some_listの（矢印）型が一意になり、従ってこの式は共有できないということを示している。（関数又はデータ）記号のカリー化バリアントの一意型を決める一般規則は、全く複雑であり、リファレンスマニュアルと[Barendsen 93]で見つけることができる。
4.3.10 一意なオブジェクトを生成
前のサブセクションでは、一意のオブジェクトを操作する方法を示した。残っている問題は、最初から一意なオブジェクトになる方法である。ファイルやウィンドウのような実世界の実体に対応する全ての一意なオブジェクトは、その世界から取得される。これは、5章で詳しく説明する。
他のデータ型の一意なオブジェクトを持つこともできる。特に配列にとっては、一意な配列だけが破壊的に更新できるので、一意なインスタンスを持つことは有用である。そのようなデータ構造は、最大の効率性が必要な場合に非常に有用である。
4.4 演習
- 標準クラスArithの型Qに対するインスタンスを定義せよ。
class Arith a | PlusMin, MultDiv, abs, sign, ~ a
- Qに似ている複素数を定義し、この新しい型に対するクラスArithのインスタンスを指定せよ。
- リスト[a]のPlusMinのインスタンスを定義し、例えば、2つのリストの加算が要素に関して出現するようにせよ（もし必要ならば、最小リストは、長さの等しい2つのリストを獲得するために、0によって拡張される）。従って、[1,2,3] + [4,5] = [5,7,3]
- なぜPipeオブジェクトは少なくとも1つの関数を保持すべきなのか（各Pipeは、適用される最後の関数を保持するDirect構成子で終わる）？終端子として引数を持たない一種のNil構成子を持つPipeの定義を想像できる。
First Uploaded : June 13, 2002
Last Modified : July 21, 2003
Back