A Graphical Service System With Variable Syntax

Lawrence G. Roberts
Lincoln Laboratory
Massachusetts Institute of Technology
Lexington, Mass.


yellow rule

Man-machine interaction in many fields of endeavor should be greatly facilitated in the near future through the use of interactive graphical languages. To provide a variety of display scope communication procedures, a Graphic Service System which functions as a generalized graphical language translator, is being developed to aid the definition as well as the use of new graphical languages.


yellow rule

Graphic Service System

In much the same way that a syntax-directed translator accepts typewritten statements in almost any language and performs the requested operation, a Graphic Service System (GSS) should accept light-pen, keyboard, button and knob actions from the user in any control language and perform the requested operation. The detailed language of the keys and light-pen should not be a fixed one, anymore than a typewriter user should be limited to a single language. Each problem area will require a different control language for optimal utility in that context. If the only use of a graphical system were for drawing pictures (automated drafting board) then one graphical control language might be sufficient, but where physical and other nongeometrical relations are to be defined and simulated as well, the language should be specifically oriented toward each problem area.

A GSS program, in accepting graphical language definitions and subsequently parsing and executing control commands in that language, is similar to a syntax-driven translator with some minor differences. One is that the inputs arrive from the light- pen, knobs, and other console attachments as well as the keyboard. This is not significant, however, since the operands such as the pen position can be delivered in a fixed sequence before or after each action operator such as a key. Another difference is that the semantic operators of a programming language are designed for generating code and manipulating the symbolic program data structure, whereas graphic statements will need semantic operators which manipulate the graphic data structure. However, a translator could have both kinds of semantic operators without any conflict. Finally, the syntax that may be requested in a two-dimensional context may be more complex than that necessary in a linear language. Again, this problem can be solved by extending the translator.

VITAL (Variably Initialized Translator for Algorithmic Languages), a general purpose translator for the Lincoln Laboratory TX-2 Computer, is currently being adapted for use as a graphical control language translator. VITAL accepts macro-like operator definitions which specify the left and right dominances of this operator as well as any redefinitions necessary for subordinate operators which fall within its scope. The operator definitions may include both semantic meta-language statements and previously defined operator statements to specify the meaning of the operator. VITAL uses a CORAL list structure [1] similar to the data structures used in all the graphical work on the TX-2. Thus, some of the existing semantic operators in VITAL are concerned with building and modifying such list structures. The semantic routines available will be ex- tended to include the matrix operations needed for geo- metric manipulations.

A simple example might be that a user points the lightpen at a point (P1) and hits the key "". Since this key is an operator in the language he is using, the pen stack (items seen by the pen that frame) would be saved and a pointer to it entered into the translator's input file before the symbol. Then the user might point at a second point (P2) and terminate his action by a pen flick or by typing a semicolon. This action would again strobe the pen stack and record the second stack pointer and the symbol to terminate. This activates the translator which sees:

P1 P2 ;

The operator calls the semantic meta-language which uses the pen stack pointer to derive the list structure location of the points. If this operator is to mean "draw a line," the next semantic operation would be to build a line block between the points in question and add this line to the display file.

The points do not necessarily have to be points already displayed; they might be interpreted as the position of the light-pen tracking cross if no other items were seen. In such a case the point blocks would also have to be added to the list structure.

A second simple operator in a graphical language might be one to determine the intersection point of two lines.

L1 X L2 ;

The x-operator would normally be used as part of another statement where a position was desired, but if used alone would cause a point block to be added to the list structure and display file at the intersection of the lines specified. This operator expects both its operands to be of type "line" just as the operator would expect its operands to be of type "point."

If we now use these two operators in a compound statement, it is necessary to parse the statement using the data type information in order to determine what needs to be done. For example, the statement:

L1 X P1 P2 L2 X L3 ;

would be generated by pointing at points and lines in a picture (Figure lA) and typing the operators. Since (L X L) is of type point and (P P) is of type line, the statement can be parsed as follows:

L1 X (P1 P2)) (L2 X L3) ;

This statement tells us to construct and display a line from the intersection of L1 and (P1 P2) to the intersection of

L2 and L3. The construction line from P 1 to P2 need not be displayed. The resultant line is shown in Figure 1B.

