Abstract

In our previous paper, we have proposed a framework for automatically translating tree-processing programs into stream-processing programs. However, in writing programs that require buffering of input data, a user has to explicitly use {\buffering primitives which copy data from input stream to memory or copy constructed trees from memory to an output stream. Such explicit insertion of buffering primitives is often cumbersome and worsens the readability of the program. We overcome the above-mentioned problems by developing an algorithm which, given any simply-typed tree-processing program, automatically inserts buffering primitives. The resulting program is guaranteed to be well-typed under our previous ordered-linear type system, so that the program can be further transformed into an equivalent stream-processing program using our previous framework.