thesis proposal

Thesis Proposal

Critters:

procedural animation by direct manipulation

Nick Thompson

September 22, 1997

Abstract
Although 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]

Introduction

Example-based programming systems offer several advantages which are unavailable to textual languages. The first of these is concreteness: rather than manipulating symbolic representations of a program, the programmer manipulates quantities directly. Another advantage is that an example-based program specification necessarily includes valid test data.

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.

Geometric Computation

Diagrams are frequently useful in explaining computations. The following diagram (redrawn from [Foley, van Dam, Feiner and Hughes 95]) shows how a ray of light bounces off an idealized reflective surface:

calculating a reflected ray given an incoming ray and the surface normal

This diagram is incomplete without a textual description of the calculations involved, but it illustrates some important spatial relationships that make the text much easier to understand. Some attempt has been made to disambiguate the drawing by adding symbols that tell us that the two angles are identical, as are the two copies of S. Is it possible to describe the reflection computation without resorting to text at all?

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.

stick	triangle

Attachment is a key concept in critters. Sticks and triangles each have control points that set their position and shape. When an object is first created these points are "free": they will stay in the same place. When the user picks up an object by one of its control points, that point is temporarily attached to the mouse, and the point will follow the cursor until it is released. The primitives have more controls than degrees of freedom: controls are related through constraints which maintain the shape of the object. We use cartesian coordinates to explain (and implement) the control points, though coordinates are invisible to the Critters user. Internally, the data associated with a stick are x0 and y0 (the base point), x1 and y1 (the head), l (length), and a (slope). The constraints associated with these data are:

x1 = x0 + l cos a
y1 = y0 + l sin a

Given 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:


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

In order to add a and b, attach the base of b to the head of a. Then attach the base of c to the base of a and the head of c to the head of b:

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

Notice that, by dragging the appropriate part of the triangle, we can translate it, rotate it about the apex, or scale it. If we scale and rotate a triangle so that one of its legs matches a stick, the other leg of the triangle will be the result of rotating that stick by the apex angle and scaling it by the ratio of the triangle's leg lengths to each other. If we want to scale a stick without rotating it, we can use a degenerate triangle that looks like a stick with an extra control point.

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

Cams

Sticks and triangles can express many useful computations geometrically. One function that is difficult to represent is linear conversions between angles and lengths. Converting an angle to a length using triangles requires the use of a Fourier series where right triangles are used to compute the sine and cosine of the angle involved. Critters will include a cam that allows this computation to be represented easily. A cam expresses an arbitrary function of a single variable. A linear cam looks like the graph of a function with two control points. The first point slides along the independent axis of the graph and causes the second point to follow the graph, giving the value of the function for the given first point. Rotary cams are similar, but are useful when the independent variable is an angle rather than a distance.

a linear cam to compute a square root	a rotary cam to convert angles to distances

Critters will allow the creation of new cams within the system: the programmer can connect a set of triangles and choose input and output points in order to specify a new cam. However, user specified cams can not use recursion to compute their outputs.

Random numbers

A random point generator appears as a circle with a point inside. The point will have a random position inside the circle each time a critter makes use of it.

Control Flow

Recursion

Vector arithmetic is all well and good, but it only allows us to build diagrams which move when prodded by the user. To create animated drawings we need a way of expressing control flow. Flow of control in Critters is similar to that in a number of parallel languages: it is most directly inspired by Pictorial Janus [Kahn and Saraswat 90] but it is also similar to the use of tail recursion in functional languages. Our first example of a recursive program is a ball traveling in a straight line.

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

In addition to a position, the ball needs a velocity. Velocity is a vector quantity so, as before, we will use a stick to represent it. The length and orientation of the stick represent how far and in what direction the ball moves at each step of the program. We don't care much about the position of the stick, so we'll attach its base to the critter's position, which isn't necessary but will come in handy when we are defining the new position of the critter after it takes a step.

the state includes a stick object	attaching the stick

Having described the default initial state of the critter, we need to demonstrate how to construct the next state in terms of the current state. We can describe straight-line motion as a difference equation:

p' = p + v
v' = v

We 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:

the result is a new ball	setting the position of the new ball

We now have a working critter. If we create an invocation of the ball critter and start the system running, the ball will move across the screen in a series of steps, each the length of the velocity stick.

If we stop the system and move the critter, it will start moving again from the new position when we restart. However, if we change the velocity, it will take one step with the new velocity and then continue with the default velocity from the definition. This happens because we didn't implement the second part of the difference equation, v' = v. Going back to the to the definition and changing the previous velocity makes it obvious where the rule is lacking.

a bug: the new velocity isn't the same as the old

It's always a good idea to wiggle the test data after describing a result and see if the result changes appropriately. To fix this bug, we have to introduce a new operation. It's easy to copy positions by attaching one point to another, but length is a more abstract quantity. The new operation is cloning. Cloning an object creates a new object of the same type which inherits values from the original. This inheritance can be overridden by user actions, so we can create a cloned stick that inherits its slope and length but has its base explicitly computed from other values.

the clone of the old velocity copies its slope and length

