--09Foley.tioga
--Rick Beach, February 15, 1987 7:59:19 pm PST
Transformations on a Formal Specification
of
User-Computer Interfaces
James Foley
Dept. of EE & CS
The George Washington University
Washington, DC 20052
Present software tools for designing and implementing user-computer interfaces are too low-level: while they provide support to the designer at the presentation level of screen layout, dialogue design, etc., they provide no support at the conceptual and semantic design levels.
Our present research project objective is to develop a formal representation for key aspects of the conceptual and semantic design of a user-computer interface. The representation embodies information about the user interface in terms of objects, actions, relations, attributes, and pre- and post-conditions associated with the actions. We are building an interactive system, using a frame-based expert system shell, which will help the designer create the specification for an intended interface. Once the designer has completed the user interface specification, our system will be able to:
 Apply consistency and completeness checks to the specification.
 Transform the specification into a series of functionally equivalent specifications, each of which has a slightly different user interface to the same functionality.
 Evaluate speed of use of the interfaces, based on task scenarios and using the keystroke-level model [2], or formal grammar analyses [1,8].
 Input any or all of the specifications into an appropriate UIMS, such as GWUIMS [9], to quickly implement any of the user interfaces.
1. A sample user interface specification
The following is an example of how we specify a user interface, given in a Pascal-like syntax. The example is used throughout the paper to illustrate ideas. The syntactic details of the specification are not important: elaboration is given where needed. A fuller definition of the syntax and semantics of the specification, along with two major examples, are in [3].
The functionality of this example interface is trivial: triangles and squares of various colors can be created, deleted, and rotated. The color of created shapes is a static attribute, and hence cannot be changed. There is a general object class, called shape, with two subclasses, called square and triangle. The pre-conditions, which are conditions that must be true before a command can be made available to the user, concern the existence of objects to operate on. The post-conditions, which are conditions that become true after a command is performed, record how many objects of type shape exist.
basedesign: begin

{declarations of the types of objects on which the user interface commands operate}

type

{shape is an object class with two subclasses. The actions and attributes originate with this class, and can be inherited by object subclasses of shape.}
shape
superclasses : ()
subclasses : (triangle, square)
actions  : (create
shape,
  delete
shape, rotateshape) : originates,
  heritable
attributes  : (position, color) : originates,
  heritable
relations  : ()

{two subclasses of the object class shape. Actions and attributes are inherited from the shape superclass, and cannot be inherited by subclasses (there are none).}
triangle, square
superclasses : (shape)
subclasses : ()
actions  : (create
shape,
  delete
shape, rotateshape) : inherits
  from
shape, not heritable
attributes  : (position, color) : inherits
  from
shape, not heritable
relations  : ()

{declarations of attributes of the above objects}
position  : range [0..10] x [0..10]
color  : set (1, 1) of (red, green, blue, white,
    black, cyan, magenta, yellow)
angle  : range [0..360]

{initial values for any pre-conditions}

initial: shape
objects = 0

{operations on the objects, with pre-conditions and post-conditions}

create
shape(p:position, c:color, a:angle,
 type
ofshape:shape)
post-condition: shape
objects = shapeobjects+1

pre-condition: shape
objects <> 0
rotate
shape(obj:shape, a:angle)

pre-condition: shape
objects <> 0
delete
shape(obj:shape)
post-condition: shape
objects = shapeobjects - 1

