[cduce-users] overloaded functions

Alain.Frisch at ens.fr Alain.Frisch at ens.fr
Sun Jul 27 11:04:22 CEST 2003

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

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.

Another use of overloading is to give more precise information about the
result, when one has more information about the argument. Simple minded

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.

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.

-- Alain

More information about the Cduce-users mailing list