Purely Applicative XML Cursor

Japanese

abstract

Cursor model is a relatively new approach for XML processing. In this model, a cursor acts like a lens that focuses on one node. You can freely move the cursor back and forth in an XML document, and edit the node it indicates. This model can be easily implemented in imperative language like C or Java, by using a pointer to subtree in the XML tree as the cursor. In a fully applicative setting, however, this simple scheme does not work since subtree modification through pointers breaks the principle of referential transparency.

We propose a purely functional data structure named “Slit” to realize a cursor on a tree efficiently in applicative manner. Slit is similar to the zipper data structure introduced by Huet, but has some improvements compared to the zipper in terms of efficiency and expressiveness while handling a tree with variadic child nodes. Using the slit, we implement an XML processing framework based on the cursor model. We also show a generalization of this framework to give an XML view for non XML data.

download

.bib

to be written..

presented by k.inaba (kiki .a.t. kmonos.net) under CC0