Thinglab is a simulation laboratory. It provides an environment for constructing dynamic models of experiments in geometry and physics, such as simulations of constrained geometric objects, simple electrical circuits, mechanical linkages and bridges under load. Using the techniques developed for these domains, the system has also been used to model other sorts of objects, such as graphical calculator, and documents with constraints on their layout and contents.

One of the principal goals of this research has been to design and implement a language that helps the user describe complex simulations easily. Starting with a combination of ideas from Sketchpad [Sutherland 1963] and Smalltalk [Ingalls 1978], a number of features have been built up. Part-whole and inheritance hierarchies are used to describe the structure of a simulation. Constraints are employed as a way to describing the relations among the parts of a simulation. Constraints are a particularly important tool for dealing with complexity, because they allow the user to specify all the relations independently of one another, leaving it up to the system to plan exactly how the constraints are to be satisfied.

ThingLab is implemented in the Smalltalk-76 programming language, and runs on the Alto, a personal computer developed at Xerox Palo Alto Research Center. All the simulations described herein are working examples.

The kernel ThingLab system consists of a Smalltalk extension, written by the present author, that is used in all ThingLab simulations. Embedded in this program is knowledge about such things as inheritance hierarchies, part-whole relations, and constraint satisfaction techniques. The kernel system doesn’t have any knowledge about specific domains in which ThingLab can be used, such as geometry or electrical circuits. Rather, it provides tools that make it easy to construct objects that contain such knowledge.

Another goal in constructing the system, besides the exploration of language design as described above, was to investigate computer-based tools for use in education. For example, a ThingLabstyle system might prove valuable as part of a geometry curriculum, or as an adjunct to a physics laboratory. With this in mind, it is anticipated that there would be two sorts of users of the system. The first sort of user would employ ThingLab to construct a set of building blocks for a given domain. For example, for user in simulating electrical circuits, such a user would construct definitions of basic parts such as resistors, batteries, wires and meters. The second sort of user could then employ these building blocks to construct and explore particular simulations. The knowledge and skills required by these two kinds of users would be different. The first kind of user would need to now about message passing the constraint specification domain (e.g.Ohm’s Law). The second kind of user, on the other hand, could deal with the system using only simple interactive graphics techniques, such as selecting items in a menu or moving pictures around on the screen. Thus, this sort of user wouldn’t need to be familiar with either the details of ThingLab, or with the domain-specific theory behind the simulation (although one of the objectives of a curriculum might be for such a user to acquire this domain-specific knowledge).

Interesting systems are usually complex. A simulation that abstracts any significant portion of such a system will probably be complex as well, making it important for the simulation system to provide tools for dealing with this. This is particularly true if the system is intended for use by people who aren’t computer sophisticates as is ThingLab. This section is a discussion of the tools available in ThingLab viewed in this light.

ThingLab, like Smalltalk, is organized around the idea of objects that communicate by sending and receiving Messages. This object-oriented factorization of knowledge provides one of the basic organizational tools. For example, in representing a geometric construction, the objects used in the representation would be things such as points, lines, circles, and triangles. This provides a natural way of bundling together the information and procedures relevant to each object. Each objects holds its own state, and is also able to send and receive messages to obtain results.

A powerful method for dealing with complexity is to describe a system hierarchically. ThingLab provides two kinds of hierarchies: an inheritance hierarchy, and a part-whole hierarchy.

The inheritance hierarchy uses Smalltalk’s class-instance structure. Object descriptions and computational methods are organized into classes. Every object is an instance of some class. In broad terms, a class represents a generic concept, while an instance represents an individual. A class holds the similarities among a group of objects; instances hold the differences. More specifically, a class has a description of the internal storage required for each of its instances; the constraints on its instances; and a dictionary of messages that its instances understand, along with methods for computing the appropriate responses. An instance holds the particular values that distinguish it from other instances of its class.

For example, one of the classes defined in ThingLab is class Line. This class describes lines in general – it is a description of all line instances, both existing and potential. It specifies that every line instance should be represented as a pair of endpoints. Lines themselves have no constraints. Finally, the class Line contains a dictionary of messages that its instances understand, along with methods for receiving those messages. Some examples of messages that lines understand are:

Point1 – return your first endpoint

Printon: stream – print a description of yourself on an output stream

Showpicture: window – show your picture in a window

A line instance has a pointer to its class, and two fields that hold pointers to its endpoints, which are instances of class Point.