Structure

To represent the relations and graphical constructions which might be specified, a very general structure is needed. A combination of list structure for associations and matrices for mathematical relations is presently being used. The current data which specifies each item, such as a line, point, surface, or object block, which is contained in a list structure is tied to all related items through property blocks. Each property block specifies what type it is (point on line, etc.) and further, usually contains some data (where on line, etc.). All data values are assigned constraint dominances by the control language so that the values are totally ordered. Thus, when the user attempts to modify a picture there is a reasonable procedure for determining which other data values should be changed. For example, when mechanical linkages are being drawn, the lengths of the lines should have a higher dominance (resistance to change) than the positions of points or slopes of lines, whereas if circuit diagrams are being sketched, the slopes of lines and rotations of elements should be of higher dominance than the lengths of the lines.

In general, the use of constraint dominances allows the structure to specify the importance of data as well as the data itself so that essential features will be preserved at the expense of secondary ones. Further, since the dominances are associated with each degree of freedom, the system can detect any attempt to overconstrain.

Mathematical Relations

When a user is working in some field of science with a computer-aided graphics system, he usually has mathematical relations to define between nongeometric varia- bles. For example, in electrical circuit design, besides the geometric variables (x, y) of circuit layout, it is necessary to define the relations between voltage, current and time for each element. These relations should be expressable in the same manner as geometric relations, since these varia- bles merely extend the dimension of the space. In particular, if we consider networks of resistors, the space vector might be v = [e, i, x, y] in a four-dimensional space. The definition of a resistor would consist of a pictorial representation and an expression of the e = iR relation. Mathematical relations could be expressed by the use of loci of permissible values of the parameters. Thus, the resistor model would be a line in four-space where each use of the model would supply a transform specifying x, y and R. An extension of this model might add temperature as a variable where the temperature relation was: T = kei. Now the model locus would be a second-order curve in five-space. Thus, each specification of a resistor would require X, Y, R and W where the wattage rating W determines the factor k.

The experience on the TX-2 with Sketchpad [2], Sketch- pad III [3] and solid object display [4] has demonstrated that the effectiveness of graphical techniques as a tool for man-machine interaction depends on developing a flexible, convenient GSS program. However, the ability to make pictures is not sufficient in itself; the pictures must be representative of data which needs computation such that the graphics system is used as an input/output tool, not merely as a display. If the problem to be solved can also be expressed graphically, then the concept of increasing the dimension of the space could allow both the organization and definition of the data elements to be accomplished with the basic graphic system. The mathematical procedures which are being developed allow for second-order functions in any number of variables to be processed with relative ease [5]. These procedures will allow many problems to be solved without recourse to any programs external to the graphics system. It is intended, however, that most problems, once defined with the aid of the graphics, will be solved or simulated by special problem-specific programs.

Regardless of the processing taking place between the man-machine exchanges, the combination of a general Graphical Service System and problem-oriental control languages should make the manipulation and evaluation of complex multidimensional relations and data arrays substantially more convenient than they have been until now.

REFERENCES

  1. Roberts, L. G. Graphical communication and control languages. Second Cong. on Information System Science, Hot Springs, Va., 1964.
  2. Sutherland, I. E. Sketchpad: man-machine graphical communication system. AFIPS Conf. Proc. 23 (1963), 329.
  3. JOHNSON, T. E. Sketchpad III: a computer program for drawing in three-dimensions. AFIPS Conf. Proc. 23 (1963), 347.
  4. ROBERTS, L. G. Machine perception of three-dimensional solids. Lincoln Lab. Tech. Rep. 315, 22 May 1963.
  5. Homogeneous matrix representation and manipulation of N-dimensional constructs. Notes for Eng. Summer Conf Course. U. of Michigan. Ann Arbor. Mich. June, 14-18, 1965

Presented at an ACM Programming Languages and Pragmatics Conference, San Dimas, California, Agust 1965.

This work was supported by the U.S. Advanced Research Projects Agency of the Department of Defense under Air Force Contract AF19(628)-5167 (ARPA Order 691).

yellow rule

Home || Contact Dr. Roberts

Copyright 2001 Dr. Lawrence G. Roberts

Contact webmaster