Generating efficient virtual worlds for visualization using partial evaluation and dynamic compilation.
We argue that runtime program transformation, partial evaluation, and dynamic compilation are essential tools for automated generation of flexible, highly interactive graphical interfaces. In particular, these techniques help bridge the gap between a high-level, functional description and an efficient implementation. To support our claim, we describe our application of these techniques to a functional implementation of n-Vision, a real-time visualization system that represents multivariate relations as nested 3D interactors, and to Auto Visual, a rule-based system that designs n-Vision visualizations from high-level task specifications. n-Vision visualizations are specified using a simple functional language. These programs are transformed into a cached dataflow graph. A partial evaluator is used on particular computation-intensive function applications, and the results are compiled to native code. The functional representation simplifies generation of correct code, and the program transformations ensure good performance. We demonstrate why these transformations improve performance and why they cannot be done at compile time.
Introduction
Modern programming language implementation techniques
are extremely important, even essential, for implementing
flexible and efficient interactive visualization tools. As a
case in point, we describe our new version of n-Vision, a
visualization tool that we originally developed to present
multivariate functions as interactive, 3D virtual worlds [3].
To appear in ACM SIGPLAN Conference on Partial
Evaluation and Semantics-Based Program Manipulation
(PEPM'97).
We have used functional programming, program transforma-
tion, partial evaluation and dynamic compilation to improve
both the functionality and efficiency of the original version
of n-Vision with the added benefit of simplifying the production
and maintenance of its code.
The primary focus of our research is the improvement
of graphics and visualization systems through knowledge-based
automated design and generation. In general, we believe
that capturing rules and techniques of graphic design,
and applying them to specific application domains can both
increase the quality of the visualizations presented to users
and relieve users of the burden of creating these visualizations
themselves. Experimental automated generation systems
have been developed in a variety of fields, including
information visualization [13, 5, 16, 3, 21], pictorial explanations
[17], and multimedia explanations [6, 1].
In our current work, we are continuing development
of AutoVisual [3], a rule-based component that designs n-Vision
visualizations from high-level, user-specified visualization
tasks. AutoVisual produces representations of real-
time, interactive, graphical scenes, which are actually small
functional programs that generate and render graphical objects
in response to user input. These programs are compositions
of small, known components that allow the user
to interactively explore 3D visualizations of multivariate re-
lations. The space of possible visualizations that can be
produced is extremely large and diverse, so an automated
tool should be very helpful in searching it. Thus, this is a
promising domain for automated generation research.
Unfortunately, straightforward evaluation of these visualization
programs is very inefficient. Even with special-purpose
3D graphics hardware, computing and rendering all
components of a scene for each animation frame is too expensive
to achieve the frame rates (10-20Hz) that we need
to make effective interactive visualizations. Therefore, we
have redesigned n-Vision to perform a few, carefully selected
transformations and optimizations on these programs.
Specifically, we exploit frame coherence, defined as the tendency
for successive frames of an animation to be very sim-
ilar, to avoid redundant computation between frames [7].
First, the visualization specification is transformed into
a cached dataflow graph. Nodes whose input values have
not changed since the previous firing are not reevaluated,
and cached output values are used instead. This is a simple
form of memoization that is very effective in this situation.
Second, partial evaluation and dynamic compilation are
used to optimize the sampling loops of those user functions
being visualized. Other than the rendering, this is the
most computation-intensive part of n-Vision so we get large
speedups by factoring out sub-expressions of the functions
that are invariant within these loops.
We find that even though our optimizations are very sim-
ple, their strategic application improves the efficiency of n-Vision
enormously, while at the same time simplifying the
implementation. We have observed that many languages are
still "batch-oriented," assuming that all compilation is done
before run-time. We conclude from this work that improved
language models and implementations would benefit interactive
system development greatly. Specifically, we conjecture
that the functionality of all stages of the compiler should be
exposed so that they are available to to the programmer at
run-time, producing a sort of "visible compiler."
n-Vision and AutoVisual
n-Vision is visualization system designed for exploring multi-variate
functions. A novel display and interaction metaphor,
called worlds within worlds, is used to represent the higher
dimensions. We use real-time 3D graphics with a stereo display
and 3D input devices so that the user works in the
highest possible natural dimension.
n-Vision worlds can be varied and complex, both in design
and implementation. It can be quite difficult for users
to get a good grasp of the space of the function they wish to
view, much less the space of all the possible visualizations
of that function. To address this problem, we are developing
AutoVisual a knowledge-based system that designs and
implements n-Vision worlds.
Worlds within Worlds
The worlds within worlds method uses a hierarchy of nested
graphs. Each graph is an interactor, a dynamic object that
responds to user inputs. Consider a function f(x1 ; x2) This
can be graphed with a height field (surface plot) in 3D. If instead
we have g(x1 ; :::; x5 ), the height field can only be used
to graph a slice of the function created by holding three of
the variables constant. In programming language terms, for
constants c3 , c4 , c5 , we can create a closure over the original
function and plot that instead. Using Scheme syntax, we
would define the "sliced" function as follows:
(define g-sliced
(lambda (x1 x2) (g x1 x2 c3 c4 c5))))
If we then allow the user to interactively modify the values
of x3 , x4 and x5 , redefining and re-plotting g-sliced, then
the whole function space could be explored interactively. We
can then define a higher-order function that actually does
the slicing:
(define g-slicer (x3 x4 x5)
(lambda (x1 x2) (g x1 x2 x3 x4 x5)))
Whenever the values of x3 , x4 and x5 change, we reevaluate
g-slicer and the resulting function is graphed as a height-
field.
The key to worlds within worlds is representing this slicing
dependency graphically. We create a 3D volume with
each of x3 , x4 , and x5 bound to an axis, so that any point
within that volume determines particular constants c3 , c4 ,
and c5 for each. We call this the outer world. We then embed
another 3D world inside this, the inner world, containing
the surface plot of g-sliced, with its origin constrained to
lie within the bounds of the outer world. The position of the
inner world's origin relative to the outer world determines
the values for x3 , x4 , and x5 . As the user translates the inner
world within the outer world, the closure is recomputed and
the resulting graph redrawn. An example n-Vision world
can be seen in Figure 1. Thus, worlds within worlds is a
method of composing graphs so that they become browsers
of a higher-dimensional space.
Traditional graphs are used to display functions. We
can think of the outer world as a graph of a higher-order
function, each point within its space determining a unique
function. The user views the function at a particular point
by placing the origin of a function graph there. This technique
can be applied recursively to visualize more variables.
Given a function h(x1 ; :::; x8 ), we could have three levels of
worlds. The inner two would be as before, the outermost
axes would be bound to x6 , x7 , and x8 . The higher-order
function graphed within this outermost world must itself return
a higher-order function of the same form as g-slicer
above:
(define h-slicer (x6 x7 x8)
(lambda (x3 x4 5)
(lambda (x1 x2) (h x1 x2 x3 x4 x5))))
Any number of instances of worlds may be placed at
any level, giving multiple samples of the higher-dimensional
space. Worlds may be rotated and scaled, as well as trans-
lated, but these operations do not have the equivalent semantics
of translation. They are used only to adjust the
worlds for better viewing.
We have presented a particular 3D example here, but
obviously the worlds within worlds method is very flexible,
and we have implemented a number of variations. Clearly,
the variables of the function may also be permuted so that
they are bound to different axes.
However, worlds may also be of any (graphically real-
izable) dimension d, 0 - d - 3. The graphs of functions
may also be of any type (e.g., line graphs, images, or volume
renderings). All that is required is that a graph be
an appropriate encoding of the function represented in that
world.

