型とパターン

型とパターン

CDuceでは、型は値の集合を意味し、パターンは値から部分値を抽出する。構文的には、型とパターンは非常に似ている。実際、型はどんな型でもパターンとして出現でき(どんな値でも受け付け、何も抽出しないパターンとなる)、又、捕獲変数のないパターンは、型にすぎない。

さらには、値も型やパターンと共通の構文を共有している。これは、基本の値、及び構築された値(つまり、中に関数値のない値)は、それ自体単一型である。たとえば、(1,2)は値、型及びパターンのすべてになる。型としては、単一型、あるいは二つの単一型からなるペア型として解釈されうる。パターンとしては、型制約として、あるいは二つの型制約のペアパターンとして解釈されうる。

このページでは、CDuceが認識する型及びパターンの全てを紹介する。CDuce値自体、対応するコンストラクション式、及びそれに対する基礎的な操作を紹介するのにいい機会ともなる。

捕獲変数とデフォルトパターン

パターン中にある値識別子は、捕獲変数として振舞う。いかなる値も受理し、束縛する。

捕獲変数には別の形式があり、xを捕獲変数(つまり識別子)、cをスカラ定数として、として、デフォルト値パターンx := cである。このパターンは、捕獲変数を定数に束縛するということを意味し、マッチした値は無視する(又、いかなる値も受理する)。

このようなパターンは、ファーストマッチポリシ(下を参照)と連動させて、"デフォルトの場合"を定義するのに便利である。例えば、パターン((x & Int) | (x := 0), (y & Int) | (y := 0))は、いかなるペアも受理し、左の成分が整数であればxに(そうでなければ0に)束縛し、ペアの右の成分も同様にyに束縛する。

ブール結合

CDuceは、ブール結合子のフルセットを認識し、その解釈は純粋に集合理論に基づく。

再帰型と再帰パターン

相互再帰型は、次のようにトップレベル型宣言で定義される。

type T1 = <a>[ T2* ]
type T2 = <b>[ T1 T1 ]

TTiを型識別子、tiを型式として、構文T where T1 = t1かつ…かつTn = tnを使うこともできる。再帰パターンも同じ記法で動作する(パターンに対しては、トップレベル宣言はない)。

再帰型に関して、重要な制約がある。循環は、型コンストラクタ(ペア、レコード、XML要素、矢印)を横断しなければならない。ブール結合子は型コンストラクタとして考えない。上のコード例は、正しい定義である。下のコード例は、TとSの間に無防備な循環があるため、不正である。

type T = S | (S,S)  (* INVALID! *)
type S = T          (* INVALID! *)

スカラー型

CDuceは三種類のアトミックな(スカラーの)値を持つ。整数、文字とアトムである。各種類の値に対して、一種類の型が対応している。

整数
CDuceの整数は、任意の大きさを持つ。整数リテラルは十進の数字列であり、オプションで単項マイナス(-)文字から始まる。
浮動小数点数
CDuceは浮動小数点数の最小機能を提供する。Float型の値を作る方法は、float_of : String -> Float関数を用いる方法しかない。
文字
CDuceはUnicode文字を扱う。文字リテラルは、シングルクォートで囲む。例、'a''b''c'。シングルクォート及びバックスラッシュ文字は、バックスラッシュでエスケープしなければならない。'\'''\\'。ダブルクォートもエスケープできるが、必須ではない。例の'\n''\t''\r'が認識される。任意のUnicodeコードポイントを十進で'\i;'(i)は十進整数である。コードがセミコロンで終わることに注意)、十六進で'\xi;'と書くことができる。他のいかなるバックスラッシュ文字の出現も禁止されている。
アトム
アトムとはシンボリックな要素である。特にXMLタグ名を示すのに、又、MLの直和型コンストラクタ及び例外名を真似るのにも、使われるものである。アトムは、`xxxがCDuceの識別子規則に従うとして、xxxと書く。例: `yes`No`my-name。アトム`nillは空のシーケンスを示すのに使われる。

ペア

ペアは、CDuceの基本的な記法であり、シーケンスに対する構造の部品となっている。シーケンスを使うと、糖衣構文によりペアは隠されるが、ペアの存在を知っておくのはよいことである。

ペア式は、e1及びe2を式として、(e1,e2)と書く。

同様に、ペア型及びパターンは、t1及びt2が型又はパターンとして、(t1,t2)と書く。例: (Int,Char)

捕獲変数xがペアパターンp = (p1,p2)の両側に出現すれば、次のような意味となる。値がpとマッチすれば、xp1によりv1に、及びp2によりv2に束縛されれば、xpにより(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 ]である。正規表現は、次のものになりうる。

再帰定義の中を含め、@演算子(シーケンスの連結)を型に対して使うことができる。例:

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 } *)

XML要素

XML elements

CDuceにおいて、XML要素の一般形は、tagattr、及びcontentの三つを表現として、 <(tag) (attr)>contentである。 通常、タグはタグリテラル`xxxであり、この場合、<(`tag)と書く代わりに、<tag>と書くことができる。同様に、attrがレコードリテラルであれば、囲んでいる({ ... })、さらに属性間のセミコロンを省略することができる。例: <a href="http://..." dir="ltr">[]

XML要素の型及びパターンの構文は、式の構文に準じており、tagattr、及び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 -> []}の糖衣構文に過ぎない。

OCamlの抽象型

記法!tは、CDuce/OCamlインタフェースで使われ、OCamlの抽象型tを表現する。

完全な構文

以下に型及びパターンの完全な構文を与える。型は、捕獲変数のないパターンである。

TO BE DONE