This chapter is an exploration of the idea of building a programming languagi around the notions of constraints and hierarchy that have been used in ThingLab. At this point, a complete design does not exist, although many of the pieces are there. The reader is therefore warned that the proposals discussed in this chapter are incomplete and untested, and some of them will doubtless turn out to be unworkable.

Discussion regarding the next major version of Smalltalk is currently under way in the Learning Research Group. An important goal in the design of the new Smalltalk is to integrate many of the language metaphors that LRG has investigated and implemented as subsystems over the past several years, including search and information retrieval, simulation, constraints, objects as editable documents, and others.

The constriant language described here is a trial design – a step towards integrating constraints into a full language. In the present document, the author has adopted an evolutionary approach that starts with the current Smalltalk messages and methods and ThingLab constraints, and works forward from that.

Like Smalltalk and ThingLab, the constraint language would be object-oriented. As a starting point, the language can use the current ThingLab inheritance and part-whole hierarchies. Constraints would be built into the language in a fundamental way. A generalization of the current constraint representation is proposed that allows constraints to be active or inactive, and to involve time and sequencing. Later in this chapter, a way of representing Smalltalk methods as constraints is described. This is an important step, as it serves to unify constraints with standard programming constructs.

The reader should think of programming in the constraint language as being like building up networks of constraints, as in the calculator example in Chapter2. The syntax of the language can involve linear text, as other languages. However, when the expression 1.8*C + 32.0 appears in a piece of code, it would have the same semantics as the equivalent network of constants, variables, and arithmetic operators. Thus + is not merely an uninterpreted atomic symbol; rather, it is the name of a complete object in its own right. This object would have attachers that seek to merge with other objects (numbers), just like the Plus object in the calcutator examples. Also like the Plus object, it would know about its inverses.

In ThingLab, the user must enter into the system both the declarative and procedural parts of a constraint, where the declarative part is the constraint’s rule, and the procedural part is the set of methods that can be invoked to satisfy the constraint. It is the user’s responsibility to ensure that these parts correspond, and that the methods do what it expected.

In the constraint language, normally the user would enter the rule portion of a constraint only. For example, the enter a constraint that a Centigrade temperature C corresponded to a Fahrenheit temperature F, the user would need only enter the rule 1.8*C + 32.0 = F. The system would take care of constructing the methods that the constraint could used to satisfy itself, namely F Ź 1.8*C + 32.0 and C Ź (F – 32.0)/1.8.

In this case, the problem of constructing these methods may be solved using the one-pass constraint satisfaction techniques. The network implied by the above constraint rule corresponds to the network constructed by the user in temperature converter example in Chapter 2. In that example, the constraint satisfier generated a plan for satisfying the constraints when the user changed C or F by using the one-pass constraint satisfaction techniques and the information owned by the arithmetic operators These same techniques would yield the desired constraint methods in the new language.

In other cases, the system would not be able to find a one-pass ordering for solving the constraint satisfaction problem. Improved constraint satisfaction techniques would help with this to some extent. However, there will doubtless be cases for which the compiler would be unable to derive the procedural parts ot the constraint from its rule. For example, unless it were equipped with some rather sophisticated algebraic problem-solving techniques, the constraint language compiler will probably be unable to derive Newton’s method for finding a square root given only the constraint y = x*x.

Therefore, the language should include facilities that allow the user to provide the system with the procedural parts of the constraint. It would be nice if the system could check to see that these procedures did what was expected of them. In general, this is the program verification problem, and is hence quite hard. However. less ambitious kinds of checking could be accomplished e.g. a print method, the compiler could be check that the method didn’t alter any parts of the object. For methods that did affect the object,the compiler could check that it aaltered only the appropriate parts. Second, the compiler could have a debugging mode, in which it would insert a run-time check to see that a constraint was saisfied after a user-supplied method had been invoked. After a constraint had been used for a while, the checks could be removed.

As discussed in Chapter 3, Smalltalk makes a strong distinction between the insides and the outside of an object. The internal aspects of an object are its class, and its instance fields and their contents; its external aspects are the messages that it understands and its responses. In Smalltalk one can thus have virtual fields. From the outside, it appears that an object has some local storage that can be read and written via appropriate messages; but internally there is no corresponding instance field.

To allow ThingLab to take advantage of this in describing part-whole hierarchies, a facility for defining virtual parts should be added. It would be rather simple to implement. In analogy to the class PartDescription, there would be a class VirtualPartDescription that would keep track of the virtual part’s constraints. When virtual part was involved in some constraints to be satisfied, the object that owned the part would inform the constraint satisfier of its existence. In generating code, the constraint satisfier would allocate a temporay variable for the virtual part and initialize it; whenever the virtual part was referenced in a method, the constraint satisfier would substitute a reference to be temporary for messages to the object asking for its part. As described in Chapter 3, an example of such a virtual part might be the center of a rectangle, which need not be explicitly stored in the instance, but can always be computed form the rectangle’s corners.