Figure

2 shows a visualization where multiple inner
worlds with volume renderings have been used to display as
many samples of the function as possible.
We have also extended the notion of a world to redisplay
portions of a function graph. In general, we define worlds as
tools, virtual interaction devices that can be used to select
values from other tools and redisplay them. (We describe
this more fully in [3], which is beyond the scope of this
paper.)
AutoVisual
n-Vision worlds can be quite complex in their design. Variables
may be permuted, functions can be sliced in many different
ways, different graph types can be substituted, and
so forth. All these factors are both difficult to master and

Figure

1: An n-Vision world representing a function of 5 variables as a hierarchy of graphs. The height field in the inner world
encodes the function for constant values of x3, x4, and x5, determined by the position of the inner world's origin relative to
the outer world. As the user translates the inner world, n-Vision updates the height field.
tedious to control interactively. To alleviate this complexity,
we are building AutoVisual, a knowledge-based system that
transforms user functions and high-level task specifications
into interactive n-Vision worlds. our work on AutoVisual has
motivated many of the design features of the new version of
n-Vision.
In any design process, there must be criteria for evaluating
the quality of a particular design specification. In
AutoVisual, we use criteria derived from those set forth in
Mackinlay's work on APT [13]: a generated static graph
must be both expressive and effective. An expressive graph
presents exactly the desired data to the user, no more, no
less. An effective graph is easy to read and draw inferences
from. In AutoVisual we try to establish that a design is
potentially expressive and potentially effective. An interactive
graph does not display all its data at once, but the user
must have the potential of seeing all the data over time.
Similarly, not every view of an interactive, 3D graph will
be effective, but it must be possible for the user to find one
or more viewpoints and configurations of the visualization
which are effective. Furthermore, the graph itself must be
reasonably responsive; a visualization that is too complex
to display in real time is too hard to work with.
Our new method of representing n-Vision worlds functionally
eases the burden on AutoVisual. Functional composition
of small, general components allows AutoVisual to
design a wide variety of worlds, and yet be able to verify
that a particular implementation is correct and that it will
exhibit reasonable performance.
Representing Visualizations
In graphical applications, one of the primary optimization
techniques is exploiting coherence, the tendency for neighboring
pixels or image regions to be similar. Often, the common
sub-expressions in the computation of an image can be

