A model recently proposed by the author for constructing a hierarchy of logical high-level graphics input devices, based on abstract data structures for input, is revisited and where necessary modified. It is shown that the heart of these so-called tools consists of an input rule, in which the pattern of input actions satisfying the tool is specified. The input rule contains a tool expression, such that tool definitions are analogous to production rules in context-free grammars. These input rules, and the role of the input rule parser are examined in more detail especially with respect to their semantics. The revised model makes it possible to embed a complete program in a tool main which is automatically activated at run-time, thus obviating the need for read-tool or get-tool primitives. Several examples are presented showing the application of tools and the clarity and modularity of the resulting code. Also some implementation issues are discussed.
Keywords: computer graphics, graphics input, high-level input tools, interaction, input devices, graphics tools, programming constructs, abstract data structures, graphics language, input language
CR category: 8.2,4.20,4.22,4.32
It is recognized by many people that the way graphics input devices have to be programmed by graphics programmers is not at the level at which output functions may be handled. For the latter we typically may construct a two- or more level hierarchy representative of the logical relationships of basic picture elements, such as lines, dots, and text characters. Input devices on the other hand have to be programmed at a level very close to the hardware: typical for this is that we have to wait for events, attentions or interrupts, we read x and y registers of a Locator (e.g. a crosshair cursor) following some interrupt, etc. This status quo is for instance illustrated in the Status Report presented by the ACM Graphics Standards Planning Committee, GSPC [1], sometimes called the CORE report.
Several attempts have been made to define higher-level input devices [2,3,4], but none of them were really based on a hierarchy of input devices, with possibly an exception for the GSPC report which offers the association mechanism. The latter allows event tools to be associated with sampling tools. However it offers no naming facility so that the definition of arbitrarily high-level tools is not possible.
In an earlier paper [5] I have proposed a hierarchical way of constructing so-called high-level graphics input tools based on a set of basic input tools such as Clock, Pick, Button, Key, Valuator and Locator, all returning standard information (see table I). For ease of reference and because of substantial modifications we briefly recapitulate the essentials of the proposed model in the next section.
| device | info returned |
|---|---|
| Clock | void |
| Pick | string segname, int pickid |
| Button | int buttonnr |
| Key | char c |
| Valuator | real or int v |
| Locator | real or int x,y(,z) |
| Escape | void |
For computer graphics the first six primitives of table I are used as the lowest-level tools in the model. These basic tools do not play the role of axioms in the tool model but are instead the crude material from which other tools are built. They may therefore be extended any time this is judged appropriate. Different from the usual approach, a complete tool may be defined by the tool class and the information returned. For example Button stands for any button, but Button.(9) stands for button 9, Pick.("menu",5) stands for the lightpen pointing in picture segment menu at the picture element named 5, etc. In order to facilitate notation an information range may be indicated as follows: lowlim..uplim, e.g. Key.("a".."z"); the entire class T with some exceptions, say a and b, may be denoted as T.(-a-b) or even T.(-a..b), the latter tool meaning all T except the range a to b.
The Escape tool plays a special role which is discussed later.
We define a tool as a logical input device, which upon activation, returns information; it may also influence the status of the (graphics) program indirectly through side-effects. In general the tool consists of a series of lower-level tools, each with its own returned information and side-effects.
A tool definition consists of a name, formal parameters (optional), one input rule, a returns expression (optional), an optional tool body consisting of nested tools, statements, and local procedures, and finally an optional initialization statement
An input rule starts with the reserved word input, it is followed by an input expression, and ends with the reserved word end. An input expression consists of operators and at least one operand. The operands of the input rule are themselves tools. They may possess a parenthesized list of parameters (attributes). Tools may also indicate the desired returned information by means of a list of constants or variables in parentheses preceded by a dot.
For simple input expressions there are 3 operators: * ; + in order of precedence. Braces { and } may be used to override this precedence. The operator * is the Kleene star. It is used as a unary postfix operator indicating that the operand may be executed zero or more times before going on to the next operand. The ; operator is the sequencing operator: a;b means that a has to complete before b starts. The + operator represents exclusive selection: a+b means that either a or b, but not both, must be executed before proceeding.
We may use the input expressions to define arbitrarily complex input functions. The operands named in the input expression are either tools defined at the same or a surrounding block level in the program or else should be defined within the tool definition; in the latter case they have a strictly local scope. Direct or indirect recursion is forbidden; also a tool must not refer to a tool it descends from. Furthermore a tool definition may use one or more global variables, which have to be passed through a parameter list, as well as local variables.
More complex input expressions may be formed with the operators &, >, <, and $. a&b means both a and b have to be performed, but the order is irrelevant; ; they may even run concurrently. a>b means the same as a+b, but if a and b can both be executed then a takes precedence; the reverse holds for the operator <. The & operator has a priority between ; and + , but < and > have the same priority as the + operator. The operator ; is distributive with respect to + < >. No other operators have this property.
Yet another form of input expression is the conditional expression:
[<cond1>:<elem1>,<cond2>:<elem2>,...,<condn>:<elemn>,<elemelse>]
The conditional element is equal to some element for which the corresponding condition (toolswitch) is true (which element is selected is left open), if none are true elemelse is selected. The elemelse part is optional; if it is missing and all tool switches are false then the conditional expression is skipped by the parser.
A conditional input expression with k elements causes k input rules to be defined. On invocation all these rules are made available to the parser, however only those for which the toolswitch is true will be considered active by the parser. Toolswitches may however be changed as a result of e.g. a side-effect or an init statement. This will cause the corresponding rule to be marked active for the parser.
Conditional expressions may occur in combination with the unary postfix repetition operator $, as follows:
[<cond1>:<elem1>,<cond2>:<elem2>,...,<condn>:<elemn>,<elemelse>]$
which means that as long as at least one of the conditional elements is true then the entire conditional tool expression is repeated. Note that the <elemelse> part is missing here, since this would lead to infinite repetition. At different cycles in the repetition different elements may become eligible for selection, since an element selected may change one or more tool switches of other elements. When all conditions are originally false, then the tool (including repetition) is skipped altogether. The $ operator has the same priority as the operator *.
The returns expression starts with the reserved word returns, followed by the types and names of the values returned, and ends with end. The values may be directly produced by the operands of the input expression or by the local tools or procedures. In addition to this mechanism tools may also operate on the outside world by means of side-effects, i.e. changing parameters or the status of the display.
Finally, there is an initialization statement at the very end of the tool definition. It starts with the reserved word init and is followed by whatever variable or display initialization the tool definer wants to perform.
In this concept of tool, the central role is played by the input rules. There is a strong resemblance between a tool definition in terms of an input rule and a production rule in grammars, particularly context-free grammars. A tool is executed when the syntactically correct input sequence is present. Since normally a number of tools have been defined (see below) there also exists a number of input expressions. Any input symbol of an input sequence will have to be matched by a parser against the active input expressions. An input sequence is syntactically correct when it matches one of the outstanding input expressions. The parser has to make a distinction between event and sampling devices. If a sampling operand occurs in an input expression, the parser will usually satisfy it, that is sampling will occur. The exception is when a particular range of values is requested in the input rule, and the sampled values do not fall within this range.
Of the seven basic tools we mentioned in Sec. 1 only one, namely the Clock may have a parameter. This integer parameter indicates the time interval which the Clock is counting down. Thus Clock provides an infinite number of interval timers. By convention if Clock is used without parameter it stands for the infinitely long interval.
Basic input tools, e.g. a Valuator which returns an integer value x, are supposed to be defined in a prolog to the program. In order to define name and type of the variables returned by a basic tool, and also by all predefined tools in a library, we use a declarative definition (which differs from a definition in that there is no input rule and no tool body) of the following form, e.g.:
tool Valuator; returns
int x end Valuator;
An init statement may also be added; this should be done with care, since it will override the original init statement. If no naming conflict occurs the integer variable may be referred to as x, otherwise the qualified name Valuator.x must be used; this of course holds for all higher-level tools as well.
As a simple example let us define a tool keyboard built on the basic tool Key. Some people consider the keyboard itself to be a basic tool, which in our model makes very little difference, because the definition is then replaced by a declaration, so that the program assumes that keyboard is either defined in a program prolog or else present in a tool library (see Sec. 5):
tool keyboard =
input [proceed :s]$ end;
returns string buf end;
tool Key; returns char sym end Key;
tool s = input Key end; # CR is mnemonic for return key #
if Key.sym=CR then proceed: = false
else buf +:= Key.sym fi # concatenate sym to buf #
end s;
init toolsw proceed:=true; buf="" # initialization #
end keyboard;
Subsequently we present an example of a composite tool that reads in a signed or an unsigned integer string from the keyboard and returns the integer representation of the string:
tool number = input {digit* + sign;digit;digit*}; Key.R) end;
returns int integer end;
string xalpha;
proc convert = (string numerical) int:
( # conversion code #
);
tool Key; returns char c end Key;
tool sign = input plussign + minsign end;
tool plussign = input Key.("+") end
end plussign;
tool minsign = input Key.("-") end;
xalpha := "-" #tool body mminsign #
end minsign;
end sign;
tool digit = input Key.("0"".."9") end;
xalpha : = xalpha+Key.c # append c to xalpha ##
end digit;
integer := convert (xalpha)
init xalpha = "" # tool body number #
end number;
This is an example of a hierarchy of three tool levels. At the highest level we see that the tool number is satisfied by either zero or more digits (unsigned number) or a sign followed by at least one digit (signed number), followed by a carriage return. Notice that a single CR satisfies the tool. On the second level the tool sign is constructed from the tools plussign and minsign. Their operation is not identical: plussign reads the plus sign but does not do anything with it, while minsign assigns the minus sign to the (still empty) string xalpha. Once a sign has been input, at least one digit should follow. Every digit read is appended to xalpha. When the outermost input expression (of tool number) is satisfied the corresponding toolbody is executed. Here this means that the completed string xalpha (possibly empty) is converted to an integer. The advantage of the tool approach is here particularly evident. The tool does not only perform the input function properly, it also does the checking for illegal characters (which it throws away) and finally the conversion. As far as the tool user is concerned this tool really reads an integer number and presents the value (and location) of it to him, which is all he is usually interested in.
A complete program consists of a tool main to which all tool definitions and declarations are internal. When the program begins to execute the input rule of tool main is automatically made active. This causes instances of the tools occurring in the input rule to be created, substituting possible parameters with their actual values. The tool definition and instance are now passed to the input rule parser. This module constructs a parse tree of the active input tools in terms of the basic tools while at the same time retaining the grouping of these tools in higher-level tools. For example imagine a tool A with input rule
inputx; {B;t+s;q;C};p end
where p,q,s and t are basic tools, tool B has an input expression a;D;b, while C has e;f+g and D has r. The parse tree looks as follows:
When this tool is activated the first thing that happens is the execution of the init statement of tool A, and if present of tool x. Assume the parser now receives an input action. If this does not come from x it does not match so it is thrown away. If it is x the parser can go two ways, either to B or to s. It therefore executes the init statements of both B and (possibly) a and s. If subsequently s and q are matched, the init statements of C, e and g are executed. After the reception of either e followed by f, or g, the tool C is matched, which means that the tool body is executed and the returns information made available. The parser then initializes p. When finally p is received the complete tool A is satisfied, which results in execution of the tool body of A and the making available of A's returns information.
In addition to initialization the init statement is very useful as a prompting function. In order to guide the user through a possibly complex series of input rules the graphics program may issue prompting messages indicating the user input actions possible in any stage of the program.
Immediately following a user input action the system should acknowledge the input. This can be done by various well-known means such as lighting a depressed button, or blinking a selected image element, etc. When an incorrect input has been received the system should return a negative acknowledgement such as a question mark, or sounding an alarm.
Once the input parser has entered a particular subtree it only handles input actions matching this subtree. Input actions from sources not occurring here are discarded and so are input actions which happen out of sequence. This may have serious consequences. Suppose we have a tool T with input rule A;B+A;C. The user has completed A and B, but realizes that he should have done A;C. Since B has been matched, its side-effects have been executed. If the user wants to recover from this error he will have to execute his own cleanup procedures to restore the display and the program to the status before the tool T was begun. He may specify this in the toolbody of the so-called Escape tool relevant to this program context. This tool should have been defined earlier in a manner analogous to the definition of other high-level tools, e.g.
tool Escape = input Pick.("menu",cancel) end
end Escape;
In the case of conditional repetition of one or a group of tools, the init statement (if present) of each tool will be executed repeatedly. For a tool followed by a Kleene star, not only the init statement of the tool itself but also the inits of the next eligible tool(s) are executed.
Ideally a program should begin with making an initial tool (something akin to an identity tool) available. This tool should be activated automatically at run-time. We do this here by embedding the entire program in a tool main. When the program starts execution the init of this tool is performed and the parser is invoked to handle the input rules. From then on the program enters one of the tools defined at a lower level and so on. To show this an almost complete demonstration program is presented. It was derived from a FORTRAN program in the GPGS [6,7] User's Tutorial (Caruthers, L.C., and Van Dam, A., General Purpose Graphic System - User's Tutorial, University Nijmegen, 1975) and uses subroutine names as actually defined in GPGS. In addition to the basic tools Button and Pick it employs a higher-level tool number defined in Sec. 2.
The program displays on frame 1 a curve consisting of a set of points connected by straight lines. The user has three choices: he may delete points from the curve, go to frame 2, or stop the program. On frame 2 there is a display of a list of the data coordinates, the array index of the coordinate, and an indicator whether the point had been deleted. The user may restore points by typing in the index of the point to be restored from the keyboard. At any time he may choose to return to frame 1 to inspect the results, or just as in frame 1, stop the program.
# Interactive plotting from GPGS User's Tutorial pp. 92-110 #
tool main = input [first:frame1,frame2]* ; stop end;
[1:50] bool mark, [1:50] real x,y;
tool Button; returns int k end Button;
tool Pick; returns int seg,pointid end Pick;
tool number; returns int value end number;
tool frame1 = input deletepts* ; goframe2 end ;
tool goframe2 = input Button.(2) end ;
first :=false ;
unplot graph;
unplot fr1 msg;
plot fr2 msg;
plot list(x,y)
end goframe2;
tool deletepts = input Pick end ;
unplot graph;
mark(Pick.pointid):=false;
plot graph(x,y)
end deletepts;
end frame1;
tool frame2 = input restorepts* ; goframel end ;
tool goframel = input Button.(1) end ;
first: =true ;
unplot list;
unplot fr2 msg;
plot fr1 msg;
plot graph(x,y)
end goframel;
tool restorepts = input number end ;
unplot list;
mark(number.value): =true ;
plot list(x,y)
end restorepts;
end frame2;
tool stop = input Button.(16) end ;
end stop;
rlsbuf(buf); rlsdev(3)
init nitdev(3); nitbuf([1:1000] int buf,1000);
for i to 50 do read(x[i],y[i]); mark[i]:=true
od ;
plot graph(x.y); plot fr1 msg; toolsw flrst:=true
end
The previous application examples of the present high-level tool mechanism show an extra benefit to be derived from the way tools are defined. Several of the tools have a more general scope than just the original program they are conceived for. This multiple applicability is exploited by placing desired tools in so-called tool libraries. Programs may then utilize these tools by making a macro-type reference, the declarational definition, to them.
Tool libraries may also be used as private libraries in order to keep user programs structured, uncluttered and easily understandable. Just like subroutines and macros, tool definitions and especially remote tool definitions enhance the modularity of graphics programs.
In addition to this tool libraries may also be used to simulate tools which are not present on the available display device. In this way one keeps the flexibility of a more powerful device without burdening the device driver with software for simulation. At the same time we make it possible for a single program to be compatible between graphics devices by running it under appropriate tool libraries.
The following example shows the simulation of a lightpen for a device with at least 1 Button, a keyboard, and a Locator. The tool uses the keyboard device defined in Sec. 2.
tool Pick =
input begin ; [miss:get]$ end;
returns string segname,int pickid end ;
tool begin = input keyboard.("LP") + keyboard.("lp") end
end begin;
tool get = input Button; Locator end ;
if find(Locator.x,Locator.y,segname,pickid)
# given x,y this rtn finds segname and
pickid of primitive #
then miss: = false
else create segment("MSG");
moveabs2(0.0,0.01);
text("LIGHTPEN MISSED");
close segment
fi
end get;
init toolsw miss: = true
end Pick;
As we see this tool Pick not only simulates the lightpen, it also issues a message in a situation of no-hit. The keyboard is not strictly necessary but entering the string "LP" (or "lp") makes the user more conscious of the fact that he is going to simulate the Pick device.
This example is similar to the way GPGS simulates the Pick on a storage tube. The significant difference is that there the simulation is part of the device driver and therefore rigidly fixed. In contrast, our tool definition method gives the user complete freedom, yet allows some default simulation to be stored in the library.
At the time of writing this report we are in the final stages of a first implementation of the tool model. This point has been reached, but not without problems. The implementor of the graphics input tools is faced with several crucial issues, sometimes dilemmas. We distinguish four main points of debate, viz.
In the sequel we shall pay attention to each of these points, and indicate how we solve them in our implementation.
From the syntax of the graphics tools it has become clear that this method is more powerful than the traditional approaches, which are in fact finite state approaches leading to a regular language. Our method offers at least a context-free grammar, but in fact the tool parameters and returns information make it potentially equivalent to even more powerful grammars. So the problem of parsing becomes paramount. A consoling thought is that, notwithstanding the formal power of the language, the actual input language used in any given program will be simple, because it is generated by a very limited number of productions. Therefore several brute force parsing methods may possibly be applied to advantage.
As a simple illustration of some of the parsing problems that might crop up let us look at some example input expressions, say a;b+a;d. Here we simply remove the ambiguity by factorization: a;{b+c}. Now take A;c+a;d, where the input expression of A is equal to a. This example is at first appearance ambiguous because tool a cannot be factored out. The reason is that A might have a tool body that has to be executed once the input rule for A, id est a, is matched. However, as soon as input c or d arrives we know which term ought to be matched, but this requires look-ahead of 1 factor. Even if we do this look-ahead what do we do with the tool body of A. It appears that we have to suspend it until c or d arrives. These problems of course accumulate when we allow look-ahead of k factors (k>1). It seems highly undesirable to allow suspended execution of several tool bodies, or perhaps suspension is even impossible when one tool body produces the value of a parameter for a next tool.
Tools with returns statements also pose serious problems. Imagine the case A.(value). We first have to execute the toolbody of A in order to determine the returned value. Only then do we know whether this is equal to value or not. In the meantime we may have changed the status of the display using an incorrect value. A similar, but even more serious problem is caused by parametrized tools.In our implementation we have imposed the following restrictions on the model: we only do LL(0) parsing, id est we parse from left to right and the leftmost, term is expanded, with no look-ahead. Furthermore to get around the problems with returns information and parametrized tools we have dictated that only one invocation of a parametrized tool may be present at any given time; in other words A(parm1 )+A(parm2) is illegal but A(parm1 );B+C;A(parm2) is all right.
Extending the model to a full graphics language is the ideal goal but it requires that a lot of effort be put in graphics output primitives and last-not-least in a compiler or interpreter.
An extendable language is a second-best solution but it depends on what is already available in the language and how powerful the extension constructs are. We are of course looking for a language with abstract data structures. However very few of even remotely popular languages offer them, with a possible exception for Simula.
Extension via the subroutine approach is something which is in principle possible but of which we think that it should be avoided because it does not add to the clarity of the language and would furthermore destroy a good deal of the modularity inherent in our model.
Our present implementation is controlled by one more parameter, namely the available languages on our machine configuration. Our local computer is a PDP under Unix which only offers Fortran, Pascal, Algol68, and C. For various reasons we have chosen to implement our model as a C extension, which through a preprocessor is converted into C code. At the university level we also have access to a large IBM computer with among other things a Simula67 compiler. For this compiler an implementation effort has recently begun. A major impetus for a Simula implementation is the presence of classes, or abstract data structures, in this language.
Many potential ambiguities can be checked at compile-time. These ambiguities should be so indicated but should not prevent object code from being produced, because potentially ambiguous branches of a program may not even be entered at execution time. Naturally these programs cannot be correct in a rigid sense, but they may still be usable, a requirement which is more important for interactive programs than for batch programs.
Other ambiguities only show at run-time, for example for parametrized tools or tools with returns information. These problems can only be dealt with dynamically. But even then the adage should be to keep the program running and if possible give the user guidance to avoid the problems (or in the future to dynamically alter input expressions?).
In our implementation we have a bit of each of these correctional methods. Removable ambiguities are handled by an optimizer and conversational modules inform the user when a dynamic ambiguity is encountered before it is active so that he may avoid it.
It is our opinion that an implementation of graphics input tools should not burden itself with lower-level graphics support, at least not in a first implementation. We would cloud the issues at hand if we were to get involved with problems such as what is basic support, how about device independence and other murky backwaters. It appears best to adopt an existing basic support package, preferably one that is close to (a subset of) the proposed CORE graphics standard [1].
Our implementation uses a subset of GPGS as basic support, firstly because it influenced the CORE proposal to a considerable extent, and secondly because we have a C (and also Algol68, Fortran and PL/I) interface to GPGS.
1. ACM-Siggraph GSPC, First report on graphics standards, Proc. ACM-Siggraph, 1977, San Jose, Cal., USA
2. Foley, J.D., and Wallace, V.L. The art of natural man-machine communications, Proc. IEEE, Vol. 62,4, 1974, pp. 462-471
3. Deecker, G.F. P., and Penny, J. P. Standard input forms for interactive computer graphics, ACM-Siggraph Computer Graphics, Vol. 11,1, 1977, pp.32-40
4. Wallace, V.L. The semantics of graphic input devices, Proc. ACM-Siggraph, 1976, Miami, Fla, USA, pp. 61-63
5. Van den Bos, J. Definition and use of higher-level graphics input tools, Proc. ACM-Siggraph, 1978, Atlanta, Ga., USA, pp. 38-42
6. Caruthers, L.C., Groot, D., Hermans, E., Van Dam, A., and Van den BDS, J. GPGS - General purpose graphic system, Proc. ACM - International computing symposium, 1977, Liege, Belgium, pp. 411-416
7. Caruthers, L.C., Van Dam, A., Van den Bos, J. GPGS - A device-independent general purpose graphic system for stand-alone and satellite graphics, Proc. ACM-Siggraph, 1977, San Jose, Cal., LEA, pp. 112-119