Rick Beach, February 15, 1987 7:57:12 pm PST
The Run-time Structure of
UIMS-Supported Applications
John R. Dance, Tamar E. Granor,
Ralph D. Hill, Scott E. Hudson, Jon Meads,
Brad A. Myers, Andrew Schulert
I. Introduction
This group was concerned with the run-time support provided by a UIMS, as opposed to design, analysis, evaluation or other support. In particular, we were concerned with the demands placed on a dialogue manager by user interfaces that require a high level of semantic feedback.
Traditionally, dialogue managers have attempted a strong separation of the seman component and the user interface component. The assumption was that these were relatively independent, and that separating them would lead to the benefits of modular programming; each component could be developed and changed independently of the other, multiple interfaces could be provided to the same application, consistent interface styles could be developed, and so on.
Unfortunately, this has not worked in practice. One important reason is that many user interfaces, especially direct-manipulation interfaces [9,17], require that semantic information be used extensively for controlling feedback, generating default values and error checking and recovery. For example, when using the Apple Macintosh, an icon may be dragged around with the mouse. When it is over other icons that can operate on it, such as the trash can, the operator icons are displayed in reverse video. This requires that semantic feedback (derived from the types of the icons) be provided while the mouse is tracking.
In general, the traditional breakdown of feedback into lexical, syntactic and semantic feedback does not adequately describe the variety of types of feedback currently in use. In fact, feedback is best classified as a continuum based on the amount of application semantic knowledge that is required. Myers [14] gives the example of mouse tracking to illustrate this. From less knowledge required to more knowledge required, the cursor can do the following: (1) directly follow the mouse, (2) follow the mouse, but move more per increment when the mouse is moving faster, (3) echo only at fixed grid points, where the application sets the grid spacing, (4) echo only at legal character positions in a text editor with a fixed width font, (5) echo only at legal character positions in a text editor with a variable width font, and (6) echo only at legal and ``good'' moves in a game (such as Go or chess).
In general, semantic information is needed frequently to support feedback. It is also needed to provide meaningful default values for parameters to commands and to allow error checking and appropriate responses. Clearly, all dialogue managers have had to allow the user interface to change in response to semantic processing. However, because of the previous emphasis on separation of the application and the user interface, the communication between the two components has been too narrow and too slow to support rapid feedback. What is needed is ``fine grain control'' [13] rather than the ``coarse grain control'' provided by most existing dialogue managers. The problem is how to provide this without giving up the advantages that were realized in separating these components in the first place.
2. Framework for run-time support
There are three areas of concern in providing semantic information to the interface: the dialogue manager, the application and what we termed the semantic support component, a subcomponent of the dialogue manager that contains information of concern to both dialogue manager and application. (When we use the term ``dialogue manager'' in this report we will often mean that part of the dialogue manager which is not the semantic support component. Unfortunately, we did not assign a name to that part of the system.) The relationship of these components is shown in Figure 1.
[Artwork node; type 'ArtworkInterpress on' to command tool]
Figure 1. Relationship among system components
This decomposition is similar to that proposed in the ``Report on Dialogue Specification Tools'' from the Seeheim conference on user interface management systems [4]. We suggest that the presentation component of that model corresponds to the workstation agent, as described elsewhere in this issue [10], and possibly to part of the dialogue manager, as described below in section 3.1.2. Their dialogue control and application interface model components are similar to our dialogue manager and semantic support components, respectively.
The following sections discuss the purpose, responsibilities and contents of each component.
2.1 The dialogue manager
The primary purpose of the dialogue manager is to provide a higher level of abstraction for interaction services. The dialogue manager contains those parts of the system that:
 Are consistent across all applications, such as support for the presentation of help,
 Are device-dependent, such as the interaction technique library,
 Are in a generic user profile of interest to many interfaces and systems, such as whether the user is right- or left-handed,
 Vary across different interfaces to the same application, such as facilities for supporting multiple command names for a given function.
2.2 The semantic support component
The purpose of the semantic support component is to provide information for semantic operations such as feedback, default values and error checking and recovery, to provide application-specific help information and to support modification of dialogue (such as changing menu contents) based on the application state. The semantic support component contains those parts of the system that:
 Are in an application-specific user profile, such as the preferred method for stereo viewing in Grip-75 [11]
 Define what is being displayed, such as the percentage shown of a file in a file browser
 Are unique to a specific application, such as the user's conceptual model
