Douglas C. Kohlert and Dan R. Olsen, Jr.
Computer Science Department
Brigham Young University
Provo, UT 84602
dkohl@tim.cs.byu.edu olsen@cs.byu.edu
This paper suggests that there exists a large class of inherently graphical applications that could use pictures as their primary input data. These applications have no need to store input data in any other format and thus eliminate the need to do conversions between input data and a graphical representation. Since the graphical representation is the only representation of the data, such applications allow users to edit an application's input data by manipulating pictures in a drawing editor. Such an environment would be ideal for users of pen-based machines since data would not have to be entered via a keyboard, instead a gesture based drawing editor could be used. CUPID, which is a tool for Creating User-Interfaces that use Pictures as Input Data, is presented.
Much of user interface design focuses on how to effectively represent application data in such a way that it can be easily comprehended as well as manipulated by the user. For many application domains, this requires converting an awkward and unnatural internal data representation to a more comprehensible graphical form. Some applications are inherently graphical in the way users visualize information. For example, the relations in a pedigree tree for a genealogical application can be quite difficult to understand if presented in a textual format, however, the same tree presented in a graphical form can be quickly grasped and understood by the user.
This paper suggests that inherently graphical applications need not try to do conversions between the internal representation and the displayed graphical representation of data such as is done by TRIP3 [9].
Instead, application input data can be stored and displayed as graphical objects with relations between objects based on geometric relations. This allows arbitrary pictures to become an application's input data. A visual language could be defined for each application domain that would determine a "picture syntax" that could be used to "parse" application data sets. This syntax would determine how objects in a picture are related and thus could be used by the application to access and retrieve information from various parts of the picture.
Using pictures to represent input data has five major advantages. First, the data that is input into the application is easily understood by the user. Pictures of data also have certain affordances that make it clear how to change relationships within the picture [3], such as by moving the position of a line. Second, "drawing pictures" to represent application data is a task that most users are familiar with. Third, modifying application data is reduced to simply editing an already existing drawing or picture. Fourth, with the ever increasing number of gesture based machines, it is very advantageous to be able to draw an application's data rather than input it in a textual form. Although a gesture-based drawing editor similar to GEdit [8] could be used for sketch recognition, only a palette-based drawing editor has been used in this work. Fifth, picture-based applications give the user significant freedom over fixed object systems. Unlike fixed object or dialogue based systems, the user has more freedom to place a variety of objects in more locations in a picture as long as the picture syntax is not violated.
The remainder of this paper will present the CUPID visual language tool for Creating User-Interfaces that use Pictures as Input Data. However, before presenting CUPID, we will first present some example applications that have been built with CUPID. We will then discuss how these types of applications would be built in a traditional approach. Next, we present how these applications can be quickly constructed using CUPID. Finally, the results of using CUPID will be presented, followed by our summary.
To help illustrate how useful picture based applications can be, we will present three picture based applications that have been built with the CUPID tool kit. The Image Composition program shown in Figure 1 represents how pictures can be used to represent image data as well as operations to be performed on that data. This application allows the user to construct an image expression tree composed of image names and operations to be performed on those images. The image resulting from parsing the expression is displayed at the top area of this window.
The leaf nodes in an expression tree are the names of files that contain images. The interior nodes represent image operations that operate on their children. All operations require one or more image parameters. An image parameter is specified by drawing a line from the operator node to the root of the subtree that computes the image parameter's value. Having constructed an image expression tree, the user can select any node in the tree and request that the image represented by the expression rooted at that node be computed and displayed. For example, in Figure 1 the user has entered an expression that adds the "CHI" and "95" images to produce the "CHI 95" image.
With this application a user can quickly construct an image expression tree to build a rather complex image by drawing lines between operators and image names, instead of having to type in a series of commands. The user explores possible combinations of image operations by simply rearranging the drawing. The interface becomes a workspace rather than an expression entry tool. Unfortunately current tool kits make such interfaces very difficult to write.
Another type of application that can be built with CUPID is one that can convert pictures of data to another representation such as a data file for another application. This might be done to create a more intuitive interface for another application. We constructed a genealogy application that parses an arbitrary simple pedigree tree as shown in Figure 2 into a corresponding GEDCOM file that can be used by other genealogy programs.
A pedigree tree is composed of individuals with lines between them to represent parental/child relationships. Thus a family is defined as individuals connected by lines. This makes building a family in our application a very simple task. To specify the father of an individual, the user would simply draw an arrow from the "Father:" text in the individual, to the connecting circle on the actual father individual as show in Figure 2.
Although creating an individual and adding them to a family in a program such as Personal Ancestral File is relatively simple, changing relationships between individuals is a rather difficult task. This requires specifically removing the individual from the current family, and adding them to the desired family. To do this requires the user to know the RIN, (Record Identification Number), of the individual to be removed. If the RIN is not known, the user must search the database for the desired individual so the RIN number can be retrieved. However, in our application the lines between individuals have an affordance to be moved from individual to individual to change the appropriate relationship. To change the father of an individual in our application the user would simply change the endpoint of the line from the old father to the new father.
The UNIX Shell Script Builder, Figure 3, is an example of an application built with our system that can be used as an interface to the UNIX shell. A shell script picture consists of five different type of objects.
The UNIX Shell Script Builder allows the user to draw a picture of a UNIX shell script. Lines between objects represent either a redirection or a pipe depending on the context of the line. When the user's picture is parsed, a corresponding shell script is executed.
With this approach, rather complex scripts can be built without having to know about all the various ways to pipe things around in UNIX. For example, the output of a command can be simultaneously piped or redirected to any number of other objects by simply drawing multiple lines out of the object to the other target objects. In UNIX one would have to learn about and use the tee command and temporary files to achieve the same result.
Although these examples are rather simple, they are only a small sample of a rather large class of applications that include logic diagrams, PERT-charts, organizational charts, multimedia synchronization diagrams, equation editors, genetic inheritance diagrams, circuit diagrams, musical notation, molecular modeling, object-oriented class structure and inheritance diagrams. All of these applications are characterized by diagrammatic representations of information.
Building a picture-based application such as the UNIX Shell Script Builder file in Figure 3 is a non-trivial task. A specialized direct manipulation editor must be built to allow the user to create and manipulate pictures representing user input. This editor would need to supply template objects of all possible components in an acceptable picture, such as a prompt object or command object. These template objects would be used to create objects in the picture.
As the user creates a new object from a template, the system would create an internal representation of the object. When the user modifies the contents of an object, the corresponding data structure would also be changed. To do this, the editor would have to continually monitor the user's actions in order to keep the internal representation up to date. For example, if the user were to create a command object with its default command line of "command line", the system would create an internal representation of a command with the value "command line". If the user changes the command line of the command object to say "ls -l *.pic", the system must change the contents of the internal command to match. Keeping the graphical representation and the internal representation synchronized requires some sort of mechanism for mapping between the two representations. Also required is the input handler to perform the edits on objects. Typically tool kits don't allow the user to directly edit a text value, instead a dialogue box is presented for editing.
Creating links between objects also requires the system to internally manage what objects are connected to what. This is a somewhat more difficult task than simply representing a picture object internally because changing connections between objects requires managing at least three internal objects. Two of these objects are the originally connected pair, and the third object is the newly connected object. For example, in Figure 3, the user may decide that he wants to send the output of the "grep Kohlert *.txt" command to the printer rather than the file "Kohlert.files." This would cause the system to change not only the command and file objects, but also the printer object.
Creating objects and maintaining an internal representation of the picture is one problem that must be overcome when building a picture based application. However, there are many small problems that must be solved such as constraint problems that will constrain graphical objects to each other so that when they are dragged they stay connected. For example, in Figure 3, if the user were to drag the entire Command rectangle, both the lines connected to it would also move, thus eliminating the need for the user to reattach the lines. However, there are systems such as Unidraw [11] that can help solve this problem.
Although creating such an editor is not extremely difficult, it does require some serious thought and design. To create such a specialized editor would take several weeks to program, not to mention design and testing time.
The focus of this section is to describe how a picture-based application is built with CUPID. To do this we will use the UNIX Shell Script application as our target application. Our approach to this problem is to start with a fully functional constraint-based drawing editor with additional picture parsing primitives. We will then restrict the editor to the target domain rather than build up an editor from tool kit primitives.
All applications built with the CUPID tool kit have two windows. The main window is based on a drawing editor. The other window is a palette of draw objects or templates that can be drawn in the drawing window. For example, the UNIX Shell Script Builder created with CUPID is shown in figure 4.
The window on the right is the main drawing window with an already existing shell script picture. The palette window on the left shows the various template objects that are used to draw script pictures.
The drawing editor used by CUPID, and the applications created with CUPID, is primitive-based similar to MacDraw. Each primitive, or draw object, is created and manipulated by control points. To create a new object in the drawing window, one of the template objects in the palette must first be selected. To then draw the object, the user clicks in the drawing area once for each control point. For example, if the selected template object was a command line object from figure 4, the user would click in the drawing window once for one corner of the rectangle, and once for the opposite corner.
Once on object has been drawn, it can be edited in many ways. An object's location may be changed by selecting the object and dragging it to the desired location. The size and possibly shape of an object can be changed by selecting one of an object's control points and dragging it to the desired position.
Placing or dragging a control point on top of an already existing object constraints that point to that object. Such control points are constrained to that object. Thus if the underlying object is moved, the control point will also move. If the object is resized, the control point will remain proportionately in the same location. For example, in the sample script picture in figure 4, the line between the "rev" command and the "sort" command are mapped to those objects. If the user grabbed the end of the line over the "sort" command and moved it to be over the "outfile" file name object, then that line control point would then be mapped to the file name object instead of the command line object.
Other attributes that can be edited on appropriate draw objects include line width, line color, fill color, font face, point size, and font style.
The drawing editor also allows for grouped objects. A group object is one or more objects that are treated as a single object. There are two different types of groups supported by this editor. One type simply takes any number of selected objects and wraps an invisible wrapper, rectangle, around them to make them one object. This type of group is not scalable since the objects have no real relation among them.
The other type of group takes a selected object, and groups all other objects that are mapped to it through transitive closure, into its own parametric space. Thus when the base object is resized, all the subobjects will also be resized. All of the interactive behavior described so far is all built into the general drawing editor, and is thus, not built by the tool designer.
Each of the template objects in the palette window in figure 4 with the exception of the arrow-line are primitive objects that have been grouped. The command line, file name, and printer objects are grouped around their base rectangles, while the prompt is grouped around the base circle.
Once an input data diagram has been drawn in a CUPID generated application, the picture may be parsed by pressing a "Parse Picture" button. Parsing a picture means to interpret the picture within the application's domain. For example, the UNIX Shell Script Builder knows how to parse and interpret pictures of UNIX shell scripts created within itself. However, the shell script builder does not know how to parse or interpret pedigree charts, or even pictures of shell scripts created in other applications.
In short, applications built with the CUPID tool kit are based around a drawing editor which allows the user to draw pictures of input data from a small, but complete, set of template objects designed especially for the application. Once the picture is drawn, the user can tell the application to interpret the picture by pressing a "Parse Picture" button.
Now that the reader is familiar with the workings of applications built with CUPID, the next section will discuss how to build such an application.
In order to build a picture based application with CUPID, there are three things that must be done: template objects must be created, a picture parsing routine must be defined, and user-changeable attributes must be decided. After all of these things have been done, CUPID can generate the code for the desired application.
Templates. Template objects are used by the user to create new draw primitives. Template objects contain most of the pertinent information needed by the desired application. For example, a file object in figure 4, contains the name of a file to be used in a shell script.
Templates are used for three different reasons. First, template objects eliminate the need for users to draw complex objects by hand. Second, templates help the user draw more easily parsed pictures by limiting their choices of drawable objects. If all draw primitives were available, without any application specific template objects, the user would be less likely to produce a parseable picture. Third, template objects can be used to enforce geometric relationships that can be utilized by the picture parsing routine.
Template objects are built in a drawing editor just like the one the end user will use except a richer interface is provided. It provides a full palette of primitive draw objects including circles, rectangles, parallelograms, arcs, splines, text and various types of lines.
A template object is created by combining one or more draw primitives together. For example, to draw the command line object template in figure 4, a base rectangle object is drawn first. Next, a text object is placed on this rectangle and its value edited to be "Command Line:." Another text object is then placed on the rectangle and its text is edited to be the default value of "Command ." Now the base rectangle can be selected and made into a group, thus making it and the two text objects one group object.
Although the command line template built above would work, there is some danger in using this template. The main danger is that all drawing objects are free to be edited by the user. Although the user should be able to edit the "Command" text object to be actual commands, they should not be able to change the "Command Line:" text since this is what will be used to identify a command line object. Also, since the picture parser will be defined using geometric relations (this will be described later) and since the "Command" text object needs to remain below the "Command Line:" text object, the user should not be allowed to change the position of these text objects.
To remedy this problem, the "Command Line:" text object can be made locked so that it may not be edited. Also, the positions of these text objects can be locked so that they may not be moved by themselves. They can then only be moved when the base rectangle is moved. With the template object constrained this way, the end user will not be able to move either of these text objects and thus will only be able to edit the "Command" text object or move the base rectangle.
To make a template object available to the user in the final application, it must be put into the template palette. To do this the desired template object is copied into the template palette window of the CUPID tool kit. CUPID will only use the objects in this window as templates for the final application. Thus, nothing else that is drawn in the main drawing editor can be used as a template. Also, none of the primitive draw objects are made available in the final application unless the application designer draws one and copies it into the template palette window.
In short, building template objects involves three main concepts: drawing the object with primitive draw objects, locking and constraining the appropriate pieces of the object, and placing the object in the palette window.
Parsing Routine. The next step is to define a parsing routine to extract pertinent information from the picture. Traditional applications that use graphical representations of internal data structures such as TRIP3, do not actually parse pictures, but rather maintain an internal representation as the picture is manipulated. Applications built with CUPID on the other hand actually retrieve all information directly from the picture itself by means the NIC [6] scripting language NICScript [7].
The NICScript is similar to other scripting languages such as Tcl [10] and SuperTalk [1]. However, the NICScript language has been extended to parse pictures created by the drawing editor described above.
The extensions made to the NICScript language for this work include geometric parsing methods on draw primitives. These parsing methods are based on the object's bounds, control points, and a selection criteria.
With NICScript, the designer may specify how to parse a picture by means of geometric relationships such as Right, Above, Touches and ConnectedTo. These are the same types of relations that are used by other visual language parsers [2][4]. Each of these relations has a corresponding method that has been defined on the base draw object class. These methods include:
Geometric Searches. These methods can be used to find objects relative to the target object. For example, in Figure 5, if object A were the target object and the DirRight (Directly Right) method were called, then the set of objects {a, b, B, E, G} would be returned.
In contrast to the DirRight method, the Right method is used to access all objects that lie somewhere to the right of the object. Thus, if the Right method were called on object A, then the set {a, b, c, B, D, E, F, G} would be returned.
Each of these methods simply uses a bounding box to locate other objects. This bounding box is an extension to the target object's bounds. Any object that intersects the defined bounding box is returned in a sorted list.
For example, in Figure 5, if we called the DirLeft method on object F, then a rectangle extending from the left edge of F with the same height would be extended to the left edge of the drawing. Objects D, b, c, and C would be returned in a list in that order. All of the left methods return objects sorted right-to-left. All of the right methods sort the list left-to-right, while the above methods sort bottom-to-top and the below methods sort top-to-bottom. The other methods, such as Touches, are unsorted.
Although there are methods for right, left, above, and below, we sometimes need to find objects that are below and to the left of an object. To accomplish this, each of the parsing methods returns a Set object containing the objects found. The Set class has methods defined on it for doing union, intersection and difference, allowing the user to access an object to the lower-left by calling the Left and Below methods on the desired object and then intersecting the resulting sets. The Set class also has methods defined for sorting the set in a particular direction such as right-to-left, or top-to-bottom. This allows the user to access objects closest to or farthest away from the current object in the desired direction.
Selection. The parsing methods as described so far, allow the user to find all objects that have a certain geometric relation to the target object, however, the script author may only be interested in certain types of objects, say circles. To allow the user to specify what type of objects should be returned a selection pattern is passed as an argument to the various parsing methods. Only objects that match the pattern are returned.
One type of pattern is simply a class name. With a class name pattern, only objects that are of the specified class are returned. For example, in Figure 5, if object A is the target object and the pattern :PolygonDO (polygon draw object) is passed as an argument to the Right method then only the set containing object B will be returned. Patterns can be used to match any attribute of an object such as color, line width etc. A complete description of NIC patterns can be found in the NIC documentation [5].
Connections. Direct relations between objects are usually represented by drawing lines between the objects. There are three methods that can be used to discover these relations: Connected, ConnectedTo, and ConnectedFrom. These methods find objects that are connected to the target object in various ways.
Before these methods are explained, it is necessary to explain that two draw objects can be connected by any other draw object. For example, in Figure 5, the objects A and D are connected by line b, objects C and B are connected by a, objects C and D are connected by c, and objects E and F are connected by object G. In order to connect two draw objects x and y, another draw object w must have its first control point within x, and its second control point within y. In our example picture, object A is connected to object D by arrow line b. Thus the first control point of b is in A, and the second control point of b is in D. Control points are numbered by the order they are specified. Thus the first control point specified is numbered 1, while the second point specified is numbered 2, etc.
It is important to note that connectedness is a pictorial relation to be discovered and not simply stored internally. Each of the methods used to find connections have, in addition to a selection pattern, a connection pattern as a parameter. The connection pattern is similar to the selection pattern but it is used to determine what types of objects can be considered as connectors. For example, a connection pattern of :LineDO, will only consider lines to be connectors, while a pattern of (| :LineDO :RectangleDO), where | is the OR operator, will accept lines or rectangles as connectors.
The Connected method simply returns all objects that are connected to the target object. The ConnectedTo method returns all objects that are connected to the target object when the first control point of the connector is within the target object and the second control point is within the other object. In the example picture, A is connected to D, C is connected to B and D, and E is connected to F. The ConnectedFrom method is just the opposite of the ConnectedTo method in that the second control point of the connector must be within the target object and the first control point must be within the other object. Thus in the example picture, D is connected from A and C, B is connected from C, and F is connected from E.
Writing Scripts. Most of writing the parsing script is simply calling various parse methods on draw objects. In the UNIX shell script builder, the "Prompt" object specifies where the script is to begin. To find the prompt object we can call the Children method on the root group draw object of the drawing editor
(:= (!RootGroup Children :CircleDO) !Prompt)passing :CircleDO as the selection pattern since the prompt is the only circle object in the picture.
From the "Prompt" it is necessary to find the first command to run. Calling of the "Connected" method on the "Prompt" similar to
(:= (!Prompt Connected :ArrowLineDO :RectangleDO)
!CmndObj )
will return all :RectangleDO objects connected to the "Prompt" object by an
:ArrowLineDO.
In the example UNIX shell script picture in Figure 4, this will be the rectangle object containing the text objects "File Name" and "infile." To get the "File Name" text object from within this object we can call
(:= (!CmndObj Children (:! (& :TextDO
([Value "File Name"])
) ) )
!FileNameLabel )
This will return all text objects that have the text "File Name" and are children of the !FileObj, where !FileObj is the rectangle object found above. To actually get the name of the file we want we could then call
(:= (!FileNameLabel DirBelow :TextDO) !FileName)
where !FileNameLabel is the "File Name" text object found above. This call will find the text object that lies directly below the !FileNameLabel object. In this case this will be the text object whose value is "infile."
It is important to note at this point that this example does not find the "infile" text object in the most efficient manner. We choose to use this example to give the reader a better feel for how the geometric parsing can be used.
Editable Attributes. The final step in building a picture-based application with CUPID is to determine which attributes the user should be able to edit in the final application. This is important because as was mentioned earlier, the parsing routine may use selection patterns that are based on an object's attributes. For example, the parsing routine of the shell script builder may require that all Printer objects be purple.
To prevent the user from making the mistake of changing the color attribute on such an object, the application designer can tell CUPID to not put the interface components necessary to change a certain attribute into the final application. CUPID provides a checklist of attributes that can be removed from the final application. Thus the designer simply selects the attributes that are to be included in the final application. For example, if the designer specified that the FillColor attribute should not be editable in the UNIX Shell Script Builder, then CUPID would generate the same application shown in Figure 4 except the FillColor interface components below the LineColor interface components would be missing.
After completing these steps CUPID can generate the NICScript code for the desired application.
Generating an Application. Because CUPID and its applications are built upon NIC, the data model, scripting language, pattern language, and user interface tools are all integrated into one data model. Thus the templates, and parsing routines, built with CUPID are nothing more than NIC data objects.
CUPID uses these data objects to modify an existing template of a generic application. This template user interface looks just like the UNIX Shell Script Builder in Figure 4 without the template objects and example picture. Inserting the template objects into a new application is achieved by adding a statement to the template interface's initialization code to load a template file which CUPID creates. The parse routine defined in CUPID can then be attached to the "Parse Picture" button by setting the Action attribute on that button with the desired routine.
Removing the user interface components that edit attributes that should not be editable is done by finding those components in the interface description and removing them from the interface.
Generally the interface generated by CUPID is sufficient. However, if the designer is not satisfied with the design of the default interface, or simply needs to add more to the interface, the interface may be loaded into NIC's interface editor to be edited as desired.