OCamlDuceプロジェクトの目標は、Ocaml言語を拡張し、XML文書を扱うのに必要な、安全かつ能率的で複雑なアプリケーションを、より簡単に書けるようにする機能を持たせることである。特に、型やパターンの概念により、あり得る全ての入力文書が正しく処理され、妥当な出力文書しか生成されないことを、静的に保証する。
極めて簡単に言えば、OCamlDuceはOCamlを拡張し、XML文書、文書片、タグ、Unicode文字列を表現するための新しい種類の値(x値)を持たせるものである。これらの値を表現するために、型の代数を拡張して、いわゆるx型を持たせる。x型の背景となる考え方は、x値の集合を表現することである。x型は非常に厳密にでき、実際、それぞれの型は単一の型(単一の値集合)に見せることが出来、かつx型のブール結合(積、和、差)を形成することができる。
OCamlDuceの型システムは、OCamlの改良と理解してよい。x種に属すると(OCamlの型システムに基づく単一化を用いて)推論される各部分式に対して、OCamlDuceは、健全となる内で最善のx型への推論を試みる。ここでいう最善とは、自然部分型関係(集合の包含)を最小にするという意味である。推論のアルゴリズムは、実際にはデータフロー解析となる。x型は、式で生成され得る全ての値を収集し、そのプログラム中であり得る全てのデータフローを考える。時には、特に、再帰関数を定義する場合や、反復子を使う場合には、型検査器がこの型を推論するのを手助けするために、明示的な型の注釈を与える必要がある。
x型に対して、部分型は暗黙的である。式がx型であると推論され、x型がsの部分型であれば、型sの値を期待するどんな文脈でもこの式を使うことができる。
言語の新機能のほとんどは、二重中括弧{{...}}で囲まれている。たとえば、次のコード例では、XML要素の値xを定義している(タグがaで、属性hrefを持ち、内容が単一の文字列である)。
# let x = {{ <a href="http://www.cduce.org">['CDuce'] }};;
val x : {{<a href=[ 'http://www.cduce.org' ]>[ 'CDuce' ]}} =
{{<a href="http://www.cduce.org">[ 'CDuce' ]}}
中括弧の間にあるものを、x式と呼ぶ。同様に、x型があり(上述のとおり)、またxパターンがある。区切り文字{{...}}が使われているのは、単に構文的な理由のためで、OCamlとCDuceの構文及び字句規則の衝突を避けている。実際には、OCaml式は、構文上x式である(二重中括弧で囲まれる)必要なくして、x値として評価される。たとえば上のようにxが既に宣言されていれば、式xはx値として評価される。
x式の一部として任意のOCaml式を使うことができる。使うには、別の二重中括弧の対で囲まなければならないだけである。たとえば、x式ではif-then-elseの作成はできないが、次のように書くことができる。
# {{ <a href={{if true then {{"a"}} else {{"z"}}}}>[] }};;
- : {{<a href=[ 'a' | 'z' ]>[ ]}} = {{<a href="a">[ ]}}
強調された部分だけがx式としてパースされる。if-then-else部分式は、OCaml式としてパースされるが、型はx型である(すなわち{{[ 'a' | 'z' ]}}である)。
x値は、要素、タグ、テキスト、シーケンスというように、XML文書や文書片を表現するように意図されている。この節では、x値の代数、対応するx式コンストラクタの構文、関連するx型を紹介する。
x値のアトミックな種類として、三種類がある
x文字は、OCamlの文字と異なる。XML仕様書で定義されたUnicodeコードポイントの範囲を表現できるものである。文字リテラルは、シングルクォートで区切られる。エスケープシーケンス\n, \r, \t, \b, \', \", \\は、例のごとく認識される。数値エスケープシーケンスは、nを整数リテラルとして\n;と書く(セミコロンが付いていることに注意)。ソースコードはiso-8859-1でエンコードされていると解釈される。結果として、Latin1文字集合の部分でないUnicode文字を入れるには、数値エスケープの仕組みを使わなければならない。x文字に対するx型は、
c及びdをリテラルとして、c -- dと書く(例: type t = {{ 'a'--'z' }})。Charと書く。Latin1Charと書く(\0; -- \255;と定義される)。x整数は、任意の大きさを持つ。リテラルは数字で書かれなければならない。負のリテラルは小括弧で括られなければならない。例: (-3)。x整数に対するx型は、
i及びjをリテラルとしてi--jと書く(例: type t = {{ 10--20 }})。iやjを**で置き換えて、限界のない範囲を定義することができる。例えば、type = {{ 1 -- ** }}。Intと書く。Int32(又はInt64)と書く。修飾された名前は、XMLのタグ名を表現するように意図されている。概念的には、名前空間URIとローカル名から成る。URIは長くなる傾向にあることから、リテラルは、localをローカル名、prefixを(リテラルのスコープにおいて)あるURIに束縛された名前空間接頭辞として、`prefix:localの形式となっている。ローカル名は、XML名前空間の仕様書による定義に従う。ドット文字はバックスラッシュで保護されなければならず、非ラテン文字は文字リテラル\n;と書かなければならない。接頭辞をURIに束縛する方法に付いては下の説明を参照のこと。デフォルトの名前空間(又は、デフォルトが定義されていなければ、名前空間なし)を指すためには、構文は単に`localとなる。修飾された名前に対するx型は、
Atomと書く。`ns:*と書く。xレコードは、主にXML要素の属性集合を表現するのに使われる。xレコードはラベルの有限集合からx値への束縛である。ラベルは先頭のバッククォートがない修飾された名前と同じ構文に従う。しかしながら、名前空間接頭辞が与えられなければ、デフォルトの名前空間は適用されない(名前空間は空となる)。レコードx式の構文は、liをラベル、eiをx式とすると、{ l1=e1 ... ln=en }となる。フィールドはセミコロンで区切ることもできる。フィールドに対する式を省略することは正当で、ラベルがフィールドの内容として扱われる(この名前の値がカレントスコープで定義されていなければならない)。例えば、let x = ... and y = ... in {{ {x y z=3} }}は、let x = ... and y = ... in {{ {x=x, y=y, z=3} }}と同じである。xレコードに対する型は、どのラベルが可能/必須であるか、対応するフィールドの型は何であるかを指定する。二種類のレコードx型がある。
{ l1=t1 ... ln=tn };{ l1=t1 ... ln=tn .. }(最後のコロン二つは構文に入っている)双方の場合において、=を=?に変えると、そのフィールド一つがオプションになる。
従って、全xレコードのx型は、{ .. }となり、型Intフィールドlと、他の任意のフィールドが出現し得るxレコードのx型は{ l = ?Int .. }となる。
xシーケンスは、x値の順序付けされた有限集合である。シーケンスx式に対する構文は[ e1 ... en ]である(要素はOCamlのリストのようにセミコロンでは区切られないことに注意すること)。それぞれの項目eiは、次のいずれかになることができる。
eをシーケンスに評価されるx式であるとすると、!e(内容が現在定義されたシーケンス中に挿入される)。例えば、let x = [ 2 3 ] in [ 1 !x 4 ]は、let x = [ 1 2 3 4 ]と同じである。[ 'abc' ]は[ 'a' 'b' 'c' ]と同じである。シーケンスに対するx型は、Rをシーケンスに許容される内容を表現するx型の正規表現として、[R]の形式をしている。正規表現の形式には、次のものがある。
t (x型tの単一の要素)R* (0回以上の繰り返し)R+ (1回以上の繰り返し)R? (0回又は1回の繰り返し)R1 R2 (シーケンス)R1|R2 (代替)(R)/t (番人。シーケンスの末尾がtに従わなければならない)PCDATA (Char*と同じ)注意: シーケンスは実際には組み込みのペアと終端子に符号化され、シーケンス型は積型と再帰型に符号化される。符号化をプログラマを利用することはできるが、このマニュアルでは説明しない。
文字列は、文字のシーケンスにすぎない。定義済の型String及びLatin1がある([ Char* ]及び[ Latin1Char* ]と定義される)。
文字列リテラル[ '...' ]は、"..."と書くこともできる(大括弧は要らなくなる)。ただし、シングル(又はダブル)クォートは、文字列がダブル(又はシングル)クォートで区切られているときのみエスケープされる必要がある。
XML要素はx値の三つ組である。対応するx式コンストラクタの構文は、<(e1) (e2)>e3である。e1が修飾された名前のリテラルであれば、先頭のバッククォート及び周りの小括弧を省略することができる。同様に、e2がxコードのリテラルであれば、中括弧及び小括弧を省略することができる。例えば<(`a) ({href="abc"})>['def']の代わりに、単に<a href="abc">['def']と書くことができる。
XML要素のx型は、<(t1) (t2)>t3と書き、同じ単純化が適用される。例えば、名前空間接頭辞nsが定義されていれば、<ns:* ..>[]は正当なx型である。これは、タグがnsに束縛された名前空間であり、空の内容と任意の属性集合を持つXML要素を表現している。(t1)の場所にあるアンダースコアは、(Atom) (任意のタグ)と同じである。
前の節で、x値のコンストラクタ(定数リテラル、シーケンス、レコード、要素のコンストラクタ)を見て来た。この節では、他の種類のx式を説明する。
整数上の算術演算子は、通常の優先順位に従う。+、*、-、div、modと書く(すべて中置である)。
レコードの結合: e1 ++ e2。x式e1及びe2はxレコードと評価されるものでなければならない。連結によって結果が得られる。同じ名前のフィールドが双方のレコードに存在すれば、最右のものが選択される。
シーケンスの結合: e1 @ e2。[!e1 !e2]と同じ。
x式eがレコード又はXML要素として評価されれば、コンストラクションe.lは、フィールド又は属性lの値を抽出する。同様に、コンストラクションe.?lは、存在すればフィールド又は属性lの値を抽出し、存在しなければ空のシーケンス[]を返す。
x式eがレコードと評価されれば、コンストラクションe -. lは、フィールドlが(存在すれば)削除された新しいレコードを生成する。
x式eがxシーケンスと評価されれば、コンストラクションe/の結果は、シーケンスeからXML要素のすべての子供を順に取って来ることによって得られる新しいxシーケンスとなる。例えばx式[<a>[ 1 2 3 ] 4 5 <b>[ 6 7 8 ] ]/は、[ 1 2 3 6 7 8 ]と評価される。
x式eがxシーケンスと評価されれば、(tをx型として)コンストラクションe.(t)の結果は、eをフィルタして、型tの要素だけを残して得られる新しいxシーケンスとなる。[<a>[ 1 2 3 ] 4 5 <b>[ 6 7 8 ] ].(Int)は、x値[ 4 5 ]と評価される。
eがx式で、tがx型であれば、コンストラクション(e :? t)は、eがt型を持っていれば、eと同じ結果を返し、持っていなければ、持っていない理由を説明する引数を持つ、Failure例外を発生させる。
eはx表
# let f (x : {{ Any }}) = {{ (x :? <a>[ Int* ] ) }} in
f {{ <a>[ 1 2 '3' ] }};;
Exception:
Failure
"Value <a>[ 1 2 '3' ] does not match type <a>[ Int* ]\nValue '3' does not match type Int\n".
OCamlDuceには強力なパターンマッチ命令がある。xパターンについては下で説明されている。パターンマッチ命令に対する構文は、match e with p1 -> e1 | ... | pn -> enである。型システムは、パターンマッチに対する網羅性を保証する。通常のOCaml式としてxパターンマッチを使うこともできる。xパターンは{{..}}で囲まれる。例: match e with {{p1}} -> e1 | ... | {{pn}} -> en function {{p1}} -> e1 | ... | {{pn}} -> en
パターンマッチはファーストマッチポリシに従う。成功した最初のパターンが対応する分岐を引き起こす。
注意: 現在のところ、一つのパターンマッチの中で普通のOCamlのパターンとxパターンを混合させることは出来ない。
x式let p=e1 in e2は、match e1 with p -> e2と等しい。Ocaml式のxパターンを使ったローカル束縛もある。let p=e1 in e2
OCamlDuceには、シーケンスイテレータmap e with p1 -> e1 | ... | pn -> en及びツリーイテレータmap* e with p1 -> e1 | ... | pn -> enがある。
双方のコンストラクションに対して、引数はシーケンスと評価されなければならない。mapイテレータは、このシーケンスの各要素に順に適用され、全ての結果を集めて新しいシーケンスを生成する。パターンの集合は、入力シーケンスの全ての可能な要素に対して網羅的でなければならない。
ツリーイテレータは、パターンが網羅的である必要はないことを除けば類似している。もし入力シーケンスの要素がマッチしなければ、XML要素でなければ、単に結果に複製されるだけである。XML要素であれば、変換は内容に再帰的に適用される。
便宜のために、OCaml式のコンストラクタをいくつかx式として使うことができる(OCamlに二重中括弧を用いて戻る必要はない)。使えるのは、(制限のない)値識別子と関数呼出である。
単純なx型の書き方について見て来たところで、これらをブール結合子で組み合わせることができる。
t1 & t2: 積t1 | t2: 和t1 - t2: 差空のx型はEmptyと書く(値を全く含まない)。汎用のx型はAnyと書く(全てのx値を含む)。
x型がOCaml識別子に束縛される(type t = {{...}})と、別のx型の中でこの識別子を使うことができる。再帰定義が認められている。
type t1 = {{ <a>[ t2* ] }}
and t2 = {{ <b>[ t1* ] }}
x値は常に有限かつ非循環である。型検査は、空の型に陥ってしまう型定義を検知する。
# type t = {{ <a>[ t+ ] }};;
This definition yields an empty type
t1及びt2がレコードx型であれば、中置++演算子で結合することができる。中置++演算子は、対応している式上の演算子(レコード連結)と類似している。同様に、シーケンスx型上の中置@連結を使用できる。
xパターンはx型と同じ構文に従う。特に、どんなx型も妥当なxパターンとなる。x型のコンストラクタに加えて、xパターンには次のものがある。
ここで、パターンの意味について簡単に説明する。入力値を与えられると、パターンは成功するか失敗するかのいずれかになりうる。成功すれば、さらにパターン中の捕獲変数からx値への束縛を生成する。
p1 | p2は、p1又はp2のどちらかが成功すれば成功し、対応する束縛を返す。もし双方のパターンが成功すれば、p1が勝つ。p1とp2が同じ捕獲変数の集合を持つ必要がある。p1 & p2は、p1とp2の両方が成功すれば成功し、二つの束縛の連結を返す。p1及びp2は排他的な捕獲変数の集合であることが要求される。レコードxパターンにおいて、フィールドの=p部分を省略することができる。内容は、捕獲変数と(又は前に定義された型と)考えられて、ラベル名で置き換えられる。
"else"節を加えることもできる。{ x = (a,_)|(a:=3) }は、フィールドxだけがあるレコードを受け入れる。内容がペアであれば、捕獲変数はその構成要素に束縛される。そうでなければ、3に設定される。
正規表現において、記法x::Rにより部分シーケンスを抽出することができる。例: [ _* x::Int+ _* ]
同じシーケンスの捕獲変数は、正規表現において複数回現れれば(あるいは繰り返しの下にあれば)、全てのマッチした部分シーケンスの連結に束縛される。例えば、[ (x::Int | _)* ]は、シーケンスから型Intの全要素をxに集める。一つの捕獲変数の繰り返しを持つのは妥当ではない。
正規表現の演算子+、*、?はデフォルトで欲張りである(できるだけ長くマッチする)。非欲張りな変種+?、*?、??も使うことができる。
名前空間接頭辞のURIへの束縛は、トップレベル宣言(ストラクチャの項目)又はローカル宣言のいずれかで行うことができる。
# {{ namespace ns = "http://..." }};;
# let x = {{ `ns: x }};;
val x : {{`ns:x}} = {{`ns:x}}
# let x = {{ let namespace ns = "http://..." in `ns:x }};;
val x : {{`ns:x}} = {{`ns:x}}
トップレベル宣言は、モジュールのインタフェース(シグネチャ)の中でも出現できる。トップレベルの接頭辞束縛は、モジュールにエクスポートされることはなく、スコープはカレントストラクチャ又はシグネチャに制限される。デフォルトの名前空間の指定したり初期化することができる。
# {{ namespace "http://..." }};;
# {{ `x }};;
- : {{`ns1:x}} = {{`ns1:x}}
# {{ namespace "" }};;
# {{ `x }};;
- : {{`x}} = {{`x}}
値の清書器が、名前空間URIに対して接頭辞を作り出していることに注意すること。デフォルトの接頭辞宣言には、ローカル形式let namespace "..." in ...もある。
上で述べたように、プログラマが型の注釈を付ける必要がある場合がある。その注釈を付けるべき場所を知るために、型検査がどのように動作するのかの基礎を理解する必要がある。
OCamlの型検査器は、最初の走査で、部分式がx種であることを検知する。次に、二回目のML型検査パスが行われ、許容される包含(暗黙の部分型)ステップを導入する。ツーパス後、OCamlDuceの型検査器が、コンパイルユニット全体に渡ってx値のデータフローサマリーを取得する。これは有向グラフであり、辺がx値に対する単純なデータフローや複雑な操作を表現している。グラフの頂点はx型の変数と考えることができる。データフローの辺は部分型の制約と対応する。操作の辺は、シンボリックな制約に対応し、対応する値に対する操作を模倣する。
頂点のいくつかは、(式又は関数の引数上の)型注釈や、MLにおける他の仕組み(データ型宣言、シグネチャ、…)を通して、プログラマにより明示的に与えられる。
また、グラフの型付けの辺だけでループがあれば、ループ上にある全ての辺が一つにマージされる。
この操作の後、グラフは非循環であることが要求される(明示的な型を持った頂点が、グラフから取り除かれると仮定する)。プログラマはこの性質を実現するための十分な型注釈を与える責任である。さもなければ、型エラーが出る。
# let rec f x = match x with 0 -> {{ [] }} | n -> {{ f {{n-1}} @ ['.'] }};;
Cycle detected: cannot type-check
# let rec f x : {{ String }} = match x with 0 -> {{ [] }} | n -> {{ f {{n-1}} @ ['.'] }};;
val f : int -> {{String}} = <fun>
上の例で、fに対する結果の型と部分式f {{n-1}}に対する型の間に循環がある。ここでは結果に対する型記法により循環を壊している。式f {{n-1}}、関数f自体、あるいはモジュールのシグネチャに対する型注釈によって壊すこともできる。
別の例を調べてみよう。
# let f x = {{ x + 1 }} in f {{ 2 }}, f {{ 3 }};;
- : {{3--4}} * {{3--4}} = ({{3}}, {{4}})
型検査器は二つのx値2および3がfの引数にフローしうることを検知する。よって、その本体はxが型2--3を持つという仮定で型検査される。従って計算結果は3--4となる。
上で説明された型推論プロセスは、本来グローバルである。非循環であるという条件が課されるのは、コンパイルユニット全体がOCamlにより型検査された後だけである(そして、モジュールインタフェースからの情報が統合される)。型変数がx種に属すると推論されれば、一般化されることはない。結果として、x型にはパラメタ多相はない。
トップレベルにおいて、型検査は、各フレーズの後で行われる。次のセッションを考えてみる。
# let f x = {{ x + 1 }};;
val f : {{Empty}} -> {{Empty}} = <fun>
# let a = f {{ 2 }};;
Subtyping failed 2 <= Empty
Sample:
2
関数fは、型{{Empty}} -> {{Empty}}を持つと推論される。最初のフレーズが型検査されるときに、データフローグラフは何の値もxにフローしないことを示しているので、入力の型は空となるためである(又、結果の型に対しても同様である)。二つのフレーズが同時に型検査されていれば(コンパイラによってコンパイルされた場合はそうなるだろう)、型検査器は、fに対する入力の型が2を含んでいなければならないと、正しく推論していただろう。
x型から上位の型への強制は、OCamlDuceでは自動的に行われる。しかしながら、この自動的な包含は、たとえ共変であっても、OCamlの型コンストラクタを越えることは出来ない。次のコードを考えてみる。
# let f (x : {{ Int }} * {{ Int }}) = 1;;
val f : {{Int}} * {{Int}} -> int = <fun>
# let g (x : {{ 0 }} * {{ 0 }}) = f x;;
This expression has type {{0}} * {{0}} but is here used with type
{{Int}} * {{Int}}
# let g (x : {{ 0 }} * {{ 0 }}) = let a,b = x in f (a,b);;
val g : {{0}} * {{0}} -> int = <fun>
# let g (x : {{ 0 }} * {{ 0 }}) = f (x :> {{ Int }} * {{ Int }});;
val g : {{0}} * {{0}} -> int = <fun>
gを定義しようとする最初の試行は、xに対する型が、x型でなく、ゆえに部分型が適用されないため、失敗する。二回目の試行では、ペアの二つの構成要素を抽出している。x値に推論しているので、部分型はその双方に適用される。従って、ペア(a.b)が再構築されれば、その型とfの入力の型を単一化するのは正当である。gに対する三回目の試行で、代わりの解決法が与えられる。明示的なOCamlの型強制の使用である。
OCamlDuceは新しいx値とOCamlの値を強く分離している。構文、式、型、パターン、さらには型検査アルゴリズムまでもが異なっている。この強い分離が、全く異なる型システムの間を単純に統合することができるキーポイントになっている。
同じ点で、国境を横断し、OCamlの値をx値に変換したり、又その逆をしたりすることとはやはり必要である。
幸いなことに、OCamlDuceは双方向のアトミックな変換を提供している。二重中括弧の代わりに、x式を中括弧とコロンで括る{: ... :}(ここで...はx式である)ことができる。その効果は、x式の結果(x値でなければならない)を変換することである。同様に、x式において、同じ構文{: ... :}でOCamlの値のx変換を得ることができる(ここで...はOCamlの式である)。
ここで、変換の働き方を述べる。それぞれのOCamlの型tに、x型T(t)、及びtとT(t)の間の変換関数のペアを関連付ける。実際には、全ての機能がサポートされているわけではない。例えば、自由型変数、抽象型、オブジェクト型、非正規再帰型は変換できない。特に、型変数が許可されていないので、OCamlの型は完全に分かっていなければならない。
OCamlの型tの変換は、tに関する構文上の帰納で定義される。型の中には、和の型に変換されるものもある。定数コンストラクタAは修飾された名前`Aに変換される。t1 * ... * tnである非定数コンストラクタAは、<A>[ T(t1) ... T(tn) ]に変換される。閉じた多相変数は、同じ変換である。レコード型は、閉じたレコードx型に変換される。他の変換は、次の通りである。
Caml type t | X-type T(t) |
|---|---|
int | Int |
int32 | Int32 |
int64 | Int64 |
string | Latin1 |
t list | [T(t)*] |
t array | [T(t)*] |
unit | [] |
char | Latin1Char |
{{t}} | t |
例はこちら。
# let f (x : {{ Int }}) = {{ x + 1 }} in List.map f {: [ 1 2 3 ] :};;
- : {{Int}} list = [{{2}}; {{3}}; {{4}}]
この例では、結果の結果の型は、{{ Int }} listに推論される(fに対する型が与えられるからである)。対応するx型は{{ [Int*] }}である。
OCamlDuceでは、OCamlのNumライブラリが標準ライブラリに含まれている。加えて、Ocamlduce及びCduce_typeと呼ばれる新しいモジュール二つが標準ライブラリにある。
C_duce_typesモジュールはx値の内部表現へのアクセスを提供するものである。現在文書化されていない。
モジュールOcamlduceは、便利なx値の機能を提供する。インタフェースの説明については、ocamldocで生成された文書を参照のこと。
OCamlDuceはx値の内部表現にある技を用いて、メモリ使用量を削減し、パフォーマンスを向上させている。OCamlの直列化関数(Marshalモジュール、input_value/output_value関数)を使いたければ、特別な注意を払う必要がある。自分の値に加えて、Cduce_types.Value.extract_allおよびCduce_types.Value.intract_all関数を用いて、内部データの一部を保存または復元する必要もあるわけである。もちろん、これは直列化されるデータが深くネストされたx値を含んでいるときも同様である。
ここにあるのは、汎用の直列化/非直列化関数で、それをどのように行えばいいのかを説明している。
let my_output_value oc v = let p = Cduce_types.Value.extract_all () in output_value oc (p,v) let my_input_value ic = let (p,v) = input_value ic in Cduce_types.Value.intract_all p; v
OCaml利用者は、OCamlDuceにおいてx文字列が単にシーケンスとして表現されていること実に驚くかもしれない。これは実際に連結リストとしてメモリに格納されていることを意味するのだろうか。そうではない。シーケンス値の内部表現はパフォーマンスやメモリ使用量を改善するためにいくつか技を用いている。特に、表現の特殊な形式により、文字列をバイトバッファとして格納することができる。XML文書がロードされたり、又Caml文字列がx値に変換されたりすると、このコンパクトな表現が使われる。
同様に、OCmal利用者は、シーケンス群に対するシーケンス結合@の使用に気が進まないかも知れない。OCamlにおいては、この演算子の計算量は、最初の引数(コピーする必要がある)のサイズに線形である。OCamlDuceは、内部表現に特殊な形式を用い、結合の格納を遅延させている。結合は、値がアクセスされたときにはじめて実際に計算される。これは、一つずつ新しい要素を加えて長いシーケンスを組み立てることも、同時に調べたりしない限りは、全く大丈夫であることを意味している。
OCamlDuceでプログラミングをするときに知っておく価値のある別の点は、パフォーマンスに影響させずに、パターンを宣言形式を書くことができるということである。コンパイラはマッチした値に関する静的型情報を使って、パターンマッチに対して能率的なコードを生成する。これを説明するために下の例を考えてみる。
x.ml:
type a = {{ <a>[ a* ] }}
type b = {{ <b>[ b* ] }}
let f : {{ a|b }} -> int = function {{ a }} -> 0 | {{ _ }} -> 1
y.ml:
type a = {{ <a>[ a* ] }}
type b = {{ <b>[ b* ] }}
let f : {{ a|b }} -> int = function {{ <a>_ }} -> 0 | {{ _ }} -> 1
二つの関数は、完全に同じ意味を持っているが、最初の実装がより宣言的である。aとbを区別するのに型検査を用いており、二つの型を区別する方法を示してはいない。これらの型宣言が次のように変化した場合を考えてみると、
type a = {{ <x kind="a">[ a* ] }}
type b = {{ <x kind="b">[ b* ] }}
最初の実装はやはり期待した通りに動作するが、二番目の実装は、書き直す必要がある。
さて、一番目の実装ではコンパイラがツリーの全てのタグを検査するコードを生成しなければならないが、二番目の実装では、コンパイラがルートタグのみを検査するので、より効率的であると考えるかも知れない。しかし、こんなことは起こらない。実際には、コンパイラは両方の実装に対して全く同じコードを生成する。パターンマッチの引数に関する静的型情報(ここでは、関数の入力の型)を考えて、型の値に対するパターンを評価する効率的な方法を計算するのである。
map ... with ...イテレータは、末尾再帰で実装される。非常に長いシーケンスに対して安全に使用することができる。
3.08.4リリース以降、OCamlDuceは対応するOCamlリリースとバイナリ互換となっている。これは、OCamlDuceがOcamlの生成した.cmiファイルを使用でき、又インタフェースにx型が用いられていなければ、OCaml互換の.cmiファイルを生成できる(このファイルはOCamlを用いて得られるものと同じである)ことを意味する。
ゆえに、OCaml向けにコンパイルされた既存のライブラリを使うことができる。インタフェースが純粋なOcamlであれば、モジュールをコンパイルするのにOCamlDuceを用い、OCamlプロジェクトの中で使うこともできる。