The semantic support component is similar to the application interface model proposed at the Seeheim conference. However, while that was proposed as a passive interface definition, we view the semantic support component as an active component of the dialogue manager. The specification of the semantic support component implicitly specifies the interface to the application, but also defines how the semantics of the application are incorporated into the user interface.
2.3 The application
The application, in addition to processing and analysis, is responsible for the integrity of the data, although the other components may be responsible for error-checking. The application contains those parts of the system that:
 Do not need to know about the user interface, and about which the user interface does not need to know, such as procedures that perform finite element analysis in a structural design system
 Are consistent across all interfaces to the application, such as the basic functions of the application
3. Potential architectures
This section presents some models for how the dialogue manager and the semantic support component might be structured to support rapid feedback. We do not propose a single architecture, but instead simply discuss alternatives that have been proposed in other research.
3.1 Structure of the dialogue manager
The two primary options for the structure of the dialogue manager discussed in our group were (1) having no structure imposed within the dialogue manager and (2) breaking the dialogue manager into lexical and syntactic components. Since there is sometimes no sharp or well understood division between the lexical and syntactic levels, the division is often made for convenience rather than strongly held beliefs in a layered structure.
3.1.1 Homogeneous object space
The first option proposes a homogeneous object space where the only differentiation among the objects is conceptual. The dialogue manager makes no distinction in its handling of an object based on the function of the object. The value of this type of dialogue manager is that it allows for a fairly flexible definition of the components constituting an interface. It is assumed that objects will be provided with timely messages informing them of relevant input data such as mouse movement, keyboard strokes, button clicks and clock ticks. Objects may also send and receive messages from other objects.
Objects may produce geometry for display in any of a number of ways. A message may be sent to a presentation server or workstation agent requesting that a previously displayed entity be replaced or updated. New display entities may also be created and old entities may be deleted as needed. The nature of the presentation server and its interface to objects may be considered to be implementation dependent. However, the specification of an object and its use of presentation server facilities must be available to the application in a standard manner.
By means of passing and acknowledging messages in turn, it should be possible to specify any needed syntax for a given interaction. In addition, instantiating several objects — each of which is capable of receiving input independently — allows for multiple concurrent interactions.
Using a homogeneous object space may involve a tradeoff of power and flexibility against ease of use and structure. A purely homogeneous system, which makes no distinctions between different levels or components of the system, provides a great deal of flexibility and power. But it may also reduce the level of structure placed on the system and consequently make such systems harder to create, debug and maintain. However, it is conceivable that a system supporting a homogeneous object space could be developed that would allow creative user interfaces to be specified more easily than with a highly structured support system.
There are several questions that need to be investigated and answered in order to develop an interface using this approach. One question is how to define the mechanisms and filtering needed for passing device input data to appropriate objects. Second, the mechanisms for instantiating and linking an object, particularly generic objects available from the dialogue manager's library, to one of several independent applications needs to be resolved. Third, there is the major issue of determining how an application will be able to define an object, instantiate an object and communicate with various objects through the dialogue manager. Finally, a dialogue manager is expected to provide a number of servers for purposes such as providing help, tracking history and accessing user profiles (as well as generating displays). Mechanisms need to be developed that will allow such servers to instantiate application-specific objects as needed in support of a given application.
3.1.2 Lexical / syntactic structure
The second option for structuring the run-time portion of a dialogue manager is to decompose it into lexical and syntactic components. The internal structure of a user interface is often expressed as having lexical, syntactic and semantic components. In the structure we developed, the semantic component is provided by the application and the semantic support component.
The lexical component is normally treated as a collection of low level building blocks with built in feedback. We call these building blocks interaction modules. Each interaction module typically implements an interaction technique — a simple, self-contained interaction with the user. Examples of possible interaction modules are tools to support pop-up menus, text string input and simple graphical input techniques like rubber-band line drawing. These typically do not change from interface to interface (although they may be customized by changing parameters), and can be collected into a library. It is important to be able to add new interaction modules that are needed by specific user interfaces.
The syntactic level is typically written for each user interface. It accepts input from the lexical level. Then it maps input sequences into commands that can be applied to the data in the semantic support component, or that can be sent to the application. Historically the syntactic level has been specified with grammars, such as finite state machines. Other possibilities include event-based specifications, such as in the University of Alberta UIMS [5], Sassafras [7], and GUIDE [3], and object-oriented techniques, such as in the GWUIMS [18]. Other techniques are possible, and in some cases the syntax may not be explicitly declared.
In the case of multi-threaded, or concurrent, user interfaces, the syntactic level is responsible for mapping (sequences of) concurrent input into semantic level commands. This implies that the syntactic level specification technique will likely require simple concurrency control constructs.
Examples of dialogue managers with a lexical / syntactic division:
 Sassafras [7]
