Lambda the Ultimate

Presents the mathematical foundations of an important practical subject in an easy to understand way. The author's intention is expressed in an epigram at the beginning of the paper: "Semanticists should be obstetricians, not coroners of programming languages." (John Reynolds).

An tutorial on sets, relations, and denotational semantics is accompanied by a small XML data model similar to the XML DOM API. The conciseness and lack of ambiguity helps one to understand DOM better.

An actual instance is given when the mathematical model helped identified an ambiguity in XPATH and influenced language definition committee decisions. Instances are also given of when semantics helps you add language restrictions for efficiency or "prove equivalences between patterns."

Mathematical formulas are translated into plain English. Reading like normal language definitions, they clearly demonstrate that mathematics is compatible with existing language definition practice.

The semantics was "developed and debugged by transliterating it into the functional language Haskell." The code is available from the author. (A formal semantics of patterns in XSLT, Wadler, 2000) [ Author's XML Papers]