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