A formalism is presented here which permits to define completely and unambiguously interactive programs: the formal dialogue systems. Initially developed for alphanumerical dialogues, it is here extended to graphical dialogues with graphical interactions and display. The formal specifications of programs which are obtained are independent of any physical implementation, terminal and software, and give facilities for the verification of programs.
Independence of graphic software and programs from computer and display systems is considered as a most important point for the development of feasible and low cost computer graphics. There has been many attempts to standardize display functions, and it can he thought that a consensus will be eventually reached.
Standardization of interactions is not yet within reach. It can be explained by the fact that we lack the necessary concepts for it: we do not know how to specify precisely an interactive program and we lack the appropriate means for modelling it, whether only alphanumerical interactions are used or whether there are full graphical interactions.
A method for describing the semantics of interactive languages and programs is needed which could serve as a reference independent from any implementation, and therefore insure the portability of the given languages and programs. It is a prerequisite for obtaining a reasonable standardization.
We present herewith an attempt to define formally the semantics of an interactive program, which had its origin in recent works by KUPKA (1972 and 1973) about the definition of conversational languages. Research is now carried on about the extension of these concepts to graphical interactions and their experimentation on CAD programs.
We will here only outline the main ideas of the theory and give a short view of its application. More details may be found in a recent thesis by QUEINNEC (1978).
Dialogues considered here are deterministic and single user. The formalism might be easily extended to nondeterministic dialogues. Main problems lying on nondeterministic dialogues are of a different domain (artificial intelligence for instance), but this formalism certainly could help to define and program such dialogues once the appropriate nondeterministic functions have been defined. Similar conclusion can be given in the case of several input streams for the same programs: there are well known techniques (semaphores ...) to deal with multi-users programs which should be possibly used in connection with this formalism.
We will consider in this paragraph only alphanumerical dialogues, as it happens for instance through a keyboard.
The idea is to define a conversational program by two relations on sequences of inputs: the first one (š) specifies sequences which lead the program to the same state, the latter one (Ÿ) characterizes sequences for which the final outputs are equal.
The two symbols used have been replaced as it was not possible to find such symbols on modern fonts.
Let us see, on a small example, how to deal with these concepts (precise definitions appear in section 1.2).
Consider a program which permits to assign integer values to variables and to retrieve these values on request.
Let I be the set of inputs, inputs may be of two types:
with α ∈ { A, B, C, ..., Z } (Set of identifiers containing at least one letter)
and β ∈ {0, 1, 2, ..., 9} (Represent integers)
where { x, y, z ... }+ is the set of nonempty words written with letters x, y, z, ...
Let σ be the set of outputs, outputs may be of two types:
Let I* denote the set of input sequences. Concatenation of input sequences will be noted with • (something like a carriage return separating inputs).
This program may be formalized by the following equivalence relations
This equivalence can be thought as: the value of a variable α is the value of the most recent assignment on α.
For the final output equivalence, we state
Binding sequences of type fα • α to output "NON DEFINED VARIABLE", and sequences of type f • α ← β to output β defines now a formal dialog system (FDS).
Example of dialogue:
A
NON DEFINED VARIABLE
A ← 35
35
B ← 3
3
A ← 1273
1273
A
1273
It can be verified that the input sequence A • A ← 15 • B ← 3 • A ← 1273 • A is equivalent with B ← 3 • A ← 1273 which will be considered as the state of the system.
A formal dialogue system (FDS) is an automaton F = (I, σ, Q , Ψ, q0 ) where I and σ are the possibly infinite sets of inputs and outputs, Q the set of states, Ψ a function from Q × I into Q × σ, called the transition function and q0 the starting state.
If the FDS is in state q and receives input i, then it goes in state q' and emits output u where (q', u) = Ψ (q, i).
In a classical manner (see for instance automata theory), states may be canonically defined by the set of input sequences which lead from the starting state to a given state, thus by classes of the equivalence relation š: f š g if Ψ(q0,f) = (q,u) and Ψ(q0,y) = (q',v) and q=q'. Similarly to each output is associated an equivalence class of the final output equivalence Ÿ : f Ÿ g if Ψ(q0,f) = (q,u•x) , Ψ(q0,y) = (q',u',y) and x=y.
It is clear that a FDS is fully defined by the sets I and σ, the equivalence relations š and Ÿ , and a mapping from I+/Ÿ (set of equivalence classes of Ÿ) into σ, provided that
∀ f , g ∈ l*, f š g → (∀a ∈ I, f•a š g•a and f•a Ÿ g•a )
This is the coherence condition between š and Ÿ. It means that if the program is in the same state after sequences f and g, then it must be in the same state after sequence f.a and g.a Moreover, the outputs emitted during the transitions f ⇒ f.a and g ⇒ g.a must be the same. This is the least requirement needed to describe conversational programs.
This general definition of FDS allows an infinite number of states and a possible non-computability of the given equivalence relations. It is clear that it is not the case in practical interactive programs as a program implies computability.
To overcome the problem of the infinite number of states, there exist two solutions:
This method, which leads to a finite state diagram (defined by the induced transitions between those new classes) as defined in Newman (1973) must be combined with the first one since usually at least one of these classes of the partitions will contain an infinite number of equivalence classes. It will nevertheless largely reduce in most cases the complexity of the computations of the relations and make possible a constructive definition of FDS from simpler ones. More precisely:
Let us call C1(f) and C2(f) respectively the input and final output
equivalence classes of f, C1
, and C2
the sets of such classes. A pair of partitions
P1 of C1
and
P2 of C2
will be said compatible with š and Ÿ if:
∀ f , g ∈ I* , C1(f) P1 C1(g) ⇒ (∀ a ∈ I, C1(f.a) P1 C1 (g.a) and C2(f.a) P2 C2(g.a))
Let us take again the previous example, restricting variable names to X and Y. It still has equivalence relations š and Ÿ of infinite indices. A finite pair of partitions is given by the following classes:
| State equivalence | Final output equivalence |
|---|---|
| X and Y undefined | Sequence with final output NON-DEFINED VARIABLE |
| Y undefined | Sequence with final output NON-DEFINED VARIABLE |
| X undefined | Sequence with final output NON-DEFINED VARIABLE |
| X and Y defined | Sequences for which the final output is an integer |
Each state can be represented by a sequence of at most two inputs. These are respectively:
The FDS may be represented by the following state diagram:
| state | input | ||||
|---|---|---|---|---|---|
| X | Y | X ← β' | Y ← β' | ||
| ε | new state | ε | ε | X ← β' | Y ← β' |
| output | NON DEFINED VARIABLE | NON DEFINED VARIABLE | β' | β' | |
| X ← β | new state | X ← β | X ← β | X ← β' | X← β • Y ← β' |
| output | β | NON DEFINED VARIABLE | β' | β' | |
| Y ← β | new state | Y ← β | Y ← β | X← β' • Y ← β | Y ← β' |
| output | NON DEFINED VARIABLE | β | β' | β' | |
| ← β • Y ← β" | new state | X← β • Y ← β" | X← β • Y ← β" | X← β' • Y ← β" | X← β • Y ← β' |
| output | β | β" | β' | β' | |
Conversely, such a finite state diagram defines a FDS if there are a transition function and an output function associated to each cell of the diagram. Each cell may be considered as a FDS and so FDS may be constructed from other ones, each of which corresponds to a specific task. It must be noted that such FDS are partial FDS as they are not defined for any input. A theory of partial FDS similar to that of fully defined FDS has been developed permitting other types of combinations of FDS (union concatenation product).
The previous formalism seems uniquely devoted to alphanumerical dialogues since one deals with string of letters. In fact nothing prevents abstract inputs or outputs to be of any other definable types, like buttons, pointing, tracking, drawing, graphical display.
A first technique will be to give to these new inputs and outputs alpha-numerical equivalents describing them. A more sophisticated technique will be to define a state as a data structure from which one can retrieve an image and on which the FDS will work. This has the advantage to make the description of a state more compact and more practical for programming than the original input sequence, but in any case there must be a unique correspondence between the data structure and the minimal description of states by input sequences.
A main advantage of such techniques here is that the description of a FDS makes no reference to the type of display unit used. As it will be seen later, there will only be a need of a graphical interface translating abstract outputs or inputs into an image or an input for a given terminal. We have in particular derived from the same FDS an alphanumerical version and a graphical version of the same program.
If at each step of the dialogue a completely new image appears, then one will have only to define a function from the set O' of outputs into the set of images on the screen.
This is unfortunately seldom the case. Generally an image is constructed step by step. So that the resulting image at a given step of the dialogue depends on all the preceding inputs. In that case it is considered that the image is a function of the state, i.e., like in a Moore automaton, the output depends only on the state. Then only this function will have to be defined and programmed for each graphical implementation.
On a graphical terminal, several types of inputs are available: keyboard, buttons, tracking and drawing devices, pointing or identifying devices (light-pens, balls, tablets may be used for both functions, but one must distinguish clearly which one they realize at a given moment). The first devices may be clearly considered as realizing alphanumerical inputs, as for instance tracking produces a sequence of numerical coordinates.
The idea about pointing is that one can only point what has already been created. Thus the result of a pointing can be specified . For example, in a graphical editor of electrical networks pointing the input gate of an electrolytical capacity placed in (3,4) is the abstract input associated to which can be shortened in input gate of electrolytical capacity placed in (3,4).
One can think of abstract inputs as alphanumerical equivalents of the graphical interactions.
Let us give an another small graphical example:
Consider a block diagram editing program where blocks can be placed on points situated on a given network Pi i = 1, N, and links are defined between blocks. The different types of blocks, B1 ... BM are permanently displayed on the screen with a menu.
Each choice from the menu must be followed by appropriate identifying of points or blocks. The valid sequences of pointings are
insert · Bi · Pj create · Pi · Pj delete block · Pi delete link · Pi · Pi
where Pi and Bj stand respectively for pointings of point Pi and block Bj and insert, create ... stand for the corresponding pointings in the menu.
The result of instructions is immediately displayed. One gets such dialogues like:
insert · B1 · P10 · insert · B3 · P2 · create ·P10 · P2 · delete link · P10 ·P2 · delete block · P2
which is equivalent to:
insert · B1 · P10
It is easily seen that formal reduction (equivalence) rules can be formally defined. It must be added rules for abnormal input sequences like
f š f • insert • create f • insert • create Ÿ g • insert • create
which means that the same input error produces the same message independently of the state of the program. The output might be for instance a warning at the top of the screen.
We thus obtain a formal definition of this block diagram editing program without any reference either to the real position of points on the screen or to the graphical representation of blocks or links.
We have so far only sketched a few problems connected to programming a FDS. We see here how FDS can directly lead to programs. This will be done on a practical example which was realized, it is a general block diagram editor, similar but much more complex than that described in section 2.
The editor contains three parts - the graphical editor itself, a help function to aid the user while working on the editor and providing comments on internal state, syntax and semantics of editor commands, and a hand-calculator facility, each one being defined independently as a FDS by finite state diagrams and transition functions. The diagram of the editor itself is in the form
| States | Inputs | ||
|---|---|---|---|
| Editor inputs | Call for Calculator | Call for Help | |
| Editor states | Editor FDS |
Hand Calculator |
Help |
Diagrams of hand calculator and help are defined similarly.
To facilitate the production of text or graphical output it was added to the minimal input sequences leading to the given state, lists giving occupied network points, blocks present on the screen, links between blocks plus different parameters.
A first program realizes the FDS, i.e. transition functions and the corresponding modifications on the data structure (lists defined above). Each cell of the finite state diagram of the FDS corresponds to a separate subroutine.
To test this program, text input and output interfaces have been implemented leading to an alphanumerical version of the editor.
These interfaces have been replaced by graphical interfaces, without any change of the FDS program itself, leading to the graphical version of the FDS. These interfaces could be changed to fit any other type of graphic terminal. The general schema of the program is:
We have defined here a formal system for the definition of interactive graphic programs completely independent from any physical display or interactive device. Although its use may seem rather cumbersome for large programs, it has many advantages among which:
Different small programs have been defined as FDS, like a simulator or a pocket calculator.
A first full test has been carried out on the block diagram editing program for analog simulation presented above. Its formal definition as a FDS needs about 70 pages and required a lot of time, but its programming took only two weeks for one programmer.
We are now defining a graphical editor in the same way. Our next step will be to formalize a graphical language by a FDS, we have gained already some experience with the formal definition of LISP.
The present definition of FDS may still be improved in order in particular to facilitate their use, but it has already proved very valuable for the description of interactive programs. It gives a good means to formalize interaction primitives and may lead to an efficient means for the formal definition of graphical languages.
KUPKA I., WILSING N. - "A formal framework for Dialog languages", Bericht no 2, Institut fur Informatik, Universitat Hamburg, 1972.
KUPKA I., WILSING N. - "Functions describing interactive programming", In International Computing Symposium 1973, North Holland 1973.
NEWMAN W.M. , SPROULL R.F. - "Principles of interactive Computer Graphics", Mc Graw Hill 1973.
QUEINNEC C. - "Contribution a l'etude des systemes interactifs", These de Docteur Ingenieur, ENSTA-Universite de PARIS VI, PARIS, 1978.