Virtual parts will be used in the proposed way of dealing with constraints on time. However, they would have other applications as well. First, they would provide a convenient way for handling multiple representation of objects. For example, the multiply represented point described in Chapter 3 could have its Cartesian representation as an actual part, and the corresponding polar representation as a virtual part. From the outside, both parts would look the same. Also, virtual parts would be useful in storing data more efficiently when so desired. As an extreme example, consider the class HorizontalIsoscelesTriangle described in Chapter 3. As represented there, it has three superclass parts: a triangle, a horizontal triangle, and an isosceles triangle. Each triangle has pointers to the three sides (which are shared). The sides in turn have pointers to the endpoints, which finally hold the x and y coordinates. This object could be stored very efficiently by having six integers as its actual parts, with all the other parts being virtual.

As a basis for a programming language, the most important missing aspect of the current constraint mechanism is that it has no facilities for dealing with time. To remedy this, a number of new mechanisms are proposed. These mechanism are intended to be general enough to describe both constraints on time in simulations, and constraints on sequencing and iteration such as one might use in ordinary programming.

The semantics of constraints would be generalized. A constraint would have the following form:

when condition [body]

The condition would be a Boolean-valued expression that determines when the constraint is active. The body would consist of further constraints. The condition could be omitted; if so, the condition when true would be implied.

As in Simula, an object would have active phases, separated by periods of inactivity. An active phase of an object is called an event. An event happens in zero time (at least as far as any temporal constraints are concerned). In the new language, one way in which an event could occur would be for the value of the condition of one of the object’s constraints to become true. Such events could be triggered either by external stimuli, such as the user’s pressing a button, or by constraints whose conditions referenced a changing part, such as the value of a clock.

The object would have to satisfy all the other constraints in the body of the active constraint as long as the constraint’s condition remained true. Using constraints as they have been defined thus far, as soon as the condition became true, the object might have to change its state to satisfy its constraints; but until the value of one of the conditions of its constraints changed, the object’s state would not alter. However, a constraint could itself trigger a succession of events with the use of temporal adverbs. A preliminary list of such abverbs is:

first – the object’s state when the constraint first becomes active

current – the object’s current state

next – the object’s state after the next event

last – the object’s state when the constraint first becomes inactive

These adverbs would be messages understood by all objects. Thus, next is a message meaning "return your state after the next event". next would be something like a virtual part ("virtual successor" might be a better description). Temporal adverbs could be used in paths, e.g. poolGame eightBall location first. As long as the constraint’s condition held, the object would take on the successive states that satisfied the next condition described in the constraint’s body. Thus, with the use of current and next constraints could specify implicit looping. For example, as long as the constraint

i next = i current + 1

were active, the value of i would continue to be incremented. [This technique for defining iterations is much like that used in the language Lucid (Ashcroft & Wadge 1977).]

If an object had several constraints that were active simultaneously, the next state of the object would have to satisfy all of the constraints. Otherwise, if two objects that were not related by constraints were active simultaneously, the events of each object would occur asynchronously.

There are various problems that need to be worked out in this formulation. For example, the constraint satisfaction techniques would need to be augmented so that they could deal with induction. Also, there are some timing issues in connection with asynchronous event. At the moment, the author does not regard these problems as insoluble. However, none of this has been implemented, so it remains to be seen if this is the case.

As a simple example of constraints involving time, a clock for use in building digital logic simulations will be described.

The driving force behind a logic simulation is the clock. As long as active is true, the logic clock will provide a steady stream of timing pulses. [Note: inverse is a message understood by instances of LogicState that means "if you are on return off; if you are off, return on." The semicolon is used here to separate a series of constraints that must hold simultaneously.] One can picture an instance of LogicClock in the following way:

Figure 6.1 – Successive states of a logic clock

