CDuceでは、型は値の集合を意味し、パターンは値から部分値を抽出する。構文的には、型とパターンは非常に似ている。実際、型はどんな型でもパターンとして出現でき(どんな値でも受け付け、何も抽出しないパターンとなる)、又、捕獲変数のないパターンは、型にすぎない。
さらには、値も型やパターンと共通の構文を共有している。これは、基本の値、及び構築された値(つまり、中に関数値のない値)は、それ自体単一型である。たとえば、(1,2)は値、型及びパターンのすべてになる。型としては、単一型、あるいは二つの単一型からなるペア型として解釈されうる。パターンとしては、型制約として、あるいは二つの型制約のペアパターンとして解釈されうる。
このページでは、CDuceが認識する型及びパターンの全てを紹介する。CDuce値自体、対応するコンストラクション式、及びそれに対する基礎的な操作を紹介するのにいい機会ともなる。
パターン中にある値識別子は、捕獲変数として振舞う。いかなる値も受理し、束縛する。
捕獲変数には別の形式があり、xを捕獲変数(つまり識別子)、cをスカラ定数として、として、デフォルト値パターンx := cである。このパターンは、捕獲変数を定数に束縛するということを意味し、マッチした値は無視する(又、いかなる値も受理する)。
このようなパターンは、ファーストマッチポリシ(下を参照)と連動させて、"デフォルトの場合"を定義するのに便利である。例えば、パターン((x & Int) | (x := 0), (y & Int) | (y := 0))は、いかなるペアも受理し、左の成分が整数であればxに(そうでなければ0に)束縛し、ペアの右の成分も同様にyに束縛する。
CDuceは、ブール結合子のフルセットを認識し、その解釈は純粋に集合理論に基づく。
Emptyは空の型(値なし)を意味する。Any及び_は汎用の型(すべての値)を意味する。好まれる記法は、型にはAny、パターンには_であるが、これらは厳密に等価である。
&は、連言ブール結合子である。型t1 & t2型は、t1及びt2に属する値全てを持つ。同様に、パターンp1 & p2は、両方の部分パターンによって受理される全ての値を受理する。一つの捕獲変数がこのパターンの両側で出現することはできない。|は、選言ブール結合子である。型t1 | t2型は、t1又はt2のいずれかに属する値全てを持つ。同様に、パターンp1 & p2は、二つの部分パターンのどれかに受理される全ての値を受理する。両方がマッチすると、ファーストマッチポリシが適用され、p1が部分値をどう捕獲するかを指示することになる。二つの部分パターンは、同じ捕獲変数の集合を持っていなければならない。\は、差ブール結合子である。左側は型でもパターンでもいいが、右側は必ず型(捕獲変数なし)となる。相互再帰型は、次のようにトップレベル型宣言で定義される。
type T1 = <a>[ T2* ] type T2 = <b>[ T1 T1 ]
TとTiを型識別子、tiを型式として、構文T where T1 = t1かつ…かつTn = tnを使うこともできる。再帰パターンも同じ記法で動作する(パターンに対しては、トップレベル宣言はない)。
再帰型に関して、重要な制約がある。循環は、型コンストラクタ(ペア、レコード、XML要素、矢印)を横断しなければならない。ブール結合子は型コンストラクタとして考えない。上のコード例は、正しい定義である。下のコード例は、TとSの間に無防備な循環があるため、不正である。
type T = S | (S,S) (* INVALID! *) type S = T (* INVALID! *)
CDuceは三種類のアトミックな(スカラーの)値を持つ。整数、文字とアトムである。各種類の値に対して、一種類の型が対応している。
Int: 全整数i--j (i及びjを整数リテラル又は無限大に対応する*とする): 整数の範囲。例: 100--*、*--0(*が正負両方の無限大を意味することに注意)i (iを整数リテラルとする): 整数の単一型Float型の値を作る方法は、float_of : String -> Float関数を用いる方法しかない。'a'、'b'、'c'。シングルクォート及びバックスラッシュ文字は、バックスラッシュでエスケープしなければならない。'\''、'\\'。ダブルクォートもエスケープできるが、必須ではない。例の'\n'、'\t'、'\r'が認識される。任意のUnicodeコードポイントを十進で'\i;'(i)は十進整数である。コードがセミコロンで終わることに注意)、十六進で'\xi;'と書くことができる。他のいかなるバックスラッシュ文字の出現も禁止されている。
Char: 全てのUnicode文字集合c--d(c及びdを文字リテラルとする): Unicode文字集合の範囲。例: 'a'--'z'c(cを整数リテラルとする): 文字の単一型Byte: 全てのLatin1文字集合('\0;'--'\255;'と等しい)`xxxがCDuceの識別子規則に従うとして、xxxと書く。例: `yes、`No、`my-name。アトム`nillは空のシーケンスを示すのに使われる。
Atom: 全てのアトムa(aをアトムリテラルとする): アトム単一型Bool: 二つのアトム`true及び`falseペアは、CDuceの基本的な記法であり、シーケンスに対する構造の部品となっている。シーケンスを使うと、糖衣構文によりペアは隠されるが、ペアの存在を知っておくのはよいことである。
ペア式は、e1及びe2を式として、(e1,e2)と書く。
同様に、ペア型及びパターンは、t1及びt2が型又はパターンとして、(t1,t2)と書く。例: (Int,Char)
捕獲変数xがペアパターンp = (p1,p2)の両側に出現すれば、次のような意味となる。値がpとマッチすれば、xがp1によりv1に、及びp2によりv2に束縛されれば、xはpにより(v1, v2)に束縛される。
タプルはペアに対する糖衣構文である。例えば、(1,2,3,4)は(1,(2,(3,4)))を意味する。
シーケンスはCDuceにおいて基本をなすもので、XML要素、さらには文字列の内容を表現する。実際には、ペアに対する糖衣構文にしか過ぎない。
シーケンス式は、大括弧で囲んで書く。要素は、[ e1 e2 ... en ]のように空白で区切られる。。この式は、(e1,(e2, ... (en,`nil) ... ))に対する糖衣構文である。例: [ 1 2 3 4 ]。
二項演算子@は、シーケンスの連結を意味する。例: [ 1 2 3 ] @ [ 4 5 6 ]は[ 1 2 3 4 5 6 ]と等しい。
`nilと異なる終端子を指定することもできる。例えば、[ 1 2 3 4 ; q]は(1,(2,(3,(4,q))))を意味し、[ 1 2 3 4 ] @ qと等しい。
シーケンス式の大括弧の中で、eがシーケンスと評価されるはずの式であるとして、形式! eの要素を持つことができる(これ自体は式ではない)。意味は、eを"開く"ということである。例えば、[ 1 2 ![ 3 4 ] 5 ]は評価されて[ 1 2 3 4 5 ]となる。したがって、二つのシーケンスの連結e1 @ e2は、[ !e1 !e2]又は[ !e1; e2]と書くことができる。
CDuceにおいて、混成であってもよい。要素は全て異なる型を持つことができる。シーケンスに対する型及びパターンは、型又はパターンの正規表現で指定される。構文は、Rを正規表現として、[ R ]である。正規表現は、次のものになりうる。
[ _ ]は、任意のシーケンスではなく、長さ1のシーケンスを表現する)。R1 R2。連結を表現する。R?、R+、R*であり、非欲張り演算子はR??R+?R*?である。型に対しては、欲張りと非欲張りの間に意味の区別はない。x;:R(もちろんパターンに対してのみ)。意味は、Rに対してマッチするシーケンスをxで捕獲するということである。反復演算子の下を含め、正規表現の中で、同じシーケンス捕獲変数が何度か現れてもよい。この場合、対応する全ての部分シーケンスが一つに連結される。同じシーケンス捕獲変数の二つのインスタンスは、。[x :: (1 x :: Int)]のようにネストにすることはできない。[ x::Int ]及び[ (x & Int) ]の間の違いに注意すること。両方とも、単一の整数からなるシーケンスを受理するが、前者はxを(単一の整数からなる)シーケンスに束縛するのに対し、後者はシーケンスを整数自体に束縛する。(R)。例:x::(Int Int) y。/p。型/パターンpは、シーケンスの現在の末尾(現在の場所から始まる部分シーケンス)に適用される。例: [ (Int /(x:=1) | /(x:=2)) _* ]は、シーケンスが整数で始まっていればxを1に、そうでなければ2に束縛する。nを正の整数定数として、反復R ** n。n個のRの連結に対する簡略表記にすぎない[ ...; ...]記法も受理する。これは、パターンの末尾を無視する便利な方法である。例: [ x::Int* ; _ ]。これは[ x::Int* _* ]と等しい。再帰定義の中を含め、@演算子(シーケンスの連結)を型に対して使うことができる。例:
type t = [ <a>(t @ t) ? ] (* [s?] where s=<a>[ s? s? ] *)
type x = [ Int* ]
type y = x @ [ Char* ] (* [ Int* Char* ] *)
type t = ([Int] @ t) | [] (* [ Int* ] *)
しかしながら、再帰定義の中で使われた場合、@は右線形でなければならない。例えば次の定義は許されていない。
type t = (t @ [Int]) | [] (* ERROR: Ill-formed concatenation loop *) type t = t @ t (* ERROR: Ill-formed concatenation loop *)
CDuceでは、文字列は、文字のシーケンスに過ぎない。型Stringは、[ Char * ]と事前定義されている。これにより、文字列に強力な正規表現パターンマッチを用いることが可能になっている。
正規表現型やパターンの中で、Char*の代わりにPCDATAを使うことができる(両方ともそれ自体は型ではないことに注意。Stringと逆で、大括弧の中でしか意味を成さない)。
型Latin1は[ Byte* ]として定義されるStringの部分型である。ISO-8859-1エンコーディングで表現できる文字列、すなわちLatin1文字集合の文字だけからなる文字列を意味する。
['a' 'b' 'c']の代わりに['a' 'b' 'c']というように、シーケンス中のいくつかの連続した文字リテラルは、二つのシングルクォートの中にまとめることができる。また、"abc"のように、ダブルクォートを用いて大括弧を避けることもできる。シングルクォートがエスケープされてもよく(しなくてもよく)、ダブルクォートがエスケープされなければならなくなる、という点を除き、ダブルクォートの中でも、同じエスケープ規則が適用される。
レコードは有限の(名前,値)の束縛の集合である。特にXML属性集合を表現するために使われる。名前は実際には修飾された名前(XML名前空間を参照)である。
レコード式の構文は、liをラベル名(識別子に対するのと同じ字句規約)、viを式として、{ l1=e1; ...; ln=en }である。式eiが、単純に、名前がフィールドのラベルliと一致する変数であれば、省略することができる。例: { x; y = 10; z }は{ x = x; y = 10; z = z }と等しい。フィールド間のセミコロンはオプションである。
二種類のレコード型がある。開いたレコード型は、{ l1=t1; ...; ln=tn; .. }と書き、閉じたレコード型は、{ l1 = t1; ...; ln = tn }と書く。両方とも、ラベルliが存在し、関連付けられた値が対応する型であるすべてのレコード値を意味する。差異は、開いた型は余分なフィールドを許容するのに対し、閉じた型は厳密に可能なフィールドの列挙でなければならない、ということである。フィールド間のセミコロンはオプションである。
加えて、開いた、及び閉じたレコード型の両方に対して、ラベルと型の間に=の代わりに=?を用いることにより、オプションのフィールドを指定することができる。例えば、{ x =? Int; y = Bool }は、Bool型のxフィールドと、オプショナルのフィールドy(存在すれば、型Intを持つ)があり、他にフィールドのないレコードを表現する。
構文はパターンに対しても同様である。捕獲変数がオプションのフィールドには出現できないことに注意すること。({ x = a } | (a := 1)) & { y = b }のような慣用句により、欠けているオプションのフィールドを置き換えて、デフォルトの値で束縛することができる。この慣用句がより便利にしたのが、特殊な構文{ x = a else (a:=1); y = b }である。
レコード式に対してと同様、パターンが、単純に、名前がフィールドのラベルと一致する捕捉変数であれば、省略することができる。例: { x; y = b; z }は{ x = x; y = b; z = z }と等しい。
+演算子(レコード連結、重なった場合は右側の引数で与えられるのが優先される)が、レコード型及びパターンで利用できる。この演算子を使って、閉じたレコード型/パターンを開いた型/パターンにしたり、フィールドを付加したりすることができる。
type t = { a=Int b=Char }
type s = t + {..} (* { a=Int b=Char .. }
type u = s + { c=Float } (* { a=Int b=Char c=Float .. } *)
type v = t + { c=Float } (* { a=Int b=Char c=Float } *)
CDuceにおいて、XML要素の一般形は、tag、attr、及びcontentの三つを表現として、 <(tag) (attr)>contentである。
通常、タグはタグリテラル`xxxであり、この場合、<(`tag)と書く代わりに、<tag>と書くことができる。同様に、attrがレコードリテラルであれば、囲んでいる({ ... })、さらに属性間のセミコロンを省略することができる。例: <a href="http://..." dir="ltr">[]。
XML要素の型及びパターンの構文は、式の構文に準じており、tag、attr、及びcontentの三つを型又はパターンとして、<(tag) (attr)contentである。式と同様に、タグや属性に対する記法を簡略化できる。例えば、<(`a) ({ href=String })>[]は、<a href=String>[]を書くことができる。
XMLの型を書き方をいくつか次の例で示す。
type A = <a x=String y=String ..>[ A* ]
type B = <(`x | `y) ..>[ ]
type C = <c x = String; y = String>[ ]
type U = { x = String y =? String ..}
type V = [ W* ]
type W = <v (U)>V
CDuceは高階関数型言語である。関数は、値の一級市民権を持っており、引数として渡されたり、結果として返されたり、データ構造の中に保存したりすることができる。
関数型は、t及びsを型として、形式t -> s型を持つ。直観的には、この型は、(少なくとも)型tの引数であれば何でも受け取り、そのような値に対しては、型sの値を返す関数に対応する。例えば、型((Int, Int) -> Int) & ((Char,Char) -> Char)は整数のペアであれば何でも整数にマップし、文字のペアであれば何でも文字にマップする関数を意味する。
上の説明で、関数の型解釈の背後にある直観が与えられた。部分型関係及び同値関係と関数の型の(ブール結合)の間にあることを理解する。例えば、(Int -> Int) & (Char -> Char)の型は、この型の関数が、上の直観により、型Int|Charの値を与えられると、(引数に応じて)Int又はCharの値を返ことより、(Int|Char) -> (Int|Char)の部分型である。
正式には、(t1 -> s1) & ... & (tn -> sn)がt -> sの部分型であれば、型t -> sは、CDuceの抽象fun (t1 -> s1; ...; tn -> sn)...を意味する。
関数の型に対応するパターンはない。
参照は、可変のメモリセルである。CDuceはビルトインの参照型を持ってはいない。代わりに、オブジェクト指向的に参照を実装している。型ref Tは型Tの値の参照を意味する。これは型{ get [] -> T; set = T -> []}の糖衣構文に過ぎない。
記法!tは、CDuce/OCamlインタフェースで使われ、OCamlの抽象型tを表現する。
以下に型及びパターンの完全な構文を与える。型は、捕獲変数のないパターンである。
TO BE DONE