This chapter describes the representation of ThingLab constraints. To support constraints, some new kinds of objects were implemented. In Smalltalk, objects communicate by sending and receiving messages; an object’s response to a message is implemented by a method. In this chapter, ThingLab objects are described that stand for Smalltalk messages and methods. The purpose of this additional mechanism is to provide tools for reasoning about messages and methods, and in particular about the interactions among messages and constraints.

 Organizational note: this chapter discusses constraint representation; constraint satisfaction is dealt with in Chapter 5. At the end of Chapter 5 are some remarks on constraints and the procedural-declarative controversy.

 A message plan is an abstraction of the Smalltalk notion of sending a message. A message plan doesn’t stand for a particular act of sending a message; rather, it is a template for any number af messages that might be sent. A message plan is itself an object – an instance of class MessagePlan. The parts of a message plan include a receiver, a path, an action, and 0 or more arguments. The receiver is normally a pointer to some object, although for some uses it may be nil, or may be a prototype representing any instance of a class of objects that might receive the message. The path tells how to get to one of the receiver’s subparts, which will be called the target of the message plan. The action is a selector for a Smalltalk method understood by the target. The arguments may be either actual of symbolic. Actual arguments are pointers to other objects; symbolic arguments are simply names (strings). The arguments are pointers to arguments passed at run-time to the Smalltalk method invoked by the action. For example, here is a message plan asking a triangle to move one of its vertices right by 10 screen dots:

triangle side1 point2 moveby 10‹ 0.

The receiver is triangle, the path is side1 point2, the action is moveby:, and the argument is the point 10‹ 0.

An important use of message plans is to describe the methods for satisfying a constraint. If a message plan is used in this way, the plan will have several Boolean flags and a pointer to the constraint that generated it, in addition to the parts listed above. The flags are: uniqueState – true if there is only one state of the target that will satisfy the constraint (given that all other parts of the receiver are fixed). See the section Relations Among the parts of a Constraint.

referenceOnly – true if the action described by the message plan only references its target, rather than alters it.

compileTimeOnly – true if the message plan is used only during constraint satisfaction planning, and not in producing executable code.

In ThingLab, an explicit class Method has been defined. The parts of a method are a list of Keywords, a matching list of symbolic arguments, a list of temporaries, and a procedural body. The selector for the method is constructed by concatenating the keywords. These parts are the same as those of a Smalltalk method, the only difference being that in Smalltalk the method is stored as text, and the parts must be found by parsing the text. One reason for defining an explicit class in ThingLab was to simplify access to the parts of a method. This is useful because methods are often generated by the system rather than being entered by the user, with different parts of the method coming from different parts of the system. Also, some methods have their own special properties. For example, all the methods that an object has for showing itself are indexed in a table owned by the object’s class. [This table is used in generating the format pane in the ThingLab user interface.] In some previous implementations of ThingLab, the idea of methods as objects was used in the scheme for deciding how the receive a message when there were conflicting inherited methods , as was described in Chapter 3.

After a ThingLab method has been constructed, it will usually be asked to add itself to some class’s method dictionary. In the implementation, the method does this by constructing a piece of text and handing it to the regular Smalltalk compiler. The Smalltalk compiler in turn produces a byte-coded string for use at run-time, and indexes it in the class'’ method dictionary.

As described in Chapter 1, a constraint represents a relation among the parts of an object that must always hold. Constraints are themselves objects. New kinds of constraints are defined by specifying a rule, and a set of methods for satisfying the constraint. Adding or modifying a constraint is a structural change, so only prototypes will accept new constraints of allow existing ones to be edited. Constraints are indexed in several tables in the prototype’s class for easy retrieval during constraint satisfaction.

The constraint’s methods describe alternate ways of satisfying the constraint; if any one of the methods is invoked, the constraint will be satisfied. These methods are represented as a list of instances of class Method. The constraint also has a matching list of instances of MessagePlan. Each message plan specifies how to invoke the corresponding method, and describes its effects.

When the constraint satisfier decides that one of the methods will need to be invoked at run-time, the message plan that represents that method is asked to generate code that will send the appropriate Smalltalk message to activate the method. Exactly which methods are used will depend on the other constraints, and the user’s preferences as to what should be done if the object is underconstrained (see Chapter 5). [In some cases, rather than generating a call on an already compiled method, the message plan will expand the method in-line.]

