<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>CDuce: Patterns</title><meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"/><link href="cduce.css" type="text/css" rel="stylesheet"/></head><body style="margin: 0; padding : 0;"><table width="100%" border="0" cellspacing="10" cellpadding="0"><tr><td valign="top" style="width:20%;" align="left"><div class="leftbar" id="leftbar"><div class="smallbox"><ul><li><a href="#key">Key concepts</a></li><li><a href="#record">Pair and Record Patterns</a></li><li><a href="#seq">Sequence patterns</a></li><li><a href="#xml">XML elements and attributes</a></li><li><a href="#optatrr">Handling optional attributes</a></li><li><a href="#recpat">Recursive patterns</a></li><li><a href="#pre">Compiling regular expression patterns</a></li></ul><p>
You can cut and paste the code on this page and
test it on the <a href="http://reglisse.ens.fr/cgi-bin/cduce">online interpreter</a>.
</p></div></div></td><td><h1>Patterns</h1><div class="mainpanel"><div class="smallbox"><p><a href="index.html">CDuce: documentation</a>: <a href="tutorial.html">Tutorial</a>: Patterns</p><p><a href="tutorial_overloading.html"><img class="icon" width="16" alt="Previous page:" src="img/left.gif" height="16"/> Overloading</a> <a href="tutorial_errors.html"><img class="icon" width="16" alt="Next page:" src="img/right.gif" height="16"/> Error messages and Warnings</a></p></div><div><h2><a name="key">Key concepts</a></h2><b style="color:#FF0080">TO BE DONE</b></div><div><h2><a name="record">Pair and Record Patterns</a></h2><b style="color:#FF0080">TO BE DONE</b></div><div><h2><a name="seq">Sequence patterns</a></h2><b style="color:#FF0080">TO BE DONE</b></div><div><h2><a name="xml">XML elements and attributes</a></h2><p>
Up to now we used for XML elements (and their types) an abbreviated notation
as for <b><tt><table align="center" valign="top">[</tt></b><i>some_content</i><b><tt>]</tt></b>. Actually, the precise syntax of XML elements is
</p><div class="code"><pre>
<(<i>expr1</i>) (<i>expr2</i>)><i>expr3</i>
</pre></div><p>
where <b><tt><i>expr1</i></tt></b>, <b><tt><i>expr2</i></tt></b>, and<b><tt><i>expr3</i></tt></b> are generic
expressions. The same holds true for record patterns, but where
the generic expressions are replaced by generic patterns (that is, <b><tt><(<i>p1</i>) (<i>p2</i>)><i>p3</i></tt></b>). It is important
to notice that the parentheses (in red) <b><tt><<strong class="highlight">(</strong><i>expr1</i><strong class="highlight">)</strong>
<strong class="highlight">(</strong><i>expr2</i><strong class="highlight">)</strong>><i>expr3</i></tt></b> are part of the syntax.<br/>
Even if <b><tt><i>expr1</i></tt></b>, <b><tt><i>expr2</i></tt></b>, and
<b><tt><i>expr3</i></tt></b> may be any expression, in practice they mostly occur in a very
precise form. In particular, <b><tt><i>expr1</i></tt></b> is an <a href="manual_types_patterns.html#basictag">atom</a>, <b><tt><i>expr2</i></tt></b> is a
<a href="manual_types_patterns.html#record">record value</a>, while
<b><tt><i>expr3</i></tt></b> is a sequence. Since this corresponds, by far, to the most
common use of XML elements we have introduced some handy abbreviations: in
particular we allow the programmer to omit the surrounding <b><tt><strong class="highlight">(` )</strong></tt></b>
when <b><tt><i>expr1</i></tt></b> is an atom, and to omit the surrounding <b><tt><strong class="highlight">{ }
</strong></tt></b> and the infix semicolons <b><tt><strong class="highlight">;</strong></tt></b> when
<b><tt><i>expr2</i></tt></b> is a record value. This is why we can write
<b><tt><table align="center" valign="top">[ </tt></b>...<b><tt> ]</tt></b>, rather than
<b><tt><<strong class="ocaml">(`</strong>table<strong class="ocaml">)</strong> <strong class="ocaml">({</strong>align="center"<strong class="ocaml">;</strong> valign="top"<strong class="ocaml">})</strong>
>[ </tt></b>...<b><tt> ]</tt></b></p><p> While these abbreviations are quite handy, they demand some care when used in record patterns. As we said, the general form of a record pattern is:
</p><div class="code"><pre>
<(<i>p1</i>) (<i>p2</i>)><i>p3</i>
</pre></div><p>
and the same abbreviations as for expressions apply. In particular, this means
that, say, the pattern <b><tt><t (a)>_</tt></b> stands for <b><tt><(`t)
(a)>_</tt></b>. Therefore while <b><tt><t (a)>_</tt></b> matches all the elements
of tag <b><tt>t</tt></b> (and captures in the variable <b><tt>a</tt></b> the
attributes), the pattern <b><tt><(t) (a)>_</tt></b> matches all XML elements
(whatever their tag is) and captures their tag in the variable <b><tt>t</tt></b>
(and their attributes in <b><tt>a</tt></b>). Another point to notice is that
<b><tt><t>_</tt></b> stands for <b><tt><t ({})>_</tt></b> (more precisely, for
<b><tt><(`t) ({})>_</tt></b>). Since <b><tt>{}</tt></b> is the <i>closed</i> empty
record type, then it matches only the empty record. Therefore <b><tt><t>_</tt></b>
matches all elements of tag <b><tt>t</tt></b> that have no attibute. We have seen at the beginning of this tutorial that in order to match all element of tag <b><tt>t</tt></b> independently from whether they have attributes or not, we have to use the pattern <b><tt><t ..>_</tt></b> (which stands for <b><tt><(`t) ({..})>_</tt></b>).
</p><p>
In the following we enumerate some simple examples to show
what we just explained. In these examples we use the following definitions for bibliographic data:
</p><div class="code"><pre>
type Biblio = [(Paper|Book)*]
type Paper = <paper isbn=?String year=String>[ Author+ Title Conference Url? ]
type Book = <book isbn=String> [ Author+ Title Url? ]
type Author = <author>[ PCDATA ]
type Title = <title>[ PCDATA ]
type Conference = <conference>[ PCDATA ]
type Url = <url>[ PCDATA ]
</pre></div><p>
Let <b><tt>bib</tt></b> be of type <b><tt>Biblio</tt></b> then
</p><div class="code"><pre>
transform bib with
<book (a)> [ (x::(Any\Url)|_)* ] -> [ <book (a)> x ]
</pre></div><p>
returns the list of all books without their Url element (if any).
</p><div class="code"><pre>
transform bib with
<(book) (a)> [ (x::(Any\Url)|_)* ] -> [ <(book) (a)> x ]
</pre></div><p>
returns the bibliography in which all entries (either books or papers) no longer
have their Url elements (<b><tt>book</tt></b> is now a capture variable). Equivalently we could have
pushed the difference on tags:
</p><div class="code"><pre>
transform bib with
<(book) (a)> [ (x::<(Any\`url)>_|_)* ] -> [ <(book) (a)> x ]
</pre></div><p>
We can perform many kinds of manipulations on the attributes by
using the <a href="manual_expressions.html#record">operators for records</a>,
namely <b><tt><i>r</i>\<i>l</i></tt></b> which deletes the field <b><tt><i>l</i></tt></b>
in the record <b><tt><i>r</i></tt></b> whenever it is present, and <b><tt><i>r1</i> +
<i>r2</i></tt></b> which merges the records <b><tt><i>r1</i></tt></b> and
<b><tt><i>r2</i></tt></b> by giving the priority to the fields in the latter. For
instance
</p><div class="code"><pre>
transform bib with
<(t) (a)> x -> [ <(x) (a\isbn)> x ]
</pre></div><p>
strips all the ISBN attributes.
</p><div class="code"><pre>
transform bib with
<_ (a)> [(x::(Author|Title|Url)|_)*] -> [ <book ({isbn="fake"}+a\year)> x ]
</pre></div><p>
returns the bibliography in which all Paper elements are transformed into
books; this is done by forgetting the Conference elements, by removing the year attributes and
possibly adding a fake isbn attribute. Note that since record concatenation gives priority to the record on the righ handside, then whenever the record captured by
<b><tt>a</tt></b> already contains an isbn attribute, this is preserved.
</p><p>
As an example to summarize what we said above, consider the the elements
<b><tt>table</tt></b>, <b><tt>td</tt></b> and <b><tt>tr</tt></b> in XHTML. In
transitional XHTML these elements can have an attribute <b><tt>bgcolor</tt></b>
which is deprecated since in strict XHTML the background color must be specified
by the <b><tt>style</tt></b> attribute. So for instance <b><tt><table
bgcolor="#ffff00" style="font-family:Arial"></tt></b>...
must be rewritten as <b><tt><table style="bgcolor:#ffff00;
font-family:Arial"></tt></b>... to be XHTML strict compliant. Here is a function
that does this transformation on a very simplified version of possibly nested
tables containing strings.
</p><div class="code"><pre>
type Table = <table { bgcolor=?String; style=?String }>[ Tr+]
type Tr = <tr { bgcolor=?String; style=?String }>[ Td+]
type Td = <td { bgcolor=?String; style=?String }>[ Table* | PCDATA ]
let strict ([Table*]->[Table*]; [Tr+]->[Tr+]; [Td+]->[Td+]; [PCDATA]->[PCDATA])
x ->
map x with
<(t) (a& { bgcolor=c; style=s })> l
-> <(t) (a\bgcolor+{style=(s@"; bgcolor:"@c)})>(strict l)
| <(t) (a& { bgcolor=c })> l
-> <(t) (a\bgcolor+{style=("bgcolor:"@c)})>(strict l)
| <(t) (a)> l -> <(t) (a)>(strict l)
| c -> c
</pre></div><p>
As an exercise the reader can try to rewrite the function <b><tt>strict</tt></b> so that the first three branches of the map are condensed into a unique branch.
</p></div><div><h2><a name="optatrr">Handling optional attributes</a></h2><p>
The blend of type constructors and boolean combinators can be used to
reduce verbosity in writing pattern matching. As an example we show how to handle
tags with several optional attributes.
</p><p>
Consider the following fragment of code from site.cd from the CDuce
distribution that we have changed a bit so that it stands alone:
</p><div class="code"><pre>
type Sample = <sample highlight=?"true"|"false">String
let content (Sample -> String)
| <sample highlight="false">_ -> "non-higlighted code"
| <sample ..>_ -> "highlighted code"
</pre></div><p>
The idea here is to use the highlight attribute to specify that
certain pieces of <b><tt><sample></tt></b> should be emphasized. When the higlight
attribute is missing, the default value of "true" is presumed.
</p><p>
But what if we have two optional attributes? The naive solution would be
to write the
<i>four</i> possible cases:
</p><div class="code"><pre>
type Sample = <sample lineno=?"true"|"false" highlight=?"true"|"false">String
let content (Sample -> String)
| <sample highlight="false" lineno="false">_ -> "lineno=false, highlight=false"
| <sample lineno="false">_ -> "lineno=false, highlight=true"
| <sample highlight="false">_ -> "lineno=true, highlight=false"
| <sample ..>_ -> "lineno=true, highlight=true,"
</pre></div><p>
The intended use for the <b><tt>lineno</tt></b> attribute is to tell us whether line
numbers should be displayed alongside the sample code.
<br/>
While this situation is still bearable it soon become unfeasible with more
than two optional attributes. A much better way of handling this situation
is to resort to intersection and default patterns as follows:
</p><div class="code"><pre>
let content (Sample -> String)
| <sample ( ({ highlight = h ..} | (h <strong class="highlight">:=</strong> "true"))
<strong class="highlight">&</strong>({ lineno = l ..} | (l <strong class="highlight">:=</strong> "true")) )>_
-> ['lineno=' !l ', highlight=' !h]
</pre></div><p>
The intersection pattern <b><tt>&</tt></b> makes both patterns to be matched
against the record of attributes: each pattern checks the presence of a specific
attribute (the other is ignored by matching it with <b><tt>..</tt></b>), if it is present it captures the attribute value in a given variables
while if the attribute is absent the default sub-pattern is used to assign the
variable a default value.
</p><p>
The use of patterns of the form <b><tt>
({ label1= x } | (x := <i>v</i>)) & { label2 = y }</tt></b> is so common in handling
optional fields (hence, XML attributes) that CDuce has a special syntax for this
kind of patterns: <b><tt>
{ label1 = x else (x := <i>v</i>) ; label2 = y }</tt></b></p></div><div><h2><a name="recpat">Recursive patterns</a></h2><p>
Recursive patterns use the same syntax as recursive types:
<b><tt><i>P</i> where <i>P1</i>=<i>p1</i> and ... and <i>Pn</i>=<i>pn</i></tt></b> with <i>P, P1,..., Pn</i>
being variables ranging over pattern identifiers (i.e.,
identifiers starting by a capital letter). Recursive
patterns allow one to express complex extraction of information from
the matched value. For instance, consider the pattern
<b><tt>P where P = (x & Int, _) | (_, P)</tt></b>; it extracts from a sequence the first
element of type <b><tt>Int</tt></b> (recall that sequences are
encoded with pairs). The order
is important, because
the pattern <b><tt>P where P = (_, P) | (x & Int, _)</tt></b>
extracts the <i>last</i> element of type <b><tt>Int</tt></b>.
</p><p>
A pattern may also extract and reconstruct a subsequence,
using the convention described before that when a capture variable appears
on both sides of a pair pattern, the two values bound
to this variable are paired together.
For instance, <b><tt>P where P = (x & Int, P) | (_, P) | (x := `nil)</tt></b>
extracts all the elements of type <b><tt>Int</tt></b> from a sequence (<b><tt>x</tt></b>
is bound to the sequence containing them)
and the pattern <b><tt>P where P = (x & Int, (x & Int, _)) | (_, P)</tt></b>
extracts the first pair of consecutive integers.
</p></div><div><h2><a name="pre">Compiling regular expression patterns</a></h2><b style="color:#FF0080">CONNECT WITH SECTION ON SEQUENCE PATTERNS WHEN WRITTEN</b><p>
CDuce provides syntactic sugar for defining patterns working on
sequences with regular expressions built from patterns, usual regular
expression operators, and <i>sequence capture variables</i> of the form <b><tt>x::<i>R</i></tt></b>
(where <i>R</i> is a pattern regular expression).
</p><p>
Regular expression operators <b><tt>*</tt></b>, <b><tt>+</tt></b>, <b><tt>?</tt></b> are
<i>greedy</i> in the sense that they try to match as many times as possible.
Ungreedy versions <b><tt>*?</tt></b>, <b><tt>+?</tt></b> and <b><tt>??</tt></b>
are also provided; the difference in the compilation scheme
is just a matter of order in alternative patterns.
For instance, <b><tt>[_* (x & Int) _*]</tt></b> is compiled
to <b><tt>P where P = (_,P) | (x & Int, _)</tt></b>
while <b><tt>[_*? (x & Int) _*]</tt></b> is compiled
to <b><tt>P where P = (x & Int, _) | (_,P)</tt></b>.
</p><p>
Let us detail the compilation of an example with a sequence capture variable:
</p><div class="code"><pre>
[ _*? d::(Echar+ '.' Echar+) ]
</pre></div><p>
The first step is
to propagate the variable down to simple patterns:
</p><div class="code"><pre>
[ _*? (d::Echar)+ (d::'.') (d::Echar)+ ]
</pre></div><p>
which is then
compiled to the recursive pattern:
</p><div class="code"><pre>
P where P = (d & Echar, Q) | (_,P)
and Q = (d & Echar, Q) | (d & '.', (d & Echar, R))
and R = (d & Echar, R) | (d & `nil)
</pre></div><p>
The <b><tt>(d & `nil)</tt></b>
pattern above has a double purpose: it checks that the end
of the matched sequence has been reached, and it binds <b><tt>d</tt></b> to
<b><tt>`nil</tt></b>, to create the end of the new sequence.
</p><p>
Note the difference between <b><tt>[ x&Int ]</tt></b>
and <b><tt>[ x::Int ]</tt></b>. Both patterns accept sequences
formed of a single integer <b><tt><strong class="highlight">i</strong></tt></b>, but the first one binds <b><tt><strong class="highlight">i</strong></tt></b> to <b><tt>x</tt></b>,
whereas the second one binds to <b><tt>x</tt></b> the sequence <b><tt>[<strong class="highlight">i</strong>]</tt></b>.
</p><p>
A mix of greedy and ungreedy operators with the first match policy of alternate
patterns allows the definition of powerful extractions. For instance, one can
define a function that for a given person returns the first work phone number if
any, otherwise the last e-mail, if any, otherwise any telephone number, or the
string <b><tt>"no contact"</tt></b>:
</p><div class="code"><pre>
let preferred_contact(Person -> String)
<_>[ _ _ ( _*? <tel kind="work">x) | (_* <email>x) | <tel ..>x ] -> x
| _ -> "no contact"
</pre></div><p>
(note that <b><tt><tel ..>x</tt></b> does not need to be preceded by any wildcard pattern as it is
the only possible remaining case).
</p></div><div class="meta"><p><a href="sitemap.html">Site map</a></p></div><div class="smallbox"><p><a href="index.html">CDuce: documentation</a>: <a href="tutorial.html">Tutorial</a>: Patterns</p><p><a href="tutorial_overloading.html"><img class="icon" width="16" alt="Previous page:" src="img/left.gif" height="16"/> Overloading</a> <a href="tutorial_errors.html"><img class="icon" width="16" alt="Next page:" src="img/right.gif" height="16"/> Error messages and Warnings</a></p></div></div></td></tr></table></body></html>
