Erik Knoop

-- ErikKnoop - Januari 30th 2004

General Reading Material

Working on

• "MSL: A model for W3C? XML Schema", Allen Brown, Matthew Fuchs, Jonathan Robie and Philip Wadler. In proceedings WWW10, May 2001
• "The Essence of XML", Siméon and Wadler. In proceedings POPL 2003, 2003
• "Scripting XML with Generic Haskell", Frank Atanassow, Dave Clarke and Johan Jeuring. Techical report UU-CS-2003-23

Summaries

"Generic Haskell: practice and theory"

Authors: Ralf Hinze and Johan Jeuring

In this lecture notes the basic principles of Generic Programming are introduced to the reader. The main keywords in the first part of these notes is structural recursion. In the end of the first section it is shown how we can abstract certain functions (i.e. encoding) with respect to the structure of the type being encoded. Section 2 describes the basics of Generic Haskell to the reader and also introduces some basics constructs needed for the translation. In the last part of the notes the translation towards Haskell is described.

"Generic Haskell: applications"

Authors: Ralf Hinze and Johan Jeuring

These lecture notes continue the story told in the previous notes by example. Three examples are discussed:

• Generic Dictionaries
• Compressing XML documents
• The zipper

These examples are used to describe more advanced feautures of Generic Haskell, like type-indexed datatypes, dependencies between and generic abstractions of generic functions, etc.

"Type-indexed data types"

Authors: Ralf Hinze, Johan Jeuring and Andres Löh

In this article the notion of type-indexed datatypes is covered more closely. Two examples are used, namely digital search trees and the zipper. In this article the translation of type-indexed datatypes to Haskell is also covered. Drawback of this article is the different notation used, with respect to the lecture notes mentioned earlier in this list.

"Scripting XML with Generic Haskell"

Authors: Frank Atanassow, Dave Clarke and Johan Jeuring

In this article it is shown that Generic Haskell fits very well in the use for XML programming. In the first couple of sections generic programming is quickly introduced and the notation of Generic Haskell programmings is explained. In section 3 the first example, XComprez, is found. Personally is think, however, that sections 4 and 5 are most interesting. A generic representation of XML Schemas is described and how they can be used to write generic XML Parsers.

"Type isomorphisms simplify XML programming"

Authors: Frank Atanassow and Johan Jeuring

In this article it is shown that using isomorphism can make the output of UUXML more readable. Further a Java XML data binding is shortly discussed. In the last part the details and main ideas of the isomorphism approach are given in greater detail.

"Universes for Generic Programs and Proofs in Dependent Type Theory"

Authors: Marcin Benke, Peter Dybjer and Patrik Jansson

A very complicated article about dependent type theory, especially if you know nothing about dependent types and category theory. But I suppose it is very interesting for readers who have some knowledge in the mentioned fields.

"Scrap your boilerplate: a practical approach to generic programming"

Authors: Ralf Lämmel and Simon Peyton Jones

This article described a technique for seperating the interesting parts of an algorithm which traverses a data structure from the uninteresting, boilerplate, code. It looks very simple, and I think it has advantages, on the other hand, some cases remain vague. Examples of untreated topics are for example data constructs like the Generalised Rose Trees.

"A Lightweight Implementation of Generics and Dynamics"

Authors: James Cheney and Ralf Hinze

This article decsribes an alternative approach to generic programming, using type representations. It uses representation types to and existensial types to provide generic and dynamic types. Many techniques look similar to the ones used in the Generic Haskell Compiler.

Project

In "Scripting XML with Generic Haskell" by Atanassow, Clarke and Jeuring we see in section 4 a translation from XML Schema to Haskell datatypes. This translations is based on an old semantics for XML Schema, described in "SML: A model for W3C? XML Schema" by Brown, Fuchs, Robie and Wadler. Recently "The Essence of XML" by Siméon and Wadler has been presented, which contains a semantics for the currents XML Schema standard.

• Find out what differences there are in the semantics of "SML: A model for W3C? XML Schema" and "The Essence of XML".
• Find out whether section 4 of "Scripting XML with Generic Haskell" should be modified according to the differences.
• If section 4 needs modification, modify it.
• Find out whether the implementation needs modification.
• If the implementation needs modification, modify it.

Differences between "MSL: A model for W3C? Schema" and "The Essence of XML"

In the introduction of "The Essence of XML" is referred to "MSL: A model for W3C? Schema" and it is stated that the latter only provides structural typing. It suggests that this is a drawback of MSL and it also states that "The Essence of XML" studies the relation between named and structural typing. So the question is: "Does "The Essence of XML" provide named typing, and if so, how?"

Plan de campagne:

• Let us first take a closer look at MSL
• Take a closer look at "The Essence of XML"
• Finally, conclude their differences

"MSL: A model for W3C? Schema"

Summary: msl.pdf

"The Essence of XML"

Summary: essence.pdf

Differences

If we take a quick look at the summaries the most obvious conclusion is that MSL defines an abstract syntax which is much more detailed. On the other hand, in "The Essence of XML" more judgements are being defined. I think the solution to our problem (does "The Essence of XML" support named typing) is not in the first of those obvious differences. The main difference between the abstract syntaxes of the two articles is that MSL restricts a lot of possibilities in the syntax which are, as it looks like now, irrelevant to the problem. "The Essence of XML" defines more judgements, this might however be relevant to the problem. If we have more judgements, it might be that one of those judgements describes named typing. There are however also minor differences between the two articles, for example in the judgements which they have in common. It might also be the case that the solution to our problem lies within the minor differences.

We will first take a look at the judgements which are defined in "The Essence of XML" but are undefined in MSL, and after that we will, if neccesary, look at the minor differences in the judgements which the two articles have in common.

I've made two example matchings in the the style of "The Essence of XML".

However, no conclusion can be based on these derivations. A hint might be that the derives construct in "The Essence of XML" offers the named typing, but it might also be the case that this isn't true. The only way to be certain about the differences between MSL and "The Essence of XML" is to define a formal mapping between the two.

Contact

If you have suggestions, comments or whatever, don't hesitate but send me an e-mail!