A Concurrent Window System …

                                          A Concurrent Window System

                                                              Rob Pike
                                                 AT&T Bell Laboratories
                                               Murray Hill, New Jersey 07974


                                                              ABSTRACT

                   When implemented in a concurrent language, a window system can be concise. If
           its client programs connect to the window system using an interface defined in terms of
           communication on synchronous channels, much of the complexity of traditional event-
           based interfaces can be avoided. Once that interface is specified, complex interactive
           programs can be assembled, not monolithically, but rather by connecting, using the same
           techniques, small self-contained components that each implement or modify elements of
           the interface. In particular, the window system itself may be run recursively to imple-
           ment subwindows for multiplexed applications such as multi-file text editors. This is the
           software tool approach applied to windows.


Introduction
Traditional window systems offer their clients -- the programs that call upon them for services -- an inter-
face consisting primarily of a graphics library and a stream of `events': tokens representing key presses,
mouse motion and so on. The clients of these systems tend to be written as state machines with transitions
triggered by these events. Although this style of programming is adequate, it is uncomfortable; state
machines are powerful but inconvenient. There are also engineering reasons to object to this interface
style: all types of events come through the same port and must be disentangled; the event handlers must
relinquish control to the main loop after processing an event; and the externally imposed definition of
events (such as whether depressing a mouse button is the same type of event as releasing one) affects the
structure of the overall program.
       To make the situation more comfortable, event-driven interfaces typically allow some extra control.
For instance, a program displaying a pop-up menu can usually arrange to ask only for mouse events, so the
code supporting the menu is not disrupted by keyboard events. Although they help, such details in the
interface are just work-arounds for the fundamental difficulties that event-driven programming must ulti-
mately face. The work-arounds accumulate: the X11 windows library, for instance, has 27 standard entry
points to handle 33 types of events [Xlib 88]; NeWS has a single general event type but still needs 20 entry
points to handle it [Sun 87]. The interface for input in GKS is comparably complex [GKS 84]. It is
demonstrably difficult to write simple programs to connect to such intricate interfaces [Rose 88].
      Although events from the various inputs may be intermingled and asynchronous, the events from any
one device will be well-behaved. We could therefore program each device synchronously and cleanly if we
could divide the events into separate streams, one per device, directed at concurrent processes. The result-
ing program would be a collection of self-contained processes, free of irrelevant bookkeeping, whose exe-
cution would be interleaved automatically.
     That approach was taken in Squeak [Card 85], a concurrent language designed for programming such
components of user interfaces as menus and scroll bars. Squeak was a small language, though, and too
__________________
NeWS is a trademark of Sun Microsystems, Inc.
PostScript is a registered trademark of Adobe Systems, Inc.
UNIX is a registered trademark of AT&T.
                                                   -2-


simple to be useful for writing complete applications. It lacked variables, a type system, communication of
anything other than integers, and dynamic creation of processes. Input management in a realistic environ-
ment requires a stronger language than Squeak and a more concentrated understanding of graphics applica-
tions and the environment in which they run.
       This paper describes the design of an experimental window system written in a concurrent language
designed for the job. The language, called Newsqueak, is documented elsewhere [Pike 89]. The window
system provides a well-specified environment for its client programs, using a synchronous procedural inter-
face for output and structured communication on a small number of synchronous channels (as in CSP
[Hoare 78]; see below) to handle input and control. The window system functions by multiplexing its
clients' access to its own environment, which has the same structure, allowing the system to be run recur-
sively. The environment is easy to program both from the client's and the window system's points of view.
The complete window system is fewer than 300 lines of Newsqueak.

Comparison with other systems
       In contrast to systems such as NeWS, which allow their clients to be written using concurrent tech-
niques, this system requires its clients to be written concurrently. The only interface to the window system
is through parallel synchronous communication channels. The main observation from this exercise is the
importance of specifying the interface between the window system and its clients succinctly and com-
pletely. Given such a specification, it becomes possible to interconnect small programs, each of which
implements a piece of the specification, to form larger interactive applications in a manner similar to the
pipeline approach to text processing on the UNIX system.
      The external structure of the system is akin to that of NeWS. Remotely executing applications imple-
ment graphical user interfaces by connecting to the window system over the network and calling upon the
Newsqueak interpreter to execute code on their behalf. It is therefore expected that production applications
would be ordinary compiled programs running remotely that achieve interactive graphics by loading cus-
tomized Newsqueak code into the window system's connections to them.
       Philosophically, the closest relative might be the Trestle window system of Manasse and Nelson
[Mana 89]. There, the connection between the window system and its clients is implemented by a bidirec-
tional module interface. By defining that interface thoroughly, Trestle achieves some of the same intercon-
nectivity and recursive structure but in a more conventional environment. (From some points of view,
object-oriented programming, modules, and concurrent communications on synchronous channels are the
same idea in different clothing.) The input mechanism in Trestle is still event-driven, however. The sys-
tem described here goes further, defining all input and window control functions, including resizing and
deleting windows, using synchronous communications.

Basics
       An application or client of a window system is an independently executing process whose display
activity is confined to a subset of the entire screen controlled by the window system. That subset is the
client's window. Ignore for the moment the process-specific aspects of the client and assume that it is a
procedure written in a high-level programming language. Moreover, assume that there is no implicit global
environment for the procedure. Instead, the environment for the procedure must be passed explicitly, as
parameters, from the window system to the client. If we can define those parameters and what they signify,
we will have completely defined the properties of a client.
       One of the parameters will obviously be a variable, say W, labeling the window in which the program
is running. W will be used by the client to place output in its window. W's precise type need not concern us
yet, but it must at least describe the window's geometry.
       W is, loosely, a capability, granted by the window system, enabling the client to use its window. W
labels a multiplexed component of a larger screen containing all the windows. Input to the client may be
regarded similarly. We need capabilities allowing communication with the multiplexed mouse, keyboard,
and perhaps other input devices. Call these K and M, and pass over their exact specifications. The client's
declaration is then, approximately,
                                                     -3-



         client: prog(W, K, M)

(The syntax used in this paper is based on Newsqueak, but should be mostly self-explanatory.) Once it has
been invoked, the client can be represented pictorially, using arrows to represent the flow of information.

                                                W
                                                K           client
                                                M

Ultimately the picture will become more complicated as we add new possibilities such as setting the mouse
position and controlling the resizing and deleting of windows.
      The window system has several independently executing clients, each of which has the same external
specification. It multiplexes a screen, mouse, and keyboard for its clients and therefore has a type reminis-
cent of the clients themselves:
         windowsys: prog(S, K, M)

where S is the screen. If we arrange the client's windows to be programmable by the same interface as the
full screen (making S a W), the window system will have the same type as its clients. Pictorially,

                                                                W1
                                                                K1          client
                                                                M1




                               W             window             W2
                               K                                K2          client
                               M             system             M2




                                                                W3
                                                                K3          client
                                                                M3


       If the window system multiplexes clients of its own type, then it may be a client of itself, or a client
may pass its environment to a fresh invocation of the window system to do further multiplexing. This
recursion allows a client of window system -- a text editor, say -- to invoke the window system afresh in
its window to manage subwindows for multiple views of files being edited.
      To fill in this sketchy outline, we need to be more precise about the properties of W, K, and M.

Output
      Two problems must be addressed by the output mechanism: how a client can draw in its window and
how multiple clients can share the screen harmoniously. The choice of output model -- bitmaps,
PostScript, display lists -- is unimportant to the structure of the client, since any model can be imple-
mented by a synchronous, procedural interface, a programming library. Replacing the library will not
greatly affect the structure of the client or its environment. The system described here is based on bitmap
graphics because that is perhaps the simplest model.
      Bitmap graphics has been described before [Guib 82, PLR 85]. Briefly, a two-dimensional portion of
memory, possibly but not necessarily visible on the display, is described by a data structure called a
Bitmap. The data structure may be passed to several graphics operators, of which the best-known is the
rectangular operator bitblt or rasterop, to effect changes to the memory and therefore to the display.
Our first guess, then, will make W a Bitmap. But that ignores the problem of multiple clients with
                                                      -4-


windows on the same screen.
      The concept of `layers' generalizes bitmap graphics so it applies to overlapping bitmap windows