Now, we can attach the base of the clone to the center of the result critter to construct a new velocity. Then we can snap the velocity in the new ball's state to the constructed vector:

attach the clone	set the new velocity from the clone

Now, if we wiggle the old velocity, the new velocity changes appropriately. Note that there is no visual indication that one stick is a clone of the other: the user must find this out by manipulating the drawing.

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.

Events and Conditionals

We now have expressions and recursion in our language. We would also like to be able to handle events, both externally generated (keyboard, mouse, or MIDI input) and internally generated (collisions between critters, clock ticks, or messages passed from critter to critter). The proposed mechanism for handling these events is to specify different "after" pictures for each event that might be handled. Some events have associated data, like the mouse position or the object collided with. If the critter responds to these events, example values for the additional data are presented in the result picture for use in constructing the critter's new state.

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.

Data Structures

Links

The geometric computation primitives presented so far allow critters to manipulate numerical quantities. In order to allow the expression of data structures such as binary trees, a link or reference type is necessary. The endpoint of a link must be a critter of some kind, and the critter which contains the link may use pattern-matching conditionals to act based on the kind of critter it points to.

Trees

Since the only compound data structure available is the critter, we represent a binary tree node as a critter with two links and no behavior. Terminal nodes are represented by critters with no state beyond their positions. A tree-walking critter contains a link to the current node. It uses a pattern-matching condition to choose the appropriate behavior based on whether the current node is interior or terminal, and it can keep a stack by maintaining a linked list of binary nodes behind it.

Compilation

Because the operations performed in a Critters program are unambiguous, expressions can be compiled to very efficient code. Linkages will compile to either assignment expressions (which can be trivially optimized away) or to sequences of a few floating-point operations. The most complicated operation that any single primitive can perform is arctangent (to go between angles and slopes).

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.

Related Work

Pictorial Janus

Pictorial Janus [Kahn and Saraswat 90] is a visual programming language. The Critters notion of pattern-matching and recursion is inspired by Pictorial Janus. Pictorial Janus programs are visually apparent: everything necessary to run the program is explicit in the visual representation. Critters is a programming-by-example system which remembers the actions used to generate a diagram rather than the diagram itself. Many but not all of the actions have visual representations - in order to be sure what a program does, the user must be able to see how it responds to input data other than the example data used to construct it. This is easy to do interactively by dragging parts of the drawing and seeing how the result changes.

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 Critters. 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 times.

ToonTalk

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