The initial state of the clock is off, This state has a virtual successor (that object obtained by sending it the message next0, whose state is on, and so forth

The above mechanisms for virtual parts and for constraints dealing with time provide a way in which Smalltalk methods can be viewed as constraints. This is important, since it serves to unify the constraints metaphor with the metaphor of Smalltalk programming. However, the pictured; rather, it is an interim formulation to help make a bridge between the continuous nature of constraints and the step-by-step nature of methods.

In Smalltalk-76, when an object receives a message selector is matched against the selectors of the object’s methods. If a match is found, the actual arguments of the message are bound to the formal arguments of the method, and space is allocated for the temporary variables. The code is then executed, causing further messages to be sent or assignments to be made. A method may be viewed as a constraint in the following way: the object that has the method should have a number of virtual parts, one with the same name as the selector, and others with names corresponding to those of the formal parameters. There is a constraint whose condition is that the virtual part that is the selector have the value true. The rule for this constraint should accomplish the same thing as the old method. Also, it should specify that the next value of the virtual part that is the selector be false, so that when the constraint becomes active, it causes the desired effects and then turns itself off. To send a message to an object, the actual arguments are placed in the corresponding virtual parts, and its virtual part that corresponds to the desired selector is set to true. [Small point: these virtual pats should really be regarded as virtual parts of the particular activation of an object so that methods can be recursive.]

This formulation can handle the current message-method behavior, but is actually somewhat more general. Interesting results may be obtained by not automatically turning the constraint off, thus allowing a number of methods to be active simultaneously. This notion of control should be thought of in analogy to digital logic circuits: there is a "control line" (i.e., the virtual part that represents the selector) that can be turned on and off. As long as the control line is on, a device (method) is active. Many devices can be connected to a control line; a device may manage the control lines of other sub-devices.

The logic clock definition can be re-written as follows:

The LogicClock should be thought of as having a virtual part active. The clock is turned on by someone invoking the method named active. [In these examples, active will be a method that starts up an object’s default activity. Thus in this case, the default activity of a clock is to trick.]

As another example of the use of this scheme, consider a simulated rocket. The rocket will have a local time frame, represented by a Clock object. [Many of the parts and constraints of the rocket ought to be inherited form a more general class such as PhysicalObject, but that is not the point of this example.]

Class Clock

Object

Part Descriptions

time: a Time

dt: a TimeChange

Methods

active

[time first = 0;

time next = time current + dt]

 

Class Rocket

Superclasses

Object

Part Descriptions

location: a Point

velocity: a Velocity

acceleration: an Acceleration

heading: a Direction

mass: a Mass

thrust: a Force

clock: a Clock

Methods

coast

[thrust = 0.0]

fullSpeedAhead [thrust = 1000.0] show | icon [icon = [thrust>0Þ

[]];

    screen showIcon: icon at: location]

active

[clock active;

location next = location current + (velocity*clock dt);

velocity next = velocity current + (acceleration *clock dt);

acceleration = heading*thrust/mass]

The active method applies the laws of physics to the rocket, and simultaneously starts the clock ticking. The testFlight method sets up constraints that will initialize the rocket’s state, and also invokes active.

An instance of Rocket could be created and tested by executing:

r ¬ Rocket new.

As long as the button was held down, the rocket would fly.

ThingLab currently uses certain kinds of constraints that specify how other constraints are to be processed; however, they are represented and used in an ad hoc manner. In the new language, meta-constraints would be constraints in their own right. The methods of these constraints would sent messages to the satisfier, rather than to the object whose constraints were being satisfied. For example, a meta-constraint that a part be fixed would tell the constraint satisfier to leave that part alone. Other things that could be expressed in a natural way with the use of meta-constraints include specifying which method should be used to satisfy a constraint (if there is a choice); masking off a given constraint; indicating that a constraint is only a preference rather than a requirement; establishing partial orderings on preferences; explicitly representing the additional information used in constructing a method that does not uniquely determine the state of a part; and specifying heuristics as to what to try next in planning a constraint satisfaction method.

Since meta-constraints would themselves be constraints, there could be meta-beta-constraints, and so on. For example, given an inherited meta-constraint deleting another inherited (ordinary) constraints, one could include a meta-beta-constraint that deleted the deletion. However, use of this facility should probably be kept to a minimum in the interest of the sanity of the programmer.

ThingLab has some facilities that support multiple views of an object. These facilities fall into two categories. First, the ThingLab user interface includes a menu of the different ways in which an object can depict itself. Second, the constraint mechanism allows the user to define two different representations of an object, and put constraint on them that keeps them in coordination. For example, one can represent a point in both Cartesian and polar coordinates, and use a constraint to keep the two representations consistent. Similarly, one can define multiple views of an object to aid in constraint satisfaction, as in the quadratic example in Chapter 2 or the voltage divider in Chapter 5. [See also the discussion of the constraint language of Steele and Sussman in Chapter1, and the views example in Chapter 2. Picture transforms are a kind of view in common use in graphics systems. An early AI system that used cultiple views was Merlin (Moore & Newell 1973). Views also play a prominent role in KRL (Bobrow & Winograd 1977a).]

There are, however, many questions that remain to be explored in this area. As presently implemented, the two kinds of multiple views described above are rather different. An object depicts itself on the screen procedurally – there is a sequence of messages that it send that causes bits to be changed on the bitmap display, but there is no separate object that corresponds to the picture as such. In the case of the point, however, there are really two objects. To make these cases of the point, however, there are really two objects. To make these cases fundamentally the same, ways of making pictures be actual objects should be investigated. Work on this problem is currently under way in the Learning Research Group. [Eventually, one might want to make the picture be a virtual object, in analogy with virtual parts; but its semantics should be as described.]

Another area for research concerns views that need not be always in coordination. Consider two views on a flip flop: as a logic device, and as an electronic circuit, Viewed as a logic device, the flip flop is fairly simple. When describing its state, one talks in terms of things being on or off. Viewed as an electronic circuit, it is more complex. It is composed of transistors, resistors, and so forth; in this case, its state will involve voltages, currents, and such. One can introduce constraints that relate the two representations – for example, a constraint that a logic state of off must correspond to a voltage between 0 and 2, while for a logic state of on the voltage must be between 3 and 5. However, one might not want both views to be active at all times. When simulating the logic behavior of a device, the electrical representation could be turned off (perhaps by employing when conditions on the constraints that relate the two views). However, if one became interested in timing considerations, these electrical properties could be turned on again. These questions are also related to the use of part-whole hierarchies. For example, one might have the amplifier module of a radio described in terms of a simple relation between its output signals that holds under normal conditions, and also in terms of the details of the circuit. When appropriate, the simple model could be used; but when its conditions of applicability were violated (e.g., drop in the power supply voltage or an input signal that was too large), the detailed representation could be used.

Such investigations might also yield a much cleaner view of what happens when a picture is edited and the depicted object is updated correspondingly. Consider the bar chart example in Chapter 2. When the user was in the midst of editing the text of one of the numbers, the constraint relating the number to the height of the bar was temporarily violated; only when the accept command was issued was the bar’s height updated. Permission to temporarily violate the constraint is currently embedded in the methods of the text editor; the proposed investigations may provide ways of describing and reasoning about such things more formally. Another problem of this sort concerns one process that provides a view on another dynamically changing process. What happens when the viewing process can’t keep up?

Another interesting area to be explored concerns cascaded views. In 3-d graphics work, picture transforms are often represented as 4x4 matrices. When a picture is to be subjected to a series of transforms, typically the transformation matrices are multiplied together in advance. In the same way, successive views could be cascaded; regarding a view as a kind of constraints, this amounts to converting a network of constraints into a single constraint.

In this essay The Architecture of Complexity [Simon 1969], Herbert Simon describes what he calls nearly decomposable systems.

In terms of the constraint language, there should be ways of viewing a complex part as a much simpler object. Dually, from within a part, there should be ways of viewing the influences of the environment in an aggregate way. As a very simple example, consider the thermometers example in Chapter 2. The thermometers object has a part that is an instance of TemperatureConverter. From the outside, it should be possible to view the TemperatureConverter as a unit: the Times and Plus constraints, the constants. and their connectivity can all be collapsed into a single constraint. There is no need for the Thermometers object to know anything about the internal construction of its parts. From within the TemperatureConverter, the outside environment impinges only at the two attachers, which in this case are connected to the thermometers. The TemperatureConverter could plan a way of satisfying its internal constraints for any state of its attachers, and synthesize a single constraint that embodies this view.

As a more complex example, in simulating planets orbiting the sun, from the outside each planet can be approximated as a point mass. From the point of view of an individual planet, the influence of its environments can be summarized as a set of forces. As a good approximation, the environment is simply the sun; the attractions of the other planets are much weaker by comparison.

Initially, the constraint language (and the next version of Smalltalk as well) could be implemented in Smalltalk-76. Eventually, however. the underlying environment could be changed to take advantage of the features of the new language. Some considerations of this sort are discussed in this section.

Suppose that the only kinds of direct pointers allowed in the system were pointers from a whole to its parts, or from an object to its successor (in a list, or its temporal successor as the next message described previously). Further, suppose that all sharing of direct pointers had to be described by merges. Any other sort of reference would be stored as a path. If this were done, then the system could easily determine how many direct pointers there were to a give object. Storage management could be done without reference counting or garbage collection.

This disadvantage of this scheme is of course that the system would have to spend more time following paths. However, Smalltalk currently spends a considerable portion of its time on reference counting; and in the end, the new scheme might come out ahead. Also, specialized hardware could speed things up greatly. Aside from these considerations, this scheme has significant advantages in terms of control for constraint satisfaction purposes.

As noted in Chapter 5, in the current ThingLab the constraint satisfier could easily notice at compile-time when it is permissible for several constraints to be satisfied in parallel. In the proposed language, parallelism (or at least pseudo-parallelism) would be needed when two or more independent objects were active simultaneously. Therefore, one of the promising directions for future research would be to experiment with running the new language on a multiprocessor machine. The parallelism would involve an interesting mixture of compile-time and run-time techniques. Some of the parallelism could be completely planned at compile-time, with the constraint satisfier automatically generating code that told the machine which steps could be done in parallel, and when the various parallel forks had to rejoin. Other sorts of parallelism could be unravelled only at run-time, for example, the parallelism implied by several when conditions that depend on user-controlled input devices.