A new class may be defined as a subclass of one or more existing classes. The subclass inherits the storage specifications, constraints, and message protocol of its superclasses. It may specify additional storage requirements, constraints, and message behavior of its own; it may delete or replace inherited constraints; and it may override inherited responses to messages. For example, one of the subclasses of Line in HorizontalLine. HorizontalLine inherits all the traits of Line, and adds a constraint that the y values of its endpoints be equal. The most abstract class in the system is class Object; all other classes in the system are descended from it.

The other kind of hierarchy in ThingLab is the part-whole hierarchy. In ThingLab, every object is composed of named parts, each of which is itself an object. The parts are thus composed of subparts, and so on. For example, a triangle is composed of three parts: its sides. Each side in turn has two endpoints; the endpoints have x and y coordinates. Note the relation between the inheritance and part-whole hierarchies: the triangle is an instance of class Triangle; its parts are instances of class Line; their endpoints are instances of class point; and finally the coordinates are instances of class Integer. Each class contains a set of part descriptions that list the common properties of the corresponding parts of each of its instances. Thus the class Triangle specifies that each of its instances should have tree parts named side1, side2, and side3; and that each of these parts should be instances of class Line.

It is rare for the decomposition of an object into parts to be completely linear, i.e. such that there are no interactions among the parts. For example, each side of the triangle shares its endpoints with the other sides. If the triangle were constrained to have a horizontal base, there would be other interactions among the endpoints (the y values of the base would have to be equal). ThingLab provides ways of representing and reasoning about these interactions, as will be described in the next section.

The basic tool for representing relations among parts is the constraint. A constraint specifies a relation that must always be satisfied. Here are some examples of constraints that have been defined in ThingLab by its various users:

a constraint that a line be horizontal;

a constraint that one triangle be twice as big as another;

a constraint that the digits displayed in an editable paragraph correspond to the height of a bar in a bar chart;

a constraint that a resistor obey Ohm’s law

a constraint determining the gray level of an area on the computer’s display; and

a constraint that a rectangle on the display be precisely big enough to hold a given paragraph.

A key fact about constraints is that the relation to be satisfied is separated from the process by which it is satisfied. All the constraints on a simulation can be specified independently of one another. It is up to the system to decide whether or not they can all be satisfied simultaneously , and if so, how to satisfy them. Constraints are thus a powerful tool for dealing wit complexity. Although the interactions among the parts of the system may be numerous, the users can specify each relation without worrying about the others.

Constraints reflect a way that humans might think about a large class of situations. In mathematics, the hypotheses of a theorem, along with the fundamental axioms, may be viewed as constraints. The laws of physics may be thought of as constraints that physical objects must obey. Other branches of the physical and social sciences have built up some laws of this sort, e.g. valences in chemistry. In design constraints represent the requirements that the thing being designed must satisfy.

In a simulation environment, constraints serve not only as descriptions of the simulated object, but also as commands to the system telling it that certain conditions must be satisfied. This makes the model of a system a dynamic, reactive one – the user can prod it and observe its responses.

The ThingLab user interface incorporates a number of tools for dealing with complexity. Multiple viewpoints are supported: a typical object can be depicted in several ways, for example, as a picture, as a structural description or as a table af values. The object itself defines the views that it can provide. Some quite general graphical editing tools are provided, and purely graphical objects, such as a triangle, can be constructed using graphical techniques alone. When the user edits an object, say by selecting a point and moving it with the cursor, the user interface automatically asks the object for a plan for moving the point while keeping all its constraints satisfied.

The representation of constraints reflects their dual nature as both descriptions and commands. Constraints in ThingLab are represented as a rule and a set of methods that can be invoked to satisfy the constraint. The rule is used by the system to construct a procedural test for checking whether or not the constraint is satisfied, and to construct an error expression that indicates how well the constraint is satisfied. The methods describe alternate ways of satisfying the constraint; if any one of the methods is invoked, the constraint will be satisfied.

An important special case of a constraint is a merge. When several parts are merged, they are constrained to be identical. For efficiency, they are usually replaced by a single part rather than being kept as several separate objects. The owner of the parts keeps a symbolic representation of the merge for use in constraint satisfaction, as well as for reconstruction of the original parts if the merge is deleted. One use of merging is to represent connectivity. For example, to connect two sides of the triangle, an endpoint from one side is merged with an endpoint of the other. Another use of merging is to apply pre-defined constraints. Thus, to constrain the base of the triangle to be horizontal, one can simply merge an instance of HorizontalLine with the side to be constrained.