Figure

2: An n-Vision world representing a function of 6 variables. The inner world is a simple volume rendering, sampling
the function over three variables, and encoding the result as a color. Multiple inner worlds have been instantiated to give the
user a quick overview of the behavior of the function.
factored out and evaluated only once. Animations generally
exhibit frame coherence, the tendency for successive images
to be similar, and hence their computations will have redun-
dancy. Unfortunately, in an interactive application such as
n-Vision, it is not possible to determine these redundancies
at compile time, because they depend on the user's actions.
We exploit frame coherence by wrapping function applications
with caching functions, in effect implementing a simple
form of memoization.
n-Vision worlds are specified using a simple functional
language. Functional expressions describe a scene to be rendered
based on user input. These expressions are evaluated
repeatedly inside an interaction loop. Expressions in this
language are easily transformed into executable dataflow
graphs.
The standard method for representing scenes in graphical
applications is the display list, developed very early in
the history of computer graphics. A hierarchical display
list represents a graphical scene as a hierarchical composition
of reference frames (coordinate systems) with objects
instanced relative to a particular reference frame. However,
display lists do not have a general representation of functional
dependency between graphical components. The hierarchical
structure does allow objects to be defined relative
to each other, but this is too limited for most applications,
and, in particular, is too limited to represent the complex
dependencies inherent in n-Vision worlds.
Data dependencies are an implicit part of the functional
specification, obviating the need for a special change propagation
mechanism, such as active variables [4, 20]. Whenever
a function node in the graph is evaluated, the interpreter
automatically distributes the results to other nodes that require
them. These dependencies specify a partial ordering of
function evaluation, ensuring that no function is evaluated
until all its arguments have been calculated. A node need
only be evaluated once, regardless of how often the results
are used.
Language Definition
The functional language used to implement n-Vision worlds
is quite simple. It is a single-assignment language that supports
let, if, and followed-by expressions and function appli-
cations. Functions may have multiple return values. Also,
a function may be tagged as volatile, indicating that it has
a side-effect. Currently, lambda expressions are not sup-
ported; functions are defined and compiled before run-time.
Implementing direct manipulation [18] requires access to
the geometry values computed in the previous animation
frame. Therefore, we need a representation of state. The
followed-by expression provides this functionality. It has the
form (followed-by head rest), and constructs an infinite lazy
stream. The first element of the stream is the value of the
first argument evaluated in the first iteration of the inter-action
loop. The k-th element of the list, for k ? 1, is the
value of the second argument evaluated in iteration
the interaction loop.
Dataflow Transformations
A dataflow graph is constructed from the functional specification
of the visualization. A function node is created for
each call site. Each expression representing an argument
to the call is recursively transformed into a dataflow graph,
and the output port of the root node connected to the appropriate
input port of the function node. Constant values
are placed in special nodes and are attached directly to input
ports. Nodes containing volatile functions are marked
and the functions are always evaluated when the node fires.
In the case of a followed-by expression, a special node
with two inputs is created. On the first firing, it removes
a token from the left arc, and on all subsequent firings, it
removes a token from the right arc. The arcs created in
constructing the argument graphs are allowed to be back
arcs, allowing values computed in one iteration of the graph
to be used in the next.
As the graph is constructed, the transformation engine
performs two standard optimizations. The first is constant
folding: when all arguments in a function call are constants
and the function is not labeled volatile, the expression is
evaluated, and the function node's output ports are replaced
by constant nodes. The second optimization is finding and
eliminating common sub-expressions. In addition to reducing
the computation within nodes, these optimizations tend
to reduce the number of nodes, and hence the overhead of
executing the dataflow graph.
Caching
After the graph is constructed, it is passed to a running
animation loop. Each evaluation of the graph produces an
image on the screen. As mentioned before, graphical applications
often display frame coherence. This implies that the
values computed at any particular call site will have a high
probability of being the same from one iteration of the loop
to the next. We use a special caching mechanism wrapped
around every function node to exploit this.
Values are transmitted around the dataflow graph in
small data structures called tokens. In each token, there
is a bit, called the change-bit, indicating whether the current
value is different from the previous one. Constant tokens
have their change-bit true during the first iteration of
the graph to force evaluation of the nodes, and false there-
after. In addition, every function node has a cache for each
output token. If a node fires and none of the input values
have changed, the function is not evaluated, and the cached
tokens are used instead with their change-bits set to false.
If one or more input values have changed, the function
is re-evaluated. Before the caches are updated, each newly
computed value is compared with the corresponding cached
value. If the new and old values are equal, the change-bits
in the outgoing tokens are again set to false. Figure 3 shows
pseudo-code for the caching mechanism.
The equality operators are specified per type by the user.
Objects for which equality is too expensive to compute may
be assigned operators that always return false. For large
objects, we often use equality of pointers.
In summary, a node is evaluated only if one or more
of its input values have changed. If a node is reevaluated,
but produces the same value or values it did before, then
subsequent nodes will not be evaluated. Thus, if a function
acts as a low-pass filter, the resulting computation will be
filtered as well. If no values change at the leaf nodes of the
graph, all computation is avoided except for the application
of volatile nodes and the overhead of traversing the graph.
Tokens have type:
struct Token!T? -
bool ch; // changed-bit
// tx[1.n] are the input tokens.
// ty[1.m] are the output token caches.
// y[1.m] holds newly computed values.
if (eval) -
// shorthand for multiple return values.
(y[1], .,
for(int i=1, i!=m; i++) -
for(int i=1, i!=m; i++)

Figure

3: C++ pseudo-code for the caching mechanism in
function evaluation nodes.
n-Vision as Partial Application
We present a model of the essential computation in n-Vision
using curried functions. This serves two purposes. As mentioned
above, we consider n-Vision to be a visual representation
of currying, so this representation seems natural. It
also helps simplify the discussion of how we use partial evaluation

For simplicity, assume that all functions f visualized in
n-Vision map n-tuples of real numbers to a single real value.
During design, AutoVisual will first produce a new function
f 0 by partitioning the arguments of f into multiple n-tuples,
each corresponding to a level of the visualization, and will
then curry the result to produce f 00 :
Now, each level of the visualization corresponds to a partial
application of f 00 .
Consider an example. Given a function
AutoVisual has designed a visualization of three levels
where each world is 2D, and the innermost world contains
a line graph. The outermost world, W0 , encodes x1 and x2 ;
the middle world, W1 , encodes x3 and x4 ; and the innermost
world, W2 , plots the value of the function against x5 . The
curried version of g, call it h0 , for this visualization is:
The outermost world W0 represents h0 . Selecting a point
in W0 and applying it to h0 yields h1 , the
function represented by W1 . Similarly, world W2 represents
h2 , obtained by applying a point selected from
world
Note that h2 has type (!) ! !, so this function can be
encoded with a traditional line graph within world W2 by
sampling it at a set of 1D points f(s0
Partial Evaluation
Within the computation of each animation frame, the sampling
of functions for each graph is by far the most expensive
computation; hence, we have targeted it for optimization.
Partial evaluation and compilation of the sampling loops are
obvious optimizations here, but the situation is complicated
by the dynamic nature of the design process and the running
application. Unlike many of the applications discussed
in [11, 10], we must run our partial evaluator at run-time.
In effect, because AutoVisual generates programs on the fly
with dynamic, higher-order functions, our language processing
and optimizing facilities must operate on the fly as well.
Consider the two-level visualization shown in Figure 2.
There is a 3 \Theta 3 \Theta 3 grid of innermost worlds, each of
which calculates a 4 \Theta 4 \Theta 4 grid, requiring over 1700 sam-
ples. A more reasonable visualization would have at least a
\Theta 16 \Theta 16 grid within each world, requiring over 100; 000
samples. Animating this visualization at a rate of, say, 10Hz
by moving the entire grid of inner worlds would thus require
over one million function samples per second. Clearly, our
goal in applying partial evaluation here should be to optimize
the functions h i of the previous section.
The language provided to the user for implementing
functions to be visualized is quite simple, consisting solely
of constants, variables and primitive functions. This serves
two purposes. The partial evaluator was much simpler to
write, and the result is lightweight, i.e., small and fast. Our
goal was to verify that partial evaluation was useful in this
context, not to build a full specializer. As a result, the partial
evaluator is little more than a cogen operator that does
constant folding. However, this is enough to confirm our
expectations that partial evaluation is an important tool in
visualization software, especially when used at run-time. As
discussed in Section , more sophisticated specializers have
been designed that could now be substituted.
Within the innermost sampling loop, we want to evaluate
the smallest possible function. In the example above, this
function would be h2 , and an obvious optimization is:
Therefore, we would like
and this is precisely the result of our specialiser.
The partial evaluation algorithm takes as arguments an
abstract syntax tree T of the function to be specialized, and
a list L of lists of variables, e.g.,
This list represents the partial applications at each level of
the visualization in order, beginning at the outermost level
and working inward, and is generated by AutoVisual.
The algorithm takes the first set of variables, labels them
static, and then performs a binding time analysis. The syntax
tree is partitioned into a forest of completely static sub-
trees, and one tree of dynamic values. The algorithm recurses
with the dynamic tree, pruned of the static sub-trees,
and generates a residual function. A generating function
that evaluates the pruned sub-trees is then wrapped around
the residual, and the result returned. The result is a set of
nested functions which implement the partial application,
performing as much computation as possible at each stage.
These are compiled and dynamically linked to ensure optimal
performance.
Step 6 is the most subtle. The evaluation of static parameters
can yield new values which must then be made
available to the residual functions. In this step, these new
values are located and added to the argument list for the
residual function. This is known as arity raising, and is covered
in more detail in [11, page 224]. These new arguments
are given generated variable names of the form "gvi", as can
be seen in the generated code in Figure 5.
Step 7 generates a list of let bindings to capture the values
of computing the sub-trees labelled static. These bindings
are then spliced into the resulting function code.
Step 8 prunes the tree of all the fully-static subtrees,
replacing them with references to the variables defined in
the binding lists in the previous step.
In the following pseudo-code, we use the Scheme macro
notation to construct new functions, the scope of Let constructs
covers the entire algorithm, and the function unparse
converts a syntax tree to an s-expression.
Given a function g:
(define (g x1 x2 x3 x4 x5)
1. Given: an abstract syntax tree T, and a list L of lists
of variable names.
2. Let
3. If TL is Nil, return the value:
'(lambda ,VS ,(unparse T)).
4. Label all leaves of T either 'S or 'D: if a constant, then
if a variable V, and V is in VS, then 'S, else 'D.
5. Traverse T depth first, labelling each internal node either
'S or 'D: if all sub-expressions of the node are
labelled 'S, then 'S, else 'D.
'(). Perform a depth first search of the tree
T, stopping at any node labelled 'S. If the node is a
variable, add its name to the list VN. If not, generate
a unique variable name, attach it to the node, and add
the name to VN.
7. Let BL='(). For each variable V in VN, create a list
'(,V ,(unparse ST)), where ST is the subtree of T labelled
by V. Add the result to the list BL.
8. Let NT= copyTree(T). For each variable V in VN,
replace the subtree labelled by V with V itself.
9. Let TTL= (tail TL), HTL= (head TL).
Let RF=(recurse NT (cons (append VN HTL) TTL)).
Let RFN= a unique function name.
10. Return the value:
'(lambda ,VS
(let ((,RFN ,RF))
(let ,BL
(lambda

Figure

4: pseudo-code for the partial evaluator used to optimize
visualization functions.
and the partioning list L:
the specializer generates the code in Figure 5. The result
is compact and efficient. After two partial applications, the
resulting function performs one multiplication and one addition
per call.
Efficiency
We present some estimates of efficiency gains resulting from
the dataflow caching and partial evaluation. Both sets of
measurements are obviously highly dependent on the individual
programs being run. However, we have observed some
general trends for our applications, and we present some approximate
figures from these.
First, the dataflow architecture introduces some extra
cost, both in the execution of the graph, and in the caching
mechanisms. With the dataflow executive running, and with
(lambda (x1 x2)
(let ((rf1
(lambda (x3 x4 gv0 gv1)
(let ((rf0
(lambda (x5 gv2 gv1)
(let ((gv2 (+ gv0 (* x3 x4))))
(lambda
(let ((gv0 (* x1 x2))
(lambda (x3 x4)

Figure

5: The specialized code for a function of five variables

caching active but always missing, the overhead averages
between 10 and 15 percent. Typically, between 20 and
percent of the nodes are labelled volatile, and always fire.
Of the remaining nodes, about one third are re-evaluated
on average. If all of the interactive controls are made to
vary continuously under program control, this climbs to 100
percent. In general, though, there are many controls, and
the user can move at most a few at a time.
However, not all nodes carry equal weight. Other than
the rendering operations, which are performed by volatile
nodes, the function sampling nodes are the most intensive.
The clean structure of the functional programming specification
makes it easy to guarantee that these nodes are only
fired when absolutely necessary. We know from hard experience
that this is not true in event propagation systems
commonly used in user interface software.
The partial evaluation and dynamic compilation perform
very well. The time required for specialization is typically
less than a second, and hence is unnoticeable in the inter-
action, as it happens only once when the function is first
defined. The compilation and loading takes several seconds,
but only because these operations require disk activity. We
believe that given a small, in-memory code generator, the
delay would also be unnoticeable.
As for the running time of the functions, it is easy to
construct unbalanced functions and visualizations where no
speedup is gained. However, for most functions we have
tried, the sampling time within the innermost loop is generally
less than 20 percent of the original, sometimes as low as
percent. Considering the formidable multipliers discussed
in section , this is an important gain.
Why Not Pre-compilation
It is important to realize the complexity of the design space
of visualizations to understand why the partial evaluation
and dynamic compilation described above are so necessary.
Assume, for the moment, that the function the user wishes
to visualize is fixed, and that the design of the visualization
is fixed, except for the order of binding variables to
particular axes. These features make using n-Vision more
pleasant, e.g., allowing the user to specify new functions
to visualize without recompiling n-Vision, but are not absolutely
essential. However, re-orienting your view of the
multidimensional space by selectively reordering the axes is
very often essential to the comprehension of such a function,
so we must allow the user to do this dynamically.
Given these fixed points, we ask the following question:
Why not just pre-compute and compile functions that implement
all the possible sampling loops? That is, for each
possible binding of axes to the innermost worlds, where the
computation is most intense, we could generate and compile
a partially-evaluated, optimized function.
The general equation for the number of functions which
must be precompiled is:
However, in general, a function will be sampled over at
most three variables (as for a volume rendering) in the innermost
world, reducing the equation to:X
(2)
If we perform matrix transposition on the results of the
sampling appropriately, we don't need to generate functions
for each permutation of parameters, just for each unique set.
Again for a maximum of three sampling variables, this is:X
6 (3)
The graph of the number of sampling functions need,
both with and without the permutations, is shown in Figure
6. Clearly, even without the permutations, the number
of functions needed increases unacceptably past 9 or 10 vari-
ables. Ideally, we would like n-Vision to be used for functions
of many more variables than this.100300500700900

Figure

The number of functions which would need to be
pre-computed for each user function of n variables.
Implementation
The dataflow interpreter is implemented in C ++ . The
datatypes and functions used in the computations are also
defined in C ++ . A simple pre-processor, written in AWK,
is used to provide nice syntax for multiple return values,
and to do code generation of the evaluation guards and
caching functions. Run-time type information is generated
so that dynamic construction of the dataflow graphs is also
type-checked. Scheme bindings for creating and connecting
dataflow nodes and constants are generated. Scheme macros
and functions are used to implement the syntax of our functional
language and to perform some of the transformations
of the programs. Currently, our scheme interpreter is STk[8],
which is reasonably efficient and has excellent support for
the
User n-Vision functions are restricted to the tiny language
described in Section . Our partial evaluator specializes
these expressions in the source language, and then generates
C code, which is compiled and loaded dynamically.
Conclusions and future work
Though we have yet to do a series of definitive benchmarks,
it is clear that the existing system gives very good perfor-
mance. The increased flexibility of the dataflow system over
our previous implementation is making the redesign and implementation
of AutoVisual much easier.
Clearly, there are many more optimizations which could
be done. The caching transformations are simplistic. At a
minimum, we will need to support lambda functions in our
language so that we can apply the caching and guards hi-
erarchically, avoiding traversal as well as recomputation of
whole subgraphs. Even better would be statistical modeling
of the reevaluation behavior of nodes. Clearly, partial evaluation
of dataflow nodes other than just the sampling functions
may be beneficial. Better scheduling of the dataflow
graph is also possible. Large sections could almost certainly
be converted to straight code.
However, we believe we have done the most important
optimizations. Our next step is to finish the automated
generation system. This will allow us to evaluate a wide
variety of visualization configurations, and really put the
system to the test. We believe this will help pinpoint much
more accurately where further optimizations should be done.
The partial ordering of computation specified in the functional
programs is precisely what is required for parallelization
of the computation. We believe that the design should
extend to a distributed version of the interpreter, though we
have not built one yet.
Partial-evaluation has been applied in similar situations.
Our inspiration for applying partial evaluation to n-Vision
was Synthesis, an efficient operating system that uses partial
evaluation as one of its optimization techniques[14].
Berlin and Weise use partial evaluation to specialize scientific
computations[2], but we believe that our system requires
different solutions because of its dynamic nature.
It is clear to us that these optimization techniques are
very useful, especially when exposed as language features
that can be invoked at run-time. Leone and Lee use partial
evaluation and run-time code generation in Fabius to
improve the performance of an ML-like language[12]. We
are currently evaluating whether Fabius has the flexibility
necessary for an efficient implementation of n-Vision. Fur-
thermore, we believe that our simple binding time analysis
and specialization is subsumed by more recent work in multi-level
specialization [9, 19], and that our application would
benefit from having a more sophisticated language for implementing
functions without loss of efficiency.
In general, we believe that if all functions of the compilation
system, i.e., parsing, type-checking, optimizing trans-
formations, and code generation, were made visible for programmers
to invoke directly, it would be possible to build
programs that would be simpler, yet more interactive and
more efficient. This makes perfect sense if one imagines a
user interface that is so flexible that the user is actually
programming interactively, acting as a kind of on-line script
generator. Most compilers are still batch-oriented. We believe
the languages and compilers need to interactive to truly
build interactive applications. We have tried to do this in a
small way with this new version of n-Vision.

Acknowledgments

We would like to thank Bruce Naylor for the original inspiration
for transforming a functional scene representation to
a cached dataflow graph.
The research described here is supported in part by ONR
Contract N00014-94-1-0564, NSF Grant CDA-90-24735, the
Columbia University CAT in High Performance Computing
and Communications in Healthcare (funded by the NY State
Science and Technology Foundation), and a gift from Digital
Image Design.



--R

WIP: The automatic synthesis of multimodal presentations.
Compiling scientific code using partial evaluation.

Scope: Automated generation of graphical interfaces.

Automating the generation of coordinated multimedia explanations.
Computer Graphics: Principles and Practice
Designing a Meta Object Protocol to wrap a Standard Graphical Toolkit.
Efficient multi-level generating extensions for program specialization
An introduction to partial evaluation.
Partial Evaluation and Automatic Program Generation.
Lightweight run-time code gen- eration
Automating the design of graphical presentations of relational information.
An Efficient Implementation of Fundamental Operating System Services.
Tcl and the toolkit.
Data characterization for intelligent graphics presentation.
Automated generation of intent-based 3D illustrations
Direct manipulation: A step beyond programming languages.
Cogen in six lines.
Using active data in a UIMS.
Data characterization for automatically visualizing heterogeneous information.
--TR
Automating the design of graphical presentations of relational information
Using active data in a UIMS
Scope: automated generation of graphical interfaces
Data characterization for intelligent graphics presentation
Task-analytic approach to the automated design of graphic presentations
Automated generation of intent-based 3D Illustrations
Synthesis: an efficient implementation of fundamental operating system services
Partial evaluation and automatic program generation
WIP: the automatic synthesis of multimodal presentations
Automating the generation of coordinated multimedia explanations
Tcl and the
Computer graphics (2nd ed. in C)
Cogen in six lines
An introduction to partial evaluation
Auto Visual
Efficient Multi-level Generating Extensions for Program Specialization
Designing a Meta Object Protocol to Wrap a Standard Graphic Toolkit
Data characterization for automatically visualizing heterogeneous information
Compiling Scientific Code Using Partial Evaluation

--CTR
David Durand , Paul Kahn, MAPA: a system for inducing and visualizing hierarchy in Websites, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.66-76, June 20-24, 1998, Pittsburgh, Pennsylvania, United States
dataflow;multivariate data visualization;partial evaluation;program transformation;virtual worlds