XDuce Examples

XDuce's values correspond to XML data; its types correspond to DTDs. For example, the XDuce value

addrbook[
  name["Haruo Hosoya"],
  addr["Tokyo"],
  name["Benjamin Pierce"],
  addr["Philadelphia"],
  tel["123-456-789"],
  name["Peter Buneman"],
  addr["Scotland"]]
    

corresponds to the following XML document:

<addrbook>
  <name>Haruo Hosoya</name>
  <addr>Tokyo</addr>
  <name>Benjamin Pierce</name>
  <addr>Philadelphia</addr>
  <tel>123-456-789</tel>
  <name>Peter Buneman</name>
  <addr>Scotland</addr>
</addrbook>
    

XDuce provides term constructors of the formlabel[...], where ... is a sequence of other values. This corresponds to <label>...</label> in XML notation. (We enclose strings in double-quotes, unlike XML.)

The XDuce type declaration

type Addrbook = addrbook[(Name,Addr,Tel?)*]
type Name = name[String]
type Addr = addr[String]
type Tel = tel[String]

corresponds to the following DTD:

<!ELEMENT addrbook (name,addr,tel?)*>
<!ELEMENT name #PCDATA>
<!ELEMENT addr #PCDATA>
<!ELEMENT tel #PCDATA>
    

Type constructors of the form label[...] have the same form as the term constructors that they classify. In addition, types may be formed using the regular expression operators * (repetition), | (alternation), and ? (optionality). The type (Name,Addr,Tel?)* means zero or more repetitions of the sequence of a Name, an Addr, and an optional Tel.

The main part of an XDuce program is a series of function definitions. As an example, we can write the following function for converting an address book into a telephone list.

fun mkTelList (val e as (Name,Addr,Tel?)*) : (Name,Tel)* =
  match e with
    name[val n], addr[val a], tel[val t], val rest
      -> name[n], tel[t], mkTelList(rest)
  | name[val n], addr[val a], val rest
      -> mkTelList(rest)
  | () 
      -> ()
    

This function takes a value of type (Name,Addr,Tel?)* and returns a value of type (Name,Tel)*. The body is a pattern match consisting of three cases. The first case matches when the input value is a sequence beginning with name, addr, and tel labels, followed by some further sequence of type (Name,Addr,Tel?)*. In this case, we pick out the name and tel elements and prepend them to the result of calling mkTelList recursively on the remainder. The second case matches when we cannot find tel after addr, and simply calls mkTelList recursively. The third case matches the empty sequence, and returns the empty sequence.