<!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: Overloading</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="#val">Overloaded functions</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>Overloading</h1><div class="mainpanel"><div class="smallbox"><p><a href="index.html">CDuce: documentation</a>: <a href="tutorial.html">Tutorial</a>: Overloading</p><p><a href="tutorial_first_functions.html"><img class="icon" width="16" alt="Previous page:" src="img/left.gif" height="16"/> First functions</a> <a href="tutorial_patterns.html"><img class="icon" width="16" alt="Next page:" src="img/right.gif" height="16"/> Patterns</a></p></div><div><h2><a name="val">Overloaded functions</a></h2><p>
The simplest form for a toplevel function declaration is
</p><div class="code"><pre>
let <i>f</i> (<i>t</i>-><i>s</i>) <i>x</i> -> <i>e</i>
</pre></div><p>
in which the body of a function is formed by a single branch
<b><tt><i>x</i> -> <i>e</i></tt></b> of pattern matching. As we have seen in the previous sections, the body of a function may be formed by several branches with complex patterns.
<br/>
The interface <b><tt><i>t</i>-><i>s</i></tt></b> specifies
a constraint on the behavior of the function to be checked by the type
system: when applied to an argument
of type <b><tt><i>t</i></tt></b>, the function returns a result of type <b><tt><i>s</i></tt></b>.
</p><h3>Simple Overloading</h3><p>
In general the interface of a function may specify several such constraints,
as the <a href="tutorial_first_functions.html#names3">names3</a> example
The general form of a toplevel function declaration is indeed:
</p><div class="code"><pre>
let <i>f</i> (<i>t1</i>-><i>s1</i>;...;<i>tn</i>-><i>sn</i>) <i>p1</i> -> <i>e1</i> | ... | <i>pm</i> -> <i>em</i>
</pre></div><p>
Such a function accepts arguments of type
(<b><tt><i>t1</i>|...|<i>tn</i></tt></b>); it has all the types <b><tt><i>ti</i>-><i>si</i></tt></b>, and,
thus, it also has their intersection <b><tt>(<i>t1</i>-><i>s1)</i>&...&(<i>tn</i>-><i>sn</i>)</tt></b></p><p>
The use of several arrow types in an interface serves to give the function a
more precise type. We can roughly distinguish two different uses of multiple
arrow types in an interface:
</p><ul><li>when each arrow type specifies the behavior of a different piece
of code forming the body of the function, the compound interface
serves to specify the <i>overloaded</i> behavior of the
function. This is the case for the
function below
<div class="code"><pre>
let add ( (Int,Int)->Int ; (String,String)->String )
| (x & Int, y & Int) -> x+y
| (x & String, y & String) -> x@y
</pre></div><p>
where each arrow type in the interface refers to a different branch of the body.
</p></li><li>when the arrow types specify different behavior for the same code,
then the compound interface serves to give a more precise
description of the behavior of the function. An example is
the function <a href="tutorial_first_functions.html#names3">names4</a> from Section "<a href="tutorial_first_functions.html">First functions</a>".
</li></ul><p>
There is no clear separation between these two situations since, in general, an
overloaded function has body branches that specify behaviors of
different arrow types of the interface but share some common portions of the
code.
</p><h3>A more complex example</h3><a name="canonical"/><p>
Let us examine a more complex example. Recall the types used to represent persons
that we defined in Section "<a href="tutorial_getting_started#type_decl">Getting started</a>" that for the purpose of the example we can simplify as follows:
</p><div class="code"><pre>
type Person = FPerson | MPerson
type FPerson = <person gender = "<strong class="highlight">F</strong>">[ Name Children ]
type MPerson = <person gender = "<strong class="highlight">M</strong>">[ Name Children ]
type Children = <children>[ Person* ]
type Name = <name>[ PCDATA ]
</pre></div><p>
We want to transform this representation of persons into a different representation that uses different tags
<b><tt><man></tt></b> and <b><tt><woman></tt></b>
instead of the gender attribute and, conversely, that uses an attribute
instead of an element for the name.
We also want to distinguish the children of a person into two different
sequences, one of sons, composed of men (i.e. elements tagged by <b><tt><man></tt></b>), and the other of daughters, composed of
women. Of course we also want to apply this transformation recursively to the
children of a person. In practice, we want to define a function <b><tt><split></tt></b> of
type <b><tt>Person ->(Man | Woman)</tt></b> where <b><tt>Man</tt></b> and <b><tt>Woman</tt></b> are the types:
</p><div class="code"><pre>
type Man = <man name=String>[ Sons Daughters ]
type Woman = <woman name=String>[ Sons Daughters ]
type Sons = <sons>[ Man* ]
type Daughters = <daughters>[ Woman* ]
</pre></div><p>
Here is a possible way to implement such a transformation:
</p><div class="code"><pre>
let fun split (<strong class="highlight">MPerson -> Man ; FPerson -> Woman</strong>)
<person gender=g>[ <name>n <children>[(mc::MPerson | fc::FPerson)*] ] ->
(* the above pattern collects all the MPerson in mc, and all the FPerson in fc *)
let tag = match g with "F" -> `woman | "M" -> `man in
let s = map mc with x -> split x in
let d = map fc with x -> split x in
<(tag) name=n>[ <sons>s <daughters>d ] ;;
</pre></div><p>
The function <b><tt>split</tt></b> is declared to be an overloaded function that, when
applied to a <b><tt>MPerson</tt></b>, returns an element of type <b><tt>Man</tt></b> and
that, when applied
to a <b><tt>FPerson</tt></b>, returns an element of type <b><tt>Woman</tt></b>. The body
is composed of a single pattern matching
</p><div class="code"><pre>
<person gender=<strong class="highlight">g</strong>>[ <name><strong class="highlight">n</strong> <children>[(<strong class="highlight">mc</strong>::MPerson | <strong class="highlight">fc</strong>::FPerson)*] ] ->
</pre></div><p>
whose pattern binds four variables: <b><tt>g</tt></b> is
bound to the gender of the argument of the function, <b><tt>n</tt></b> is bound to
its name, <b><tt>mc</tt></b> is bound to the sequence of all children that are of
type <b><tt>MPerson</tt></b>, and <b><tt>fc</tt></b> is bound to the sequence of all children
that are of type <b><tt>FPerson</tt></b>.
</p><p>
On the next line we define <b><tt>tag</tt></b> to be
<b><tt>`man</tt></b> or <b><tt>`woman</tt></b> according to the value of <b><tt>g</tt></b>.
</p><div class="code"><pre>
let tag = match g with "F" -> `woman | "M" -> `man
</pre></div><p>
Then we
apply <b><tt>split</tt></b> recursively to the elements of <b><tt>mc</tt></b> and <b><tt>fc</tt></b>.
</p><div class="code"><pre>
let <strong class="highlight">s</strong> = map <strong class="highlight">mc</strong> with x -> <strong class="highlight">split</strong> x in
let d = map fc with x -> split x in
<(tag) name=n>[ <sons><strong class="highlight">s</strong> <daughters>d ] ;;
</pre></div><p>
Here is
the use of overloading: since <b><tt>mc</tt></b> is of type <b><tt>[MPerson*]</tt></b>, then
by the overloaded type of <b><tt>split</tt></b> we can deduce that <b><tt>s</tt></b> is of type
<b><tt>[Man*]</tt></b>; similarly we deduce for <b><tt>d</tt></b> the type <b><tt>[Woman*]</tt></b>. From this
the type checker deduces that the expressions <b><tt><sons>s</tt></b> and
<b><tt><daughters></tt></b> are of type <b><tt>Sons</tt></b> and <b><tt>Daughters</tt></b>, and therefore it
returns for the <b><tt>split</tt></b> function the type <b><tt>(MPerson -> Man) & (FPerson
-> Woman)</tt></b>. Note that the use of overloading here is critical: although
<b><tt>split</tt></b> has <i>also</i> type <b><tt>Person ->(Man | Woman)</tt></b> (since <b><tt>split</tt></b> is of type
<b><tt>(MPerson->Man) & (FPerson->Woman)</tt></b>, which is a subtype), had we
declared <b><tt>split</tt></b> of that type, the function would not have type-checked: in
the recursive calls we would have been able to deduce for <b><tt>s</tt></b> and for
<b><tt>d</tt></b> the type <b><tt>[ (Man | Woman)* ]</tt></b>, which is not enough to type-check the
result.
If, for example, we wanted to define the same transformation in XDuce we would
need first to apply a filter (that is our transform) to the children so as to
separate male from females (while in CDuce we obtain it simply by a pattern) and then
resort to two auxiliary functions that have nearly the same definition and
differ only on their type, one being of type <b><tt>MPerson -> Man</tt></b>, the other of
type <b><tt>FPerson -> Woman</tt></b>. The same transformation can be elegantly defined
in XSLT with a moderate nloc increase, but only at the
expense of loosing static type safety and type-based optimizations.
</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>: Overloading</p><p><a href="tutorial_first_functions.html"><img class="icon" width="16" alt="Previous page:" src="img/left.gif" height="16"/> First functions</a> <a href="tutorial_patterns.html"><img class="icon" width="16" alt="Next page:" src="img/right.gif" height="16"/> Patterns</a></p></div></div></td></tr></table></body></html>
