Philip Wadler

Also see XML: Some hyperlinks minus the hype.

XQuery, a typed functional language for querying XML

Philip Wadler. Lecture notes for the Summer School on Advanced Functional Programming, Oxford, August 2002.

Lecture notes. Available in: pdf.

Slides. Available in: pdf.

Lab. Available in: tar.

The Essence of XML

Jerome Simeon and Philip Wadler. Preliminary version: FLOPS 2002, Aizu, Japan, 15-17 September 2002 (invited talk). Revised version: POPL 2003, New Orleans, January 2003.

The World-Wide Web Consortium (W3C) promotes XML and related standards, including XML Schema, XQuery, and XPath. This paper describes a formalization XML Schema. A formal semantics based on these ideas is part of the official XQuery and XPath specification, one of the first uses of formal methods by a standards body. XML Schema features both named and structural types, with structure based on tree grammars. While structural types and matching have been studied in other work (notably XDuce, Relax NG, and previous formalizations of XML Schema), this is the first work to study the relation between named types and structural types, and the relation between matching and validation.

Preliminary version (FLOPS 2002): pdf.

Revised version (accepted to POPL 2003): pdf.

Slides of the talk (FLOPS 2002): pdf.

XQuery tutorial

Peter Fankhauser and Philip Wadler. XML 2001, Orlando, 9-14 December 2001.

Available in: pdf.

Et tu XML? The fall of the relational empire

Philip Wadler. VLDB, Rome, September 2001 (keynote).

Three decades past, the relational empire conquered the hierarchical hegemony. Today, an upstart challenges the relational empire's dominance, threatening the return of hierarchy. XML is Lisp's bastard nephew, with uglier syntax and no semantics. Yet XML is poised to enable the creation of a Web of data that dwarfs anything since the Library at Alexandria. This talk examines the design of XQuery, the W3C standard query language for XML, and related standards such as XML Schema.

Available in: pdf.

MSL: A model for W3C XML Schema

Allen Brown, Matthew Fuchs, Jonathan Robie, Philip Wadler. WWW10, Hong Kong, May 2001.

MSL (Model Schema Language) is an attempt to formalize some of the core idea in XML Schema. The benefits of a formal description is that it is both concise and precise. MSL has already proved helpful in work on the design of XML Query. We expect that similar techniques can be used to extend MSL to include most or all of XML Schema.

Available in: pdf, dvi, ps, dvi.gz, ps.gz.

The slides from the presentation in Hong Kong.

Available in: pdf.

A semistructured monad for semistructured data

Mary Fernandez, Jerome Simeon, Philip Wadler. ICDT, London, January 2001.

An updated version of the paper An Algebra for XML Query.

Available in: pdf.

An Algebra for XML Query

Mary Fernandez, Jerome Simeon, Philip Wadler. FST TCS, Delhi, December 2000.

An updated version of the manuscript An Algebra for XML Query.

Available in: pdf.

An Algebra for XML Query

Mary Fernandez, Jerome Simeon, Philip Wadler. Draft manuscript, June 2000.

This note presents a possible algebra for an XML query language, submitted as an input to the XML Query working group.

Available in: pdf, ps.

Please try out our implementation of the algebra!

There is also a November 1999 draft of the algebra, which is rather different.

The Next 700 Markup Languages

Philip Wadler. Invited Talk, Second Conference on Domain Specific Languages (DSL'99), Austin, Texas, October 1999.

XML (eXtensible Markup Language) is a magnet for hype: the successor to HTML for Web publishing, electronic data interchange, and e-commerce. In fact, XML is little more than a notation for trees and for tree grammars, a verbose variant of Lisp S-expressions coupled with a poor man's BNF (Backus-Naur form). Yet this simple basis has spawned scores of specialized sublanguages: for airlines, banks, and cell phones; for astronomy, biology, and chemistry; for the DOD and the IRS. Domain-specific languages indeed! There is much for the language designer to contribute here. In particular, as all this is based on a sort of S-expression, is there a role for a sort of Lisp?

Available in: pdf, dvi, ps, dvi.gz, ps.gz.

A second version, with more on XSLT and Xduce, but less on syntax. Invited talk, DIMACS workshop on Data Processing on the Web: A Look into the Future, 6-7 March 2000.

Available in: pdf, dvi, ps, dvi.gz, ps.gz.

XML Query Languages: Experiences and Exemplars

Mary Fernandez, Jerome Simeon, Philip Wadler (editors). Draft manuscript, September 1999.

This paper identifies essential features of an XML query language by examining four existing query languages: XML-QL, YATL, Lorel, and XQL. The first three languages come from the database community and possess striking similarities. The fourth comes from the document community and lacks some key functionality of the other three.

Available in: pdf, dvi, ps,

A formal semantics of patterns in XSLT

Philip Wadler. Markup Technologies, Philadelphia, December 1999. Revised version in Markup Languages, MIT Press, June 2001.

This note presents a formal semantics of the pattern language from the 16 December 1998 draft of XSLT. The semantics is clear and concise, summarizing in one page of formulas what required about ten pages of prose to describe. With the aid of the semantics one can rigorously state and prove properties of the language; these properties helped to guide future development of the XSLT design. The semantics was developed using standard techniques from the programming language community, and this article provides a tutorial introduction to these techniques. While little here will be new to the language theorist, some of what is here may be of use to the markup technologist.

Available in: pdf, dvi, ps, dvi.gz, ps.gz.

Two semantics of XPath

This note summarizes two approaches to a formal semantics for XPath. It was written to facilitate discussions in the XSL W3C WG.

Available in: pdf, dvi, ps, dvi.gz, ps.gz.

Philip Wadler,