It is up to the user to specify the constraints on an object; but it is up to the system to satisfy them. Satisfying constraints is not always trivial. A basic problem is that constraints are typically multi-directional. For example, the horizontal line constraint is allowed to change either endpoint of the line. Thus, one of the tasks of the system is to choose among several possible ways of locally satisfying each constraint. One constraint may interfere with another; in general the collection of all the constraints on an object may be incomplete, circular, or contradictory. Again it is up to the system to sort this out.

The approach taken in ThingLab is first to analyze the constraints on an object and plan how to satisfy them, and then to make the actual changes to satisfy the constraints. In ThingLab, the particular values that an object holds usually change much more rapidly than its structure. For example, if on the display the user moves some part of a constrained geometric object with the cursor, the values held by this object will change every time its picture is refreshed. Each time some value is changed, other values may need to be changed as well to keep the constraints satisfied. However, the object’s structure will change only when the user adds or deletes a part or constraint. The design of the ThingLab constraint satisfaction mechanism is optimized for this environment. A constraint satisfaction plan may depend on the particular structure of an object, but should work for any values that the object might hold. (If not, appropriate tests must be included as part of the plan.) Once a plan for satisfying some constraints has been constructed, Smalltalk code is compiled to carry out this plan. Thus each time the part of the constrained geometric object is moved , it is this pre-compiled method that is invoked, rather than a general interpretive mechanism. Also, the plan is remembered in case it is needed again. Planning is done using symbolic references to the constrained parts, so that the same plan may be used by all instances of a class. If the class structure is changed so that the plan becomes obsolete, it will be automatically forgotten.

When an object is asked to make a change to one of its parts or subparts, it gather up all the constraints that might be affected by the change, and plans a method for satisfying them. In planning a constraint satisfaction method, the object will first attempt to find a one-pass ordering for satisfying the constraints. There are two techniques available in ThingLab for doing this: propagation of degrees of freedom, and propagation of known states. In propagating degrees of freedom, the constraint satisfier looks for an object with enough degrees of freedom so that it can be altered to satisfy all its constraints. If such an object is found, that object and all the constraints that apply to it can be removed from further consideration. Once this is done, another object may acquire enough degrees of freedom to satisfy all its constraints. The process continues in this manner until either all constraints have been taken care of, or until no more degrees of freedom can be propagated. In the second technique propagating known states, the constraint satisfier looks for objects whose states are completely known. If such an object is found, the constraint satisfier will look for one-step deductions that allow the states of other objects to be know, and so on recusively.

If there are constraints that cannot be handled by either of these techniques the object will invoke a method for dealing with circularity. Currently, the classical relaxation method is the only such method available. As will be described in Chapter 5, relaxation can be used only with certain numerical constraints, and is also slow. In this method, the object changes each of its numerical values in turn so as to minimize the error expressions of its numerical values in turn so as to minimize the error expressions of its constrains. These changes are determined by approximating the constraints on a given value as a set of linear equations by finding the derivative of the error expressions with respect to the value, and solving this set of equations. Relaxation continues until all the constraints are satisfied (all the errors are less than some cutoff), or until the system decides that it cannot satisfy the constraints (the errors fail to decrease after an iteration).

If the relaxation method is used, the system issues a warning message to the user. The user can either let things stand, or else supply additional information in the form of redundant constraints that eliminate the need for relaxation.

Where are constraints useful? In discussing this question, it is important to differentiate what can be expressed using constraints from what sets of constraints can be satisfied. Many more things can be expressed than can be satisfied, For example, it is easy to state the following constraints:

xⁿ + yⁿ = zⁿ

x, y, z, n integers

x, y, z >0

n > 2.

However, finding values that satisfy these constraints, or proving that no such values exist, requires either a counterexample or a proof of Fermat’s Last Theorem.

What can be expressed using constraints? To express a relation as a constraint, the following information is needed: a rule (from which the system will derive a satisfaction test and an error expression); and one or more methods for satisfying the constraint. For numerical constraints, the methods may be omitted if the user is willing to live with the relaxation method. Any relation that must always hold, and for which this information can be supplied, may be expressed as a constraint. Some relations that cannot be expressed as constraints in a general way using current ThingLab techniques include: any relation involving ordering or time; relations that need hold only under certain conditions; and meta-constraints (constraints on other constraints or on constraint satisfaction strategies).