end {base
design}
This style of interface specification takes its command and parameter approach from Cousin [5,6] and in general from frame-based systems. One can think of each parameter as a slot in a frame, and the name of the frame as the command. The pre- and post-conditions come from Green [4]. More recently, Olsen in his MIKE system [7] has used a similar approach to user interface specification, but for other purposes.
The operations on the objects specify all the information and context needed to carry out the operation. This specification contrasts with lower-level BNF or ATN syntax specifications, where this knowledge is not explicitly represented and therefore cannot be used to assist in designing or implementing the interface.
Because information about the interface is specified at the semantic and conceptual levels, rather than at the suntactic and lexical levels, the user interface designer can request the UIMS to implement a syntax such as prefix, postfix, or ``nofix'' (free-form syntax with automatic prompting for missing information). This eliminates concerns about inconsistent syntax specified using tools such as BNF or ATNs, because the designer is working at a higher level of specification. The change from one syntactic structure to another is very easy for the UIMS to carry out, and relieves the designer of the tedium of syntactic-level specifications.
It will not be necessary to specify that all commands have a certain syntax: the designer might ask that all operations on one type of objects have one syntax, with operations on another type of object having a different syntax. While this might appear at first to be promoting inconsistency, careful observation of successful user interfaces finds such mixing within an application. Many Macintosh programs are examples of such mixings.
The pre- and post-conditions are not required, but are provided as a way for the user interface designer to specify dependencies between various commands. They will be used in the UIMS to selectively enable only those commands whose pre-conditions have are satisfied. The equivalent effect can be had if the application routines directly enable and disable commands: we prefer to give this type of control to the designer.
2. Consistency checks
Given an interface specification, some analysis can be done to help the designer make sure the specification is complete and consistent. If a post-condition is not used elsewhere as a pre-condition, then either the post-condition should be deleted because it is not serving any useful purpose, or a pre-condition using the post-condition needs to be added to some operation. In a similar vein, conditions specified in pre-conditions must always be initialized.
If two object classes can each be created, but only one can be deleted, the designer will be asked whether the other class should also have a delete operation. This ``gentle reminder'' strategy will be used extensively, to make sure the designer has not overlooked specifying some commands.
3. Transformations of the user interface specification
User interface designers typically explore a number of alternative ways to structure the semantics of an application. In designing complex systems, we have found that it is difficult to organize and think about the various alternatives. Our user interface design system is being designed to help with this process, by automatically generating design alternatives based on a number of generic design strategies which we have identified. As additional design strategies are identified, they will be incorporated into the system.
In the following subsections the design strategies are described. In some cases, the effect of applying the strategy to the commands in the sample user interface design of Section 1, called basedesign, is also presented.
3.1 Factoring
This broad design strategy, also called orthogonal-ization, takes several forms. The basic idea is that one or more of the units of information (that is, parameters) required to carry out a command are specified by a separate command, and hence become modal or global. This strategy is attractive when many different commands take the same parameter, or when a command has many parameters, or as one way to provide default values. When a parameter is factored out of a command, we call the parameter implicit, in contrast to the case where it is part of the command, or explicit.
When the parameter factored out of the commands is the object on which the command operates, the currently-selected object paradigm is established.
In the first example of a factoring transformation, the color parameter used in basedesign is made implicit. Note that the color parameter is not assumed to have a default value (this is done in a later example). Hence there is a pre-condition on creating a shape, to require that color has been previously set. The design shown below can be generated automatically from basedesign. The comments in square brackets are meta-comments explaining what the automatic transformation has done.
factoreddesign: begin
initial: shape
objects = 0 {initial values for post
        conditions}
initial: color
set = false [added automatically]

set
color(c:color) [added automatically]
post-condition: color
set = true
     [added automatically]
pre-condition: color
set = true
     [added automatically]
create
shape(p:position, c:color implicit, a:angle,
 type
ofshape:shape)
post-condition: shape
objects = shapeobjects+1
     [implicit added automatically]
pre-condition: shape
objects <> 0
rotate
shape(obj:shape, a:angle)
pre-condition: shape
objects <> 0
delete
shape(obj:shape)
post-condition: shape
objects = shapeobjects - 1
end {factored
design}
Applying factoring to object selection in basedesign, to give a currently selected object, or CSO, produces:
CSOdesign: begin
initial: shape
objects = 0 {initial values for post
        conditions}
initial: CSO
set = false [added automatically]
create
shape(p:position, c:color, a:angle, typeofshape:shape)
post-condition: shape
objects = shapeobjects + 1
post-condition: CSO
set = true
     [added automatically]
     [newly-created object is the CSO]
pre-condition: shape
objects <> 0
     [added automatically]
select
shape(obj:shape)
     [added automatically]
post-condition: CSO
set = true
     [added automatically]
pre-condition: shape
objects <> 0
     [deleted automatically]
pre-condition: CSO
set = true
     [added automatically]
rotate
shape(obj:shape implicit, a:angle)
     [implicit added automatically]
pre-condition: shape
objects <> 0  
     [deleted automatically]
pre-condition: CSO
set = true
     [added automatically]
delete
shape(obj:shape implicit)
post-condition: shape
objects = shapeobjects - 1
post-condition: CSO
set = false
     [added automatically]
end {CSO
design}
Just as objects can be factored from commands to create a currently selected object paradigm, it is possible to create a currently selected command paradigm. Typically a CSO paradigm restricts the available commands to those which can be performed on the CSO (in essence establishing a mode). So too the currently selected command (CSC) restricts the available objects to those on which the CSC can operate (creating a mode). The two types of modes are in some sense duals of one another.
In the following example, only the deleteshape command is made modal; the transformations to make others modal are analogous:
CSCdesign: begin
initial: shape
objects = 0
initial: delete
shapemodeset = false
     [added automatically]
pre-condition: delete
shapemodeset = false
     [added automatically]
create
shape(p:position, c:color, a:angle, typeofshape:shape)
post-condition: shape
objects = shapeobjects + 1
pre-condition: delete
shapemodeset = false
     [added automatically]
