The evolution of interactive graphics programming bears a strong resemblance to the history of programming languages. Initially, there was a range of devices (or machines) with their own peculiarities and systems were designed to maximise the use of the facilities available (for example, the ARITHMETIC IF statement of FORTRAN or the cursor input of GINO-F). This assembler language age suffered from the standard problems of lack of portability, difficultly of modification and impossibility of debugging in a satisfactory manner.
Over the years, efforts have been made to formalise the design process. Standard techniques exist for lexical and syntactic analysis in compilers. Optimisation algorithms are defined which satisfy a range of machine architectures. In graphics systems, menu handling hierarchies have been designed using a finite state approach with the available input devices being mapped onto a set of distinct virtual devices. This corresponds closely with the lexical analysis phase of a compiler and the tendency has been to look to language theory and compiler design for a lead when specifying more complex graphical systems. For example, systems have been designed with an initial stage generating lexemes (or input primitives) which are then passed to a syntax analyser which parses the input and automatically generates the required action.
This approach has been described by Sancha [1]. In broad outline his approach provides operations to associate a text string with each input primitive. When that primitive is activated, the associated string is appended to the input stream of the syntax analyser. The input language is very free from device dependencies and can be mapped onto virtually any selection of input devices.
Bo and Wessel [2] have described a system (GRANADA) for command language description based on a syntax analyser. This system has no direct connections with graphical command languages, but could be envisaged as analysing the input stream from the kind of system described by Sancha. The authors of GRANADA recognise that a command language ought to be adaptive to suit the users level of competence, a criticism frequently aimed at dialogue systems which insist on guiding the user through the problem one question at a time when after a little experience the user will want to supply answers to a considerable number of questions simultaneously. GRANADA provides a mechanism to prompt the user should he omit essential parameters when specifying a command. A similar approach has been followed in at least one recent Job Control Language (for ICL 2980). The limitation of this kind of system is that it is statically rather than dynamically adaptive, ie the system cannot adapt to the users mode of operation by studying the interaction sequences he uses.
Many systems cry out for the ability to modify themselves depending on the pattern of inputs from a particular user.
At this stage it is worth considering whether language theory is the right discipline to look to for guidance. We have a multi-stream input of information which is arriving at the system. We wish the system to have sufficient intelligence to display simple-minded skill acquisition in the response.
A particular discipline orientated towards problems of this type is that area of AI research interested in the simulation of human behaviour, human protocol analysis and robot learning. Such systems are categorised in much the same way as interactive graphics systems. Stimuli or inputs arrive at the interface from a variety of devices or sensory channels. Actions need to be taken as a result of such stimuli and, to some extent, the appearance of stimuli in regular patterns should affect the system's response to future stimuli.
A particular methodology, Production Systems [3], for modelling such systems has become of great importance over the last few years. The aim of this paper is to explore how Production Systems could be used to define interactive dialogues and show the advantages they have over current formalisms.
Descriptions of production systems and their uses are given in Newell [3], Davis and King [4] and Anderson and Gillogly [9]. The main components of a system are shown in figure 1. In any time interval, input stimuli arrive in STM (Short Term Memory) and are acted upon by CPU (Central Processing Unit) depending on the contents of LTM (Long Term Memory). The result of these actions may be changes to STM and LTM as well as responses to the environment.
Many different mechanisms have been proposed for the selection of items from LTM to be obeyed and the effect they have on the contents of STM. Frequently the same results can be obtained by different mechanisms. The system described below is just one possibility. It is used for illustration only.
All input to the system appears as tokens in STM which are usually unordered in time - all items in STM have equal value irrespective of their origins. LTM contains a set of Production Rules which define the actions to be taken depending on the contents of STM. A typical production is:
<input stimuli> ⇒ <response><output stimuli>
The meaning of the production is that if the input stimuli are present in STM then the specified response takes place and the output stimuli overwrite the current contents of STM. Thus, in each time interval, stimuli may arrive in STM both from the outside world and as output from the previous time interval. The CPU examines the set of productions in LTM in order to find one or more productions whose left hand sides exist in STM. A subset, possibly all, of these productions is obeyed which results in a certain set of actions being generated. The various approaches to Production Systems depend on the particular application area and frequently differ in the implementation, for example:
Newman [6], in an early paper, gives a state-diagram representation shown in figure 2 for a program to draw a rubber band line. A pushbutton (B1) is hit initially to enable the tracking device. This is then moved to the starting position of the line and a second pushbutton (B2) is hit. Movements of the tracking device now cause a rubber band line to be drawn to the current position until a third pushbutton (B3) is hit. This establishes the end point of the line.
This could be modelled as a Production System with stimuli B1, B2, B3 and X, where X defines the coordinate pair of the current position of the tracking device. Hitting a pushbutton causes the particular stimuli to appear in STM, while X, the current coordinate position of the tracking device always appears in STM each time interval as long as the tracking device is enabled. There is an analogy here between interrupts and polling.
A possible set of production rules in LTM would be:
B1 ⇒ <enable tracking device> X ⇒ <display cursor> B2 ⇒ <store start point> S X ⇒ <display rubber band line> B3 ⇒ <store end point>
Any stimuli matched in STM are removed so that, in the next time interval, the only stimuli in STM are the ones received from the environment and those written back into STM in the previous time interval. There is no distinction between internally and externally generated stimuli. The method chosen to select productions has a significant bearing on the behaviour of the system. Suppose stimuli S and X are present in STM. The conditions for rules 2 and 4 are then satisfied. If both rules are obeyed, a rubber band line will be drawn to the current position indicated by the tracking device and the cursor will be displayed at that position.
A similar problem is posed by stimulus B3. If the operator follows the sequence given above, one may expect that at the start of some time interval stimuli B3, S and X will be present in STM. To store the end point, the production:
B3 ⇒ <store end point>
must be obeyed; the rubber band line to the final tracking device position may or may not be drawn depending on whether this is the only production obeyed or the fourth production is obeyed also.
We will assume here that rules are ordered in LTM and that a single production rule is obeyed in each time interval (that with highest priority). For this example, the ordering in descending priority would be:
B3 ⇒ <store end point> S X ⇒ <display rubber band line> S B2 ⇒ <store start point> S X ⇒ <display cursor> B1 ⇒ <enable tracking device>
In the production system defined above, the states of the system are less clearly defined than in the finite state model. A production set equivalent to the finite state model would be:
SI Bl ⇒ <enable tracking device> S2 32 X ⇒ <display cursor> S2 32 B2 ⇒ <store start point> S3 S3 X ⇒ <display rubber band line> S3 S3 B3 ⇒ <store end point> S1
The advantage of the first production system is that it is less rigorously defined than the finite state system and has a sensible meaning if pushbuttons are pressed in a different order. For example:
B1 X X X B3 X X B2
could be a valid set of input stimuli. It would define the line by a cursor movement to the end point and press B3 followed by a cursor movement to the start position and press B2. The example is rather contrived in as far as the disabling of the tracking device is not clearly defined. However, it does indicate the potential of the production system approach.
One major advantage of the production system approach is the ease with which distinct interactions can be amalgamated. Consider a second example where a timer is to be displayed to allow the user to clock particular events. Hitting the first pushbutton causes a clock to appear. A second pushbutton hit starts the interval timer while a third stops the timer to allow the elapsed time to be recorded.
This example has a similar finite state representation to our first example (see figure 3)- It can be defined as a set of production rules as follows:
B4 ⇒ <enable clock> T ⇒ <update clock> B5 ⇒ <start timer> S4 SU T ⇒ <update clock and timer> S4 B6 ⇒ <stop timer>
Notice that a time stimulus, T, has been introduced which it is assumed will appear in STM at regular intervals equivalent to clock ticks.
The rubber band line definition and interval timer are two independent processes. The user may wish to have both functions in operation at the same time. For example, he might wish to initialise the clock in the middle of the line drawing. The number of states proliferate as can be seen from figure 4.
However, to amalgamate the two actions in a production system, all that is necessary is to amalgamate the sets of productions:
B3 ⇒ <store end point> S X ⇒ <display rubber band line> S B2 ⇒ <store start point> S X ⇒ <display cursor> B1 ⇒ <enable tracking device> B4 ⇒ <enable clock> T ⇒ <update clock> B5 ⇒ <start timer> S4 SU T ⇒ <update clock and timer> S4 B6 ⇒ <stop timer>
The assumption is made that stimuli remain in STM until a production is executed that matches the stimulus.
An interactive graphics system should not be passive. It should react to the user and respond to any patterns of interactions that emerge by anticipating user actions. Consider, for example, the simple trajectory game where the operator has a cannon and he attempts to hit a target protected by a wall. At each shot, he can vary the muzzle velocity and angle of fire (see figure 5).
Before each go, the user indicates whether he is inputting a new muzzle velocity or angle of fire by pressing either pushbutton B1 or B2. The user has a number of ways in which he can input the new value:
By hitting B3, B4 or B5, the user determines which method of input he requires. Finally, hitting B6 causes the next shot to be fired. It is assumed that a lightpen hit, L, defines the potentiometer value to be used. Keyboard inputs are divided into the two classes, I for characters and Z for the terminator. The production set is then:
B1 ⇒ <initialise velocity> V B2 ⇒ <initialise angle of fire> F B3 ⇒ <invitation to type> T B4 ⇒ <display potentiometer> P B5 ⇒ <display angular potentiometer> A B6 ⇒ <fire> I ⇒ <ignore> Z ⇒ <ignore> T I ⇒ <accumulate value> V T Z ⇒ <store velocity> F T Z ⇒ <store angle of fire> V P L ⇒ <change velocity by increment> V A L ⇒ <error> FPL ⇒ <change angle by increment> F A L ⇒ <store angle of fire>
Note that the STM structure used here is such that only matched stimuli are deleted from STM after each time period. Thus if the operator elects to supply a velocity value from the keyboard, the stimulus V will remain in STM whilst the value is accumulated by rule 9. This is necessary to decide when the terminator is received whether to obey rule 10 or rule 11.
It is likely that a particular user will tend to concentrate on a particular input method for defining the velocity and, possibly, a different method for the angle of fire. For example, his operations might fall into the general format:
B1 B4 ... B2 B5 ... B6
Eventually, the pushbuttons B4 and B5 should not be necessary. The system should learn the connection between B1 and B4, and between B2 and B5.
A number of systems allow the production set in LTM to be modified depending on the sequence of productions obeyed. Consider, for example, the following set of rules for creating productions:
A ⇒ <x> B ⇒ <y>are obeyed in consecutive time intervals then generate a production:
A ⇒ <x> Band add it to the production set at the bottom.
The effect of this set of rules is to produce productions that attempt to predict future stimuli. If such a prediction is consistently correct, the original rule is eventually replaced by the predictive rule. Skill acquisition can then be achieved by a new rule:
A ⇒ <x> B and B ⇒ <y>are obeyed in consecutive time intervals with B appearing as an input stimulus, generate a rule:
A -⇒ <x> <y>and add to the production set.
In the example given above, the two rules obeyed in consecutive time intervals will frequently be:
B1 ⇒ <initialise velocity> V B4 ⇒ <display potentiometer> P
This will lead to the creation and eventually the promotion of a rule:
B1 ⇒ <initialise velocity> V B4
which will be obeyed in place of the original rule. Further use of the two rules will result in the creation of a rule:
B1 ⇒ <initialise velocity, display potentiometer> V P
The system eventually learns that B1 is always followed by B4.
Skill acquisition of this type must also be capable of deconditioning. This can be achieved by providing an additional input (pushbutton B7, say) which indicates that the wrong action has been taken. In this case, the appearance of B7 will cause the last production obeyed to be demoted. After a time, the system returns to its original state except that additional productions still exist in the list so that some memory of the skill is retained and will be that much easier to condition to a second time.
We now outline a section of a program for defining character fonts and how this might profit from formulation as a production system. The program is presently defined in the PIGS system [7] using a finite-state approach.
The state system is defined on three levels, each level associating different meanings to the pushbuttons used to control state transitions. At the top level, the program is initialised, on the middle level individual characters are accessed, on the lower level a particular character (selected at the previous level) is defined or manipulated. The push button controls are as follows:
BUTTON TOP LEVEL MIDDLE LEVEL BOTTOM LEVEL B1 XFIDUC GET CHAR DELETE ALL B2 YFIDUC PUT CHAR DELETE/INSERT B3 INIT DOTTED/NOT DOTTED/NOT B4 DISPLAY FONT SEEN/NOT B5 DOWN DOWN Tracking cross control B6 QUIT UP UP
Characters are defined on a mesh WIDTH units wide and HEIGHT units high. When the program is entered B3 initialises the program and requests the user to type values of WIDTH and HEIGHT on the display keyboard. B1 and B2 enable the mesh to be broken up in the X and Y directions by allowing lines at regular intervals to be intensified. After either button is pushed, the user is invited to type a number (N) which results in the intensification of every Nth vertical or horizontal line. B5 changes the state of the program to the middle level, new meanings then being assigned to the buttons. B6 terminates the program. Within the middle and lower levels a mesh is displayed on the screen and the current character is displayed with reference to this mesh. In addition, three small copies of the character are displayed at 1, 2 and 3 times the basic raster size. Thus a character defined on a 32 × 32 grid will be displayed having height and width 32, 64 and 96 rasters respectively. Characters are defined by a sequence of vectors each of which may be visible or invisible.
Pushbuttons on the middle level operate as follows. Pushbutton B1 requests a number to be typed on the keyboard. This number identifies the position of the character within the font. If a character with this identifier has already been defined the character definition will be displayed on the grid for further manipulation. Pushbutton 2 stores the current character definition in the font.
Pushbutton 3 determines whether the invisible lines within the character will be displayed as dotted lines or not shown at all. Pressing pushbutton 3 toggles this option.
B5 changes the state of the program to the lowest level, B6 to the top level.
p>At the bottom level B1 throws away the current character definition and the program expects a new definition to commence. B2 defines the current mode of operation ie whether a vector is to be inserted into the definition or deleted from the definition. B3 toggles the invisible vector display option as in the middle level. B4 defines whether new vectors to be added to the definition are visible or invisible. B6 returns control to the middle level.B5 activates the tracking cross, used to insert vectors in the character definition. The action is similar to that described in section 3 for drawing a rubber band line. Hitting B5 causes the tracking cross to appear at the free end of the last vector in the definition (or the origin if no vectors have been added). The cross is then moved using the light pen to the vertex of the mesh where the next vector is to end (the vector may be displayed as a rubber band line during this operation). Once it is positioned correctly B5 is hit again, the tracking cross is removed from the screen and a full line will be displayed on the grid and in the character definition if the vector is visible. If the vector is invisible, a dotted line will be displayed on the grid if the DOTTED option has been selected.
An example of the operation of the system is the sequence of actions required to define the character V, starting at the middle level.
The state transition network of this system is shown in figure 7. Note in the dialogue above that there are a number of redundant actions, hitting B4 for example is always followed by hitting B5. Note that setting DOTTED mode is in some sense a global action, available in this case at two levels. In general there are actions falling into this category, for example an action to zoom in on a picture or rotate a 3D object to get a better view, which need to be accessible from a large number of states of the system [8]. Such actions are poorly catered for in the finite-state approach. For the operator it can be exceedingly tedious to effect a return from such an action to the state the system was in previously.
The problem is indicated by the difficulty in the system described of changing grid line enhancement whilst at the bottom level. The only way possible is to return to the top level (B6 hit twice) then select a new enhancement value by hitting B1 or B2, then returning to the bottom level by hitting B5 twice. A similar problem would occur if the system had an option to select the scale at which the character definition is displayed (in addition to the built-in values of 1, 2 and 3 times the grid size).
A possible representation of this system as a set of productions is:
B1 ⇒ <initialise XFIDUC> X
B2 ⇒ <initialise YFIDUC> Y
I ⇒ <collect number>
X Z ⇒ <set XFIDUC>
Y Z ⇒ <set YFIDUC>
B3 ⇒ <initialise WIDTH> W
W Z ⇒ <set WIDTH> H
H Z ⇒ <set HEIGHT>
B4 ⇒ <display font>
B5 ⇒ <display middle level buttons> S1 D1
B6 ⇒ <exit>
G Z S1 ⇒ <get character> S1
S1 B1 ⇒ <initialise GETCHAR> G S1
S1 B2 ⇒ <put character and get next> S1
D1 S1 B3 ⇒ <display dotted lines> S1 D2
D2 S1 B3 ⇒ <remove dotted lines> S1 D1
S1 B5 ⇒ <display lowest level buttons> S2 I V
S1 B6 ⇒ <display top level buttons>
S2 B1 ⇒ <delete all> S2 I V
I S2 B2 ⇒ S2 R
R S2 B2 ⇒ S2 I
D1 S2 B3 ⇒ <display dotted lines> S2 D2
D2 S2 B3 ⇒ <remove dotted lines> S2 D1
V I S2 B4 ⇒ S2 N I
N I S2 B4 ⇒ S2 V I
V R S2 B4 ⇒ S2 N R
N R S2 B4 ⇒ S2 V R<
I S2 B5 ⇒ <enable tracking> S2
X ⇒ <display line> S2
X S2 B5 ⇒ <draw line> S2
R S2 B5 ⇒ <enable lightpen> S2
L S2 ⇒ <delete line> S2
S2 B6 ⇒ <display middle level buttons> S1
Note that these rules have to be ordered to ensure that the appropriate level action is selected for each button. This representation is deliberately forced to use only six buttons and maintain the three command levels of the previous system to illustrate a point. Note the use of stimuli S1 and S2 to represent the middle and bottom command levels, whenever stimulus S1 is present in STM the system is in the middle level, S2 present and the system is in the bottom level.
The modes SEEN/NOT SEEN, DOTTED/NOT DOTTED, INSERT/DELETE can also be represented by stimuli (V/N, D1/D2, I/R). These can be used to effect the flow of control in the system, but as Davis & King point out [4] this can get very involved when the control flow is complex and states of the system are very well defined.
If we were to allow the introduction of more push buttons into the system then global actions can be very readily added. For example, we might define B7 to mean request new scale for character display and display character. This could be very easily done by adding a production of the form:
B7 ⇒ <request scale factor and display character>
This is accessible at any time and in any state of the system.
Skill acquisition can be readily applied to this system. For example, as noted above in the example dialogue, a hit to B4 is generally followed by a hit to B5, at the bottom level. This involves the productions:
V I S2 B4 ⇒ S2 N I I S2 B5 ⇒ <enable tracking> S2
The following rule will be generated and will eventually be preferentially obeyed:
V I S2 B4 ⇒ S2 N I B5
Note, however, the undesirable consequences of the system recognising that a hit to B5 is followed by a second hit to B5, after a variable time delay.
The argument can be taken a stage further by examining the likely initial dialogue starting at the middle level:
hit B1: input number associated with character to be defined hit B5: down to lower level
If the system can condense these actions and generate a production of the form:
S1 B1 ⇒ <get char> S1 B5
the need to hit a button to change state can be eliminated. The system can learn when a state change is likely, and perform the necessary menu change automatically.
The aim of this paper has not been to provide a rigorous formulation of production systems as applied to interactive systems design. However, the examples are intended to show that production systems could be used to provide a formulation which is more flexible than the standard finite state model. It can be made to adapt to a particular environment and it is particularly effective in a situation where a well-defined sequence of inputs is unlikely.
1. T. Sancha, Private Communication.
2. T. Wessel and K. Bo, 'GRANADA, A System for Command Language and Data Description1, RUNIT Report (1976)
3. A. Newell and H. A. Simon, 'Human Problem Solving', (Prentice Hall, 1972)
4. R. Davis and J. King, 'An Overview of Production Systems', Stanford University Report STAN-CS-75-524 (1975)
5. M. S. Rainford, 'Early Cognitive Development: A Theory and a Computer Model', Ph.D. Thesis. Brunei University (1977)
6. W. M. Newman, 'A System for Interactive Graphical Programming', Proc Spring Joint Computer Conference (1968)
7. W. D. Shaw and J. R. Gallop, 'PIGS: A Command System for Interactive Graphics', Interactive Systems, ONLINE 1975, 361-367
8. G. A. Butlin, 'Techniques for Processing Interactions in FORTRAN', in CAD Systems (Ed J. J. Allan, North-Holland 1977) 35-60
9. R. H. Anderson and J. J. Gillogly, 'RAND Intelligent Terminal Agent: Design Philosophy', RAND Report No R-1809-ARPA (February 1976)