Squeak(ID:1185/squ002)Luca Cardelli and Rob Pike 1985 Graphical movement description language People: Related languages
References: essential concurrency among multiple interaction devices, such as mice, buttons, and keyboards. Squeak is a user interface implementation language that exploits this concurrency rather than hiding it, helping the programmer to express interactions using multiple devices. We present the motivation, design and semantics of squeak . The language is based on concurrent programming constructs but can be compiled into a conventional sequential language; our implementation generates C code. We discuss how squeak programs can be integrated into a graphics system written in a conventional language to implement large but regular user interfaces, and close with a description of the formal semantics. pdf Extract: Introduction Introduction User interface implementation languages ([Buxton 83], [Thomas 83]) usually address the construction of a user interface from building blocks such as menus, scroll bars and freehand curves. Although it is worthwhile to automate the building of programs from such building blocks, there is an underlying level that these languages do not address: the implementation of the building blocks themselves. Moreover, the procedures that provide menus, graphical potentiometers and other user interface modules tend (in our experience) to be more difficult to write or modify and clumsier in execution than one would expect. The primitives never seem complex in principle, but the programs that implement them are surprisingly intricate. Providing a suitable graphical display is not especially difficult; what causes problems is the complicated flow of control required to deal with all the possible sequences of user actions with the input devices. One might consider a scrolling menu, for example, as a finite state automaton reading an input token for each event generated by the user: buttons up and down, entering and leaving the scroll bar rectangle, etc. Interaction primitives would probably be simpler to write and understand if they were implemented as state machines. A translator that converted state machine descriptions into regular programs would make the job even easier. There are a couple of factors that limit the usefulness of this technique, however. First, the presence of multiple input devices invalidates the notion of a single stream of tokens driving the state machine; for example, the procedure implementing a menu should not worry about characters typed on the keyboard, even those typed while the user is using the menu. Second, the passage of time is often important in user interfaces. Some pairs of events are only meaningful when the individual events occur sufficiently near in time. Consider clicking a mouse button twice: if the clicks are nearly simultaneous, they might be construed as the single event ?double click.? A more powerful structure is a set of communicating finite state machines, each of which implements the actions associated with some set of user events. If the individual machines execute concurrently, each may be enabled when an event is available for it, so the user interface need never ?lock up? waiting for a specific event. Another concept from concurrent programming, the timeout , can be used to encode time-sensitive procedures. In contrast to approaches based on parsing a single input stream [van den Bos 83], the language we present here, called squeak , is an explicitly concurrent language, resembling CSP [Hoare 78] and CCS [Milner 80], and with the passage of time built rigorously into the semantics as in SCCS [Milner 82] and ESTEREL [Berry 84]. Processes in squeak communicate by exchanging simple messages on multiple channels. A predefined channel is used for communicating with each device. The concurrency in a squeak program must be expanded out for squeak to be of practical value in a conventional programming environment. Our implementation generates an opencoded (as opposed to table driven) state machine, written in C [Kernighan 78], that expresses all possible execution paths of the set of processes in the program. The sequence of input events controls the path taken by the single-stream sequential execution of the program. In practice the relatively simple programs needed to describe user interfaces are well-behaved, although in general the state space of a set of concurrent processes can explode. Extract: Tutorial introduction to squeak Tutorial introduction to squeak The following sections will explain squeak in detail; this tutorial introduces and motivates the basic ideas. Squeak programs are composed of processes executing in parallel. A process, or perhaps a few processes, typically deal with a particular action or external device; the composition of processes then handles the set of actions and device events relevant to the program. Communication between processes is achieved by sending messages on channels . There are two classes of channels: primitive and non-primitive. Primitive channels are pre-defined, and provide access to external devices. Non-primitive channels are for ordinary message-based communication. The syntax c !exp sends the value of the expression exp on channel c ; c?var reads the message on channel c into the variable var . Our implementation of squeak defines the primitive channels DN and UP, which report mouse button transitions; M, mouse cursor position (M!p sets the cursor position, M?p reads it);? K, characters typed on the keyboard; T , the current absolute time; and E and L , the mouse entering and leaving certain rectangles. The primitive channels return appropriate values; M for example returns a point data structure. UP and DN return no value; if the mouse had several buttons, they might return the mouse button number, or there could be a separate channel for each button. E and L return the appropriate rectangle. Squeak does not specify how the program announces its interest in rectangles on the display; our implementation provides C-callable functions to push and pop sets of rectangles to be watched. Events come in meaningful order, so that UP and DN events must alternate, as must E and L of a given rectangle. Here is a simple squeak program that places typed text on the display at points indicated by the mouse: proc Mouse = DN? . M?p . moveTo!p . UP? . Mouse proc Kbd(s) = K?c . if c==NewLine then typed!s . Kbd(emptyString) else Kbd(append(s, c)) fi proc Text(p) = < moveTo?p . Text(p) :: typed?s . {drawString(s, p)}? . Text(p) > type = Mouse & Kbd(emptyString) & Text(nullPt) Process structure in the example program The last line states that the generated C procedure type is the result of the parallel execution of three processes. The Mouse process waits for the mouse button to be depressed. When it is, the mouse coordinates are sent on channel moveTo , where they will be read by the Text process. Mouse then waits for the mouse button to be released, and restarts. (The precise semantics of these actions are discussed in the following sections.) Kbd waits for a character to be typed. If the character is a newline, it sends the complete line on channel typed and restarts; otherwise it appends the character to the line. The append function is a C routine defined elsewhere; squeak treats its invocation as a literal expression. Note that because Mouse and Kbd are processes, not functions, their recursive invocations do not stack; they are goto ?s, not subroutine calls. Finally, the Text process waits for a message on channel moveTo or typed , and records the mouse position or draws the string on the display, as appropriate. The code in brace brackets { } is a C expression evaluated at that point in the execution of Text . Typical squeak programs implement only the flow of control; the actual work at each state of execution is done by such calls to external code. This simple example is artificial, but illustrates the basic ideas of squeak . Most important, a process monitors each input device, and each such process is independent. If a mouse button is held down while typing continues, the text will still be displayed when a newline is typed. This works because of the concurrent execution of the Mouse and Kbd processes. Newsqueak Hoare's language was novel and influential, but lacking in a few key aspects. The main defect is that the unbuffered channels used for communication are not first-class objects: they cannot be stored in variables, passed as arguments to functions, or sent across channels. As a result of this, the communication structure must be fixed while writing the program. Hence we must write a program to print the first 1000 primes rather than the first n primes, and to multiply a vector by a 3x3 matrix rather than an nxn matrix. Luca Cardelli and Rob Pike developed Hoare's ideas into the Squeak mini-language [4] for generating user interface code. (This Squeak is distinct from the Squeak Smalltalk implementation mentioned in earlier chapters.) Pike later expanded Squeak into the fully-fledged programming language Newsqueak [5][6] which begat Plan 9's Alef [7] [8] and Inferno's Limbo [9]. The main semantic advantage of Newsqueak over Squeak is that Newsqueak treats communications channels as first-class objects: unlike in CSP and Squeak, channels can be stored in variables, passed as arguments to functions, and sent across channels. This in turn enables the programmatic construction of the communication structure, thus allowing the creation of more complex structures than would be reasonable to design by hand. In particular, Doug McIlroy demonstrated how the communication facilities of Newsqueak can be employed to write elegant programs for manipulating symbolic power series [10]. Similar attempts in traditional languages tend to mire in bookkeeping. In a similar vein, Rob Pike demonstrated how the communication facilities can be employed to break out of the common event-based programming model, writing a concurrent window system [11]. |