What sets of constraints can be satisfied? If the constraint dependency graph has no circularities, or if the circularities can all be broken using one-step deductions, then the one-pass constraint satisfaction techniques will always succeed, and will provide correct results. Further, the constraints can be satisfied, or determined to be unsatisfiable, in time proportional to that required to execute the local methods provided by the constraints. If the dependency graph does have circularities that cannot be broken by one-step deductions, the constraints for which relaxation can be used. These constraints must either be linear, or else constraints for which linearization is an adequate approximation. An example of a set of circular constraints for which the relaxation method does not work are those that describe a cryptarithmetic problem, e.g. DONALD + GERALD = ROBERT with D=5. [See Newell & Simon 1972 for a description of this domain.] Relaxation is useless here, since the constraints cannot be approximated by linear equations. To solve such kinds of problems, other constraints satisfaction techniques would be needed, such as heuristic search.

As mentioned previously, the two principal ancestors of ThingLab are Sketchpad an Smalltalk. It is also closely related to work on constraints by Gerald Sussman and his students; other related work includes Simula the Actor languages, KRL, and a number of problem solving systems. Following a discussion of these and other systems, a summary of the novel features of ThingLab is presented.

One of the principal influences on the design of ThingLab has been Sketchpad [Sutherland 1963]. Sketchpad was a general-purpose system for drawing and editing pictures on a computer. The user interacted directly with the display, using a light pen for adding, moving and deleting parts of the drawing. Sketchpad’s influence on the field of computer graphics has been tremendous. However, it contained many other important ideas besides that of interacting with a computer using pictures; and these ideas have been less widely followed up. In reading the following description, remember that this program was written in 1962!

Sketchpad allowed the user to define new kinds of pictures by composing primitive picture types (points, line segments, and circle arcs), and other user-defined pictures. These picture definitions could be used in two ways. First the user could copy the picture definition, and use this copy in composing another picture. No record was maintained of the relation between the copy and the original, and the user was free to modify the copy in any way. Second the picture definition could be used as a master for making arbitrarily many instances. Each instance had the same shape as the master, but could be translated, rotated and scaled. In this case, if the master was edited, each instance would change correspondingly. In the master, certain points could be designated as attachers. The corresponding points in each instance could be used to connect it to points in the rest of the picture.

Constraints were used to specify conditions that the picture had to satisfy. For example, one could constrain a line to be horizontal, or a point to lie on a line. Constraints were uniformly described using error expressions, each of which returned a number indicating how well the constraint was satisfied. The system would adjust the constrained variables to minimize the values of these error expressions. Two methods for satisfying constraints were available: propagation of degrees of freedom ("the one-pas method") and relaxation.

The operation of recursive merging was used to connect part of the drawing, and to apply predefined constraints. For example, to connect two sides of a polygon, an endpoint from one line was merged with an endpoint form the other. To constrain a line to be horizontal, first the constraint definition was copied, and then each endpoint of the copy was merged with the corresponding endpoint of the line in the picture. The resulting topology of the picture was explicitly stored in ring structures. For example, every point had a ring of lines that terminated on it, while every line had pointers to its endpoints. These structures were automatically updated as the user edited the picture.

ThingLab has adopted much of Sketchpad’s flavor of user interaction, and the Sketchpad notions of constraints and of recursive merging have been central to its design.

Thinglab extends Sketchpad in a number of ways. The Sketchpad domain of constrained geometric objects has been expanded to include domains that are not purely graphical. For example, an object like a resistor has a picture, but also contains information such as its resistance and the voltage across it. Thinglab uses Smalltalk’s class-instance structure. This mechanism is more general than the mater-instance relation in Sketchpad, since Smalltalk instances have internal variables that can hold whatever instance state is desired.

Constraints in ThingLab can apply to numeric objects such as text, as well as to numeric values. While Sketchpad constraints were uniformly described using error expressions, in Thinglab local procedures for satisfying the constraint may be included as part of its definition. [ThingLab started out using only error expressions. Later, the use of local procedures was permitted to allow constraints to apply to non-numeric objects, as well as to speed up the program.] In addition to the Sketchpad constraint satisfaction methods, ThingLab provides a method for propagating known states. Constraint satisfaction in ThingLab has been divided into two stages: planning and run-time. During planning, a plan is generated for satisfying the constrains, and is then compiled as a Smalltalk method. At run-time, it is this compiled code that is invoked. Typically, the same plan will be used many times.