The rule is used 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. Both the test and the error expression are instances of class Method. These methods are constructed in a fairly simple-minded way. If the constraint is a numerical equation, the test will check that the two sides of the equation are equal to within some tolerance; the error will be the difference of the two sides of the equation. If the constraint is non-numerical, the rule will be used directly to generate the test; the error will be 0 if the constraint is satisfied, and 1 if it is not. (See the examples below.) If the user wants to override these default methods, he or she can replace them with hand-coded Smalltalk methods.

Consider the structure described by the class HorizontalLine, a subclass of Line.

point1 y Ź point2 y

point2 y Ź point1 y

The class HorizontalLine has a constraint that the y values of the endpoints of each of its instances be equal. The constraints has two ways of satisfying itself, as described by the two methods listed under the rule.

For most methods, including those listed above, the user need provide only the body of the method. The method’s selector is generated automatically, and a simple parser is used to construct the corresponding message plan. Methods for a test and for an error expression are also generated by the constraint. All these methods compile code in the class that owns the constraint, in this case HorizontalLine.

Class HorizontalLine

horiz- point1- y [point1 y Ź point2 y]

horiz- point2- y [point2 y Ź point1 y]

horiz- test [Ý (line point1 y – line point2 y ) abs <self tolerance]

horiz- error [Ý line point1 y – line point2 y]

The first method is one of the ways of satisfying the constraint that was provided by the user. There is a matching message plan for this method, indicating that it alters point1 y, and uniquely determines the state of that subpart. The second method is analogous to the first. The test returns true if the constraint is satisfied. The message tolerance that is invoked in the test returns a number; for graphical objects, the default tolerance is 1 unit of resolution on the graphic display. The error expression returns a number whose value is 0 if the constraint is precisely satisfied. [The selectors for all of these methods are generated by the constraint. They all have the prefix horiz (supplied by the user) to distinguish them from methods for other constraints that might be applied to the class. In the method bodies, Ý means "return a value".]

Another example is the midpoint constraint used in the introductory example in Chapter 1.

Class MidPointLine

midpoint Ź (line point1 + Line point2) / 2

Line point1 Ź line point2 + ((midpoint-Line point2)*2)

Line point2 Ź line point1 + ((midpoint-Line point1)*2)

There are three methods, one to alter the midpoint to satisfy the constraint, and the other two to alter the line’s endpoints. As mentioned previously, the three methods represent alternate ways of satisfying the constraint. The user may want one way to be used in preference to another if there is a choice. This is indicated by the order of the methods – if the system has a choice about which method to use to satisfy the constraint, the first one on the list will be used. In the case of the midpoint, the user preferred that the constraint be satisfied by moving the midpoint rather than by moving an end of the line. [It would be better to represent this sort of metaconstraint more explicitly – see the section on Meta-Constraints that follows.]

The following Smalltalk methods are compiled in class MidPointLine:

Class MidPointLine

inMiddle-midpoint [self midpointŹ (line point1 + line point2)/2]

