Abstract
There are two ways to write a program for manipulating tree-structured data
such as XML documents:
One is to write a tree-processing program
focusing on the logical structure of the data
and the other is to write a stream-processing
program focusing on the physical structure.
While tree-processing programs are easier to write
than stream-processing programs,
tree-processing programs are less efficient in memory usage
since they use trees as intermediate data.
Our aim is to establish a method for automatically translating
a tree-processing program to a stream-processing one
in order to take the best of both worlds.
We first define a programming language for processing binary trees
and a type system based on ordered linear type, and show that
every well-typed program can be translated to an equivalent
stream-processing program.
We then extend the language and the type system
to deal with XML documents.
We have implemented an XML stream processor generator based on our
algorithm, and obtained promising experimental results.