Internally, ThingLab objects are stored in a manner somewhat different from that used in Sketchpad. In contrast to Sketchpad’s extensive ring structures, ThingLab uses no back pointers; rather, information about constraints and merges is represented using symbolic paths to the affected parts. These constrains and merges are associated with an entire class, and apply to each instance of that class. The ThingLab scheme has the advantage that objects are stored much more compactly, and less manipulation of pointers is required. On the other hand, it requires that a new class be defined whenever an object with a new kind of topology is to be constructed. It would be useful also to have a class of objects represented in such a way that constraints and merges could be associated with particular instances of that class, while preserving the efficiency of the current scheme for places where it is more appropraite.

The other principal of ThingLab is Smalltalk [Kay 1972a, Kay 1972b, Kay & Goldberg 1977, Kay 1977, Ingalls 1978] ThingLab started out as system simulated in Smalltalk, but has evolved to become an extension of Smalltalk. The important ideas in Smalltalk – objects, classes and instances, and messages – are now all used directly in ThingLab. As these ideas were needed in presenting the overview of ThingLab, they have been described previously. [A reader who is unfamiliar with Smalltalk should be able to understand Chapter 1 and 2; however, the remaining chapters assume familiarity with Ingalls 1978.]

ThingLab adds a number of new features to Smalltalk, including constraints, a facility for defining class by example, and multiple superclasses. Also, a large number of declarative structures have been implemented that describe information previously embedded only in Smalltalk’s computational methods and object references. Most of these declarative structures have been implemented in response to the demands of constraint satisfaction. In satisfying constraints, it is necessary tot reason about the interactions among the parts of an object. To allow this, the static structure of an object is described using parts and part descriptions. Any sharing of parts must be explicitly represented using a merge. The dynamic relations among the parts are represented with contraints.

Smalltalk is an evolving system. Discussion regarding the next major version of Smalltalk is currently under way in the Learning Research Group, and it is likely that many of the ideas developed in ThingLab will find their way into the Smalltalk language itself. Some thoughts on this topic may be found in Chapter 6.

ThingLab is related to recent work on a constraint language at MIT by Guy Steele and Gerald Sussman [Steele & Sussman 1978], and also to other work by Sussman and his students on the problem of applying artificial intelligence techniques to computer-aided design [Sussman & Stallman 1975, Stallman & Sussman 1977, Doyle 1977, de Kleer & Sussman 1978].

The Thinglab representation of an object in terms of parts and subpart, with explicit representation of shared parts, is nearly isomorphic to the representation independently developed by Steele and Sussman, Their system has a built-in set of primitive constraints, such as adders and multipliers. Using these primitive constraints, compound constraints can be built up. This is much like the method used in the StringLab calculator example described in Chapter 2. These similarities are interesting, given the rather different environments in which the system were written (Lisp and Smalltalk).

To handle constraints that cannot be satisfied using a one-pass ordering, they employ multiple redundant views that can cooperate in solving the problem; in their previous work, symbolic algebraic manipulation techniques were employed. They note that powerful algebraic manipulation techniques alone are not enough to solve many interesting problems that can be solved by people; rather, ways are needed of organizing the solution so that the system can use canned theorems, coupled with simple algebra only. Multiple views are one way of encapsulating such theorems. Their use of multiple views has been adopted in ThingLab directly, and the voltage divider example in Chapter 5 is taken from their work. ThingLab does not have any symbolic algebraic capabilities.

Their language retains dependency information – a record of the justifications for each conclusion – to identify which constraints are responsible in the event of an inconsistency, for use in propagating the effects of an edit, and to allow efficient backtracking when search is needed (dependency-directed backtracking). [since ThingLab has no dependency information, when the structure of an object changes it checks more things, and throws away more constraints satisfaction plans, than it really needs to.]

On the other hand, ThingLab has a number of features that are not present in their language. Steele and Sussman have an abstraction mechanism like the one used in ThingLab for building a class given a prototypical example, but do not have a general inheritance hierarchy that allows subclassing. Their system does not have any graphics. In regard to constraints, ThingLab allows constraints on non-numerical objects such as text, as well as on numerical quantities, and can express preferences in addition to absolute requirements. Also, it incrementally compiles the results of constraint satisfaction planning, rather than using an interpreter.

