Sketchpad(ID:191/ske001)Interactive graphics environmentIvan Sutherland, MIT, 1963. Computer-aided design. Constraints using value inference. Introduced the "ring" list structure. Used master objects as templates for instances, which featured full inheritance. Kay claims it is the first true object-oriented system. First feature of drag-and-drop system. Places People: Structures: Related languages
References: in [AFIPS JCC 23] Proceedings of the 1963 Spring Joint Computer Conference in Detroit SJCC 1963 view details in [ACM/IEEE] Proceedings of the SHARE design automation workshop 1964 view details in Orr, William (ed) "Conversational Computing", 1968 view details in Burck, Gilbert "The Computer Age" view details in Burck, Gilbert "The Computer Age" view details in Proceedings A.C.M. National Meeting, 1967 view details in Karplus, W. J. ed. "On-Line Computing", McGraw-Hill, New York, 1967 view details techniques, thereby reducing the time required to imple- ment the language. Although the syntax of one-dimen- sional languages is not a natural medium for two-di- mensional problems, it is at present the only practical technique for making progress with graphic languages. Abstract: Interactive use of computers with graphic terminals will permit many new problems to be solved using machines. In order to handle a variety of applications, it is expedient to develop a general purpose graphic language that is useful on a number of graphic devices. A system has been designed to produce such a language quickly and cheaply. A model graphic language which has been developed with the system is presented. in [ACM] CACM 11(04) (April 1968) view details in [ACM] CACM 11(04) (April 1968) view details Sutherland (1963)--describes SKETCHPAD, a man-machine graphical communications system, developed at MIT; in [ACM] ACM Computing Surveys 2(4) Dec1970 view details Historically SKETCHPAD (Sutherland) was the first widely recognized general purpose graphics system. The SKETCHPAD system consists of a collection of subroutines called interactively through a menu selection process. The system allows pictures to be constructed hierarchically from other pictures and is noted for its use of a ring data structure to store picture descriptions. Kulsrud, Williams, and Giloi presented models for the definition of a general purpose graphics language, Kulsrud suggested that the first version of the proposed language have written commands and that it later be adjusted to accept input from graphics devices such as light pens and trackballs. The language she described was capable of picture description, manipulation, and analysis. Although it could be used with interactive applications programs, it was not an interactive language. Williams described a language that provided (i) data types with related operations particularly suited to graphical applications, and (2) the ability to add new data types and operations. For example, a "point,' could be a data type, and a specially defined addition operator would operate on that data type. The language was thus highly extensible, but it was not interactive. Giloi proposed a model to be used in constructing either subroutine packages for graphic display applications or graphical extensions to existing languages. In this model, pictures were described as a hierarchy of subpictures and picture primitives. Primitives were defined as anything for which there was a hardware generator in the display processor, placing limits on the device independence of a language developed from his model. An interactive version of the model was developed by extending APL to include graphics capabilities, and a non-interactive version was developed as a FORTRAN subroutine package. The general purpose graphics systems presented in recent years can be classified as (i) subroutine packages for graphics applications, (2) graphics extensions to existing languages, and (3) new languages possessing graphics capabilities. Graphics subroutine packages are most widely distributed particularly by manufacturers of graphics display hardware. Some example packages are GINO-F, GPGS, GRAF, DISSPLA, and EXPLOR. Most packages are limited to the manipulation of picture displays with few programming control or storage capabilities. Where such abilities are available they often serve specialized purposes as in WAVE, a package for waveform analysis. One exception is the VIP system where the user is able to combine the available system function subroutines into special purpose functions which can then be used in the same way that the original system functions were used. Extensions of an existing language such as Euler-G, IMAGE, APLBAGS, APLG, and PENCIL, provide a programmer with graphics capabilities as well as general programming features. Euler-G has excellent data structure definition facilities. IMAGE, an extension of FORTRAN, cannot provide the data structure description capabilities that are available in Euler-G, but it has the advantage of being based on the most widely distributed host language available. APLBAGS, APLG, and PENCIL, an extension of the MULTILANG on-line programming system, are truly conversational languages. GRASP, a PL/I extension, is a compiled language but it allows dynamic interaction. GRASP also allows the definition of models from which complex pictures can be created hierarchically. ESP3, an extension of SNOBOL4, is a non-interactive language from which many of the high-level concepts found in PIGLI are drawn. Language extensions are found mainly in experimental installations. Two complete graphics languages are METAVISU and GLIDE. Both take characteristics from a base language (PL/I and ALGOL, respectively) and add capabilities for defining, displaying, and manipulating pictures. Full languages are less widely distributed than subroutine packages or language extensions. in Proceedings of the 1978 annual conference 1978, Washington, D.C., United States view details The Kernel ThingLab System 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). Extract: Constraint Representation and Satisfaction Constraint Representation and Satisfaction Representation of Constraints 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. Merges 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. Constraint Satisfaction 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? 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: xn + yn = zn 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. Relation to Other Work 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. Extract: Sketchpad Sketchpad 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. in Proceedings of the 1978 annual conference 1978, Washington, D.C., United States view details in Proceedings of the 1978 annual conference 1978, Washington, D.C., United States view details |