AbstractAlthough visual and direct-manipulation programming systems have been a topic of research for many years, there is still no consensus on how they should be designed. Critters is a novel direct-manipulation system which incorporates several ideas for visual programming. Geometric computation allows a wide variety of mathematical expressions to be built by direct manipulation. A simple example-based programming interface is used to specify control flow and recursion. The inference algorithm that creates behavior from examples is deliberately simple: the goal is to make it as predictable and easily remembered as the operator precedence rules in many text-based languages. Geometric data structures allow the programs to record and exchange information. Finally, Critters programs can be compiled to a low-level language, allowing them to run at nearly native code speeds.
In this thesis, I propose to demonstrate the usefulness of geometric primitives in expressing computations. I will build a system for specifying computations geometrically, and implement a number of sample applications and algorithms using this system. For each sample problem, I will evaluate the usefulness of geometric computation in creating the solution. I will also report on experiences in teaching a variety of other users how to solve simple programming problems using the system. I will show that, for some problems, geometric computation offers significant advantages in expressiveness over existing programming systems. In addition, I will show that a wide range of problems can be solved by geometric computation with expressiveness comparable to that of more traditional systems.
|A Harsh Book of Geometry|
|This is a thick, brown, leather-covered book, stippled with gold numbers. When opened, complex three-dimensional geometrical diagrams rise up out of the pages like models in a pop-up book. The pages flicker with logarithmic numbers and figures. Angles are measured by needle-thin metal pendulums that swing freely, activated by magnets concealed in the thick paper. [Greenaway 91]|
Critters is a new direct-manipulation, example-based programming system which is aimed at animations, simulations, and video games: programming problems which should be susceptible to visual solutions. The use of a visual programming language in these areas is motivated by the frustration of the text-based graphics programmer who must often debug their program by printing out the coordinates of their data and plotting them by hand on graph paper. The "visual solutions for visual problems" approach may also have benefits when teaching programming skills, because visual problems and solutions are more gratifying to many users [Papert 80].
The most important principle in designing Critters is geometric computation. The programmer manipulates distances, vectors, angles, and ratios as concrete geometric objects rather than as numerals and symbols. Sticks and triangles visually represent translation, rotation, and scaling operations, and snapping points together represents assignment. In addition to obviously geometric quantities, many other kinds of data can be usefully expressed geometrically. For example, real numbers can be expressed and manipulated as sticks whose length is the magnitude of the number they represent. The position and direction of the stick aren't necessary to the computation but may make it clearer, just as careful choice of variable names improves the presentation of a textual algorithm.
Geometric computation provides the equivalent of the "expression sublanguage" found in imperative textual programming languages. Control flow (function call and conditionals) are specified with example-based programming: the user specifies the initial state of the computation and then shows how to construct the next state in terms of that state. Unlike many example-based programming systems, Critters is not an end-user programming system: it makes no attempt to hide the complexities of programming, it only offers more convenient representations for manipulating geometric data. The Critters programmer must demonstrate an algorithm to implement the desired behavior, rather than demonstrating a behavior and asking the system to develop an algorithm implementing it.
Critters programs can also operate on geometric data structures similar to the linkages used to express geometric computations. These allow the programmer to express abstract structures like collections and binary trees as well as more concrete objects like paths.
Another difference from most example-based programming systems is that Critters is designed to work with a compiler. The user interface includes heuristics and bidirectional constraints, but once specified a Critters program is unambiguous and does very little search. Even at the user interface level, Critters does less sophisticated inferencing than most example-based programming systems: the design goal for the inference system is that it be as simple as possible, comparable to an operator precedence table or a type checker in a textual programming language. Critters will include a compiler to a low-level language, most likely C or Java bytecodes.
The work proposed here begins with the implementation of a system based on geometric computation and data structures. The implementation will be used to construct a number of example applications and algorithms, and to evaluate informally how easily users can learn and make use of geometric primitives. The dissertation will include a discussion of the strengths and weaknesses of geometric computation found when solving the sample problems, and a report on the experience of teaching others to use the system.
The next section describes how geometric computation is used in Critters. This section is followed by discussions of control flow including recursion and conditionals and a description of geometric data structures. Following that, Critters is situated relative to existing work in the field and the problems that it is expected to solve. The proposal concludes with the schedule for completion.
|calculating a reflected ray given an incoming ray and the surface normal|
One way for a computer to detect the important features in a diagram is by inference: a program may observe that two quantities in the diagram are equal and infer that they should always be equal [Maulsby and Witten 93]. While this approach is easier for inexperienced users performing simple tasks, more complicated tasks may require the user to give multiple examples of the same behavior, or to tailor their examples to the strengths of the inference algorithm.
The approach to geometric computation taken in Critters is to rely as little as possible on inferences (some of the exceptions will be described below). The user must explicitly demonstrate equality by snapping points together or cloning shapes. Because all actions are explicit, only one example is necessary to specify a particular behavior.
The idea of using geometry for computation was suggested by the program Geometer [Davis 95]; a very similar but better known and documented system is Geometer's Sketchpad [Jackiw and Finzer 93]. The constructions made with these programs are limited to those possible with compass and straightedge, but they are surprisingly flexible; Geometer can be used to generate a cube that rotates as the user moves a point, and Geometer's Sketchpad includes a demo which calculates shadows from a light source and shape.
Since the goal of Critters is to maximize the flexibility of its geometric operations rather than demonstrating the consequences of a small set of axioms, its system is somewhat different. The main geometric primitives are the stick (a line segment) and the triangle which are useful for operating on distances, angles, and ratios. Other primitives will be necessary to represent regions and random variables: some of these are discussed below. It is important to realize that sticks are not the same as vectors: a stick has a position as well as a difference of positions.
x1 = x0 + l cos aGiven these constraints, a stick in critters may be performing one of three computations: computing the head from the base, length, and slope, computing the base from the head, length, and slope, or computing the length and slope from the base and head. A stick behaves differently depending on which of its control points are being moved:
y1 = y0 + l sin a
|dragging the base of a stick||dragging the head of a stick|
Notice that when we drag the base it recalculates the head from the base and the old slope and length, but when we drag the head it recalculates the slope and length. This is the simple inference described above: if a stick is underconstrained it will compute its head from its other variables by default. The biases are set up in this order because some values are easier to control than others: it's easy to override the position of the head by snapping it to another point, but cumbersome to override the length by copying from another stick.
From the implementation perspective, "sticks" only exist in the user interface; a stick may represent any of three different computations depending on context. The choice is made before the program can run (by default if necessary). It wouldn't change the semantics of Critters to make the programmer choose the computation by hand, but the user interface would be much more cluttered.
The next example shows how to compute the sum of two vectors. Vectors are usually represented with sticks. Begin with three sticks: a, b, and c (they may already exist, or new ones can be created with default positions and shapes):
|a, b, and c represent vectors|
|base(b) = head(a)||base(c) = base(a)||head(c) = head(b)
c = a + b
We see that after this construction has been done both a and b are in their default states, computing their head. the computed vector c, on the other hand, has both its base and head bound to other points and is forced to compute its length and slope as a result. This change occurred as soon as we began dragging the head of c, and when it was attached to the head of b it was fixed in that state.
Sticks give a simple way to express addition and subtraction of vectors (and scalars as a special case). We would also like to express addition and subtraction of angles, rotation of a vector by an angle, and scaling of a vector or scalar. All these operations can be expressed using triangles. Triangles have a more complicated list of biases than sticks: some of the more interesting cases are shown below:
|translation||rotation and scaling||deformation|
|we want to transform vector v using triangle T||connect the base of T to the base of v||fit the triangle to the vector. v' is the transformed vector|
|a linear cam to compute a square root||a rotary cam to convert angles to distances|
Each active object in the system is a critter, an object with its own state and thread of control. At minimum, the critter's state includes its definition and position: if the critter's definition requires more state than just the position, we can add it. To create our ball, we will start with a fresh critter definition. Specifying the critter is not unlike declaring a function - there is a unique name for the critter type and one argument for each part of the critter's state.
|a blank critter definition|
|the state includes a stick object||attaching the stick|
p' = p + vWe begin by specifying a new "result" picture for this definition. The result picture includes a copy of the definition picture (in another color), which gives us the initial state necessary to build the result by example. In this case, the result is another invocation of the ball critter, but with a different state. Having begun the definition of the ball, we can invoke it recursively even though we haven't finished defining it yet. The invocation starts out with the same structure as the definition, and also copies default values from it. To specify the position of the new critter, we attach its position to the head of the stick from the previous state:
v' = v
|the result is a new ball||setting the position of the new ball|
|a bug: the new velocity isn't the same as the old|
|the clone of the old velocity copies its slope and length|
|attach the clone||set the new velocity from the clone|
|the new velocity is copied from the old|
While explicitly copying all the data is simpler to think about in programming language terms, it's easy to see that this will get cumbersome for critters with more state. Extending the cloning operation to allow cloning a complete critter allows all the state to be inherited with a single operation, greatly simplifying the construction of the example above.
An event triggers a computation. The result of an event may also depend on conditions. As with other objects, conditions are represented by geometric objects with control points, but with the additional attribute that not all values of the control points will satisfy the condition. An event will not trigger a particular result unless all conditions in the result are satisfied. For example, an event handler may include a point-in-circle condition. The visual representation of this condition includes a center, radius, and test point, and the condition is only satisfied when the test point is inside the circle with the given center and radius.
Some geometric conditions provide additional data for the event handler to use: "do these two sticks intersect? if so, where?" There are also pattern-matching conditions: "is the critter at the end of this link of a particular kind? if so, what is its state?"
Conditionals can introduce more ambiguity: if several conditions match at once, which of them is chosen? In keeping with the goal of minimal ambiguity, the order in which conditions are checked will be exposed to and controllable by the programmer.
Critters programs will be more efficient than most example-based programs because they do very little search at runtime, relying on connections demonstrated by the user rather than searching for nearby geometry. Geometric search can be accomplished by responding to collision events, if necessary.
In Pictorial Janus, layout is primarily accidental: pieces of a program
frequently obscure each other during execution. Solving this would be
a difficult problem in graph layout. Critters turns this problem into
a feature: the purpose of a Critters program is to allow users to
specify screen layouts.
Geometer and Geometer's Sketchpad
Geometer [Davis 95] and
Geometer's Sketchpad [Jackiw and Finzer 93]
are systems for exploring geometric constructions. They are intended
as ways of exploring the possibilities of compass-and-straightedge
constructions rather than as tools for building useful geometric
expressions, so their primitives are more limiting than those of
Neither Geometer nor GSP contains a programming language: although GSP
has "scripts" which may invoke a rule recursively several times, it is
not possible to construct a loop which iterates a variable number of
ToonTalk [Kahn 96] is a followup to
Pictorial Janus that is designed for children learning to program.
ToonTalk programs can explicitly move sprites around, but the
computation is described numerically: geometry is not a fundamental
part of the programming model.
KidSim and Cocoa
[Cypher and Smith 95] is the system most similar to
Critters in spirit. It uses programming by demonstration to specify
rewrite rules, which control the behavior of "characters" in a
simulated world. The KidSim world is cell-based rather than
geometry-based. This makes it simpler to represent spatial
relationships (since there are only four possible immediate neighbors
for each cell) but makes it impossible to describe smooth motion.
Math in KidSim is done with a simulated calculator, a less concrete
representation of numbers than is used in Critters. KidSim includes a
limited subtyping hierarchy which reduces the number of rules that
need to be described by the user. Something similar would be very
useful in Critters.
Although both Gamut and Critters are motivated by video games, they concentrate on different aspects of the problem. The bulk of the Gamut work is in cleverly deducing intended relationships, while in Critters the strategy is to assume a higher level of programming knowledge: it provides a useful toolbox of relationships and requires the user/programmer to demonstrate constructions and dependencies explicitly. As a result, Gamut requires less programming knowledge from the user if the relationship being demonstrated is one that it can infer, but it lacks the fine control over algorithms that Critters provides (and requires). McDaniel states that "Gamut's most serious flaw is a lack of feedback": it is not obvious what behavior it will infer given a particular set of examples. The simpler biases used by Critters make it less susceptible to this problem. Gamut uses "temporal ghosts" to allow a rule to depend on a previous state: this is very similar to how results are constructed from previous states in Critters. Some of the metaphors developed for Gamut (e.g. using decks of cards to represent discrete choices in programs) would probably combine well with the geometric computation techniques introduced here.
Critters is more general but lower level than Klik & Play: it will be interesting to see how difficult it is to implement the high-level abstractions presented by Klik & Play in terms of the geometric operations offered by Critters. Having multiple levels of the game requires some way to save and restore the current state of a Critters program from within another Critters program, which is not yet designed. One area where Klik & Play will certainly shine is that it has customized editors for these high-level objects: although they may be implementable in Critters they will probably not be as obvious visually. Critters is much more powerful for simulation purposes because it is much more flexible: a ball that loses energy when it bounces would be impossible in Klik & Play.
The strengths of the two systems are complementary and one possible future for Critters would be as an extension language for a system similar to Klik & Play.
One major limitation is that Critters has no way of using text. Although it can respond to single keypresses and mouse clicks, it has no support for drawing characters or manipulating strings. Interfaces to host operating system services such as the file system or process control are also unavailable.
Another limitation is that Critters can manipulate limited kinds of data structures. Two-dimensional points and angles are the most obvious data type in use; implementing 3D points in terms of the 2D primitives provided would be very cumbersome. Most integer and boolean arithmetic expressions can be expressed in terms of geometry using a number line. Some real-number operations may present problems. Although exponentiation could be provided with a linear cam, the dynamic range of the result might be difficult to cope with. Critters provides no way of using a logarithmic scale in a view to keep large and small numbers onscreen at the same time.
Critters has compound data structures. The system places no limit on the amount of state that a critter can have (though the visual complexity could be high). Programs can also manipulate trees using critters with links. Collections can be built using trees, but there is no built-in collection or array type. It is difficult to imagine how something like a hash table would be built in Critters. Finally, critters has no equivalent to higher-order functions.
Finally we come to issues of program structure. Critters provides no support for inheritance, modularity, or abstract data types. This will limit the size of programs. All loops are done with tail recursion, which provides very flexible control flow. Parallelism is implicit in the system, but facilities for synchronization are poorly defined at this time. Another limitation, hard to characterize, is the difficulty of making global changes. For example, there isn't a graceful way to implement the saving and restoring of a whole world as is done in the two-player version of an Asteroids game.
Critters also demonstrates how data structures and recursion may be integrated with geometric computation to increase its usefulness. This is a unique combination of capabilities: past geometric programming systems have not had sophisticated control flow constructs, and the visual languages with powerful control flow have not had a convenient way to manipulate geometric quantities.
The most difficult aspect of Asteroids to reproduce in this system is the maintenance of separate worlds in the two-player version of the game: for now the system is concerned with computation in a single world. Implementing multiple worlds is beyond the scope of the thesis, but a discussion of how it might be accomplished will be included in the dissertation.
The second example program tests the speed of compiled Critters programs. The example will be a particle system which simulates fluid flow as a large number of identically behaving particles. The goal is to simulate several thousand particles.
The third example is an implementation of the Bresenham line-drawing algorithm. This example demonstrates that a Critters program may be more expressive than its textual counterpart: in particular the error variable in Bresenham's algorithm is much more intuitive when it obviously represents the distance from the current pixel to the ideal line being drawn.
Organized user testing of Critters is outside the scope of this work. Informally, I will report on the experiences of a variety of users in using the system to solve simple problems. These problems will be simpler than the examples given above: possibilities include drawing circles, creating a bouncing ball, and a predator-prey simulation.