pre-condition: shape
objects <> 0
rotate
shape(obj:shape, a:angle)
pre-condition: delete
shapemodeset = false
     [added automatically]
pre-condition: shape
objects <> 0
   {multiple preconditions must all be true}
begin
deleteshapemode
     [added automatically]
post-condition: delete
shapemodeset = true
     [added automatically]
pre-condition: delete
shapemodeset = true
     [added automatically]
pre-condition: shape
objects <> 0
delete
shape implicit (obj:shape))
     [implicit added automatically]
post-condition: shape
objects = shapeobjects - 1
pre-condition: delete
shapemodeset = true
     [added automatically]
end
deleteshapemode
     [added automatically]
post-condition: delete
shapemodeset = false
     [added automatically]
end {CSC
design}
3.2 Initial values
A factored parameter such as color can be given an initial value, which is in effect until explicitly changed (unfactored parameters can be given a default value, which is a different concept than that of initial value). The following is a further transformation of factoreddesign, in which the transformation algorithm has automatically removed the lines in italics to effect the transformation:
factoredinitialdesign: begin
initial: shape
objects = 0
     {initial values for post conditions}
initial: color
set = false
     [added automatically]
     [deleted automatically]
initial: color = black
     [initial condition
added automatically]
set
color(c:color)
     [added automatically]
     [deleted automatically]
post-condition: color
set = true
     [added automatically]
     [deleted automatically]
pre-condition: color
set = true
     [added automatically]
     [deleted automatically
]
create
shape(p:position, c:color implicit, a:angle,
 type
ofshape:shape)
     [implicit added automatically]
post-condition: shape
objects = shapeobjects + 1
pre-condition: shape
objects <> 0
rotate
shape(obj:shape, a:angle)
pre-condition: shape
objects <> 0
delete
shape(obj:shape)
post-condition: shape
objects = shapeobjects - 1
end {factored
design}
3.3 Specialization
The specialization transformation ``pushes down'' operations from the general to the specific. For example, the type declaration for the triangle and square subclasses specifies that there are two types of shape objects. Hence it is possible for any operation on objects of type shape to be replaced by two comparable operations, one on objects of type square, the other on objects of type triangle, provided that the operations are declared heritable. The following illustrates a specialization of the creation operation:
specializationdesign: begin
initial: shape
objects = 0
create
shape(p:position, c:color, a:angle,
 type
ofshape:shape)
     [deleted automatically]
create
triangle = createshape(p:position, c:color,
 a:angle, triangle:shape)
   [modified automatically to give literal value
    for shape parameter]
post-condition: shape
objects = shapeobjects + 1
create
square = createshape(p:position, c:color, a:angle, square:shape)    
   [modified automatically to give literal value
    for shape parameter]
post-condition: shape
objects = shapeobjects + 1
pre-condition: shape
objects <> 0
rotate
shape(obj:shape, a:angle)
pre-condition: shape
objects <> 0
delete
shape(obj:shape)
post-condition: shape
objects = shapeobjects - 1
end {specialization
design}
3.4 Generalization
The converse of specialization is generalization, the process of aggregating up one level in the class hierarchy. An example of generalization is to aggrogate the createtriangle and createsquare operations created in section 3.3 back into the createshape operation.
Both specialization and generalization operations need to be provided, because the original interface design might have been done with specialized operations which can be generalized, or might have been done with general operations which can be specialized.
3.5 Currently selected set
The normal CSO paradigm works with a currently selected object; an alternative is to have a currently selected set (CSS) of objects. Any command applies to all elements of the CSS. Commands exist for adding new objects to the CSS, removing elements from the CSS, and emptying the CSS. This strategy is attractive in task domains where different operations are typically applied in sequence to the same set of objects, not just to a single object.
3.6 Object naming
Some interaction styles require that objects be named, so that object names can be entered through a keyboard or voice recognizer. Naming can be added to a user interface specification by automatically adding name as a parameter to any command which creates objects of the type which are to be named. One might also automatically add changename and listname commands.
3.7 Collapsing command chains
If command A has post-condition a and command B has pre-condition b, then it may be reasonable to consolidate the two commands A and B into a new command AB. One application of this would be to reverse the orthogonalization discussed in Section 3.1. However, there are other more general applications. For example, the cut and paste paradigm used in Star and Macintosh is another example. A cut command has a post-condition (clipboard has information), and the paste command has the same pre-condition. The cut and paste are thus potentially combinable into a move command. This is not to say that such a combination is desirable, only that the system can identify such a possibility for the designer to evaluate. We have seen user interfaces which are so that the designer was not even aware that such collapsing was possible. If the designer requests that the commands be collapsed, then the system can automatically do so.
3.8 Scope
The scope of commands is another design decision. Consider the combination of the CSO and global color specification transformations used in preceding sections. When a CSO exists and a setcolor command is specified, are the color of the CSO, the current color, or both affected? Does setcolor affect only the next shape created, or all subsequently created shapes? Each of these possibilites represents a viable design alternative. Again, the designer should have the ability to select, and the system will then effect that choice.
3.9 Generate a canonical form
We have seen examples of transformations among user interface specifications. Is there a canonical form, a unique specification of a class of functionally equivalent interfaces? For the answer to be ``yes,'' there must be a set of rules which can be applied to an arbitrary specification to convert it into the canonical form. We are not yet prepared to positively claim that there is a canonical form, but it appears that the rules to create a canonical form are:
 Generalize everything: ``push up'' all operations to the highest possible level of abstraction (this will be a problem with multiple inheritance situations, where operations can be pushed up along different paths).
 Make all parameters be explicit.
 Remove all modes, both command and object.
