An algebraic notation called flow expressions is proposed for specifying graphics command languages, systems software, and the interactions between them. Flow expressions are an extension of regular expressions to handle interleaving of symbols, cyclic activities, and synchronization. The paper defines the notation, presents several applications in the graphics domain, and argues for the flexibility and descriptive accuracy provided by interleaved and cyclic commands and processes.
Finite state techniques are adequate in relatively simple applications for describing and modelling graphics command languages (throughout this paper I use the terms command language, user input language, and user interface language, synonymously) and their processors. However, these methods, as well as others based on more powerful models such as context-free languages and their corresponding pushdown automata, are not widely used because they cannot conveniently handle many of the more interesting aspects of interactive languages and graphics. Instead, systems are normally specified in an ad hoc manner, with imprecise English descriptions for user interface languages and no model except the program itself for the language processing and interpretation.
I believe there are several reasons why the conventional tools do not work well in the interactive graphics environment:
In this paper, I propose a description technique called flow expressions [13,14] that can be applied to some of the problems raised in the last three points above. Flow expressions (FEs) are an extension of regular expressions to handle interleaving of symbols, cyclic activities, and synchronization. The FE notation is defined informally and motivated with many examples in the following section. Several larger applications in graphics command language specification are then outlined. I next discuss some language parsing issues and give examples of system software descriptions combined with user interactions. The final section summarizes the contributions.
The language of flow expressions was developed to describe the flows of computer system entities, such as resources, messages, jobs, commands, and control, through sequential and concurrent software components such as programs, procedures, processes, and modules. FEs are defined formally in [14]; here, a more intuitive and less abstract definition is presented.
1. Start with a set Σ of atomic flow elements and the language of regular expressions (e.g. [8] ). Σ contains the vocabulary of our language and its members denote indivisible flow elements, such as characters, signals from a keyboard, and indivisible software components.
If a is in Σ and S, S1 and S2 are FEs then:
a is an FE, λ, the null string, is an FE and Φ is an FE.
S1S2, S1 ∪ S2 and S* are FEs.
Each FE S denotes a set of flows or a language L(S); for a regular expression S, L(S) is the corresponding regular set. Thus:
L(a) = {a}, a ∈ Σ.
L(Φ) = {}, the empty set.
L(S1S2) = {xy: x ∈ L(S1) and y ∈ L(S2)}.
L(S1 ∪ S2) = {x: x ∈ L(S1) or x ∈ L(S2)}.
L(S*) = L(S0) ∪ L(S1) ∪ L(S2) ... where Si = Si-1S (i > 0).
S* represents 0 or more repetitions of S. S+ will mean SS*.
A line drawing command sequence might be described by:
(Line (x y ∪ r θ))* ⊣
where Line, x, y, r, θ, and ⊣ represent atomic elements (members of Σ ). The interpretation here is that a series of connected lines is specified by zero or more repetitions of the Line command followed by either an x, y pair or an r, θ pair; the command sequence is terminated by ⊣ . Note that a command and its operands could be entered through a variety of modes. One virtue of this notation, of course, is the existence of simple machines, finite automata, for recognizing regular sets. Figure 1 shows a state diagram for the above example.
2. Just as cyclic, non-terminating processes appear naturally in computer systems, it is also the case that there are many examples of inherently non-terminating command languages and their terminal processing systems; that is, the languages have infinite length sentences and the terminal processors are cyclic. The regular expression '*' can be used to approximate this type of activity but I prefer to characterize an infinite repetition explicitly. For this purpose, a cyclic operator ∞ is defined:
L(S∞) = L(S S S...) = {x1x2x3... : xi ∈ L(S) )} where the 3 dots denote an infinite sequence.
((Rotate ∪ Scale) Globe)∞
might describe the commands continuously available to public users of a map system which permitted the uniform rotation and scaling of a globe. The Globe component of the command might consist of either the origin of scaling or the axis of rotation.
3. In graphics systems, as in all interactive applications, there may be a certain amount of controlled parallelism between the terminal user and the computer system. In addition, there are some natural concurrent activities in graphics systems, such as the concurrent execution of the display processor and central processor, and the possible logical concurrencies in animated systems. These concurrencies can be modelled using an interleaved model.
Interleaving is also useful for interactive languages where ordering of operands is often not important and where it is sometimes convenient to have several invocations of one or more command sequences concurrently active. We will describe these kinds of activities with the shuffle or interleave operators ⊙ and ⊛:
L(S1 ⊙ S2) = {x1y1...xkyk : xi,yi ∈ Σ*, x1...xk ∈ L(S1) and y1...yk ∈ L(S2)}.
S1 ⊙ S2 denotes the result of taking a string from L(S1) and shuffling or interleaving it with a string from L(S2) , Note that xi and yi need not be atomic and that x1 and yk could be null in this definition. (The definition must be extended in the case that S1 or S2 uses the ∞ operator (see [14]).
S = {Box LowerLeft ⊙ UpperRight)
might give the command for specifying a rectangular box by its two corners LowerLeft and UpperRight.
L(S) = {Box LowerLeft UpperRight, Box UpperRight LowerLeft}.
⊙ is convenient here since it is presumably of no importance which corner is specified first.
An indefinite number of interleaves is denoted by the operator ⊛, the closure of ⊙. We define:
L(S⊙) = L(S⊙0) ∪ L(S⊙1) ∪ L(S⊙2) ∪ L(S⊙3) ...
where S⊙i = S⊙i-1 ⊙ S) (i > 0) (the i-fold shuffle of S; e.g. S⊙3 = S ⊙ S ⊙ S.
The FE (Box(LowerLeft ⊙ UpperRight))⊛ would permit any number of partially specified Boxes. For example, a user might want to specify only one corner of several boxes before finally completing each box. For two boxes, say B1 and B2, a possible command sequence satisfying the FE is:
Box1 UpperRight1 Box2 LowerLeft2 LowerLeft1 UpperRight2
where the numbers distinguish between the invocations for B1 and B2.
4. More precise control of the degree of interleaving and of the interactions between interleaved entities is often required. This control is provided by a facility that resembles some standard process synchronization mechanisms.
An FE can be locked with respect to the interleave operators by surrounding it with the labelled lock brackets k[,]k. The flows inside the brackets are then treated as indivisible (critical sections) when interleaves are attempted with other flows having the same lock brackets. Thus, for example:
L(k[S1]k ⊙ k[S2]k = L(S1 S2) ∪ L(S2 S1)
When only one lock label is used (k here), the label will often be omitted, e.g. L([S1] ⊙ L[S2]). The examples assume that no further j or k locks occur within S1 and S2.
L(k[ab]k ⊙ k[cd]k = {abcd, cdab}
L(j[S1]k ⊙ k[S2]k = L(S1 ⊙ S2)
If Lower-Left and UpperRight in Example 4 were not atomic but consisted of (x,y) pairs, we might require that each corner be fully specified before any interleaving is possible. Thus, the Box command might become:
(Box k[xl yl]k ⊙ k[xr yr]k))⊛
(It would be a straightforward addition to also permit a box definition with upper left and lower right corners.)
The second facility is a wait/signal mechanism. The notation ωi informally means wait on signal i and σi means send signal i. ω and σ are interpreted as Boolean semaphores and permit more complex interactions with the interleave operators. These operators are defined so that every ωi must be preceded by one or more σis for a well-formed flow. Thus:
L((a ωi b) ⊙ (d ωi)) = {adb,dab}
L((ω a σ)) = { } (empty)
It is possible to define the locks [ and ] in terms of ω/σ but it is more convenient to keep them separate. Other examples using waits and signals are presented in the next two sections.
5. This completes the language definition. To summarize,
(1) a, λ, Φ, σk and ωk are FEs (a ∈ Σ.k is any wait/signal.)
(2) If S1, S2, and S are FEs, then so are S1S2, S1 ∪ S2, S*, S1 ⊙ S2, S ∞, S⊛, and k[S]k. (k is any lock).
FEs resemble and were most strongly influenced by the event expression and message transfer expression notation of Riddle [10,11,12]. FEs are also related to path expressions [3,4]. A detailed comparison is given in [14]. A recent paper by Bos [1] proposes that path expressions be used in graphics programs to define logical input devices, called graphics input tools; this approach to graphics program design appears similar in spirit to mine, even though it emphasizes programming language features rather than those of the input language directly. The application of the shuffle operator ⊙ for string command languages was first suggested, as an extension to BNF, by Welter [15].
The short examples given in the last section show how the more novel operators of FEs may be used for the specification of user interface languages. In this section, several more detailed examples are presented where the FE notation is the syntactic metalanguage for graphics command languages.
1. The public globe of Example 2 is one application where the cyclic operator provides an accurate characterization of the continuous nature of a system. There are many other examples of graphics and other interactive systems that accept languages with infinite length sentences.. (These systems are permanently running and always able to accept commands.) The languages generally have the form:
CommandLanguage = (C1 ∪ C2 ... ∪ Cn )∞
where the Ci correspond to a single command.
Applications include air traffic control systems, commercial data base systems such as banking and reservations, process control systems, and other systems that are continuously up.
Consider another version of the public globe system. Assume that it is part of a world atlas utility connected to a large data base that stores gross and detailed maps of any part of the world. This hypothetical but useful utility provides a 2D display map of any area and permits a user to interactively search and examine maps at any level of detail. The command language might be:
WorldAtlas = (Search ∪ Display ∪ Transform)∞
Search = Relation+
Display = MapObject Args*
Transform = MapObject (Scale ∪ Rotate ∪ Translate) Params*
The Search command searches the data base for a set of objects satisfying a given list of Relations. The Display command displays a MapObject. The Transform command allows the user to transform the MapObject that is already on the display screen.
A user may wish to have several map objects simultaneously displayed on different parts of the screen; for example, it might be useful to examine a map of a country and several of its cities at the same time. Changing the first rule above to:
WorldAtlas = ([Search] ⊙ ([Display] [Transform]* )⊛ )∞
would specify that global Searches could be interleaved with zero or more instantiations of Transform sequences and Display; each instantiation consists of a Display of a MapObject followed by zero or more transformations of it.
2. Curry |5| describes a 2D programming system where programs are constructed (on a display) by demonstrating the processing to be done, such as moving data between storage cells and registers and activating arithmetic and comparison devices, rather than giving the normal linear string descriptions of programs. For example, to program an add operation in a simplified system of this type, a user could perform the actions (Figure 2):
It does not make any difference in what order (1) and (2) are accomplished; other operations might also be interleaved with this command. The add command is described by the FE:
(LoadAreg ⊙ LoadBreg) ActivateALU+
In this method of programming, a 2D display of some representation of the instruction or statement being constructed is continually displayed. It is also possible to display some approximation to the state of the corresponding executed program, even at program construction time [5].
A system of the above type has a number of active computing objects, such as the ALU, that can be triggered by a user. Each object has several input and output parameters, such as cells or registers. Each object accepts a command sequence given by the FE:
([P1] ⊙ [P2] ⊙ ... ⊙ [Pn]) TriggerObject
where the Pi are the command operands.
Alternatively, one can view an object as waiting on a trigger signal, say t, that is sent when the command is activated. Thus, the object's activity is characterized by the FE:
(ωt PerformObjectOperation)∞
while a single command is:
{[P1] ⊙ ... ⊙ [Pn]) TriggerObject σtGardenswartz [6] is using some of these ideas to construct a system for microprogramming on the writeable control store of the Cal Data minicomputer. The processor architecture is displayed at various levels of detail under user control; the user specifies microcommands by moving data among the machine registers and triggering various units. The system permits much interleaving of operations and the command language is described by the FE notation.
Part of the language is given by the FE's:
MicroCommand = [Asource] ⊙ [Result] ⊙ [Body]
Body = LogicalCommand ∪ Arithmeticcommand ∪ Special Command
LogicalCommand = LogicalOperator ∪ LogicalMC ∪ (Branch ∪ Skip ∪ SpecialFunction)
LogicalOperator = (Areg ∪ Areg) ⊙ (Breg ∪ Breg) ⊙ (And ∪ Or ∪ Xor ∪ Nand ∪ Nor ∪ Coincidence ∪ Move ∪ SignExtend)
In this section, I discuss several problems connected with the parsing of FEs and also present an application of FEs for specifying some of the interactions between terminal users in a graphics system and the corresponding systems software.
1. Given an FE description of a command language, it would be desirable to either automatically generate a parser for the language or to use a general FE parsing algorithm. In |14|, it is proven that FEs minus the ⊛ and ∞ operators can be recognized by finite state automata (more precisely, if S consists of regular expressions, ⊛, locks, and waits and signals, then L(S) is a regular set). Thus finite state methods can be used for parsing these restricted forms of FEs. The cyclic operator ∞ can also be included in those simple but common situations where the FE has the form S∞ and S does not contain ⊛ or ∞; in this case, S∞ can be replaced by S* for parsing purposes.
The complexity increases considerably when ⊛ is used. FEs that can contain all operators except ∞ are descriptively more powerful than regular expressions; for example, L((abc)⊛) is not context-free. (Some theoretical results have been obtained on the complexity of shuffling using Riddle's notation [9].)
Some insight into the complexity of parsing FEs can be obtained by examining the following algorithm that parses FEs restricted to regular expressions, ⊛ , and ⊛ ( ∞, locks, and waits and signals are not included). In the algorithm, 'a and b' is interpreted as 'if a then b else false' and 'a or b' means 'if a then true else b'. The function Shuffle invokes Parse at least 2n times in the worst case, where n is the length of the input string x. (Two strings of length n1 and n2 respectively, have (n1 + n2 over n1) possible interleaves.) The exponential nature of the algorithm makes it impractical and probably indicates that each FE should be handled on a one-of-a-kind basis or, more reasonably, that efficient parsing algorithms for FEs that use the operators in restricted ways should be investigated.
function Parse(S:FE, x:flow) : Boolean ; {A Pascal-like notation is used.}
{Parse determines whether x ∈ L(S)}
case S of {Select on the form of S}
a ∈ Σ,λ : Parse := (S=x) ;
Φ : Parse := false ;
S1 ∪ S2 : Parse := Parse (S1,x) or Parse (S2,x) ;
S1 S2 : Parse := Try(S1,S2,x,0) ;
S1* : Parse := (x ∈ λ) or Try(S1,S1*,x,1) ;
S1 ⊙ S2 : Parse := Shuffle(S1,S2,x,0) ;
S1⊛ : Parse := = (x=λ) or Shuffle(S ,S1⊛ ,x,l)
end
function Try(S1:FE, S2:FE, x:flow, start:integer) : Boolean ;
{Try determines whether x ∈ L(S1S2) by assigning initial substrings of x to L(S1)
and the remainder to L(S2).}
{start = 0 for S1S2 and start = 1 for S1*, to ensure proper termination.}
begin i := length(x); match := false ;
while ¬match and i ≥ start do
begin
match := Parse(S1, substr(x,i)) and Parse(S2,fsubstr(x,length(x)-i));
{substr{x,i) returns the initial substring of the first i characters of x;
fsubstr(x,i) returns the last i characters of x.}
i := i-1
end ;
Try := match
end Try
function Shuffle(S1:FE, S2:FE, x:flow, start:integer) : Boolean ;
{Shuffle determines whether x ∈ L(S1 ⊙ S2) by trying all possible interleaves.}
{start = 0 for S1 ⊙ S2 and start = 1 for S1⊛ , to ensure proper termination.}
begin match := false ; i := 2length(x) - 1 ; {No. of interleaves}
while ¬match and i ≥ start do
begin x1 := select1(i,x);x2:= select0(i,x) ;
{select1(i,x) returns a string corresponding to those elements ak of x for which the binary representation of
i has a 1 in the k th position; select0 does the same except that a 0 bit must
appear in the k th position.}
match := Parse{S1,,x1) and Parse(S2,x2) ;
i := i-1
end
Shuffle := match
end Shuffle
2. I now consider some applications of FEs for describing the flow of control through systems software in an interactive environment.
Figure 3 contains a conventional block diagram of a single user, statement-at-a-time graphics system implemented locally [2,7]. The interactive user prepares a statement through a text editor; after editing, the statement is interpreted to produce textual and pictorial output on the CRT display and, possibly, on hard copy. The system components are the software modules of each box in the figure; we also include the terminal user H, the human responsible for constructing a statement and receiving the CRT results, for completeness. The execution time control paths though the system are described by the following FEs:
System = (InputEdit Interpret)+
InputEdit= (H TextEditor CRTdisplay)*
Interpret = H TextEditor Parse ((Evaluate Output) ∪ CRTdisplay)
Parse = Parser ((TapeFile Parser)* ∪ (DiskFile Parser)*)
Evaluate = Eval (DiskFile Eval)*
Output = CRTdisplay ∪ (PaperPlot CRTdisplay)
The FEs are standard regular expressions since this is a conventional sequential system. The flow descriptions provide a reasonably clear, top-down specification of the system components and their control interactions.
The purpose of the second example is to show the global interactions between an interactive user H at a terminal and the driving software residing in the computer. A user issues a command followed by a carriage-return (CR) and then waits for a system response (RES). The terminal system is cyclic to reflect the continuous availability of the system. Similarly, a new user can always sit down and start a session if the terminal is free; hence, the user activities can also be considered non-terminating. The synchronized flows through both subsystems are given by:
System = H∞ ⊙ Terminal
H = LogOn σCR ωRES (InputCommand σCR ωRES)* LogOff σCR σH ωT
Terminal = (ωCR LogHon σRES ωCR(AcceptCommand ExecuteCommand OutputResponse σRES ωCR)* ωH LogHoff σT)∞
The flows are also illustrated in Figure 4. The T/H waits and signals ensure that the terminal and H are properly synchronized at LogOff. The other waits and signals in the FEs are used to clearly mirror some of the coroutine-like handshaking between H and the terminal.
3. There are a number of other possible uses of FEs for describing user interactions and the architecture of graphics systems. The following three relate to the actual or logical concurrencies that exist.
At the hardware level, refreshable graphics systems contain at least two processors - a display processor and a conventional processor. As display processors become more complex, the communications and synchronization between these two machines and their software will also increase in complexity and some technique that can describe these interactions and concurrencies, such as FEs, should be useful. The display processor and display file program often interact with pointing and positioning commands of users, and it would be desirable to specify these more precisely. Finally, there is potentially much logical parallelism and interleaving involved in animation sequences that contain several independent animated objects at the same time; FEs are a natural means for describing these concurrent animated objects.
I have proposed a notation called flow expressions for specifying user interface languages, for describing the interactions between terminal users and the underlying systems software, and for describing control flow through graphics system components. The principal contributions of this work are:
The notation will undoubtedly evolve somewhat as more experience is gained in applying it to graphics problems; nevertheless, the FEs approach offers a promising solution to some of the problems, characteristic of the interactive graphics environment, that were listed in the introduction.
I am grateful to W. Mallgren for several helpful discussions and for his comments and suggestions on the draft of this paper. The research was supported in part by the National Science Foundation through Grant No. MCS75-19480 and by the Institut fur Informatikat ETH.
[1] J. van den Bos: Definition and use of higher-level graphics input tools, Proc. SIGGRAPH '78, Computer Graphics 12, 3 (August 1978), 38-42.
[2] C. Caldwell: An interactive graphic programming language with application to text and picture formatting, M.S. Thesis, Dept. of Computer Science, Univ. of Washington, Seattle, WA (July 1974).
[3] R.H. Campbell: Path expressions: a technique for specifying process synchronization, Ph.D. Thesis, Computing Lab., The Univ. of Newcastle Upon Tyne, Newcastle Upon Tyne, England (August 1976). (Also reprinted as UIUCDCS-R-77-863, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Urbana, IL (May 1977).)
[4] R.H. Campbell and A.N. Habermann: The specification of process synchronization by path expressions, Lecture Notes in Computer Science, Vol. 16, Springer-Verlag, Heidelberg (1974).
[5] G. Curry: Programming by abstract demonstration, Ph.D. Thesis, TR # 78-03-02, Dept. of Computer Science, Univ. of Washington, Seattle, WA (March 1978).
[6] L. Gardenswartz: A graphics system for microprogramming, M.S. Thesis in preparation, Dept. of Computer Science, Univ. of Washington, Seattle, WA (1979).
[7] B. Lewis and A,C. Shaw: Reflections on a graphics language and its implementation, TR #78-07-02, Dept. of Computer Science, Univ. of Washington, Seattle, WA (July 1978).
[8] M.L. Minsky: Computation: Finite and Infinite Machines, Prentice-Hall, NJ (1967).
[9] W.F. Ogden, W.E. Riddle, and W.C. Rounds: Complexity of expressions allowing concurrency, Proc. of SIGPLAN Conf. on Principles of Programming Languages (Jan. 1978).
[10] W.E. Riddle: Modelling and analysis of supervisory systems, Ph.D. Thesis, Computer Science Dept., Stanford Univ., Stanford, CA (March 1972).
[11] W.E. Riddle: A method for the description and analysis of complex software systems, SIGPLAN Notices, Vol. 3 (Sept. 1973), 133-136.
[12] W.E. Riddle: Software system modelling and analysis, RSSM/25, Dept, of Computer and Communication Sciences, Univ. of Michigan, Ann Arbor, MI (July 1976).
[13] A.C. Shaw: Systems design and documentation using path descriptions, Proc. 1975 Sagamore Computer Conf. on Parallel Processing, IEEE Computer Society, Silver Spring, MD (1975), 180-181.
[14] A.C. Shaw: Software descriptions with flow expressions, IEEE Trans. on Software Engineering, Vol. SE-4, 3 (May 1978), 242-254.
[15] M. Welter: Counter expressions, RSSM/24, Dept. of Computer and Communication Sciences, Univ. of Michigan, Ann Arbor, MI (Aug. 1976).