In Sassafras, the lexical level consists of an extensible library of interaction modules. These are coded in a systems programming language, and provide a high level interface to the input devices. The syntactic level is specified in Event-Response Language. This is an event-based language specifically designed to support implementation of concurrent or multi-threaded interfaces.
 GUIDE [3]
As in Sassafras, the lexical level in GUIDE consists of interaction modules called tools. These are coded in Pascal, using CORE graphics [2] and reside in an extensible library. The syntactic level is composed of tasks, each of which may contain several tools. Tasks are created by the user-interface designer and provide the user with alternative methods of providing input.
 GWUIMS [18]
The GWUIMS is based on an object-oriented approach. While it does not require or enforce a distinction between lexical, syntactic and semantic objects, the authors suggest that such a categorization could be layered on top of the underlying system.
The technique and graphical objects deal primarily with lexical level issues, while the interaction and representation objects provide the syntactic level, and part of the semantics (primarily parts of the semantic support component).
3.2 Structure of the semantic support component
Give the decomposition of an interactive application into dialogue manager, semantic support component and application, the layout of the data structures in the semantic support component (SSC) can depend on: the application (APPL), the dialogue manager (DM) or both the application and the dialogue manager. Alternatively, the data structures can be independent of both the dialogue manager and the application. These alternatives can be represented as: (DM) (SSC APPL), (DM SSC) (APPL), (DM SSC APPL) and (DM) (SSC) (APPL).
In this approach, the application determines the structure of the information in the semantic support component. This allows the structure of the shared information to reflect the specific needs of the application. However, it may make it more difficult for the user-interface implementor to use this information (or may even render it inaccessible to the user interface).
This approach limits the structuring of the shared information to using structuring techniques explicitly specified by the dialogue manager. Although this may restrict the generality of the shared information, it makes it much easier to access from the user interface. It also allows the dialogue manager to provide standard display update and dependency analysis tools that have embedded knowledge of the structures. The availability of these tools may simplify the implementation of some user interfaces.
This approach is probably not possible. It would require that the user interface and the application both impose restrictions on the structuring of the information in the semantic support component. In some cases this may work well, but there is the risk of imposing too many constraints. This approach is likely to suffer from the limitations of both (DM) (SSC APPL) and (DM SSC) (APPL), without any of the benefits.
 (DM) (SSC) (APPL)
If the structuring of the information in the semantic support component is independent of the user interface and the application then there are likely to be interface problems on both sides of the semantic support component. Thus, this does not appear to be a viable alternative.
In practice, the (DM SSC) (APPL) approach will be preferred in dialogue managers that attempt to provide a lot of support for display update, or are designed for applications with specific types of user-visible data. The (DM) (SSC APPL) approach is more flexible, but this flexibility requires extra effort from the user-interface implementor.
The (DM) (SSC APPL) approach will require the application to export both data and procedures to the semantic support component. The procedures will be used by the user interface to update both the display and the data. In the (DM SSC) (APPL) approach, the structure of the data in the semantic support component is constrained by the design of the dialogue manager, so the dialogue manager can provide the standard routines to update the display and the data.
Examples of the (DM SSC) (APPL) approach:
 Cousin [6]
Cousin is one of the first examples of a system that makes the exchange and sharing of information between the application and the user interface explicit. It uses a form exchange paradigm, where the types of elements that may appear in the form are determined by the user interface.
 DOMAIN / Dialogue [16]
With DOMAIN / Dialogue the connection between dialogue manager and application is based on shared data. Each datum is called a task. Each task is presented to the user by one or more interaction techniques. When the user modifies a task the application is notified. Similarly, when the application modifies a task, the technique is updated. There is a fixed set of task types, and it is managed by the dialogue manager.
 Higgens [8]
The information in the semantic support component in Higgens must be encoded in structures that are purposely limited by the designer of Higgens. This allows Higgens to provide tools to assist in display update, including dependency analysis, to ensure that these updates are done efficiently. This means that many user interfaces can be quickly and easily implemented. The cost is a lack of flexibility. This is not a major problem if the goal is to provide tools for developing specific types of user interfaces.
Examples of the (DM) (SSC APPL) approach:
 GUIDE [3]