The basedesign of Section 1 is in this canonical form. We note that this design also has the most compact representation of the various alternatives presented here.
A canonical form would be useful for defining a standard interface between a UIMS and the semantic modules which implement the functionality of an interface.
4. Automatic evaluation
Another planned capability is to evaluate some or all of the alternative designs generated by the various transformations discussed in Section 3. The only evaluation currently planned is speed of use (ease of learning is a much more complex question). The speed of use evaluation requires the following information:
 A set of task scenarios, expressed as sequences of the operations found in the proposed canonical form. The system can deduce what commands are needed if the design being evaluated is not the canonical form, because it knows what transformations have been effected. (In some cases this will be tricky, such as with the CSS transformation.)
 A definition of the interaction techniques used to input each type of information.
 The syntax for commands.
 Human performance data, for actions such as keying, mouse movement, device acquisitions.
5. Input to a UIMS
Some number of design alternatives will be judged by the interface designer to be worthy of actual implementation. They will be input to GWUIMS. Application modules (or at least simulations thereof) will have to be coded and made accessable to GWUIMS. Once this is done, default interaction techniques can be used to provide an immediate implementation of a user interface to the functionality.
6. Status
We have developed specifications for two existing user interfaces, as a way of testing the robustness of the formalisms we have developed [3]. Not surprisingly, this process led to several improvements in the formalisms.
We have implemented an interactive system which allows a user interface designer to specify a user interface, using the syntax illustrated in this paper. The system is written in Franz Lisp and a locally-developed frame system. The transformations discussed in this paper, plus others, have been implemented. For each transformation, an inverse transformation has been defined. We are currently testing the transformations on several interface specifications to ensure that they posess the mathematical properties of closure, commutativity, and associativity, and to make sure that the inverses work under all situations. Our next steps are to use the formal specifications as input to a simple UIMS to automatically create user interfaces based on the specification, and to create a better interface to the design tool itself.
Acknowledgements
The Graphics and User Interface Research Group at GWU provided an intellectual environment supporting this work, while financial support was provided by the National Science Foundation, Grant DMC-8420529, and the Department of Energy, grant DE-AS05-83ER13122. T. Bleser, C. Gibbs, J. Sibert, and W. Kim provided useful comments on earlier versions of this paper.
References
[1] Bleser, T., and Foley, J. Towards Specifying and Evaluating the Human Factors of User-Computer Interfaces. Proceedings Human Factors in Computer Systems Conference, (Gaithersburg, Maryland, March 1517, 1982), ACM, New York, 309314.
[2] Card, S., Moran, T. and Newell, A. The Keystroke-Level Model for User Performance Time with Interactive Systems. Communications of the ACM 23, 7, (July 1980), 398410.
[3] Gibbs, C., Kim, W.C., and Foley, J. Case Studies in the Use of IDL: Interface Definition Language. Report GWU-IIST-86-30, Dept. of EE&CS, George Washington University, Washington, DC 20052.
[4] Green, M. The Design of Graphical User Interfaces, Technical Report CSRI170, University of Toronto, 1985.
[5] 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.
[6] Hayes, P. Executable Interface Definitions Using Form-Based Interface Abstractions. In Advances in Computer-Human Interaction, Hartson, H.R. (Ed.), Ablex, New Jersey, 1984.
[7] Olsen, D.R. MIKE: The Menu Interaction Kontrol Environment, BYU Tech Report, Brigham Young University, Provo, Utah, 1986.
[8] Reisner, P. Further Developments Toward Using Formal Grammar as a Design Tool. Proceedings Human Factors in Computer Systems Conference, ACM, 1982, 304308.
[9] 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.