sharing a physical display by storing in the window system complete backup bitmaps for obscured portions
of windows [Pike 83a]. By extending the Bitmap type to encompass the properties of layers, the standard
operators such as bitblt can be applied to partially or wholly obscured windows on the hardware dis-
play. Clients of a window system may remain unaware of each other, free to draw in their respective win-
dows regardless of overlap and oblivious to changes in the visibility of their windows.
       Other systems typically send their clients `expose' events when the visibility of their windows
changes. Such events require all affected clients to run when the display is rearranged, which can cause
considerable paging overhead and delay. A rationale for expose events is that some such mechanism is
necessary when a user asks a client to change the size of its window, since the original contents of the win-
dow will be lost anyway. Unfortunately, flipping between windows is much more common than changing
their sizes. Reducing the common case to the hard case therefore obviates an important optimization: a sin-
gle bitblt executed by the window system can restore a window much faster than can paging in and execut-
ing client code. When windows take longer to repair themselves, the entire user interface becomes less
dynamic and less comfortable [Pike 88]. Layers permit very responsive interfaces.
        On the other hand, the layers model offers no guidance on how to implement resizing, which is a cen-
tral issue in the design of a window system. It does not however prevent resizing, and there is a clean solu-
tion to the problem, which is explained below, in the section on `Control'.
      Layers have other difficulties. Especially on displays with many bits per pixel, layers are expensive
in memory, because they maintain off-screen backup memory for invisible portions of windows. But dis-
play memory has become much cheaper, and in systems such as the one under discussion, the machine with
the display has no other major use for its memory. It is there to maintain the display, to run the window
system.
       A more telling criticism is that layers require some shared memory, atomicity, and synchronization.