KidSim (now "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.

Gamut

Gamut is a system being developed by Richard McDaniel [McDaniel and Myers 97] for programming board games and video games by demonstration. Gamut infers the program from multiple ambiguous examples: as such it contains much more sophisticated inference rules than 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.

Klik & Play

Klik & Play is a commercial video game construction set [EuroPress 94]. It provides high-level but inflexible tools to allow users to construct video games: there are built-in implementations of "scores" and "levels," and motion is limited to user-constructed paths or a few varieties of interactive control. Events can trigger several actions including replacement of an object, creating a sound, or bouncing. There is also a mode to run the game but prompt the user whenever an unknown event is encountered, which is similar to Tinker [Lieberman 93].

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.

Chimera

Geometric pattern-matching and replacement is also important in Chimera [Kurlander 93], a system for automating repetitive operations in drawing editors. Chimera uses before-and-after pictures to describe parametrized graphical search and replace operations. This is similar in some ways to a single step of a Critters program, but Chimera lacks recursion and parallelism. Chimera searches the entire drawing for matches to the search, while Critters narrows down the search by only doing replacements where there's an active critter. Additionally, the relationship between before and after pictures in Chimera is more ambiguous than in Critters: it requires relatively complex heuristics to determine which aspects of the before and after pictures are significant. The recursive and parallel aspects of Critters could probably be incorporated into Chimera with interesting results.

Pavlov

Pavlov [Wolber 96] is a demonstrational interface builder which makes use of many of the same ideas as Critters: it is oriented toward interactivity and geometric computation, and programmed using before ("stimulus") and after ("response") demonstrations. However, it makes extensive use of text, both for entry of expressions and for display of learned behaviors. Pavlov has built-in knowledge of directions and actions (such as "MoveForward"), making some behaviors easier to construct: however, this results in a physically inaccurate model of turning, where an object will usually maintain a constant speed as it changes direction. Like Critters, Pavlov uses a single demonstration for each learned behavior: however, it uses a more complicated explanation-based learning algorithm to decide which parts of the demonstration are important to the behavior. Pavlov is closer to a keyframe animation system than Critters, which is purely procedural. The Pavlov programmer uses a clock to specify the time at which a particular response should occur, and keeps track of times and actions in a score. Something similar to Pavlov's clock might work well in the Critters system.

3D-Visulan

3D-Visulan [Yamamoto 96] is a rule-based programming system whose domain is three-dimensional bitmaps. A rule specifies how one bitmap should be transformed into another. Rules can also match on the result of a random-number generator or on the state of the mouse buttons. One interesting aspect of 3D-Visulan is that rules and data live in the same space. This introduces the possibility of manipulating programs as data, though this is not actually done in the system. Although an example of a space invaders game in 3D-Visulan is given, the system has difficulty abstracting over directions: most of the rules for invader movement are duplicated depending on whether they are moving left or right. Because the system is grid-based, directions other than the 6 axis-aligned ones would be very difficult to represent. 3D-Visulan is also very slow, perhaps because pattern-matching on 3D bitmaps is expensive.

Scope

The techniques demonstrated in Critters are most useful for animation and mouse interaction, though they are not limited to those areas. This section discusses some of the strengths and limitations of Critters. Many of the limitations could be avoided by adding new primitives, but in most cases the additions would not take advantage of the strengths of geometric computation.

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.

Contributions

The primary contribution of this work is the introduction of flexible geometric computation. Triangles, sticks, and cams are more powerful than the primitives used in other systems such as Geometer's Sketchpad, and more precise than the computations inferred by systems such as Gamut and Pavlov.

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.

Evaluation

Critters will be evaluated using several example programs. The most important of these will be a partial implementation of the classic arcade game Asteroids. This will provide experience with several important aspects of the system. At minimum, the game play aspect will be implemented: navigation and several types of collisions. The features that will be tested include interactivity, handling collisions with different types of objects, and random number generation. The ability of critters to manipulate integers will be exercised by keeping track of the score and the number of lives remaining.

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.

Conclusions

Critters is a new design for direct-manipulation programming languages that plays to the strengths of direct-manipulation interfaces. The process of turning the design into a workable environment for constructing small-scale programs will require novel representations of many programming techniques. Additionally, Critters applies programming by example techniques in unusual areas; the programs produced are dynamic and interactive: they evolve in time and respond to user input.

Bibliography

[Cypher 93]: Cypher, Allen. Watch What I Do: Programming by Demonstration. MIT Press, Cambridge, Massachusetts, 1993.
[Cypher and Smith 95]: Cypher, Allen and Smith, David C. "KidSim: End User Programming of Simulations". In Proceedings of CHI, 1995 (Denver, May 7 - 11). ACM, New York, 1995, pp. 27-34.
[Davis 95]: Davis, Tom. personal communication.
[EuroPress 94]: EuroPress Software Ltd. Klik & Play User's Manual. EuroPress Software Ltd, Macclesfield, UK, 1994.
Klik & Play home pages and demos are at http://www.europress.co.uk/knp/ and http://www.maxis.com/shopping/product.cgi?ProductName=klik_n_play.
[Foley, van Dam, Feiner and Hughes 95]: Foley, James, van Dam, Andries, Feiner, Steven, and Hughes, John. Computer Graphics: Principles and Practice. Addison-Wesley, Reading, MA, 1995.
[Greenaway 91]: Peter Greenaway. Prospero's Books: A Film of Shakespeare's The Tempest. 1991.
[Jackiw and Finzer 93]: Jackiw, R. Nicholas and Finzer, William F. "The Geometer's Sketchpad: Programming by Geometry". In [Cypher 93], pp. 292-307.
Demo versions of GSP are available at http://www.keypress.com/product_info/sketchpad.html.
[Kahn and Saraswat 90]: Kahn, Ken M. and Saraswat, Vijay A. "Complete Visualizations of Concurrent Programs and their Executions". 1990 IEEE Workshop on Visual Languages, IEEE Computer Society Press, Skokie/IL, Oct. 4-6, 1990. pp. 7--14.
[Kahn 96]: Kahn, Ken. "ToonTalk - An Animated Programming Environment for Children". Journal of Visual Languages and Computing (1996), 7, 197-217.
The ToonTalk home page is at http://www.toontalk.com.
[Kurlander 93]: Kurlander, David. "Chimera: Example-Based Graphical Editing". In [Cypher 93], pp. 271-290.
[Lieberman 93]: Lieberman, Henry. "Tinker: A Programming by Demonstration System for Beginning Programmers". In [Cypher 93], pp. 49-64.
[Maulsby and Witten 93]: Maulsby, David and Witten, Ian H. "Metamouse: An Instructible Agent for Programming by Demonstration". In [Cypher 93], pp. 154-181.
[McCloud 93]: McCloud, Scott. Understanding Comics. Kitchen Sink Press, Northampton MA, 1993.
[McDaniel and Myers 97]: McDaniel, Richard G. and Myers, Brad A. "Building Applications Using Only Demonstration." To appear in Proceedings of the 1998 International Conference on Intelligent User Interfaces, January 6-9, 1998.
[Papert 80]: Papert, Seymour. Mindstorms: Children, Computers, and Powerful Ideas. Basic Books, 1980.
[Wolber 96]: Wolber, David. "Pavlov: Programming by Stimulus-Response Demonstration". In Proceedings of CHI, 1996 (Vancouver, April 13 - 18). ACM, New York, 1996, pp. 252-259.
[Yamamoto 96]: Yamamoto, Kakuya. "3D-Visulan: A 3D Programming Language for 3D Applications". Pacific Workshop on Distributed Multimedia Systems, 1996.