Every interactive system requires a presentation mechanism, to show the user the data it handles. Often, the relationship between the data and its presentation is complex; further, it is often mediated by a style mechanism, allowing the user or a designer to describe how the data should be displayed. It is a standing engineering challenge to develop a presentation model that is flexible, handling many kinds of data and layout; powerful, giving the user extensive control over appearance; and efficient enough for interactive work.

In this thesis, we propose a model of presentation by tree transformation. Because information often has a hierarchical logical structure, trees are widely used to represent documents and other data. The layout or presentation of a document is also often modeled as a computation over a tree. But these trees are not generally identical. In other words, presentation can be seen as a mapping between trees. Casting it as a formal tree transformation offers both expressive, compact style specifications and efficient implementation.

We present a general framework for presentation by tree transformation. It has been implemented as part of Ensemble, a software development environment and multimedia document system developed in our research group at Berkeley. We describe the tree-transformation mechanism, and a language for specifying presentation styles as transformations. In addition, we have developed several distinct output tree languages or "media": a pretty-printer for formatting programs, a graphing tool for presenting numerical data as x,y plots, and a general tree viewer for displaying the structure of any document.

We define four measures of efficiency that are important for interactive presentation. These are startup time, the time taken to bring up a document for the first time; refresh time, the time to redraw a document; change time, the time to process a simple change such as a character insertion; and the size of presentation data in memory. We show that the implementation can be tuned to provide good performance according to each measure.




Download Full History