[cduce-users] overloaded functions

Warren Harris wh232 at pacbell.net
Sun Jul 27 20:06:17 CEST 2003


Alain.Frisch at ens.fr wrote:

>On Sat, 26 Jul 2003, Warren Harris wrote:
>
>  
>
>>I'd like to understand the motivation for overloaded functions in CDuce.
>>It seems that the examples using overloaded functions in the white paper
>>could just as well be expressed with mutually recursive functions (with
>>different names).
>>    
>>
>
>You're probably referring to the "split" function ("sort" in the
>white paper - note that our ICFP03 paper to be presented is an updated
>version of the white paper, available at http://www.cduce.org/papers.html).
>
>type Person = FPerson | MPerson
>type FPerson = <person gender = "F">[ Name Children ]
>type MPerson = <person gender = "M">[ Name Children ]
>type Children = <children>[Person*]
>type Name = <name>[ PCDATA ]
>
>type Man = <man name=String>[ Sons Daughters ]
>type Woman = <woman name=String>[ Sons Daughters ]
>type Sons = <sons>[ Man* ]
>type Daughters = <daughters>[ Woman* ]
>
>let split (MPerson -> Man ; FPerson -> Woman)
>  <person gender=g>[ <name>n <children>[(mc::MPerson | fc::FPerson)*] ] ->
>     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 ]
>
>
>The function could actually be expressed using mutually recursive
>functions, like:
>
>let split_common([ Person* ] -> [ Sons Daughters ])
> [ (mc::MPerson | fc::FPerson)* ] ->
>     let s = map mc with x -> splitM x in
>     let d = map fc with x -> splitF x in
>     [ <sons>s  <daughters>d ]
>
>let splitM (MPerson -> Man)
>  <person>[ <name>n <children>c ] -> <man name=n>(split_common c)
>
>let splitF (FPerson -> Woman)
>  <person>[ <name>n <children>c ] -> <woman name=n>(split_common c)
>
>let split (Person -> Man|Woman) MPerson & x -> splitM x | x -> splitF x
>  
>
This is what I mean when I ask if there's something about XML that 
requires overloading at the function level. In ML, we would solve this 
problem by defining a new type to handle Man|Woman, and introduce new 
constructors to discriminate:

type ManOrWoman = M of Man | W of Woman

In ML, the split function could then avoid overloading by using this new 
type:

val split : Person -> ManOrWoman

However, when outputting the XML, you don't want the superfluous M and W 
nodes to appear. The XML document, after the split transformation would 
want to produce either a Man or Woman tag directly, not one wrapped in 
constructors (tags) of the ManOrWoman type.

>
>To avoid duplicating code between splitM and splitF, we have to introduce
>a function split_common. We also introduce a function split to recover the
>fact that we want to apply the function to Person elements. Here, it is
>easy to factorize common code, but it is not necessarily the case.
>  
>
So I think it's more than just the convenience and ability to avoid 
duplication of code. The desired structure of the XML imposes type 
system constraints, in particular the requirement to mix constructors 
(XML tags) that originate from different type declarations.

(Actually, I've often thought it unfortunate that ML needs additional 
levels of constructors to discriminate different types of values, 
particularly when the underlying values have their own discriminating 
constructors. But maybe these are factored away by the compiler.)

>
>Another use of overloading is to give more precise information about the
>result, when one has more information about the argument. Simple minded
>examples:
>
>type Nat = 0--*
>let succ (Int -> Int; Nat -> Nat) x -> x + 1
>
>Here, we would have to completely duplicate the body of the function:
>
>let succInt (Int -> Int) x -> x + 1
>let succNat (Nat -> Nat) x -> x + 1
>
>Suppose we want to use succ like this:
>
>type T = [ Int* Nat* ]
>let succSeq (s : T) : T = map s with x -> succ x
>
>If we want to use succInt/succNat instead, we have to dispatch between Nat
>and Int in the caller:
>
>let succSeq (s : T) : T = map s with x & Nat -> succNat x | x -> succInt x
>
>But this dispach is completely useless, because the dynamic behavior is
>the same in both cases. Now replace Nat and Int by complex XML types,
>and x -> x + 1 by a complex transformation, and you get the picture.
>
This is another example where ML would require a wrapper constructor to 
distinguish Nat from Int values.

>
>
>There are also probably interesting examples combining overloaded
>functions and higher-order functions, but we haven't found a convincing
>one yet.
>
>  
>
>>Are they simply a matter of convenience, or is there
>>something specific about the way XML types are expressed/extended that
>>requires overloading (and extensible overloading -- section 3.5
>>"incremental programming"). Thanks,
>>    
>>
>
>I let Beppe answer this part.
>  
>
Regarding Beppe's comments on this -- overloading that's extensible 
w.r.t the module system looks like the unfortunate path that overloading 
takes you down, and one that's avoided when mutually recursive functions 
are used. But, as discussed above, the desire to eliminate intermediate 
tags when generating XML probably make this necessary.

Warren
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listes.math.univ-paris-diderot.fr/pipermail/cduce-users/attachments/20030727/e33d70bc/attachment.html>


More information about the Cduce-users mailing list