The interface designer provides GUIDE with declarations for all application objects that are visible to the interface. These may include constants, types, variables and headers for procedures and functions. This allows GUIDE to perform type-checking on all references to application objects. The semantic support component for GUIDE also converts between the types of interaction technique values and the tasks that contain them. For example, it will convert from a character string to a real number or check to see that a string is a valid file name. The application is responsible for display of application objects, while GUIDE controls display of interaction techniques. This approach gives the interface designer a great deal of expressiveness in describing the interface. However, information passing is restricted to one direction, from the application to the interface; the interface must invoke application routines to modify application variables.
 Sassafras [7]
With Sassafras the application programmer must supply procedures to do all updates and redisplays. Sassafras controls the interactions with the user, and maps the user commands into invocations of the procedures supplied with the application routines. This makes Sassafras very flexible. This flexibility costs in two ways: the application programmer (or perhaps the user-interface implementor) must write routines in a traditional programming language for the semantic support component, and the functionality implemented in these routines may not be adequate to support some user interfaces, thus impeding their development.
4. Research issues
This section discusses research questions that the working group felt were important. These are mostly orthogonal to the issues discussed in the above sections.
4.1 Concurrency
Concurrency is necessary to allow multiple input devices to be operating at the same time. This is different from allowing multiple input devices to be available at the same time, which just means that the user can choose which device to use. Dialogue managers that support multiple concurrent input devices include Sassafras [7], Adagio's Switchboard [20] and Peridot [12].
The advantage of allowing concurrent access to multiple input devices is that it makes some interactions more natural and efficient. Experiments have demonstrated that users can easily and naturally use two hands at the same time and in doing so, will perform some tasks faster, more efficiently and with less learning time than with conventional one-handed interfaces [1]. Examples of this kind of concurrency are (1) setting the position of a graphical object with one hand while controlling its size with the other hand, and (2) selecting words in a document with a mouse while using the other hand to control scrolling using a touch tablet [1]. Although these interfaces can be implemented in systems without concurrency by alternately sampling the two devices, such systems make it more difficult to define a modular run-time structuring of the user interface.
A disadvantage to providing concurrency is the performance penalty that must be paid if there is inadequate operating system support. Also, concurrent programs are significantly more difficult to debug. This is especially true if the application program must also be concurrent and/or deal with the concurrency of the interface.
4.2 Multiprocessing and network issues
An important question is how a UIMS architecture is affected by the need to support distributed applications. For instance, one might identify four levels of interprocess communication, with progressively slower bandwidth: processes sharing address space, processes with disjoint address spaces, processes separated by a local area network and processes separated by a wide area network.
Smooth feedback requires a responsiveness in the order of a tenth of a second. We therefore suspect that the dialogue manager and semantic support component must be connected by a local area network or reside on the same machine. The connection between the semantic support component and application is less critical in many (but not all) applications. However a ``distant'' application must have some way to export semantics to those dialogue manager facilities which are close to the user and able to support direct manipulation.
Predicting the performance requirements of these links, providing user-interface design guidelines for reducing the dependencies on these links and making the most of the available links are important research questions. Also, the capabilities required to export semantics from a ``distant'' application to a dialogue manager supporting direct manipulation remain to be determined.
4.3 Role of object-oriented programming
A very promising model for how dialogue managers should be built is based on object-oriented programming. Systems using this new style include GWUIMS [18] and MacApp [15]. The advantages of this approach are that the inheritance properties of objects makes it easy to provide specialization and slight modifications on existing and supplied interaction techniques as well as higher level structures. Whereas object-oriented programming makes it much easier to program user interfaces, it is still a programming technique, and dialogue managers can do more to help create user interfaces than just providing a programming framework. Therefore, the research in this area is investigating how object-oriented programming fits into dialogue managers, how the objects should be structured to handle user interfaces (for example, the model-view-controller structure of Smalltalk) and how object-oriented programming affects the dialogue manager model.
4.4 Support for evaluation of user interfaces
Clearly, the run-time part of the dialogue manager should be saving information that the post-processors can evaluate the interface. This information might also be used to enable UNDO and REDO facilities and macro construction.
The real challenge is not to record this information, but instead to aid in its evaluation. The manual process of reviewing and evaluating recorded user sessions can be quite tedious and time consuming. The dialogue manager could help by adding semantic information to the recorded session, such as what tasks or application commands were being invoked by the lexical actions recorded. This would allow the user-interface evaluator to quickly look at a cross section of users performing a particular task and concentrate on trouble spots in the interface. The dialogue manager might also keep basic statistics on the number of times facilities such as Help, Cancel or Undo were invoked before, during and after particular tasks or commands. This could provide a rough guide to quickly isolating trouble spots in the interface.
4.5 Support for sequencing
Direct-manipulation interfaces tend to have much less syntax and fewer ordering constraints than textual interfaces. However, there are still some situations where sequencing is important and necessary. For example, often one menu selection will cause a different menu to appear. It would be useful to have a tool to help with this kind of ordering.
Typically, transition diagrams have been used in this area. But they do not handle concurrency and seem inappropriate for interfaces where semantics plays a big part in determining what comes next. Hill's event-driven system [7] and GUIDE [3] are other approaches, but more work needs to be done.
5. Summary
We recognized the need to incorporate semantic information into a dialogue manager. We addressed this need by introducing a subcomponent of the dialogue manager, which we termed the semantic support component. However, this raises questions about how the semantic support component is coupled with both the application and dialogue manager. More research needs to be done to learn how to structure this area to better support interactive applications.
6. References
[1] Buxton, W. and Myers B.A. A study in two-handed input. In Proceedings CHI'86 Conference on Human Factors in Computing Systems (Boston, April 1317, 1986), ACM, New York, 321326.
[2] Status report of the Graphics Standards Planning Committee. Computer Graphics 13, 3, (August 1979), entire issue.
[3] Granor, T.E. A User Interface Management System Generator. Technical Report MSCIS8642, GRAPHICS LAB 12, Computer Science Dept., University of Pennsylvania, 1986.
[4] Green, M. Report on dialogue specification tools. In User Interface Management Systems, Pfaff, G.E., ed., Springer-Verlag, 1985, 920.
[5] Green, M. The University of Alberta user interface management system, Proceedings of SIGGRAPH'85 (San Francisco, Calif., July 2226, 1985). In Computer Graphics 19, 3 (July 1985), 205213.
[6] Hayes, P.J. and Szekely, P.A. Graceful interaction through the COUSIN command interface. International Journal of Man-Machine Studies 19, 3, (September 1983), 285305.
[7] Hill, R.D. Supporting concurrency, communication and synchronization in human-computer interaction — the Sassafras UIMS. To appear in ACM Transactions on Graphics, 1987.
[8] Hudson, S.E. A User Interface Management System Which Supports Direct Manipulation. PhD thesis, University of Colorado, Boulder, Colorado, August 1986.
[9] Hutchins, E.L., Hollan, J.D. and Norman, D.A. Direct manipulation interfaces. In User centered system design, Norman, D.A. and Draper, S.W. (eds.), Lawrence Erlbaum Associates, Hillsdale, NJ, 1986, 87124.
[10] Lantz, K.A. et al. Reference models, window systems, and concurrency. In this issue, Computer Graphics 21, 2 (April 1987).
[11] Lipscomb, J., Pique, M., Brooks, F.P., and Wright, W.V. The GRIP75 man-machine interface [videotape]. SIGGRAPH Video Review 4. (1981), ACM, New York.
[12] Myers, B.A. and Buxton, W. Creating Highly Interactive and Graphical User Interfaces by Demonstration, Proceedings of SIGGRAPH'86 (Dallas, Texas, August 1822, 1986). In Computer Graphics 20, 4 (August 1986), 249258.
[13] Myers, B.A. Creating dynamic interaction techniques by demonstration. To appear in Proceedings of CHI+GI'87 (Toronto, April 59, 1987), ACM, New York.
[14] Myers, B.A. The issue of feedback. In preparation.
[15] Schmucker, K.J. MacApp: An Application Framework, Byte, (August 1986), 189192.
[16] Schulert, A.J., Rogers, G.T. and Hamilton, J.A. ADM—A dialog manager. In Proceedings CHI'85 Human Factors in Computing Systems (San Francisco, April 1418, 1985), ACM, New York, 177183.
[17] Shneiderman, B. Direct manipulation: a step beyond programming languages, IEEE Computer 16, 8 (1983), 5769.
[18] Sibert, J.L., Hurley, W.D. and Bleser, T.W. An Object-Oriented User Interface Management System, Proceedings of SIGGRAPH'86 (Dallas, Texas, August 1822, 1986). In Computer Graphics 20, 4 (August 1986), 259268.
[19] Sisson, N. Dialogue Management Reference Model. SIGCHI Bulletin 18, 2, (October 1986), 3435.
[20] Tanner, P.P., MacKay, S.A., Stewart, D.A. and Wein, M. A Multitasking Switchboard Approach to User Interface Management, Proceedings of SIGGRAPH'86 (Dallas, Texas, August 1822, 1986). In Computer Graphics 20, 4 (August 1986), 241248.