inMiddle-line-point1 [line point1Ź

inMiddle-line- point2 [line point2Ź

inMiddle-test [Ý ((line point1 + line point2) / 2 – midpoint) abs

inMiddle-error [Ý (line point1 +line point2) / 2 – midpoint]

[Minor detail: the system has inserted self in the first method midpointŹ is a message to the instance of MidPointLine, rather than being an assignment statement. See the section on Assignment Statements later in this chapter.]

Besides altering parts of the owner, a constraint may merely reference some of its owner’s parts. The referenced parts may not be changed to satisfy the constraint, thus allowing the implementation of one-way constraints. For example, suppose the user wants a word to be the result of concatenating a prefix and a stem. When either the prefix or the stem is changed, the word should be updated; but changing the word cannot affect either the prefix or the stem. (If someone sends a message trying to change the word without changing the prefix or stem, the word will spring back to its old value.)

Class ConcatenationExample

word Ź prefix concat: stem

The following methods are compiled:

Class ConcatenationExample

concatenate-word [self word Ź prefix concat: stem]

concatenate-test [Ý word = (prefix concat: stem)]

concatenate-error [word = (prefix concat: stem)Þ [Ý 0.0] Ý 1.0]

Only the first method has generated any executable code – the other two are used only during planning. The error will be simply 0 or 1, since either the word is correct or it isn’t

The relations among the parts of a constraint are fairly rigidly defined. Each of the methods, if invoked, must cause the constraint to be satisfied. For every part that is referenced by the rule, there must be either a method that alters that part, or a dummy method referencing it. Currently, it is up to the user to see that these requirements are met; none of this is checked by the machine.

As has been previously discussed, Smalltalk makes a strong distinction between the insides and the outsides of an object. A method for satisfying a constraint is internal to the constraint and its owner, while the message plan that describes the method is the external handle of that method. It is the message plan that is used by the constraint satisfier in planning how to satisfy an object’s constraints.

In particular, the path of a message plan describes the side effects of its method. The constraint satisfier uses this information to detect overlap in the parts affected by the various methods. Therefore, the more precisely one can specify which subparts are affected by the method, the more information the constraint satisfier will have to work with. Also, the constraint satisfier can do more with a method if it is known that there is only one state of the subpart affected by the method that will satisfy the constraint, given the states of all other parts. [This is described by the Boolean variable uniqueState listed previously.] In all the examples given, uniqueState has been true.

This way of describing constraints allows the representation of relations that are not very analytically tractable. Any sort of relation can be expressed as a constraint, if a procedural test exists, and some algorithm can be specified for satisfying the relation. In the most extreme case of analytical intractability, the constraint will have a single method that affects the entire object that owns the constraint, and this message will not be uniqueState. However, in such a case, the constraint satisfier will have little to work with, and only one such constraint can be handled.

A subclass of Constraint, namely class SetConstraint, is used to represent constraints that apply to the members of a set. The rule portion of a SetConstraint is the same as for a normal constraint. However, rather than being listed explicitly for each constrained part, the methods that the SetConstraint can use to satisfy itself are specified by a template for the method to be used to alter any one of the members of the set. (All the members are treated alike.) An example of an object that uses a SetConstraint is an ElectricalNode, as described in Chapter 2.

[current Ź 0.0 – (current excluding: current) sum]

For this class, to make it easier to find all the parts affected by the constraint, the set is stored as a set of paths to the currents, rather than as direct pointers [of. the section on External References in Chapter 3 ] During constraint satisfaction, the constraint on the node generates a method for each current flowing into it by substituting the appropriate path from the set for the formal name current in the template. For example, consider two resistors r1 and r2 that are connected in series with the merge r1 lead2 node = r2 lead1 node. The set of currents flowing into the node that connects them would containt the paths r1 lead2 current and r2 lead1 current. When the constraint was asked for its methods, it would return:

r1 lead2 current Ź

and

r2 lead1 current Ź

Two message plans are also generated to describe these methods. When one of the message plans is asked to generate code to invoke its method, it inserts that method in-line.

A constraint on several objects can be owned by any object that has all of the constrained objects as parts or subparts. For example, the horizontal constraint involves two points, both of which are parts of an instance of HorizontalLine. The constraint is owned by HorizontalLine.

There are a number of pieces of information embedded in ThingLab’s structures and code that are best regarded as meta-constraints, that is constraints on how other constraints are satisfied. For example, in the midpoint constraint, the user preferred that the constraint be satisfied by altering the midpoint rather than one of the endpoints of the line. Similarly, the anchors on the constants in the temperature converter in Chapter 2 tell the constraint satisfier that these numbers should not be changed to satisfy other constraints. There is also a global meta-constraint built into ThingLab’s constraint satisfaction mechanism: don’t change something unless you have to.

Currently, ThingLab has no general meta-constraint facility. It would be well if these sorts of meta-constraints were explicitly represented and used. Some ideas on this may be found in Chapter 6.

An important special case of a constraint is a merge. When several parts are merged, they are constrained to be all equal. For efficiency, they are usually replaced by a single object, rather than being kept as several separate objects. The owner of the parts maintains a symbolic representation of the merge for use by constraint satisfier, as well as for reconstruction of the original parts if the merge is deleted. There are two principal uses of merging, both of which were illustrated by the introductory example in Chapter 2. The first use is to represent connectivity, for example, to connect the sides of the quadrilateral. The other is for applying pre-defined constraints, as was done with the midpoint constraint. As with constraints, adding or modifying a merge is a structural change, so only prototypes will allow their merges to be edited. The process of merging is the same for both these uses. The object that owns the parts to be merged (e.g. QTheorem) is sent the message merge: paths, where paths is a list of paths to the parts to be merged.

When it can be done, the replacement of several merged objects by a single object yield a more compact storage format, and speeds up constraint satisfaction considerably, since information need not be copied back and forth between the parts that have been declared equal. It does not result in any loss of information, since the owner of the parts keeps a symbolic representation of the merge that contains enough information to reconstruct the original parts. On the other hand, it is slower to merge or unmerge parts, since more computation is required; so for applications in which the structure of the object changes frequently, equality constraints are more efficient. [For a while, merges were always represented using equality constraints; but this was abandoned it was too slow for typical uses of ThingLab. However, it was much simpler – see the section Programming Difficulties in this chapter.] Another efficiency consideration is that a single merge can apply to an indefinite number of objects, while constraints have built into them the number of objects to which they apply. Thus, it is simple to make five separate points be equal using merges. To do this with equality constraints would require either that four separate constraints be used, or that a special equality constraint be defined for use with five objects.

The method for the merge: message uses another message, mergeWith:, which will now be described. The default method for mergeWith: is implemented recursively as follows. The receiver self and the argument arg must both be instances of the same class. After checking that this is the case, a new instance result of the receiver’s class is made. Then, result’s parts are constructed by merging the corresponding parts of self and arg, again using the mergeWith: message. The process stops when primitive parts are reached. Some object have their own interpretations of the mergeWith: message. For example, the result of merging two sets is the union of those sets.

The internal effects of the merge: message depend on what sorts of parts are being merged. There are three cases. In the first case, the parts being merged are all instances of the same class, and are ordinary parts as opposed to primitive parts. [A primitive object, e.g. an integer, is one that has no parts of its own.] In the second, the parts are again not primitives, but are instances of different classes. In the third, the parts are primitive parts (the classes don’t matter in this case.)

In the first case, a new part is constructed using the mergeWith: message described above. A pointer to this new part is then substituted for each pointer to either of the original parts. In addition, an instance of class MergeConstraint is created that owns paths to the merged points, and is indexed in a table owned by the object’s class.

In the second case, the simple strategy described above won’t work, because the mergeWith: message can be used only with instances of the same class. [Otherwise, what would be the class of the result?] Instead, the object finds the nearest common primary superclass of the classes of each of the parts being merged. [Since all classes are subclasses of Object, all classes have some superclass in common.] Next, the object asks the common superclass for its part names, and send itself a series of merge: messages to merge the subparts of the parts being merged that were inherited from this common superclass. If the common superclass has no parts, then the merge is vacuous, and the error handler is invoked. [This will not happen when graphically adding a merge with the ThingLab window. A moving object will stick only to those parts with which it can merge non-vacuously.]

An example may make this second case clearer. Suppose that we have an object with two parts, a HorizontalLine and a DottedLine. Both parts are instances of subclasses of Line

Superclasses

We ask it to merge the two lines by sending it the message

merge: ‘part1’, ‘part2’.

[The argument is a list of length 2 consisting of a path to part1 and a path to part2.] It cannot use the simple method, since the parts are of different classes. Therefore, it finds the nearest common superclass of HorizontalLine and DottedLine, which is Line. Next, it finds the part names of Line, namely point1 and point2. Finally, it sends itself the messages

merge: ‘part1 point1’, ‘part2 point1’

and

Since the endpoints are all instances of class Point, MergeExample can use be simple kind of merging in responding to these new messages.

In the third case, the parts being merged are primitives. Here, the object will automatically construct an equality constraint instead of using a merge. The reasons for this will be discussed in the section Assignment Statements,to follow. [This is why the horizontal line had a constraint rather than a merge to keep equal the y values of its endpoints.]

The complexities of the second case arise because of he way primary superclasses are represented; for other superclasses, which are represented in ThingLab by having an instance of the superclasses as a part, the first method can be used. Indeed, before the algorithm for doing the second case was discovered, all subclasses in ThingLab were represented by including an instance of the superclass as part.

Are merges symmetric with respect to the merged parts? This question has been divided into two parts: symmetry in the representation of the merge, and symmetry during the process of adding the merge. The representation is completely symmetric. The process of adding the merge could be symmetric, but often is not. In the editor, normally one of the parts being merged is moving with the cursor, while the other is stationary. The stationary part is given preference in computing the result of the merge. For example, when the line part of the moving MidPointLine was merged with a side of the quadrilateral, the result of the merge was a new line whose endpoints had the same locations as those of the original side.

The most difficult parts of the ThingLab system to program and debug were those that deal with adding and editing merges. As an example of the sort of complexity that arises, consider the following editing operation. The object being edited has two parts, both triangles. A side of the first triangle is being merged with a side from the second.

When the sides are merged, a new line results. The new line must be substituted for the old side3 of triangle1 and for the old side1 of triangle2. Further, because of the merges in the class Triangle, point1 of the new line must be substituted for triangle1 side1 point1 and for triangle2 side3 point1. Similarly, point2 of the new line must be substituted for triangle1 side2 point2 and for triangle2 side2 point1. All this is happening in the context of an interactive editing session, so it shouldn’t take forever.

Perhaps all this could be simplified by viewing merges as constraints on bindings, and using the regular constraint satisfaction mechanism; but this has not been done in the current version.

As should be apparent from the above description, substituting a new part for an old one can be expensive when merges are present. However, in ThingLab it is a comparatively rare operation. The usual case of an assignment statement is handled by recursively copying the values from one object into the other, rather than by smashing the pointer to the old object. A little background is needed in explaining this.

In procedure-oriented languages, a reasonable way of viewing assignment is that there is an assignment operator to which the system presents the address of a variable along with a new value to be stored into that variable. Smalltalk doesn’t do it this way. Rather, the object that has the variable as a part is sent a message requesting assignment of some value to that variable. This messages will invoke a method. The method may substitute a pointer to the new value for the pointer to the old one; but then again it may do something else. The sender of the message need only be concerned with its effect, not with the internal method for receiving the message. This is another example of Smalltalk’s strong distinction between the outside and the inside of an object.

As described in Chapter 3, methods for reading an writing an object’s parts are automatically generated and compiled by the part descriptions. The exact methods depends on the type of the part, which will be either ordinary or primitive. Primitive objects, e.g. integers, are considered to have no parts of their own. The part description always compiles the same method for reading the field, but compiles different methods for writing it depending on whether the part is ordinary or primitive. [It finds what type it is by sending the part’s class the message isPrimitive.] For an ordinary part, such as a line that is the side of a triangle, the following sorts of methods are compiled.

side1 [Ý side1]

side1Ź temp [side1 copyFrom: temp]

For those not familiar with Smalltalk syntax, the first method is interpreted as follows:

To receive the message side1, return my part named side1.

The second method is interpreted as:

Note that in this method the pointer to the side is not changed, so that none of the triangle’s merges will be affected.

On the other hand, for a primitive part, such as the x value of a point, a method for writing this part is compiled that does change the pointer to the value.

Class Point

The first method is interpreted as in the previous case. The second method is interpreted as: to receive the message x¬ , get a single argument and bind it to my part named x.

The implementation of the copyFrom: message is of interest. For an object composed of ordinary parts, such as a triangle, the message is interpreted as follows:

Class Triangle

On the other hand, the interpretation is different for an object with primitive parts, such as a point.

Class Point

For an ordinary part, the copyFrom: message results in recursively sending the copyFrom: message to that part. For a primitive part, the pointer in the field changed. [In the actual system, each class doesn’t have its own method for copyFrom: Rather, there is a default implementation in class Object that branches on the type of the part.]

An important feature of this scheme is that the external behavior of both kinds of parts are the same. If an object has a part p and p¬ . Internally, the methods for receiving these messages depend on what type of a part is p.