Hosoya and Pierce present the modern experimental programming language Xduce, which is specifically designed to process Extensible Markup Language (XML) documents. The language uses XML documents as basic data, and provides powerful functionality to manipulate them. Supported operations include composition of XML documents by schema, extraction of the parts of a document, and transformation of documents from one schema to another.

A type system is one of the most interesting aspects of Xduce. It uses a static type system, based on information from document type definitions (DTD), to actually type-check a program. This language design results in reliable, error-free programs, which generate XML documents that always conform to specified types.

Another remarkable feature of Xduce is its support for flexibility in subtyping relations, which therefore imposes no restrictions on dependencies between document schemas. The language is also helpful in schema design and implementation. Xduce demonstrates an efficient matching facility, based on regular expression pattern matching. The paper presents the core features of the language, including formal definitions of values, types, terms, and type checking, along with proofs of their soundness and completeness.

The major contribution made by this paper is its complete description of Xduce as a programming language. The ideas used in Xduce have already inspired the development of a family of XML processing and schema languages, such as Cduce, tree regular expressions for XML (TREX), and relational exchange next generation (RELAX NG). Researchers and developers in XML processing languages will benefit from reading this paper.