The window system must maintain a central data structure describing the configuration of the display, and
the clients must not be writing to their windows when that data structure is being modified. That problem
is easily overcome, however, using techniques standard in operating systems. For example, bitblt could
be made a system call, at least when it is operating on a window. In our case, the structure of the interpreter
solves the synchronization problem implicitly.
      In summary, although layers have limitations, they have important advantages and are used in this
system. Output is handled by passing the client processes a variable, W, of type Bitmap (extended to be
applicable to overlapping windows) that the client may use to access its window using whatever graphics
package is available. There are no expose events, and resizing is handled by special techniques.

Input
       It remains to decide on the types of the variables K and M that provide the client with access to the
multiplexed keyboard and mouse. The type of K is easily determined: it can be a synchronous channel that
yields integral values identifying the key that has been pressed. It is analogous to a file descriptor on the
UNIX system, from which may be read successive input characters. Since K will provide only keyboard
data, no further specification is necessary; we need not distinguish keyboard data from mouse data, as the
mouse information is available only through M. K does not provide events, it just delivers characters, syn-
chronously, as they become available and are requested. If it were desired to track up and down transitions
of the keys, the transitions could still be represented easily as integers. K is declared in Newsqueak as
          K: chan of int;

that is, as a channel of integers.
      The behavior of the mouse is harder to model. It has three buttons that go up and down and two
dimensions of translational motion. The usual solution is to represent the mouse's behavior by a series of
events: button down, button up, motion, motion while button down, etc. It is simpler instead to track the
mouse by a series of synchronous messages reporting the entire state of the mouse.
        The state of the mouse is represented by a data structure:
                                                    -5-



         type Mouse: struct of{
              buttons: int;
              position: Point;
         }.

The variable buttons has a bit set for each button that is depressed, and the position is held in a Point,
a type that is already part of the graphics library:
         type Point: struct of{
              x,y: int;
         }.

The actions of the mouse are reported on the channel M, defined as
         M: chan of Mouse.

Each time the state of the mouse changes, the current state is made available on the channel M. If the mouse
is idle, reads from M will block. The semantics of communication in Newsqueak implies that mouse-ahead,
if desired, must be provided explicitly. (The properties of channels are discussed in the next section.)
       A programmer accustomed to an event-driven mouse interface might argue that the synchronous way
of handling the mouse is awkward. If the program is waiting for some genuine event such as a button tran-
sition, then decoding the complete state of the mouse to look for the transition might seem harder than just
waiting until the specified event happens. But before making that decision, we should look more closely at
how the mouse is programmed. For simple cases such as waiting for a single button event, it makes no
practical difference; the loop
         do
              e=getevent();
         while(e.type!=LEFTBUTTONDOWN)

is equivalent to
         do
              m=readmouse(M);
         while(m.buttons&LEFTBUTTON).

Imagine, though, that a more complicated condition is to be met, such as the left button being held down
while the mouse is inside some rectangle. The proposed interface solves the problem well:
         do
              m=readmouse(M);
         while(!(m.buttons&LEFTBUTTON && pointinrect(m.position, r))).

The full programming language may be used to specify the condition. The mouse may be programmed as
if it were being polled, which is probably the simplest way to write mouse software. An event-based inter-
face would instead have to be programmed to reconstitute the state so the condition may be tested. Why
provide a complex interface when the programming language can already handle all the complexity
required? Events add unnecessary complexity to the problem of interpreting the mouse. But we can only
avoid that complexity when we can write code to read the mouse channel independently of the code that
handles the keyboard; otherwise, the event mechanism is the only way to collect both mouse and keyboard
actions. To keep those two tasks separate, we need processes.

Channels, concurrency and multiplexing
      Here is the declaration of the type of clients of the window system developed so far:
         type Client: prog(W: Bitmap, K: chan of int, M: chan of Mouse).

Any program of type Client, including the window system itself, can be run in a window.
      A client program is started by the window system by creating a window and channels for the key-
board and mouse and then by calling the client program as a separate process. In Newsqueak this is written
         begin client(newW, newK, newM).

The window system records the values of the new channels and uses them to send keyboard and mouse data
                                                                 -6-


to the client. The clients execute independently and concurrently and are likely themselves composed of
concurrent subprocesses. The clients are true processes, not coroutines; their execution is finely inter-
leaved, and not just switched at I/O time as in mpx or NeWS [Pike 83, Sun 87]. No client can completely
dominate the system, even if it is in a tight loop without I/O. The user interface of the window system or its
clients does not block because a client is busy.
       The channels that carry messages between processes in Newsqueak, and hence within the window
system, are synchronous, bufferless channels as in Communicating Sequential Processes (CSP) or Squeak,
but carry objects of a specific type, not just integers [Hoare 78, Card 85]. To receive a message on a chan-
nel, say M, a process executes
           mrcv =