Ideas about constraint languages have been around for some time. M. V. Wilkes [Wilkes 1964] proposed that constraint statements be allowed in an Algol-like programming language. The compiler would use symbolic differentiation to find a linearized from of the constraint statement; at run-time, relaxation techiques would be used to satisfy the constraints. Richard Fikes [Fikes 1970] constructed a system REF-ARF, for solving problems stated as procedures. In the programming language REF, select functions were used to indicate the permissible values for a variable, while condition statements were used to build up sets of constraints that the variables had to satisfy. ARF, the problem solver, then attempted to find values for the variables that satisfied all the conditions by first using a number of rather clever constraint manipulation methods to limit the possible values of the variables, followed by a GPS-style search to find an answer. ABSET [Elcock et al. 1971] was a set-oriented language developed at the University of Aberdeen. It allowed statements of the from A+B=3 AND A=1; given this statement, it could deduce B’s value. ABSET had a number of interesting features: it emphasized the avoidance of unnecessary ordering restrictions in the statement of a program; and it allowed assertions (or constraints) to apply to non-numeric objects such as sets or text.

One of the principal ancestors of Smalltalk is the programming language Simula, which was one of the first systems to use the concepts of classes, subclasses, and instances [Dahl & Nygaard 1966, Dahl Myhrhaug, & Nygaard 1970]. The Simula notion of an event plays an important part in the proposed way of dealing with constraints on time that is described in Chapter 6. The idea of objects that communicate by passing messages in used in the Actor languages developed by Carl Hewitt and his students [Hewitt 1976, Yonezawa and Hewitt 1977]. Both the Actor languages, and the Director language developed by Kenneth Kahn [Kahn 1987], have also been very useful in thinking about constraints on time.

Other relevant work includes representation languages, in particular KRL [Bobrow & Wingograd 1977a, Bobrow & Winograd 1977b]. Ideas in KRL regarding object-centered factorization of knowledge and the inheritance of properties have been very helpful. A comparison of the approaches taken in KRL and ThingLab to the questions of inheritance and the relation between classes and instances may be found in Chapter 3. Such questions also arise in the design of semantic nets [see e.g. Woods 1975, and Brachman 1976].

There is a large body of work in artificial intelligence on problem solving systems of various kinds. Most of these systems are concerned with more complex problem-solving tasks than those tackled in ThingLab. In contrast, in ThingLab much of the emphasis has been on finding ways of generalizing plans and compiling them as procedures so that they may be used efficiently in a graphical environment. However, the problem solving techniques developed in these other systems may well prove useful if ThingLab’s constraint satisfaction abilities are to be strengthened.

In the domain of physics, Johan de Kleer describes a program, Newton, that understands and solves problems in the mini-world of objects moving on surfaces [de Kleer 1975]. Emphasis is placed on planning the solution to a problem using the technique of envisionment, or qualitative simulation of the event. Another mechanics problem solving system is the MECHO program [Bundy 1978], which has been used for a number of kinds of mechanics problem, including pully problems, and also the roller-coaster problems investigated by de Kleer.

A rather different sort of physics problem solver is the Mechanisms Lab developed by Chuck Rieger and Milt Grinberg [Rieger and Grinberg 1977]. The Mechanisms Lab uses a cause-effect representation to describe both natural and artificial systems. Given such a declarative representation of a system, their program can then translate this representation into a population of associatively triggerable procedures, which can in turn be used to simulate the system under consideration.

There has also been considerable work in the more general domain of planning how to solve a problem, from the venerable General Problem Solver onward. In the work of Sacerdoti on planning nets [Sacerdoti 1975], and the related work of Tate [Tate 1977], plans are represented as a partial ordering of actions with respect to time, without premature commitments to a particular order by achieving subgoals. This methodology is compatible with the approach to constraint specification taken in ThingLab, and may prove useful in expressing and satisfying constraints involving time (see Chapter 6).

Finally, a preliminary description of ThingLab itself was published in the IJCAI-77 proceedings [Borning 1977].

It is customary in documents such as this to give an explicit statement of what is new. Here is the author’s list of novel features of ThingLab:

• An hierarchical part-whole representation of objects has been developed that includes an explicit, symbolic representation of shared substructure. Virtually the same representation has been independently invented by Steele and Sussman.

• The Smalltalk class-instance structure has been extended by the inclusion of multiple superclasses, prototypes, and a facility for class definition by example.

• A representation for constraints is used that bundles together a declarative description of the constraint with procedures for satisfying it.

• Constraint satisfaction techniques have been implemented that incrementally analyze constraint interactions and compile the results of this analysis into executable code.

• A user interface has been implemented that provides multiple views on each object, along with appropriate editing facilities for these views. The object itself defines the views that it can provide.