UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Automating the generation of interactive applications Noik, Emanuel Gerald 1990

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1990_A6_7 N64.pdf [ 7.4MB ]
Metadata
JSON: 831-1.0051979.json
JSON-LD: 831-1.0051979-ld.json
RDF/XML (Pretty): 831-1.0051979-rdf.xml
RDF/JSON: 831-1.0051979-rdf.json
Turtle: 831-1.0051979-turtle.txt
N-Triples: 831-1.0051979-rdf-ntriples.txt
Original Record: 831-1.0051979-source.json
Full Text
831-1.0051979-fulltext.txt
Citation
831-1.0051979.ris

Full Text

Automating the Generation of Interactive Applications by Emanuel Gerald Noik B.Math., The University of Waterloo, 1988 A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Science in The Faculty of Graduate Studies Department of Computer Science We accept this thesis as conforming to the required standard University of British Columbia July 1990 ©Emanuel G. Noik, 1990 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Computer Science The University of British Columbia Vancouver, Canada D a t e J u l y 1 7, 1990 DE-6 (2/88) Abstract As user interfaces become more powerful and easier to use they are often harder to design and implement. This has caused a great demand for interface tools. While existing tools ease interface creation, they typically do not provide mechanisms to simplify application development and are too low-level. Furthermore, existing tools do not provide effective mechanisms to port interactive applications across user interfaces. While some tools pro-vide limited mechanisms to port applications across user interfaces which belong to the same class (e.g., the class of all standard graphical direct-manipulation user interfaces), very few can provide the ability to port applications across different interface classes (e.g., command-line, hypermedia, speech recognition and voice synthesis, virtual reality, etc.). With my approach, the programmer uses an abstract model to describe the structure of the application including the information that the application must exchange with the user, rather than describing a user interface which realizes these characteristics. By specifying application semantics at a very high level of abstraction it is possible to obtain a much greater separation between the application and the user interface. Consequently, the resulting applications can be ported not only across user interfaces which belong to a common interface class, but across interfaces which belong to distinct classes. This can be realized through simple recompilation - source code does not have to be modified. NAAG (Not Another Application Generator), a tool which embodies these ideas, en-ables programmers to create interactive applications with minimal effort. An application is modelled as a set of operations which manipulate objects belonging to user-defined ob-ject classes. The input to NAAG is a source program which describes classes, operations and their inputs and outputs, and the organization of operations within the application. Classes and operations are implemented as data structures and functions in a conven-tional programming language such as C. This model simplifies not only the specification and generation of the user interface, but the design and implementation of the underlying application. NAAG utilizes existing technology such as macro-preprocessors, compilers, make pro-grams, and low-level interface tools, to reduce the programming task. An application that is modified by adding, removing, or reorganizing artifacts (classes, operations, and menus), can be regenerated with a single command. Traditionally, software maintenance has been a very difficult task as well. Due to the use of a simple abstract model, NAAG applications are also easier to maintain. Furthermore, this approach encourages software reuse: applications consisting of arbitrary collections of original and pre-existing artifacts can be composed easily; functions which implement abstract operations are independent of both, user interface aspects, and the context in which they are employed. Application development is further simplified in the following ways: the programmer describes the semantics of the user interface - a conventional explicit specification is not required; output primitives are defined in an interface-independent manner; many pro-gramming tasks such as resource management, event processing, and communication, are either handled directly by the tool or else simplified greatly for the programmer. NAAG is currently used by the members of the Laboratory for Computational Vision at the University of British Columbia to maintain a sophisticated image processing system. 1 Preface Two roads diverged in a wood, and I -I took the one less traveled by, And thai has made all the difference. —Robert Frost, The Road Not Taken This document describes my research into techniques for automating the genera-tion of interactive applications. My work was originally motivated by the lack of and the demand for tools which could enable programmers to generate interactive applications which employ graphical, direct-manipulation user interfaces. The pri-mary focus and test bed was in the domain of image processing and computational vision at the Laboratory for Computational Vision (LCV). A number of constraints and requirements were identified during the early phase of this work. In particular, members of the LCV wanted a system which: 1. would automatically generate user interfaces, 2. would not be dependent on a particular user interface or interactive style, and, 3. would allow individuals to add new features to existing applications and create custom applications from existing artifacts. The tool that I have developed is currently used to create vision and image processing applications for both research and teaching purposes at UBC, and will be distributed to other sites in the future. The LCV image processing system is described in an Appendix to this document. n Contents Abstract i Preface ii List of Figures vi List of Tables viii Acknowledgements ix 1 Overview 1 1.1 Introduction 1 1.2 Sneak preview 3 1.3 Definition of terms 6 1.3.1 What is an interactive application? 6 1.3.2 What is a user interface? 6 1.3.3 What is an application generator? 8 1.3.4 How are user interfaces generated? 9 1.3.5 Dialogue independence 12 1.4 Why do we need better tools? 13 1.4.1 A brief history 13 1.4.2 What is required? 13 1.4.3 What is currently available? 14 1.4.4 What I have done 14 2 Related topics 16 2.1 Application generators 16 2.1.1 Third- versus fourth- generation languages 17 2.1.2 Pros and cons 17 2.1.3 Application generators and user interface tools 18 2.2 Programming languages and methodology 18 2.2.1 Little languages 19 2.2.2 Very high level languages 21 iii 2.2.3 Specification of semantics versus syntax 23 2.2.4 Object oriented programming 24 2.3 Software engineering considerations 24 2.3.1 Reuse 25 2.3.2 Portability 28 2.3.3 Correctness and conformance . 29 2.3.4 System models 30 3 Previous work on user interface tools 32 3.1 Motivation 32 3.2 TIGER/UIMS 33 3.3 MENULAY 34 3.4 SYNGRAPH/MIKE 35 3.5 UIDE/IDL 37 4 M y approach 42 4.1 Motivation and justification 43 4.2 NAAG 47 4.2.1 Who is involved: roles and tasks 48 4.2.2 Application model 49 5 Implementation 59 5.1 Overview 59 5.1.1 Main program 60 5.1.2 Lexical analysis 61 5.1.3 Syntactic analysis 62 5.1.4 Code generation 64 6 Discussion 67 6.1 Dialogue independence 67 6.2 Software reuse 68 6.2.1 Application software 68 6.2.2 UI software 68 6.2.3 Software sharing 68 6.3 Levels of representation of abstract objects 69 6.3.1 The NAAG perspective 70 6.3.2 The image processing perspective 71 6.3.3 Conclusions 71 6.4 Conformance issues 72 6.4.1 Look-and-feel 73 6.4.2 Interactive facilities 73 6.4.3 Operation semantics 75 6.4.4 System model 75 iv 6.5 Relationship to existing systems 76 6.6 Experiences 77 7 Final remarks 78 7.1 Summary and conclusions 78 7.2 Future directions 80 7.2.1 Extensions 80 7.2.2 Graphical editors 81 7.2.3 Adaptive dynamic generation of user interfaces 83 Bibliography 86 A N A A G command line arguments 90 B N A A G language grammar 91 C U B C Integrated Vision System 94 C.l Utilities 94 C.2 A sample image processing operation 95 C.3 Existing components 97 C.4 NAAG listing of main program 97 v List of Figures 1.1 The UBC Integrated Vision System (X Windows version) 4 1.2 A sample drawing application (X Windows version) 5 1.3 An application taxonomy based on the duration of a typical operation and the degree of interactivity 7 1.4 Relationship of the IAG to other tools 10 1.5 An early UIMS model 10 1.6 A current UIMS model 11 2.1 Ranking reuse strategies by cognitive distance (least to greatest). . . 27 3.1 IDL specification of the squares and triangles example 39 4.1 Role interaction in N A A G 50 4.2 Slice operation description 51 4.3 Slice dialog box generated by N A A G 52 4.4 A N A A G menu 53 4.5 A partial menu tree attached to an image object 54 4.6 N A A G class inheritance tree 54 4.7 A N A A G main program 55 4.8 N A A G program tree 56 4.9 A N A A G class definition 57 4.10 Subclass data structure 57 4.11 A rubber-banding routine 58 5.1 N A A G framework for application development 60 5.2 range argument data structure 63 5.3 argument data structure 63 5.4 application data structure 63 5.5 Dynamic creation of the range data structure 64 6.1 Range Demo operation description 74 6.2 Range Demo dialog box generated by N A A G 74 7.1 Framework for adaptive dynamic generation of human-computer in-terfaces 85 vi B . l A basic N A A G program 92 B.2 A N A A G class 92 B.3 A N A A G menu 92 B.4 A N A A G operation 93 B. 5 A stub menu item 93 C. l util.h header file 95 C.2 image.h header file 96 C.3 Precondition functions for image object class 96 C.4 C source code for the invert operation 97 C.5 N A A G source code for the invert operation 99 vii List of Tables 4.1 NAAG operation argument types 51 4.2 NAAG primitives 53 5.1 A set of useful routines for manipulating common UI elements 66 6.1 Levels of object representation 70 B. l Coding conventions 91 C. l Existing classes 97 C.2 Existing operations 98 vi i i Acknowledgements I am indebted to my supervisor, David Lowe, for many reasons. He brought to my attention the problems which lead to this work, and helped to shape my ideas - to separate the essential from the merely fantastic. Above all, however, David treated me with the respect befitting a colleague. He showed great faith in my work and was a constant source of inspiration and confidence. David will be one very tough act to follow. I would also like to extend my gratitude to Jim Little for his willingness to read this thesis and for his many helpful suggestions. His infectious zeal and sharp wit are a pleasure to behold. I will be survived by the other two thirds of Cerberus: Andrew Csinger and Michael Horsch. Andrew is unique in having helped me to realize that there is more to life than meets the average eye, and that realizing this has to be the full-time responsibility and occupation of each and every one of us. I hope I will continue to profit from his wisdom and friendship. Mike has been a very supportive friend. He was always willing to listen, to offer a constructive opinion, and has stood up for on more than one occasion. He will remain with me always. Oh yeah, Cerberus also helped with the thesis and was great company at the Pit. There are many others who in their very own unique and personal way made a difference. Among them are: Julian Craddock, Heidi Dangelmaier, Cal Deedman, Norman Goldstein, Hilde Larsen, Steve and Sarah Mason, and David Sidilkover. Last, but never least: my parents. Although they were four thousand kilometres distant, their love and support was steadfast and unsparing. I guess I have been very lucky. ix Chapter 1 Overview I must create a system, or be enslaved by another man's. —William Blake 1.1 Introduction In recent years we have witnessed a growing trend in the use of interactive appli-cations which employ sophisticated user interfaces. In order to combat the high development cost which characterizes such applications, a number of interface gen-eration techniques have emerged. Many approaches have attempted to reduce the complexity of the programming task by casting the interface specification problem in high-level terms. In so doing, they possess many advantages of application gen-eration systems, such as those offered by fourth generation languages. With the advent of this new technology, there has been a pressing need for tools which allow programmers to build interactive applications quickly, inexpensively, and in a manner which promotes not only device independence, but also user inter-face independence. In most current approaches the user interface has been treated as an add-on to an otherwise independent application. Common interface tools provide the mechanisms to create a user interface and the glue to bind it to the underlying application. Most tools, however, do not provide mechanisms to aid the design, implementation, and maintenance of interactive software systems - they lack an overall unified approach to application development. This deficiency is just a hint of a much greater prob-lem: the lack of progress and innovation in software engineering practices. While computer hardware has been continuously evolving, the way that we build software systems has changed very little during the past twenty years. If we do not succeed in finding more powerful methodologies for producing software systems, the gap be-1 CHAPTER 1. OVERVIEW 2 tween the hardware and software technologies will continue to widen. In particular, if we fail to devise more effective techniques to generate user interfaces, we may not be able to take advantage of the improved hardware. Assuming that the main goal of human-computer interaction research is to build computer systems which are easier to use, progress in this direction is crucial. In my work I propose a radically different alternative to the user interface as an add-on philosophy. Instead of viewing the user interface creation task as being separate from application development, I treat the user interface as something that can be generated automatically as a side-effect of describing an application. This approach relies heavily on the use of an appropriate application model during all stages of software development1. I show how an application model can both simplify the development task, and provide the means to automate the generation of user interfaces. I conclude that future progress in user interface construction may depend on the discovery of relevant models - models which are capable of describing ap-plication semantics at a very high level of abstraction, and which contain sufficient information to generate a wide variety of user interfaces. In the rest of this chapter I define the basic concepts and justify the need for tools which reduce the amount of programming effort required to develop interactive applications. Chapter two identifies relevant issues in related areas and may be omitted on first reading. Specifically, it refers to work in the following: • automatic application generation, • programming languages and methodology with reference to little and very high level languages, specification of semantics versus syntax, and object-oriented programming techniques, and, • software engineering aspects with reference to reusability, portability, program correctness and conformance, and system models. Chapter three outlines previous work in the area of interface tools and techniques. Chapter four describes my approach and the tool which I have developed. Chap-ter five features the implementation details and a discussion of some of the issues which arose during development. Chapter six uncovers several consequences and implications due to my approach, contrasts it to previous approaches, and discusses the experiences of users who have used my tool. Chapter seven offers summary and concluding remarks including suggestions for future work. xIn this context, the function of the application model is to describe the architecture or structure of the application through the specification and organization of its constituent abstract compo-nents (rather than modelling the semantics of the underlying computation). An essential part of this description is the specification of the inputs and outputs of each component - this information is used in part to generate a suitable user interface. CHAPTER 1. OVERVIEW 3 1.2 Sneak preview Before launching into the thesis, it may be helpful to see an example of the type of application that we are trying to generate automatically. As mentioned in the Preface, the key testbed for NAAG was in the domain of computational vision and image processing. Aside from the constraints listed in the Preface, the requirements in this area could be characterized as follows. 1. Most objects belong to several object classes (data types) such as Image, Edges, and Mask. This implies the following. • Most operations will manipulate objects belonging to one of these classes and thus operations can be composed (the output of one operation may become the input to another). A sequence of simple operations can be used to describe complex operations. • A standard set of routines for reading, writing, creating, destroying, and displaying objects can be reused. 2. An interface must provide the means to view and manipulate image and graph-ical data. It must also provide effective ways for the user to access any of a large number of operations, including help information, and context-free and context-sensitive enabling of commands. Without further delay, Figure 1.1 shows a vision application which was created using NAAG.2 In particular, note the presence of several objects each of which is displayed in its own window. These objects belong to several classes: an unsigned and a signed image, a histogram, and a set of linked edges. The objects were created as follows: 1. The unsigned image was read in from a file using the readlmage operation which reads a file and returns an image object. 2. The histogram was obtained by applying the histogram operation on the un-signed image. This simply counts the number of occurrences of intensity values in a number of intervals as specified by the user. 3. The signed image was obtained by applying the convolution operation on the unsigned image. This operation prompts the user for the filename of a con-volution mask to be used in the operation and returns the resulting signed image. 4. The edges object was obtained by applying the UnkEdges operation on the signed image. This operation uses the signed data to find edges (marked by 2The vision system is described in more detail in Appendix C. CHAPTER 1. OVERVIEW 4 Figure 1.1: The UBC Integrated Vision System (X Windows version). CHAPTER 1. OVERVIEW 5 Figure 1.2: A sampie drawing application (X Windows version). abrupt intensity changes) and then attempts to link these edges to form linked lists of edges. As a further example, Figure 1.2 shows a simple drawing application created with NAAG. This program allows the user to draw points, lines, rectangles, and freehand sketches by using the mouse. The graphical output is completely resizable - when the drawing window is resized, its contents are resized appropriately and the correct aspect ratio is maintained. Window management is performed automatically by NAAG - the programmer does not have to supply code to do this. CHAPTER 1. OVERVIEW 6 1.3 Definition of terms 1.3.1 What is an interactive application? As its name implies, an interactive application communicates or interacts with the user - to obtain information required to carry out some task, to display results, and to provide help information and other forms of semantic feedback. This stands in contrast to non-interactive applications which, once invoked, function independently of the user. For example, consider an application which performs simple image processing operations on image data. In the two extreme cases it could be written as: 1. a non-interactive program which obtains al l of the necessary information at the time of invocation via command-line arguments, or, 2. an interactive application which, once invoked, displays intermediate results, and prompts the user to provide information as it is required. Note that al l applications exhibit some degree of interaction. The degree of interaction forms a continuum along which al l applications can be positioned. A more helpful way to classify applications might be by the relationship between the degree of interactivity and the duration of a typical operation. Figure 1.3 is a graph of duration versus interactivity for a number of common programs. Al though the absolute positions of programs are highly subjective, their relative positions provide useful information. In particular, note the following: SW Corner - Simple, relatively non-interactive programs. N W Corner - Complex, slow, batch-oriented programs. SE Corner - Fast, specialized, and highly interactive programs. N E Corner - None; a highly interactive application wi th long operation durations is a contradiction in terms. Diamond - Common interactive workstation applications. Circle - NAAG'S intended target area. 1.3.2 What is a user interface? A user interface (UI) , in simplest terms, is that part of the application which in-teracts wi th the user - by prompting for inputs, displaying outputs, and providing various forms of semantic feedback. The U I can be thought of as the the medium through which man and machine communicate. It is comprised of both hardware and software. Note, however, that CHAPTER 1. OVERVIEW 7 Long Duration of a Typical Operation Short Oweather Forecasting System's, o DP Applications,^' /o / Compilers o grep, sort o Vision Systems ° o Software Tools w ^ CAD Packages-' •-P n / / Spreadsheets X--"' / Paint .Brogratfis o \ more, rn x \ o Is, clear, who / Text Editors Flight Simulators O I Low High Degree of Interactivity Figure 1.3: An application taxonomy based on the duration of a typical operation and the degree of interactivity. CHAPTER 1. OVERVIEW 8 the UI is distinct from the dialogue. The dialogue is a language or protocol which describes the interaction - as an exchange of (abstract) symbols between man and machine, for example.3 Furthermore, note that just as a single UI can be used to implement many dialogues, so can a given dialogue be realized using many UIs. From the software development perspective, it can be advantageous to view the UI as being separate from the rest of the application, although this separation is seldom fully achieved in practice. I give a more detailed discussion of this concept in Sections 1.3.5 and 6.1. An example of a common type of UI is the graphical direct manipulation interface used by the Apple Macintosh computer. The user can use the mouse to interact with various objects by pointing, clicking, and dragging. This type of interface relies heavily on a visual rather than a textual means to communicate with the user. For example, objects such as files or programs are displayed as icons - small graphical symbols which typically represent more complex objects. 1.3.3 What is an application generator? An application generator (AG) is a special purpose tool which can be used to create an application from a high-level description. AGs typically provide a number of standard utilities, such as: • obtaining simple inputs from user, • providing help information, : • plotting simple graphs (bar graphs, pie charts), and, • database utility functions (create, read, write, compute statistics). Most AGs are designed to create very specialized applications. By far the most common type of AG is one which generates business applications for storing, re-trieving, analyzing, and displaying information. A feature supported by many AGs is a Symbolic Query Language (SQL) facility which can be used to combine and display database information in a variety of ways. While interest in AGs has waned in academic circles, many companies use AGs to remain competitive - by increasing their productivity and their ability to rapidly develop applications in order to meet customer needs quickly. AGs were the first tools which addressed a number of problems in UI design. In my work, I have attempted to create an AG which emphasizes the creation of the UI, and is less domain-specific. I use the term interactive application generator 3In fact, dialogues have been expressed as various forms of finite automata, consisting of states, inputs, and transition functions [Jac83, Was85]. ' CHAPTER 1. OVERVIEW 9 (IAG) to refer to this type of tool. 4 Figure 1.4 shows the relationship between the I AG and other tools. A prototypical AG is IBM's Interactive System Productivity Facility (ISPF). ISPF is a commercial form-filling, menu-oriented display management tool, designed specifically for the IBM 3270 display terminal and MVS/TSO or VM/CMS operating systems. 1.3.4 How are user interfaces generated? A number of different techniques have been devised to automatically generate UIs. In this section I briefly describe three common techniques: UI toolkits, User Interface Management Systems (UIMSs), and Interactive Interface Builders. i Toolkits One of the earliest ways to provide a standard set of tools to manage the dialogue between man and machine, was to create a set of routines which could be invoked by the application to obtain inputs and to display outputs. Toolkits have grown from very simple systems which contained only a few basic functions, to sophisticated systems which enable the programmer to build complex graphical user interfaces. Regardless of its complexity, a UI toolkit is characterized by the presence of a set of routines which may be invoked by the application to carry out various types of interaction. A well-known example is the X Windows System, developed at the Massachusetts Institute of Technology [SG86]. User interface management systems The focus of early work in UIMSs was on support for the execution of the UI -especially through the use of graphics software. The summary report of the Graph-ical Input Interaction Technique Workshop illustrates this emphasis by stating that "The role of a UIMS is to mediate the interaction between an end-user and an ap-plication..." [GII83]. Figure 1.5 shows one early model of a UIMS. Note that in this model the connection to the user is not shown. In particular, early UIMS work did not emphasize UI development activity - it was not concerned with the user, human factors of UIs, or methodologies for software or UI development. A more recent view of the UIMS is depicted in Figure 1.6. It includes consider-ations of the user and the dialogue developer. A dialogue developer creates the UI (Dialogue Component) with the aid of UI tools. An application programmer pro-duces the system's computational software, providing its functionality. The UI is 4While the application domain of AGs is typically specific (e.g., business information systems), the domain of the IAG is the creation of UIs. CHAPTER 1. OVERVIEW 10 Figure 1.4: Relationship of the IAG to other tools. " I 1 User Interface [ Application Manager | • Program Graphics System Figure 1.5: An early UIMS model. CHAPTER 1. OVERVIEW 11 external dialogue ( User ) Evaluator internal dialogue Computational Component Dialogue Development Tools Programming Environment feedback for iterative refinement inter-role communication Application Programmerj L E G E N D Computer-Computer Interaction Human-Computer Interaction Human-Human Interaction Figure 1.6: A current UIMS model. CHAPTER 1. OVERVIEW 12 typically executed at run time and communicates with the Computational Compo-nent via an internal dialogue. The two developer roles communicate and coordinate their efforts, while users and evaluators give feedback about the interface and system functionality. Interactive interface builders Interactive interface builders are UI tools which allow the dialogue developer to describe the UI interactively. Several arguments favour the use of interactive UI tools. First, interactive tools are often easier to use than tools which rely on a textual specification of the UI. Second, it is often useful to describe the UI using a tool which employs a similar UI, because it gives the dialogue developer a better feel of the UI that is being created. Third, interactive tools may provide better facilities for direct simulation of UIs and therefore may be more appropriate for use in rapid prototyping. An example of one such tool is the SmethersBarnes Prototyper - a tool for rapid design, prototyping, and testing of UIs for Macintosh applications. The intention with Prototyper is to ease the task of learning the intricacies of application de-velopment on the Macintosh, to provide a tool that complements the developer's existing tools, and to provide an effective means of communication for those in-volved in the development task. Prototyper's operational metaphors exploit widely used object-oriented drawing concepts - Prototyper focuses on menus and windows, with a menu editor and a window editor that include a palette of standard UI ob-jects. Prototyper dynamically creates Macintosh resource data structures and uses the Macintosh Toolbox, thus applications produced using Prototyper are highly compliant with accepted Macintosh UI standards. 1.3.5 Dialogue independence The notion that an application consists of an interactive or dialogue component which is responsible for carrying out human-computer interaction, and a compu-tational component which consists of the software which realizes the application's functionality can be very useful. The situation in which this feature can be maxi-mally exploited, is in developing software in a manner which allows the two compo-nents to be independent - a change in one will not affect the other. This property is known as Dialogue Independence (DI) [HH89](pp. 12-16). Note, however, that the term DI is somewhat misleading. At the more abstract, conceptual level of the dialogue, the application will necessarily communicate the same information (albeit in a different manner) regardless of the UI. Thus a more appropriate name might be UI independence. While good programmers have been separating code which interacts with the user from code which performs computations, the resulting programs still contain CHAPTER 1. OVERVIEW 13 inter-mixed code. It is not sufficient to simply isolate dialogue software in sepa-rate functions or modules. In this scenario, dialogue-oriented code is linked to the computational code and thus cannot be modified independently of the rest of the program. In order to achieve Dl, we must be able to support design-time separation of dialogue and computational software. Thus an interactive application consists of a dialogue component which handles all of the communication between the user and the application, and a computational component which realizes the underlying functionality. While kept separate during system design and maintenance, these components are typically bound together at execution. 1.4 Why do we need better tools? 1.4.1 A brief history Many early systems were very low-level and required substantial programming effort in order to carry out even the simplest tasks. In response to this problem a number of toolkits were developed. These allowed the programmer to describe the UI at a higher level and reduced the complexity of the programming task. Unfortunately, as UIs became more powerful and easier to use, they typically became more difficult to create. The original motivations and advantages of toolkits were thus diminished. Furthermore, since little consensus has been reached regarding standard guidelines for designing UIs, a proliferation of UIs and toolkits has resulted. This has had the unfortunate consequence that software written for a given UI cannot be easily ported to a different one. Rewriting only those portions of the application which interact with the user is expensive and in most cases is simply not feasible. For these reasons there has been a great deal of reluctance to employ new technology due to fear of commitment to a single environment and premature obsolescence. The growing acceptance of X Windows as a standard architecture for developing interactive graphical applications is encouraging. 1.4.2 What is required? What we would like is a method which lets us describe what the UI should accom-plish without having to specify how it can do that. The general purpose dialogue processor described by Black is one early attempt to reconcile these ideas [Bla77]. In this effort the emphasis was on the design and use of special purpose little languages. Black argued that generality is not always desirable or even necessary when the ease of use is the main goal. By focussing on the semantics of the human-computer interaction (what kinds of information should the UI obtain or display) rather than the syntax of the UI (how can the UI realize this interaction), it is possible to describe the goals of the CHAPTER 1. OVERVIEW 14 interaction in an abstract, high-level manner. This description provides the minimal semantic information needed to describe the application's interactive requirements. This technique is independent of the method used to interact with the user and thus cannot be made obsolete by evolving UI technology. Therefore future and existing UI tools can be employed to create the latest generation of UIs without having to modify the description or the underlying application code. 1.4.3 What is currently available? Most current UI tools focus almost entirely on the syntax of the UIs that they support. Rather than describing the interface in the manner which I advocate in the previous section, current systems require the programmer to give a detailed description of the interface in terms of its physical components (e.g., dialog boxes, sliders, pull-right menus, etc.). It should be obvious that this type of specification is not only more difficult to prepare, it is far less general. By describing the interface in terms of predetermined components5, the ability to easily port applications to environments in which UIs employ radically different styles of interaction is lost (e.g., hypermedia systems, systems which use natural language or speech understanding, speech synthesis, virtual reality, etc.). Very few UI tools have ventured in the direction that I have proposed. Of those that have, we find an interesting mix of compromises. Some of these have not taken this concept far enough, while others have focussed on very narrow application domains. I analyze several tools in Chapter 3. 1.4.4 What I have done Out of intense complexities intense simplicities emerge. —Winston Churchill In my work, I looked at how we could specify the needs of the computational com-ponent of the application, rather than of the the interactive component [HH89] (pp. 12-18). By describing this aspect of the application we have an implicit descrip-tion of the UI - an explicit description is unnecessary. The task of creating the UI is highly environment-specific and complex, the details of which are best handled by the computer. This allows us to ignore all implementation-related details and concentrate on specifying purely the needs of the computational component, and provides a general UI independent method of describing the role of the UI. Lastly, I observed that since the structure of the underlying application can be implicitly encoded in a hierarchical description, this too can be exploited to automatically 5Or hybrid components built out of a set of primitive components. CHAPTER 1. OVERVIEW 15 generate complete applications. Thus, applications employing graphical UIs can be automatically generated from a simple high-level description of the components making up the application and their organization within the application. These ideas led to the design and development of NAAG. Chapter 2 Related topics This chapter outlines some background topics which are related to the task of au-tomating the generation of interactive applications. Although this summary is not exhaustive, it does include those areas which were directly relevant to, or significant in, my research. 2.1 Application generators Give a man a fish and you'll feed him for dinner. Teach a man to fish and you'll feed him for life. —An ancient Chinese proverb AGs translate specifications into executable programs [Cle88]. AGs differ from tradi-tional compilers in that the input specifications are typically very high level, special purpose abstractions in a very narrow application domain. The specification may take several forms: interactive dialogue, graphical, or textual - often called a fourth-generation or application-oriented language. AGs have been shown to reduce both the time to develop applications and the number of errors in the implementation [Lev86]. When used successfully, AGs clearly separate the system specification from the implementation, and make it possible for non-programmers who are familiar with concepts in a particular application domain to build systems, independent of knowl-edge about conventional implementation technologies. Furthermore, since it is rela-tively easy to modify and extend system specifications, AGs encourage prototyping. In contrast, building prototypes with conventional high level (third-generation) lan-guages is less effective since this can often be as difficult as building the final system [Zav84]. 16 CHAPTER 2. RELATED TOPICS 17 2.1.1 Third- versus fourth- generation languages While there does not seem to be a standard definition for either third- or fourth-generation languages (3GLs or 4GLs), a simple distinction may be that 3GLs are mainly procedural while 4GLs are essentially non-procedural [MJ88]. According to Martin and Leben 3GLs are high-level languages such as Cobol, Basic, C, and Pascal [ML86]. These are standardized and largely independent of hardware. Programmers using 3GLs rely on procedures composed of tokens (commands, types, and functions). The kinds of applications that can be created are limited by the available tokens, the grammar, and the programmer's imagination. In contrast, Martin and Leben define 4GLs as end-user-oriented languages. These languages typically offer diverse features such as integrated database systems, ease of use, and screen- and report-generation capabilities. Programmers using 4GLs must rely on predefined procedures that may or may not be well suited to a particular application. While there are procedural tools which help the user to go beyond the AG's capabilities, these tools typically lack the expressive power of 3GL tokens. 2.1.2 Pros and cons As alluded to earlier, by automating system design AGs can significantly increase productivity during development and maintenance. They also let the user customize and reuse software artifacts. Other advantages of using AGs are [Cle88]: • reducing programming errors, letting the designer concentrate on specification errors, • generating and maintaining applications by non-programmers, • ease of prototyping and testing alternative specifications, and, • ease of standards implementation by using the generator to create automati-cally a standard interface or output format. On the other hand, the following are some of the disadvantages associated with AGs. • A single AG can be used effectively only in a few situations. • AGs are difficult to build. They require carefully designed specification lan-guages and user interfaces, an intimate knowledge of the application domain, and the ability to design generic units of reliable software in the domain. In fact, building an AG requires knowledge and skill in both the application do-main and in building parsers and language translators. CHAPTER 2. RELATED TOPICS 18 • Recognizing where an AG can be used is difficult and often occurs late in the life cycle, when there is less motivation to redo development. • Introducing a new technology poses several organizational questions. How and where do AGs fit in the development process? Who should consider them? If off-the-shelf generators are not available, should you build them? How do you build and incorporate generators in development? It is difficult to weigh the potential long-term cost of building AGs. Also, it is hard to predict how an unusual technology will effect development schedules, making project management more precarious. 2.1.3 Application generators and user interface tools With the advent of new and powerful workstation technology and graphical user interfaces, the emphasis on productivity has been shifting from the more traditional AGs to UI tools. Building AGs is difficult. One approach which makes this task easier, consists of a seven-step process and a software tool called Stage [Cle88]. Stage and tools like SSAGS [PKP+82] and Draco [Nei84] assist in building AGs. To do this, they rely on AG technology, and are therefore application generator generators! Stage has been used to build AGs for a variety of application areas including UIs. AGs have been build to construct UIs for telecommunications equipment, software development tools, administrative tools, and design processes. The domain of UIs is an excellent candidate in which to apply AG technol-ogy. While UIs can be described conceptually in relatively simple abstract terms, their implementation is typically riddled with complex detail. An AG can be used to automatically generate the implementation based on the conceptual high level specification of the UI. 2.2 Programming languages and methodology It is of interest that while some dolphins are reported to have learned English - up to fifty words used in correct context - no huma?i being has been reported to have learned dolphinese. —Carl Sagan Computers are tools with which we carry out certain tasks. They are, however, useless in themselves - we must give a computer a detailed recipe to enable it to accomplish even the simplest task. Describing computational tasks is central to computer science. This topic is studied extensively from both a theoretical and a practical perspective. CHAPTER 2. RELATED TOPICS 19 One issue in computer languages is the level of abstraction at which the problem should be stated. At the most fundamental level, we must provide the computer with a set of machine instructions which it can execute. However, the majority of tasks are described at a much higher level. We are free to choose the high-level method insofar as it must be possible to derive the low-level description from the high-level one. Another issue is the question of just what it is that we should describe. Depend-ing on the problem we are trying to solve, it is possible to restate the problem in several ways. These issues bring forth a more general question - which programming paradigm is most appropriate for describing the task. The object-oriented programming ap-proach has emerged as an important and powerful tool for describing complex sys-tems of interacting agents. In the rest of this section we cover each of these issues in turn. 2.2.1 Little languages Most programmers associate the term language with big languages such as C, Pascal, or Cobol. A language is simply a mechanism for expressing intent, and the input to most programs can be viewed as statements in a language. What then is a little language? To answer that question it is easier to describe what a little language is not. It is not a big language - a little language typically does not have complex constructs found in big languages such as declarations, loops, conditionals, and facilities for separate compilation. According to Bentley [Ben86]: Little languages are an important part of Fourth- and Fifth-Generation Lan-guages and Application Generators, but their influence on computing is much broader. Little languages often provide an elegant interface for humans to control complex programs or for modules in a large system to communicate with one another. Principles Bentley summarizes the principles of language design, which although well known among designers of big programming languages, are just as relevant to the design of little languages. Design Goals. Before you design a language, carefully study the problem you are trying to solve. Should you instead build a subroutine library or an interactive system? An old rule of thumb states that the first 10 percent of programming effort provides 90 percent of the functionality; can you make do with an awk or BASIC or Snobol implementation that cheaply provides the first 90 percent, or do you have to use more powerful tools like lex and yacc to get to 99.9 percent? CHAPTER 2. RELATED TOPICS 20 Simplicity. Keep your language as simple as possible. A smaller language is easier for its implementers to design, build, document, and maintain and for its users to learn and use. Fundamental Abstractions. Typical computer languages are built around the world-view of a von Neumann computer: instructions operate on small chunks of data. The designer of a little language has to be more creative: the prim-itive objects might be geometric symbols, chemical structures, context-free languages, the files in a program, or the questions in a survey. Linguistic Structure. Once you know the basic objects and operations, there are still many ways of writing down their interactions. The infix arithmetic expression 2+3*4 might be written in postfix as 234*+ or functionally as plus(2,times(3,4)); there is often a trade-off between naturalness of expression and ease of implementation. But whatever else you may or may not include in your language, be sure to allow indentation and comments. Yardsticks of Language Design. Here are some desirable properties: Orthogonality: keep unrelated features unrelated. Generality: use an operation for many purposes. Parsimony: delete unneeded operations. Completeness: can the language describe all objects of interest? Similarity: make the language as suggestive as possible. Extensibility: make sure the language can grow. Openness: let the user escape to use related tools. The Design Process. Like other great software, great little languages are grown, not built. Start with a solid, simple design, expressed in a notation like Backus-Naur form. Before implementing the language, test your desing by describing a wide variety of objects in the proposed language. After the language is up and running, iterate designs to add features as dictated by real use. Insights from Compiler Building. When you build the processor for your little language, don't forget lessons from compilers. As much as possible, separate the linguistic analysis in the front end from processing in the back end; that will make the processor easier to build and easier to port to a new system or new use of the language. And when you need them, use compiler-building tools like lex, yacc, and make. CHAPTER 2. RELATED TOPICS 21 Examples As Bentley points out, programmers use microscopic languages every day. For ex-ample, in order to print a floating point number, a programmer might use F6.2 in Fortran, %6.2f in C, and define the picture 999.99 in Cobol. Each of these descrip-tions is a statement in a well-defined little language. lex, a tool for creating lexical analyzers (or lexers), uses a little language to describe lexers. The lex language specifies a lexer as a series of expression-action pairs: when the lexer observes a regular expression it performs the associated action. Observe that regular expressions are a microscopic language for describing strings, yacc, on the other hand, is a parser generator. It uses a little language to describe languages! In the same article, Bentley describes Brian Kernighan's pic language for making line drawings, and chem - a pic preprocessor which allows chemists to describe chemical structure diagrams in a little language. A companion paper in the same issue of Communications describes grap, a more sophisticated pic preprocessor for drawing graphs (pp. 782-792). The document preparation tools TgX and IATgX both employ little languages to describe the structure of documents, as does trof f. Little languages and user interface tools Little languages can be very useful in describing the structure and function of UIs. IDL or Interface Definition Language, described in Section 3.5 is a little language, as is TICCL or Tiger Interactive Command and Control Language described in Section 3.2. 2.2.2 V e r y h i g h l e v e l l a n g u a g e s VHLLs are to high level languages (HLLs) what HLLs are to assembly languages. With HLLs abstractions such as iteration and relational expressions, which were considered specifications with respect to assembly language implementation, be-come constructs in the HLL. Similarly, VHLLs allow programmers to construct executable systems using constructs which are considered specifications by today's HLL implementation standards. For this reason, VHLLs are also know as Executable Specification Languages. Software development with VHLLs is very similar to development with HLLs. As in the case of HLLs, VHLLs provide a notation and a semantics for expressing a general form of computation. Just as HLL specifications may be an order of mag-nitude more succinct than the corresponding assembly language implementation, the VHLL specifications may be considerably more succinct than the corresponding HLL implementations. CHAPTER 2. RELATED TOPICS 22 Relationship to AGs and little languages VHLLs resemble AGs in that executable systems are created directly from high level specifications. VHLLs differ from AGs and little languages, since the latter are typically restricted to specifying computation in a specific domain, while VHLLs use specifications which express a more general notion of computation. We thus observe the familiar trade-off between generality and high level specifi-cation once again. AGs and little languages typically sacrifice generality in order to capture much higher level concepts in the specification language. Insofar as they suc-ceed in this respect, AGs and little languages provide a more powerful and succinct specification in a smaller domain. VHLLs, on the other hand, have the advantage of being generally applicable for system development. In a similar way, VHLLs and AGs exemplify the trade-off between generality and leverage in reuse techniques [BR87]. Typically, the more general a reuse approach is, the more effort is required to implement systems with it [Kru89]. Examples Three VHLLs are briefly described by Krueger [Kru89]. SETL is a VHLL based on set theory [KSS84]. With a small number of primitives, most mathematical operations can be succinctly expressed in set-theoretic terms. PAISLey combines the models of asynchronous process, functional programming, and set theory into a single VHLL [ZS86]. MODEL is a constraint language based on the simultaneous solution of a collection of constraint equations [CLP84], In this model, data flow and control flow are automatically determined by the compiler, rather than explicitly specified as in HLLs. V H L L s and user interface tools While most interface description languages are little languages, a general purpose language for describing all aspects of human-computer interaction may very well be a VHLL. 1 One challenge in UI research is to devise a language which exhibits the generality of VHLLs without sacrificing the very high level of abstraction provided by special-purpose little languages. lln order to capture all aspects of HCI, we must first identify these aspects. This is one of the main and most challenging long-term research goals in HCI. CHAPTER 2. RELATED TOPICS 23 2.2.3 Specification of semantics versus syntax Never tell people how to do things. Tell them what to do and they will surprise you with their ingenuity. —George S. Patton An approach characterized as describing what the computational task should ac-complish rather than how it can be performed relies on the semantics of the problem rather than the syntax of a candidate solution as a means of describing the task. Perhaps the easiest way to explain this distinction is by example. A most compelling illustration of the difference between these two approaches is found in document creation systems. Document creation can be viewed as the prob-lem of describing how textual data should be formatted in order that the resulting manuscript is to possess some desired appearance. Early document preparation systems were almost exclusively syntax-oriented. They typically required the user to insert various control codes which caused the printer to skip lines, print in bold font, jump to a new page, and the like. The user described how to obtain the desired appearance - by issuing printer instructions.2 By contrast, systems which allow the user to describe the document as made up of, for example, chapters, where chapters consist of sections, sections of subsections, subsections of paragraphs, and so on, rely on semantic information to format the document. These systems generally employ a mark-up language to classify selected portions of the textual data as belonging to some logical document group.3 The key observation is that the user does not describe how each component is formatted, but instead defines the document in an output-independent fashion. A well-known document preparation system which utilize these principles is IATgX [Lam86]. In fact, this manuscript was prepared and typeset using L^ TgX. In the context of creating UIs, this approach can yield a significantly simpler method for describing UI components and their inter-relationships. Notice that creating a UI is conceptually a very similar task to that of creating a document -the key difference is that a document is a static entity while a UI has a dynamic component.4 Nevertheless, many similarities remain. Alternatively, the document preparation system could interpret simple commands which it translated into printer instructions. 3Note that the mark-up language is a little language. 4Admittedly, this is a somewhat old-fashioned (classical) view of a document - a hypermedia document may be dynamic. CHAPTER 2. RELATED TOPICS 24 2.2.4 Object oriented programming Object-oriented programming (OOP) languages like C++ [Str87], Smalltalk [GR83], and Eiffe l have attracted a growing number of fans during the last decade. The success of the OOP approach has resulted in the creation of a number of interest groups. The key advantages offered by OOP languages over procedural languages are [HH89]: Abstraction mechanism. Objects encapsulate state and operations, hide most of the implementation details, and provide a simple abstract interface for the programmer. Property inheritance. Inheriting properties from other objects exploits existing objects to derive new objects. By reusing existing objects, new objects can be created faster and with fewer errors. Low code bulk. Systems are easier to develop and maintain due to the higher code density and simpler object interfaces which can be achieved with OOP techniques. These aspects make OOP languages particularly appropriate for creating UI tools. The Dialogue Management System [HH86] is implemented using Smalltalk, and the architecture of the George Washington University UIMS [SHB88] is largely object-oriented. The major strength of the XView Open Look Toolkit [Hel89] is its object-oriented programmer's interface, which is simpler to use than that of the X Windows Xlib [Nye89]. An unusual UI tool is PROWindows by Quintus Computer Systems Inc. is dis-tributed with the Quintus Prolog compiler [PR088]. A set of Prolog primitives provides an interface to the Sunview environment through a combination of named objects and message-passing. Complex objects can be designed and manipulated using simple rules and with minimal understanding of the Sunview environment. This approach bridges the object-oriented and logic programming styles by combin-ing both in a common application, and using each for what it does best [KE88]. Essentially, this is the philosophy behind the notion of multiparadigm programming [SBK86]. A less obvious use of the object-oriented paradigm is in the design of the UI model. In many cases it is helpful for the user of an interactive application to think of the various UI components as objects which she can manipulate by applying abstract operations. We discuss this possibility in Sections 2.3.4 and 6.4.4. 2.3 Software engineering considerations The field of computer science is now roughly fifty years old. While we have made great progress in standardizing many aspects of how we use computers, we are CHAPTER 2. RELATED TOPICS 25 still very primitive with regard to how we develop software. One of the greatest limitations of computer programs is our inability to create software components which can be used in many applications, on different computers, and in a variety of ways. As a result, most of the software developed is used only once or twice - on a specific architecture, in a specific application, and for a single purpose. This problem is a serious one and has received commensurate attention. From the industry's point of view, reducing this problem could represent a substantial increase in productivity - we would no longer (re)invent existing software. From the scientific perspective, a solution could be viewed as a necessary condition for progress - greater gains achieved through cooperation and coordination. In this section, we outline several software engineering issues which are particu-larly relevant to interactive application development. 2.3.1 Reuse By way of introduction, the following is due to Krueger [Kru89]. What is software reuse? It is the process of utilizing existing software artifacts rather than building them from scratch. Typically reuse involves the selection, specialization, and integration of existing artifacts, although different reuse techniques may emphasize or de-emphasize certain of these. Why software reuse? The primary motivation is to reduce the time and effort required to build software systems. The quality of software systems can also be enhanced through the reuse of quality software artifacts, which reduces the time and effort required to maintain software systems. What is required for software reuse? Creating a complex executable system with fewer key strokes and less cognitive burden on software developers clearly implies a higher level of abstraction over the way we build systems now. To successfully select, specialize, and integrate reusable artifacts requires natural, succinct, high level abstractions, which describe artifacts in terms of what they do rather than how they do it. The ability of the developer to practice software reuse is limited primarily by their ability to reason in terms of these abstractions. In other words, there must be a small cognitive distance between informal reasoning and abstract concepts defined by the reuse model. Why is software reuse difficult? Useful abstractions for large, complex, reusable software artifacts will typically be complex. In order to use these artifacts, developers either need to be familiar with the abstractions a priori or need to take considerable time to study and understand the abstractions. The latter case defeats some or all of the gains from reusing an artifact. The former case is where we have seen significant successes in reuse. For example, math libraries used by developers who are familiar with the mathematical concepts, abstract data types such as stack and queues used by developers who have been educated in their semantics, and domain specific application CHAPTER 2. RELATED TOPICS 26 generators and domain languages used by developers who are familiar with concepts in the application domain of interest. Krueger provides the following list of general requirements on reuse techniques. 5 1. In order for a reuse technique to be effective, it must reduce the cognitive dis-tance between the ini t ia l conceptualization of a system and the final executable specification of the system. 2. It must be easier to reuse (e.g., select, specialize, and integrate) artifacts than to bui ld from scratch. 3. In order to select an artifact for reuse, you have to know what it does. 4. To reuse a software artifact effectively, you have to be able to find it faster than you can build it. Krueger defines cognitive distance as the amount of mental effort that must be expended by software developers in order to take a system from one stage i n the life-cycle of development to another. 6 He suggests two ways of reducing the cognitive distance: reducing the amount of effort required to go from informal requirements of a system (in terms of concepts in the application domain) to a specification of the system (in terms of concepts in the reuse model); and, reducing the amount of effort required to produce an executable system once the software developer has produced a specification in terms of concepts in the reuse model. Krueger ranks eight reuse approaches in approximately increasing order for cog-nitive distance: 1. between informal requirements and specifications in the reuse model, and, 2. between specifications in the reuse model and executable systems as shown in Figure 2.1 (the number of symbols associated with each technique indicates its relative ranking; e.g., five symbols implies that the particular technique is the fifth best at reducing the cognitive distance). Krueger concludes: A n ideal technology for software reuse would utilize both approaches to reduc-ing cognitive distance. In addition, this ideal technology would be useful in all application domains. A software developer using this technology would be able to quickly find abstraction specifications in the reuse model that would be amenable to any particular application domain of interest. The abstrac-tion specifications in the reuse model would be automatically translated into executable code. 5Although these may appear to be simple, they have proven difficult to achieve in practice. 6Unfortunately, this metric is difficult to define and even more difficult to measure. CHAPTER 2. RELATED TOPICS 27 Application • • • • • • • • Program • • • • Generators O O O O O O Schemas O O O Design • • • • • • • Source Code • • • Structures O O O O O Components QO Transformational • • • • • • Systems O O O O Code Scavenging o Very High Level • • • • • Languages O O O O O O O High Level Languages • oooooooo j—i Distance between informal requirements and Distance between specification in the reuse model ' specification in the reuse model ^ and executable systems Figure 2.1: Ranking reuse strategies by cognitive distance (least to greatest). While these ideas apply to software development in general, they are especially relevant to the development of artifacts which will be used in a variety of interactive environments. Just as it is necessary to employ a higher level of abstraction in order to build reusable artifacts, it is equally important to maintain this high level of abstraction in the resulting application. This allows the user of the application to interact with artifacts of equal or higher abstraction - a practice which reduces the amount of effort required to understand an interactive system, both by hiding details, and by establishing a closer association between the tasks that the user carries out and the operations that the application performs (e.g., by reducing the cognitive distance). Furthermore, a crucial (albeit obvious) observation is that abstract operations should be defined in a TJI-independent manner. From the perspective of performing an operation, it is irrelevant how inputs are obtained, how outputs are displayed, or how semantic feedback such as error and help messages are conveyed to the user. This is more than a point of elegance - it is essential, for without it, we could not reuse artifacts, regardless of their remaining characteristics. Finally, notice that AGs are ranked 1 and 4 according to the two criteria. This lends further support to my claim that AGs provide an effective mechanism for software reuse. CHAPTER 2. RELATED TOPICS 28 2.3.2 Portability Portability is a very important issue in software engineering. By creating software which can be used in a number of environments, we can substantially increase its value. Portability can be exploited in two ways: new software can be immediately available to a larger audience; and existing software can be easily ported to new architectures. This allows us to reach larger markets, and to take advantage of the latest technology without having to sacrifice existing software. We have remained vague with regard to what we mean by portability. Portability can be achieved at several levels. Relying on a combination of a portable high-level language and operating system such as C and Unix, provides one avenue for ensuring compatibility across heteroge-neous hardware architectures. Unix hides a number of device-dependencies such as the file system, for example. High-level languages and operating systems alone, however, are not sufficient to support sophisticated peripherals such as graphical displays and input devices. The Graphical Kernel System (GKS) was an early attempt to standardize many aspects of interaction with graphical input and output devices [IEE84]. GKS provides a set of functions for graphical data processing independent of specific graphical devices, programming languages, and application systems. It includes two-dimensional in-put/output primitives and a segment facility for subdividing graphical pictures. A GKS software layer can be ported to different architectures. Thus software which uses GKS to realize its UI needs, has a clear migration path. While GKS is a standard for static graphical images, the Programmer's Hierar-chical Interactive Graphics Standard ( P H I G S ) has improved capabilities for dynamic interaction [Bro85]. However, GKS and P H I G S are both general software packages which emphasize graphics power - UI considerations are secondary. Many draw-backs associated with these tools, such as the lack of window management facilities, for example, led to a new class of toolkits which were more oriented toward the problems of UI development. The X Window System supports an arbitrarily branching hierarchy of resizable, overlapping windows upon which UIs can be built. The base window system pro-vides high performance, high level, device independent graphics, and facilities for building applications and managers for input and windows. X also provides widgets or primitives with which a variety of UI styles can be constructed. Although X has become a very popular UI support tool, it is necessarily complex, requiring a high degree of understanding and programming sophistication from its users. This makes it inappropriate for casual use. One tool which has been devel-oped, at least in part, to answer this weakness, is the XView Open Look Toolkit. XView employs an object-oriented programmer's interface which simplifies the UI building task. Since XView creates X UIs, it benefits from many of X's advantages, device independence in particular. CHAPTER 2. RELATED TOPICS 29 While there has been substantial work in the preceding areas, little effort has been spent trying to generate applications which are independent of the UI. In studies conducted at Wordstar Inc., it was found that it is more difficult to update an existing UI than to build a new one from scratch [Tel90]. Changes in technology, changes in equipment, new platforms, changes in UI standards, built-in limitations of the older interface, and pressure from competitors are listed as some of the factors which necessitate change. Change is said to be more difficult than design because of the added issues concerning the existing user base, such as training and functional consistency. While the above study emphasizes the impact on the user, the developer is faced with an equally difficult problem: reconciling many differences between an existing Ul-application interface and a new one. Without a clear separation between the UI and the underlying computational component, the porting task is generally very difficult. Since many large applications were created ten or more years ago, most were not developed in a manner which emphasized this type of separation, thus the problem of updating UIs is especially pronounced in these cases. Often, an older application must be abandoned and replaced by a program written from scratch. By using more intelligent software development techniques, such as making explicit the separation between application and UI, and employing a set of portable interface primitives, this problem can be largely avoided in the future. 2.3.3 Correctness and conformance To err is human. To really foul things up requires a computer. — Unix /usr/games/fortune Inconsistency is the only thing in which men are consistent. —Horace Smith A very important aspect of software engineering both in theory and in practice, is program correctness. In theory, we would like to be able to prove that a given program is correct: that for any set of valid inputs, the program always produces the desired outputs. Unfortunately, since the set of inputs is typically very large, we cannot use brute force methods to validate program correctness and must instead turn to theoretically-grounded alternatives. From a practical point of view, correctness is crucial. To appreciate why this is the case, simply consider the alternative: a business firm uses computers to carry out all of its financial transactions; since large amounts of money are involved, it is CHAPTER 2. RELATED TOPICS 30 essential that the underlying software produce the correct results. A concept which is closely related to correctness, is conformance. Conformance is usually defined in relation to some aspect of the implementation. While correctness is concerned with the absolute behaviour of programs and is a measure of whether the implementation produces the desired result, conformance is a measure of the consistency of the implementation with respect to a set of preestablished rules or conventions. An example may serve to clarify the difference. Consider these two concepts in the context of UI software. A UI can be said to be correct if given a sequence of inputs (program and user actions) it produces the desired outputs (help, messages, invocation of appropriate application software, etc). A UI can be said to conform to some guidelines or conventions, if it provides consistent and uniform services. I am intentionally vague, for the guidelines in question could refer to a number of UI features. For example, a common type of conformance is look-and-feel, and is concerned with the visual appearance and behaviour of UI components. 2.3.4 System models For the purposes of their discussion, Gentner and Grudin use the following simple model of a system [GG90]. A system consists of an underlying mechanism that pro-duces the desired behaviour. Since we typically want to vary the system's behaviour in some way, the mechanism has several control points that alter its workings and change the behaviour. The control points in a mechanical system might be valves or levers, while the control points in a software system might be variables or function arguments. Gentner and Grudin argue that a UI based on an engineer's model of the system (which is based on knowledge of the underlying mechanism and is the most natural UI for an engineer) may be unsuitable for the user (who is primarily concerned with accomplishing some task). A problem may arise if the user's model of the system does not map cleanly onto the system mechanism. An alternative strategy is to base the UI on a task model of the system. Gentner and Grudin proceed to explore a number of factors involved in making this decision. Wenger discusses the user's model of the system in terms of black box models and glass box models [Wen88]. While with the black box model the system's mechanism is completely hidden from the user (who is aware of only the inputs and outputs), the glass box model completely exposes the mechanism to the user. Since the glass box model allows the user to reason about the relation between input and output, the user can make predictions about how changes in user actions will affect the system behaviour - making applications easier to learn and understand by combining learning with doing. Gentner and Grudin propose a third possibility: the tool box model. In this model the user is not shown the mechanism, but instead is presented with a set CHAPTER 2. RELATED TOPICS 31 of abstract objects and a set of operations to perform on those objects. The Unix character stream data model is one example of a tool box model. In this model, heterogeneous devices such as files and terminals are presented to the user in a consistent manner. The user can combine programs using pipes, redirection, and shell scripts to produce a wide variety of behaviours. Essentially, the tool box model is an abstraction of the system mechanism that provides the user with a set of objects and actions which are easy to understand and to use. Often, these systems give users the ability to construct their own applications, complete with interfaces which they define. A well-known example is HyperCard, a program for the Apple Macintosh computer which lets users build their own hypertext applications. The tool box model is very useful in this respect, as it can be utilized to facili-tate not only the design of effective UIs, but also the design and generation of the underlying applications. Chapter 3 Previous work on user interface tools The historical sense involves a perception, not only of the pastness of the past, but of its presence. —T.S. Elliot This chapter summarizes past research in UI tools, with special emphasis on systems which automatically generate UIs, or alternatively, complete interactive applications. A brief motivation is followed by a description of four UIMSs which contain many elements found in my approach. These are described in a chronological order. 3.1 Motivation We clarify the need for programming tools to aid the design and implementation of UIs by reviewing some of the key reasons for using such tools. UI tools have been created primarily for the purpose of making UIs cheaper and easier to design and implement. Using UI tools to create UIs has the following advantages [Mye89]: 1. The resulting UIs are better. • Designs can be rapidly prototyped and implemented. • It is easier to incorporate changes discovered through user testing because the UI is easier to modify. • One application can have many UIs. • More effort can be expended on the UI tools than may be practical on any single UI because the tools will be used repeatedly. 32 CHAPTER 3. PREVIOUS WORK ON USER INTERFACE TOOLS 33 • Different applications will have more consistent UIs because they have been created with the same tools. • It is easier to investigate different styles for a UI. • It is easier for many specialists to be involved in designing the UI. 2. The UI code is easier to create and more economical to maintain. • The code is better structured and more modular because it has been separated from the application. • The code is more reusable because the tools incorporate common parts. • The reliability of the UI is higher. • Interface specifications can be represented, validated, and evaluated more easily. • Device dependencies are isolated in the UI tool so it is easier to port an application to different environments. 3.2 TIGER/UIMS The toolkit UIMS allows a designer/developer to focus on the logical functionality of an application without the usual bookkeeping associated with conventional pro-gramming languages [Kas82]. UIMS contains two components: a special purpose, application-independent dialogue specification language, and a run-time interpreter that provides a number of interaction extensions not possible with procedure li-braries. UIMS is part of The Interactive Graphics Engineering Resource (TIGER), which provided a framework for the development of engineering applications at the Boeing company [Kas85]. At the time of its conception, the toolkit UIMS approach was novel in a number of ways. At that time, in order to develop an interactive application, the designer had to specify both the logical functionality of the application and the physical tech-niques for accomplishing that function. The designer was responsible for tasks such as screen layout, interrupt handling, and extensive legality checks. UIMS removed many of the burdens of physical interaction handling from the task domain of the system designer. The role of the designer or developer is viewed as consisting of three tasks: constructing a UI for the functions to be provided; developing algorithms to perform each function; and determining efficient storage techniques for the data. The application is viewed as made up of two independent components: the user dialogue, and the algorithmic portions of each function. Any interactive function can then be understood to contain an input collection phase, a function execution phase, and an output modification phase. User dialogue is required only during the CHAPTER 3. PREVIOUS WORK ON USER INTERFACE TOOLS 34 input collection and output modification phases. UIMS is active when an application is being processed and is responsible for invoking application functions in response to user actions. The physical interactions a user performs are handled immediately by the UI manager without application intervention or interpretation. This allows extended functionality with no performance degradation. Note that in this model, the user has become the controller of the application. This greatly reduces the complexity of the underlying application as it is very difficult to achieve this type sophistication with a traditional embedded control philosophy (where the developer has to anticipate every conceivable path through the system and write code to handle these instances). In the interface between UIMS and application, the commands available to the user are defined as part of the application and contain the user's logical interface to application functions. This is realized with two components: a special purpose programming language used to define dialogue sequences, and a preprocessor which compiles these sequences into a form which is used by a run-time interpreter. Two types of information are captured: menu structure and parameter lists for the ap-plication functions. The language in question is the Tiger Interactive Command and Control Lan-guage (TICCL). TICCL lets the programmer define and organize interactive dialogue sequences. However, the type of information captured is relatively low-level. While TICCL provides an effective separation between interactive and application code, it doesn't remove enough complexity from the former. The programmer must provide Pascal code to interpret various interactions while TICCL code is used to sequence the physical interactions. The main contribution of this toolkit is in showing how a language which allows a designer to specify dialogue sequences outside of the application makes it more natural to design the dialogue independently of the underlying algorithms. The user is provided with a more consistent UI, while the programmer's task is eased through more powerful and uniform tools. 3.3 M E N U L A Y A UIMS developed at the University of Toronto is made up of two components [BLSS83]. The first component, MENULAY, is a design/implementation tool implemented as a preprocessor. It permits the applications programmer to use interactive graph-ics techniques to design graphics menus and specify their functionality. The out-put of the preprocessor is high-level code which can be compiled and linked with application-specific routines. The second component is a run-time support package which handles interactions between the system and the user. CHAPTER 3. PREVIOUS WORK ON USER INTERFACE TOOLS 35 MENULAY lets the designer define UIs which are made up of networks of menus. This definition is automatically converted into C language programs which imple-ment the graphical UI. It contains the following information: 1. the name of a user-specified procedure which is to be invoked upon the detec-tion of a specified input event, 2. fields to contain (variable) parameters of that procedure, 3. the x and y hit area for procedures triggered by pointing events, 4. any text (or the name of a graphics file containing a picture) to be displayed, 5. the x and y coordinates of the item to be displayed, and, 6. the item's size and colour. While MENULAY's specification is at a higher level than that of the toolkit UIMS, it is also more limited. MENULAY generates code which operates in a single window on the screen and does not support multiple windows. On the positive side, MENULAY does provide a more natural way of integrating graphical design specification with application code. MENULAY was one of the first tools which could be described as a generator of interactive applications rather than a tool for creating UIs. 3.4 S Y N G R A P H / M I K E SYNGRAPH (SYNtax directed GRAPHics) was an early tool which allowed the pro-grammer to represent a dialogue in the form of a BNF grammar and generated Pascal code to implement the UI [OD83]. The programmer described the UI in terms of menu items, function buttons, valuators, and a single locator device. The generated code was compiled with standard interface code and the application's semantic code to create the final interactive program. The concept of generating entire interactive applications was further developed by SYNGRAPH. MIKE [01s86] was created in response to the large amount of effort required to teach programmers how to use SYNGRAPH. MIKE was developed with the following goals in mind: 1. a UIMS must be based on a simple conceptual model for designing UIs that is readily understood by both programmers and non-programmers alike, 2. it must be possible to generate a working prototype of the UI immediately on the basis of the basic definition alone, CHAPTER 3. PREVIOUS WORK ON USER INTERFACE TOOLS 36 3. it must be possible to refine and enhance the default-generated UI continu-ously, using tools that are appropriate for the non-programming professionals who become involved in the design process, 4. where possible, all device dependencies, including those of a particular in-teraction style, should be isolated in the UIMS rather than in the dialogue description or the application, and, 5. UIs generated by the system should be extensible in the sense that new com-mands and capabilities can be added without modifying the application code. The components that make up a MIKE interface specification are: 1. the command procedures and functions that define the application semantics, 2. bindings between these procedures and the specific techniques to be used for interactively expressing them, and, 3. a set of viewport definitions that define how the screens will appear and how interactive behaviours are attached to visual objects. MIKE UIs are defined using a graphical editor rather than a textual UI specification language. The basic definition of an interactive UI is a set of types and a set of functions and procedures that can operate on data objects of those types. The addition of a data model is an important contribution for it allows us to think of application functions as operations which manipulate objects rather than simply performing some computation. Consequently, the definition is at a much higher level - rather than having to specify hit areas for pick events as in MENULAY, we can now define functions which return objects as a result of a pick action. MIKE also has a more advanced mechanism for mapping visual objects and their behaviours onto its otherwise textual command parsing syntax - through the use of active viewports. Viewport definitions consist of layouts, defined in dynamic coordinates, and action expressions attached to viewports. Definitions are used by the application as viewport templates. Layouts were designed to have two properties: they must be able to adapt to viewports that vary in size and position on the screen, and they must be specified within the interface editor in a what you see is what you get fashion. This has several implications. First, the programmer is given more control over the way that graphical output is displayed. Unfortunately, the programmer interface to control the viewports is quite complex - it could be simplified without giving up too much flexibility. The programmer has to write code to control many aspects of the interface. For example, actions like hiding or resizing viewports must be accounted for. These types of tasks should be managed by the tool. Second, this type of approach may be less appropriate in cases where we wish to automate the development task to a greater degree. We would really like to define graphical output CHAPTER 3. PREVIOUS WORK ON USER INTERFACE TOOLS 37 in a way which is independent of how the graphical data is displayed. The tool should perform all necessary screen and window management. If the programmer is allowed to use direct manipulation techniques to describe some aspects of the interface, it must be possible to save the resulting descriptions for later use by an automatic generator. An important contribution of the MIKE approach is that it shows how we can increase the application's independence from devices and dialogue styles. For ex-ample, since menus are defined as a tree of terms, the external presentation of the menu is left up to the UIMS and can be displayed as Macintosh pull-down menus, Xerox Star pop-up menus, or TIGER's layered menus with defaults, without having to modify the UI or application specification. While each of the above adaptations would require some modifications to the tool's run-time system, the port would be substantially cheaper than rewriting many applications or their UI specifications. The MIKE style of UI specification brings up an interesting compromise. On the one hand, it limits the variety of dialogue syntax that can be specified. For example, many continuous commands such as dragging or rubber-banding are difficult to express using MIKE. In my work, I show how such commands can be accommodated without sacrificing simplicity. On the other hand, for a wide variety of graphical applications, MIKE makes it possible to create UIs easier and faster. Furthermore, due to the restrictive nature of MIKE-created applications, the UIs exhibit a high degree of uniformity and consistency of style both within a single application, and among different applications. This consistency is achieved without any expense to the programmer. One weakness of the MIKE approach is its relatively weak mechanism for dealing with the ambiguity associated with object selection. MIKE's parser does not know what type of object a user might be pointing at. When an operation requires that several objects should be chosen, MIKE prompts for each object in turn. In this situation, a dialog box or forms approach would be inadequate for it allows the parameters to be specified in any order. One solution is to allow the application to decide for itself what kind of object is returned. In my work, I provide an alternative approach. 3.5 UIDE/IDL UIDE (User-Interface Design Environment) is a system developed at the George Washington University [Fol87, FKKM89]. UIDE uses a knowledge-based represen-tation of the interface's conceptual design based on an object-oriented data model and an operation-oriented control model. UIDE's knowledge representation consists of: t the class hierarchy of objects in the system, • properties of objects, CHAPTER 3. PREVIOUS WORK ON USER INTERFACE TOOLS 38 • actions that can be performed on the objects, • units of information required by the actions, and, • preconditions and postconditions for the actions. The knowledge base is used to: • produce a description of the design in the Interface Definition Language) (IDL), • check the conceptual interface design for consistency and completeness, • transform the knowledge base, and thus the interface it represents, into a different but functionally equivalent interface via a set of transformation algo-rithms, • evaluate the interface, • provide the input to the Simple UIMS (SUIMS), which implements the interface, and, • automatically generate intelligent run-time help. UIDE provides a design-specification interface which is used to specify the inter-face. The major definition stages are: 1. building the design knowledge base, 2. checking it for completeness, and, 3. analyzing if for consistency. UIDE can be viewed as a sophisticated graphical tool which enables the designer to describe UIs. The design information required to build the knowledge base is input by selecting options from menus and by answering prompts. While this implies that the designer does not have to learn IDL syntax rules, it also creates the possibility that he may specify an incomplete design. The existence of this possibility means that the system must be able to carry out completeness checks to verify that all frames in the knowledge base contain enough information for the transformation system to operate and for the SUIMS to implement the interface. It is not clear whether the graphical specification method is superior to simply writing the IDL code. For one, the latter method can eliminate the possibility of incomplete specifications and hence the need for having to perform completeness checks. In the case of NAAG for example, I show how class information can be used to handle this problem in a simple, straightforward manner. The IDL language lets the designer describe object classes, subclasses, actions which can be performed on objects which belong to these classes, and attributes that these objects may have. CHAPTER 3. PREVIOUS WORK ON USER INTERFACE TOOLS 39 type shape superclasses: () subclasses: (triangle, square) actions: (createjshape, delete_shape, rotate-shape) attributes: (position, angle, color) triangle, square superclasses: (shape) subclasses: () actions: (create_shape, delete_shape, rotate_shape) attributes: (position, angle, color) color: set (1, 1) of (white, gray, black) angle: range [0..360] of integer position: range [x: (O..Max_X), y: (O..Max_Y)] of integer initial: number(shape) = 0 pre-condition: true create_shape(obj_type: shape.class, anchor.pt: position, color.value: color, orientation: angle) post-condition: number(shape) = number(shape) + 1 pre-condition: number(shape) > 0 rotate_shape(obj.type: shape, orientation: angle) post-condition: none pre-condition: number(shape) > 0 delete_shape(obj_type: shape) post-condition: number(shape) = number(shape) — 1 Figure 3.1: IDL specification of the squares and triangles example. The following example comes from [FKKM89]. The shape class contains two sub-classes: triangle and square. The actions which may be performed are: createjshape, deleteshape, and rotateshape. The attributes of these objects are: position, an-gle, and color. The preconditions and postconditions simply maintain a the current count of shape objects, and are used to ensure that at least one object exists before rotate-object or delete-object can be selected. The way this information is specified in IDL is shown in Figure 3.1. The following are several observations about the UIDE approach. 1. It is unclear why the actions and attributes of the parent class have to be repeated for its subclasses. These should be inherited - an explicit respecifica-tion should not be necessary, otherwise the advantages of the object-oriented approach appear to be diminished. CHAPTER 3. PREVIOUS WORK ON USER INTERFACE TOOLS 40 2. I D L , like most object-oriented systems, requires al l of the actions (methods) to be prespecified. This can be a l imitat ion in cases where there are many actions, where the designer does not require to or does not wish to know all the existing actions, and where the programmer's task is simply to add a new action to an existing application. 3. The practice of using the preconditions and postconditions to manipulate vari-ables which are defined within the framework of the U I tool is questionable. It is not clear whether it is possible to perform more extensive checks within the confines of the current system. For example, for tests which necessitate the writing of code in a traditional language, we would require the abili ty to specify a user-supplied test routine. 1 Furthermore, while the postconditions may make the effect of certain actions explicit, the equivalent effect could be obtained completely within the application code. 4. The paper fails to describe how graphics operations are specified and per-formed, or what operations are available. Whi le I D L can be used to create U I designs, these designs to not prescribe a pre-sentation style, dialogue syntax, or a set of interaction techniques. This information is found in the S U I M S . S U I M S uses both the conceptual knowledge base and an additional knowledge base that describes the runtime context for both the S U I M S and the application. S U I M S executes concurrently with the client application and manages al l U I re-sources such as windows. The additional knowledge base includes a set of inter-action techniques to carry out the different interaction tasks: command-selection, class-selection, instance-selection, attribute-selection, position-selection, text-input, and integer-input. S U I M S instantiates application objects whenever the user invokes an action that creates an object; it maintains the attribute values for each object and makes them available to the application's semantic action procedures. Arguably, this task should be the responsibility of the application. W i t h N A A G , for example, the UI maintains a single pointer (handle) to a user-defined data structure which contains al l of the attribute information for the given object. The action routines can query this data structure to obtain the required values. S U I M S cycles through the following loop. 1. Establish and update the screen layout. 2. Check al l preconditions and recognize enabled actions. Consider the situation where the enabling of an action depended on whether the application was running on a particular workstation, or on the presence of special-purpose hardware. In this scenario, the programmer would have to write code to perform this check. CHAPTER 3. PREVIOUS WORK ON USER INTERFACE TOOLS 41 3. Accept the action the user has selected. 4. Process each parameter according to its kind (such as explicit or implicit). 5. Accept parameter values in arbitrary order, using any of the enabled interac-tion techniques. 6. Confirm implicitly (if all missing information is provided), explicitly (if re-quired), or cancel an action. 7. Execute an action. 8. Evaluate postconditions. To wrap up my discussion of UIDE, I would like to point one flaw in its design. UIDE was designed to be a relatively self-contained tool - it does not employ existing tools to carry out any of its functions. In particular, the task performed by the SUIMS can be accomplished using most modern UIs without having to reinvent the wheel. Delegating this task to existing tools can increase the performance of the resulting system, as the existing UIMS is optimized for its particular target. It can also ease the porting task, as the SUIMS does not have to be rewritten - a task which is far more difficult than simply employing an existing tool: in the latter case we must generate source code for the tool; in the former, we must create a complete UIMS capable of supporting the runtime aspects. Chapter 4 My approach First I'll instruct thee in the rudiments, and then wilt thou be perfecter than I. —Christopher Marlowe, Doctor Faustus First Law of Computing: "Fast, reliable, cheap: pick two." —Anonymous The automation of the generation of interactive applications is a task in which a number of issues have to be reconciled. The challenge is to satisfy several mutually antagonistic constraints simultaneously: functionality vs ease of use; performance vs programming effort; use of special hardware vs portability; use of specific interaction techniques vs generality. I set out to tackle this problem with the following goals in mind. • The tool should be easy to use. In particular, UIs should be defined at a very high level of abstraction. The programmer should not be burdened with details. • The tool should provide an integrated programming environment - it should not merely create stand-alone UIs. • The tool should allow the programmer to create complete applications by combining preexisting components with his own. • Applications should be portable across machines and UIs. • The tool should be able to generate a wide range of functionally equivalent UIs (even if the UIs employ radically different interaction techniques). 42 CHAPTER 4. MY APPROACH 43 These objectives were met as follows. • Use an object-oriented application model which allows the programmer to define the application in terms of a set of operations which manipulate objects belonging to programmer-defined classes. • Describe the semantics of the application rather than the syntax of the U I (by specifying what kind of information the application must exchange wi th the user rather than how the U I can realize this exchange). t Generate the entire interactive application 1 not just the U I . • Isolate environment- and UI- specific information in the tool's code generation module. I proceed by outlining some motivations and justifications for my approach. Subsequently, I provide a detailed description of NAAG - a tool which embodies these ideas. 4.1 M o t i v a t i o n a n d j u s t i f i c a t i o n Automatic simply means than you can't repair it yourself. —Frank Capra Tools which generate an interactive application from a specification of its semantics have a number of advantages over and above those common to most U I tools. Interactive applications are easier to design. The use of abstract applica-tion models, as by most application generators for example, can greatly simplify the design of sophisticated applications. In particular, an object-oriented operational model which reduces the design problem to the task of identifying and organizing sig-nificant high-level operations, can reduce the amount of effort required to design an interactive application. The cognitive distance between the programmer's concep-tual model of the application and its design specification is very small. Furthermore, since the programmer does not have to confront U I issues (e.g., the details of a given U I , and the challenge of producing reusable and portable software artifacts), he is free to concentrate on the design of the underlying computational component. Interactive applications are easier to implement and maintain. In my approach, the U I is generated automatically from the information implici t in the xAn application is composed of programmer-supplied modules and the tool-generated UI. Rou-tines which perform most run-time tasks such as event processing, device control, and resource management, are also generated automatically by the tool. CHAPTER 4. MY APPROACH 44 description of the application's semantics. For example, consider an operation which requires as one of its inputs an integer value selected from a given range of integers. In most systems the programmer would have to describe how such a value might be obtained (e.g., using a slider widget). A programmer using a tool which relies on semantic information, however, might describe this input simply as an integer in a specified range - the tool would decide how to obtain such a value using the available resources. A n appropriate model can further ease the creation and maintenance of appli-cations. Since many tasks can be eliminated or simplified, minimal programming effort is required to implement interactive applications. For example, most win-dow systems require the programmer to supply routines for resizing and repainting windows, event processing, and resource management. Most of these tasks can be performed by the tool, while others such as locator device event processing can be greatly simplified. Traditionally, these have been the greatest impediments to U I development — even once the programmer has mastered these aspects there is no guarantee that the programs that are written wi l l be portable across different UIs, since most toolkits and U I M S s handle these issues differently. In my approach, how-ever, the tool is responsible for carrying out these tasks. The programmer does not have to write code to do this and thus cannot create non-portable applications. Abstract application-oriented approach is an advance in software de-velopment methodology. The difficulties associated wi th the use of many current U I tools is evidence of a larger problem: the lack of significant progress in software engineering practices. Al though hardware technology has been improving at nearly exponential rates, the way that we build software systems has remained relatively static during the past twenty years. We are st i l l faced with the same problems: how can we create software which is portable, reusable, and easier to write? Appl ica-tion generators and fourth-generation languages combat these problems by raising the level of abstraction of the specification. Document preparation systems such as IATgX, employ a what vs how approach. In my work, I promote the view that an abstract application model can simplify the design, implementation, and main-tenance of applications. This is achieved through the aforementioned means: an abstract specification which focusses on the application's semantics rather than on the details of a specific implementation. Greater separation of interface and application can be achieved. Since the programmer does not have to describe the U I explicitly, it is possible to achieve a greater separation between the U I and the application code. Furthermore, it is easier to generate UIs which are tailored to a specific user community and employ a unique style of interaction. Where alternatives exist, the tool can be designed to pick the most suitable interaction technique. For example, if the application requires an integer from a given range, a tool which generates a graphical direct-manipulation U I may generate a slider widget if the range is large, and a numeric text widget wi th increment and decrement buttons if the range is small. A t a more abstract CHAPTER 4. MY APPROACH 45 level, a user-modeller can be used to guide the human-computer conversation. Tools which generate UIs automatically could be used in conjunction with such facilities to select the most suitable style of interaction during execution (through a run-time evaluation of the interaction). Since the tool relies on semantic information only, it can generate UIs which are more uniform and reliable (at the cost of reduced flexibility as the programmer is given less control over what is generated). More information can be embedded in the tool. Since the tool has int i-mate knowledge of the target environment, it can generate code which is optimized. For example, there are usually many ways to perform graphics operations in a given system. The tool can be designed to choose the most efficient means to carry out computationally-intensive tasks. A tool which contains more information can also provide a more complete pro-gramming environment. Since the tool generates a complete application it can utilize existing tools to reduce the programming task and to produce applications which are more modular, contain fewer bugs, and use resources more efficiently than hand-coded programs. For example, the tool could invoke a make program to compile the source code which it generates and to combine it with external object modules and libraries to obtain an executable version of the application. The make program, in turn, would utilize existing compilers and linkers. The tool is more portable. Whi le most U I tools implement every aspect of the U I environment which they support, I propose that the U I tool should be one level above the traditional toolkit or U I M S . In this way, the tool can utilize al l of the features of a low-level toolkit or U I M S . It can, for example, employ a low-level tool to perform most of the U I operations (e.g., managing windows, processing events, invoking user-supplied functions, etc.) instead of having to implement these itself. Since each major workstation family has its own set of common low-level U I tools (which are typically mutually incompatible), the developer of a high-level tool which adopts this approach is free to choose the most appropriate existing tool and to utilize al l of its features without having to first implement them. Generally, it is easier and faster to alter the code generation module of a high-level tool to produce suitable input for a new low-level tool, rather than having to port an entire low-level tool. The very high level specification makes the fewest assumptions about the na-ture of the U I or of the underlying application. This allows the tool to select the most appropriate devices and techniques to realize the human-computer interac-tion (e.g., graphical direct-manipulation UIs, speech synthesis and recognition UIs, mouth wands and other special devices used by the physically-handicapped, data gloves in vir tual reality systems, etc.). The fewest-assumptions aspect also makes it easier to provide mechanisms to customize the output of the application generator (whereas the output of most toolkits is fixed). The resulting applications are more portable. In order to achieve a level CHAPTER 4. MY APPROACH 46 of U I independence most common UIMSs treat the UI as an add-on - a module which is designed and implemented separately from the application's computational component. Al though this approach is capable of providing a high degree of U I independence (since the tool can be altered to generate a variety of UIs) it has one major drawback: the dialogue developer must st i l l define the U I explicitly. In my approach, the U I is created automatically from the information which is embedded in the application model. This can be thought of as the process of obtaining a U I as a side-effect of creating an application. Unlike U I M S s , UI toolkits tend to blur the distinction between the U I and the application. As a result, UI independence is sacrificed. In order to create the U I the dialogue developer must write a program in a conventional language (a task which requires substantial effort). Al though the U I toolkit can be ported to different ma-chines, the resulting applications cannot be ported to other UIs - they can only be used wi th the original UI . This is a major l imitat ion. In practice this means that substantial programming effort is wasted by creating applications which are doomed to obsolescence due to our inabil i ty to port them to future UIs in a relatively auto-matic fashion. W i t h my approach, however, we can utilize new technology as soon as it is available. After altering the tool's code generation module we can recom-pile existing programs to immediately obtain ready-to-run interactive applications. The programmer does not have to learn a new U I system in order to port existing applications - this information is isolated and hidden in the code generation module. Reducing functionality is good — not bad. In general, the simpler a tool is the easier it is to use. Ease of use, however, comes at a price: reduced functionality. One of the key considerations in any task is the choice of the right tool for the job. Where possible, we should strive to find the simplest tool which is capable of performing the given task - excess functionality serves only to complicate the task. Although A G s are l imited with respect to the kinds of applications they are capable of producing, they nevertheless have a number of important advantages and are of significant practical value. Aside from simplifying the generation of applications, a very high level approach has the advantage that it ensures a much higher level of consistency and a reduction in the number of bugs over hand-coded programs. A n A G which is capable of generating a variety of interactive applications (independent of the application domain) is a more general tool than conventional A G s (which are usually designed for very specific domains). The range of the tool's applicability is largely dependent on the degree of generality exhibited by the tool's application model. Whi le the object-oriented operational model is simple, elegant, and sufficient to describe many types of applications, an unusual domain may require the use of an unusual application model. Automatic generation of UIs will be even more important in the fu-ture. The ability to automate the generation of UIs wi l l be more important as UIs become more sophisticated and diverse. A U I tool can be viewed as a combination of compiler and expert system: it must use large amounts of information to solve CHAPTER 4. MY APPROACH 47 a translation problem - creating a low-level description from a high-level one. As the gap between the source and target descriptions widens, the tool wi l l have to use more information and smarter translating schemes to carry out the transforma-tion. In order to maintain generality and portability, the specification of interactive applications must be at a very high level of abstraction. 4.2 N A A G The suspense is terrible. I hope it will last. —Oscar Wilde NAAG is a tool which generates interactive applications from a high-level descrip-tion of the application's semantics. Essentially, it enables a programmer to create an interactive application by specifying in a lit t le language what the application's interface should accomplish rather than how. As a direct consequence, NAAG appli-cations are portable not only across machines, but across UIs and interaction styles as well. Exis t ing UI tools can be extremely time-consuming to learn and difficult to use. NAAG insulates the programmer from many complexities at some cost in terms of reduced functionality. For example, NAAG provides for interface independent graphics. The programmer simply calls predefined routines to output graphical elements in his own coordinate system. NAAG maintains an internal display list and performs such tasks as the repainting and resizing of graphics windows while maintaining correct aspect ratios. Note, however, that NAAG is much more than a U I generator - it is a program-ming environment consisting of a lit t le language, macro preprocessor, compiler, and automatic make util i ty. Exist ing Unix tools are used to realize most of these com-ponents. Furthermore, NAAG allows the programmer to define classes and opera-tions which can be applied to objects belonging to these classes. NAAG generates graphical, object-oriented UIs, suitable for interacting wi th the objects which the application creates. CHAPTER 4. MY APPROACH 4 8 4.2.1 Who is involved: roles and tasks All my life I wanted to be someone; I guess I should have been more specific. —Jane Wagner, Unix /usr/games/fortune Before giving a detailed account of the N A A G application model, I describe the key roles or tasks in the N A A G application development cycle. N A A G provides the means to define object classes and operations, realize these as C data structures and functions respectively2, and to combine these to obtain complete interactive applications. In order to satisfy a broad range of requirements and tastes, N A A G can be modified to generate specific UIs which employ specific styles of interaction and run on specific hardware and software platforms. This suggests that several related tasks must be performed. Consequently, I define the following roles: Programmer - the programmer implements data structures and functions using a high-level language such as C or Lisp. Each function which realizes an abstract operation which is intended to be made available to the user of an interactive system, requires an additional N A A G specification to document several of the operation's features. This may be done by the programmer or by the composer. Composer - the composer builds complete interactive applications by composing (arranging, organizing) N A A G components. UI expert - the UI expert, in consultation with the domain expert, prepares an appropriate code generation module which N A A G uses to automatically create UIs. Domain expert - the domain expert is a human-factors specialist who is aware of both the general principles of human-computer interaction and the details of the target domain: the intended user community, the nature of the application domain, and so forth. In some cases, several or all of these roles could be filled by the same person. Note, however, that our model provides sufficient separation to make these tasks inde-pendent for most practical purposes. This greatly improves productivity, since an individual who performs one of these tasks does not require a deep understanding of the other tasks. For example, the composer does not have to possess extensive programming skills - the task of building applications from a collection of high-level components requires minimal programming sophistication and may be better per-formed by a human-factors expert. The composer's task can be further simplified 20ther high-level languages could be used for this purpose. CHAPTER 4. MY APPROACH 49 by employing direct-manipulation graphical editors to manipulate the components using a pictorial representation. Of greater importance is the fact that the programmer does not have to learn the many intricacies of the underlying UI and platform, nor the numerous interactive styles and techniques and the often unintuitive subtleties of human-computer inter-action. This is by far the most significant practical aspect of interactive application development using N A A G , for it provides the programmer with the means to create UI, style, and platform independent applications. Figure 4.1 shows the interactions between the various roles (including the ulti-mate end-user and evaluator). 4.2.2 Application model This section provides an overview of the N A A G application model. Since operations are the main building blocks of N A A G applications, we begin by looking at an example. Assume that we would like to have an operation which obtains image density slices.3 The programmer prepares a C function to implement the abstract operation and a N A A G operation description to specify the inputs and outputs, help information, and the location of the object code. Figure 4.2 contains the N A A G specification for the slice operation, while Figure 4.3 shows the resulting dialog box.4 Consider the operation specification. The preconditions construct lets the programmer specify an arbitrary conjunction of boolean functions all of which must succeed for the operation to be enabled. The argument construct is used to describe what type of value the application must obtain from the user in order to carry out the operation. Table 4.1 shows the argument types which are currently implemented in N A A G . All of the argu-ment types with the exception of the object argument are explicit - the user must explicitly supply a value (although defaults are provided). The object argument is i m p l i c i t - it is supplied to the operation without user involvement. Note that when the programmer specifies a set of arguments that an operation requires, she is describing the nature of the information that is required by the operation - not the interaction technique used to obtain it. The result construct identifies the type of object that the operation creates. Given a set of operations, the next step is to organize these into a hierarchy of menus - this is the task domain of the composer. Note that while this information 3A common format for representing image data is as an array of pixel intensity values. A typical scheme allows for 256 intensity levels by allocating one byte of storage for each pixel. The slice operation is simply a filter which selectively includes or excludes pixels whose values lie in a specified range. 4Generated for a particular user interface and look-and-feel convention - see the implementation section. CHAPTER 4. MY APPROACH 50 Interactive Application LEGEND Computer-Computer Interaction Human-Computer Interaction Human-Human Interaction Figure 4.1: Role interaction in NAAG. CHAPTER 4. MY APPROACH 51 .operation Slice { .class Image .libraries { "-limglib" } .preconditions { ImageUnsigned ImageDepth8 } .label "slice" .help "Obtain a density slice of the source image" .argument { .object } .argument { .range .minimum 0 .maximum 255 .initial 64 .label "Lower limit" .help "Lower limit of the density slice" } .argument { .range .minimum 0 .maximum 255 .initial 192 .label "Upper limit" .help "Upper limit of the density slice" } .argument { .flag .initial 1 .label "Retain Depth" .help "If 'on' use original depth; else depth = 1" } .argument { .flag .initial 1 .label "Inclusive" .help "If 'on' 1 <= pix <= u; else pix < 1 or pix > u" } .result { .class Image } } Figure 4.2: Slice operation description. Argument Description range set flag text a numeric value from a range an item from a given set a boolean value a text string point region a point in the window a region in the window object a handle to the object Table 4.1: N A A G operation argument types. CHAPTER 4. MY APPROACH 52 Lower limit 0 ^ r j = 1255^4 Upper limit 0 BI^H ™[J=i 255 192 Retain Depth | off | on | Inclusive | off | on | ( Continue ) ( Cancel j Figure 4.3: Slice dialog box generated by NAAG. establishes a semantic grouping of operations, there is no assumption of how these groupings will be realized in the target interface. Figure 4.4 contains a N A A G description of one menu in a vision application, while Figure 4.5 shows a part of the menu hierarchy which was generated by NAAG. Menus contain menu items which may be other menus, operations, or stubs - operations which have not been implemented. Note that operations and menus are defined to belong to classes. N A A G uses this information to ensure that operations and menus are nested in a valid manner: a component may appear within another only if it belongs to the same class or a parent class. This provides a simple mechanism for associating root menus with objects and limits the accessible operations to the relevant ones. Figure 4.6(a) shows the general form of the class hierarchy, while Figure 4.6(b) gives a specific example. Thus, a component which belongs to the directed graph class can be placed inside a menu which belongs to the directed graph class, the acyclic directed graph class or the cyclic directed graph class, but not any other class. By using include files it is possible to easily assemble existing menus and op-erations into complete menu hierarchies. As the composer does not have to be intimately familiar with the contents of the included files, this method of building new applications from existing components is not only simple, but very powerful. Now that we have a menu hierarchy, we can look at the basic N A A G application. It consists of a section for denning classes and a section for defining menus. Figure 4.7 shows a N A A G main program, while Figure 4.8 shows the general form of a N A A G program graphically. What is left to describe is the way we define a class in NAAG. Figure 4.9 shows the definition of the Image class used in the preceding examples. The display routine is a user-supplied function which is invoked by N A A G to display an object. It simply invokes some sequence of N A A G drawing primitives to render the given object. The N A A G pnmitiv.es are listed in Table 4.2. Since these primitives are device and interface independent, a single display routine will suffice for all target environments. The destroy routine is a user-supplied function which is invoked by N A A G to release any resources held by the object (typically, it frees CHAPTER 4. MY APPROACH 53 .menu { .class Image .label "Image operations" .help "A collection of image processing operations" .menu { .class Image .label "Transformations" .help "Operations for geometric transformations" # include "flip.mn" # include "rotate.mn" .menu { .class Image .label "Rescale" .help "Operations which rescale images" # include "zoom.op" # include "munch.op" # include "resample.op" # include "resamplenn.op" # include "rescale75.op" .stub "iscale" } } # include "statistics.mn" # include "window.mn" # include "lowlevel.mn" } Figure 4.4: A NAAG menu. int n.drawjmage(int x, int y, int width, int height, int depth, char *data); int n_drawJine(int xl, int yl, int x2, int y2); int n_draw_point(int x, int y); int n_draw_rectangle(int xl, int yl, int x2, int y2); int n_draw_text(int x, int y, char *s);  int nJocator(void (*event_proc)(int event, int x, int y)); int n_message_error(char *s); int n_message_plain(char *s); int n_window_clear(); int n_window_create(int xl, int yl, int x2, int y2, char *title); int n.window_restore(); int n_window-save(); Table 4.2: NAAG primitives. CHAPTER 4. MY APPROACH 54 Figure 4.5: A partial menu tree attached to an image object. acyclic cyclic (a) Genera! form (b) Example Figure 4.6: N A A G class inheritance tree. CHAPTER 4. MY APPROACH 55 .application vision .label "UBC Integrated Vision System" .help "An application for image processing and vision" .classes # include "hist.cl" # include "image.cl" .menus # include "file.mn" # include "image.mn" Figure 4.7: A N A A G main program. memory allocated to store the object's data structure). In order to use class inheritance, the programmer must adhere to the following convention when defining a C data structure associated with a subclass of an existing class. If Y is being declared as a subclass of X, then the data structure for Y should include all the information which is specific to the class Y, and one field named parent declared as a pointer to the data structure of class X. This means that a subclass inherits the data structure of the parent class. Thus a subclass can never contain less information than its parent class. For example, if one wishes to create a class of directed graphs as a subclass of the class of all graphs, then given that there already exists a data structure for the graph class, we would define the data structure for the subclass as shown in Figure 4.10. A few words about the primitives. The drawing primitives function in the co-ordinate system defined by the programmer when creating a new window. This eliminates scaling of coordinate values as N A A G maintains the correct aspect ratio when a drawing window is resized, and is an example of one more way that the programmer's task is simplified. The n_window_save primitive can be used to record the state of the window while n_window.restore restores the window to a previously saved state. N A A G maintains an internal display list and treats image data in the same manner as graphical elements such as lines. Images are automati-cally resampled when a window is resized, and gray-level images are automatically dithered if they are being displayed on a bi-level display. This makes it possible to easily combine textual, image, and graphical data.5 The n Jocator routine lets the programmer register a routine for processing locator events. Locator events have been reduced to just four types: button up, button down, move, and drag. The locator primitive in conjunction with the screen save and restore primitives can be 5A future extension may incorporate video and sound data in a hypermedia system. CHAPTER 4. MY APPROACH 56 t menu t operation Figure 4.8: NAAG program tree. t stub CHAPTER 4. MY APPROACH 57 .define.class Image { .class .none /* not a subclass */ .includes { "image.h" } /* C data structure */ .libraries { "-limg" } /* object library */ .display_routine Displaylmage .destroy.routine Destroylmage Figure 4.9: A N A A G class definition. /* The data structure for the Graph class. */ typedef struct { /* fields which define a graph */ } Graph; /* The data structure for the DirectedGraph class */ /* It is a subclass of the Graph class. */ typedef struct { /* fields that only apply to a directed graph */ Graph *parent; /* handle to the parent Graph data structure */ } DirectedGraph; Figure 4.10: Subclass data structure. CHAPTER 4. MY APPROACH 58 void RubberBandRegion(int event, int x, int y) { static int u, v; switch(event) { case N.LOCATOR-DOWN : n_window_save(); u = x; v = y; break; case N.LOCATOR-DRAG : n_window_restore(); n_draw_rectangle(u, v, x, y); break; case N.LOCATOR.UP : n_window_restore(); /* (u,v) - (x,y) is the chosen region */ /* ... code to do something with it ... */ break; default : break; } } Figure 4.11: A rubber-banding routine. used to implement rubber-banding, dragging, and graphical undo operations with just a few lines of high-level code. For example, Figure 4.11 contains C code for rubber-banding rectangular regions. 6 Given a complete program, the composer can generate the complete application with a single command. N A A G automatically creates the complete application and any related files. The composer can alter the menu tree by moving, adding, or removing components and obtain the modified application wi th a single recompila-tion. 6A library of routines which implement standard interactions can be defined in this manner. Chapter 5 Implementation It is easy to build a philosophy. It doesn't have to run. —Charles F. Kettering In this chapter I describe the implementation and discuss several issues which arose while I was building NAAG. I begin by presenting a high-level overview of the system components and then proceed to describe each component in greater detail. It is my intention to provide sufficient information to enable the motivated reader to implement a tool like NAAG. As such, I have tried to emphasize only those aspects which I feel are essential to this task, choosing to forego details which are not crucial. To facilitate this somewhat difficult task, I chose to employ a question-answer format whereby I pose questions and then proceed to answer them. This approach should be self-explanatory. 5.1 Overview The current version of NAAG produces X Windows [SG86] applications for Sun 3, 4, and SparcStation architectures. To simplify the generation of X-based applications we chose to use the XView Open Look Toolkit [Hel89]. XView enables the programmer to build interactive applications without having to know many of the details of the underlying window system - its object-oriented programmer's interface is simpler to learn and easier to use than XI ib. A number of Unix tools are used in constructing NAAG [JL78]. The C prepro-cessor cpp is used as a first pass filter and allows the programmer to take advantage of all of its features (such as the file include facility) when preparing NAAG source code, lex and yacc are used to implement the lexical analysis and parse phases of the compiler and to generate a parse tree. Code generation is performed by a module written in C, which creates the following outputs: 59 CHAPTER 5. IMPLEMENTATION 60 A p p l i c a t i o n components (wr i t ten b y user) NAAG operations NAAG menus NAAG classes 1-C data types Display, destroy mouse routines NAAG Application N A A G suppor t (p rov ided w i f e tool) •1 NAAG includes NAAO libraries: generic/specific —i. N A A G c o m p i l e r cpp: =:lex: lyacc: : ;C: jjmake: j preproc <: tokenize : parse :: codegen :compile • f • and link -c C code Hi—! *| Manual | '• Executable Figure 5.1: N A A G framework for application development. 1. a C program which calls a number of functions supplied in the N A A G run-time support libraries to build an XView interface, 2. a makefile for compiling the generated C code and linking all external object modules and libraries, and, 3. help information to be used at run-time. The make program is invoked by N A A G to compile the generated source code and link all associated object modules and libraries including the N A A G generic and target-specific run-time support software. Figure 5.1 shows the relationships among the various components which collectively define the NAAG framework for application development. 5.1.1 Main program The main program is a function written in C. What does the main program do? The main program performs several tasks. First of all, it parses command line arguments (see Appendix A) and initializes a number of global flags. If a N A A G source filename has been supplied, the C CHAPTER 5. IMPLEMENTATION 61 preprocessor (cpp) is used to filter the source code. The processed code is then consumed by the lex-generated lexical analyzer (lexer). How is the preprocessor invoked? The popenO command is used to invoke cpp, and to create a Unix pipe from which the lexer reads the preprocessed file as a stream of data produced by cpp. How is lexical analysis performed? The main program invokes yyparseO - a function generated by yacc. This function automatically calls yylex() - a function generated by lex - to obtain a stream of tokens. The interface between lex and yacc is well-documented. How is code generation initiated? If the source program parses correctly, yyparseO builds a parse tree which it passes to the code generation module. Fur-thermore, the code generation module automatically invokes the make program to compile and link the generated code. 5.1.2 Lexical analysis Lexical analysis is performed by yylex() - a function generated by lex. What does lex do? lex is a program generator designed for lexical processing of character input streams, lex accepts a high-level, problem-oriented specification for character string matching, and produces a program in a general-purpose language which recognizes regular expressions. The input to lex is a program written in a little language consisting of input-action pairs - when the input is observed the associated action is performed. How do I use lex? yylex() performs lexical analysis of the N A A G source files. Essentially, this function converts N A A G keywords into tokens and maintains file and line information for use in error reporting. What does yylex() return? yylexO is an integer-valued function - it returns a token number which represents the token read. If there is a value associated with that token, it is assigned to the external variable yylval (this is a C union, allowing many data types to be returned). What actions are performed? The most common action in my implemen-tation is to simply return an integer constant (token) which represents a N A A G keyword. These constants are defined in the companion yacc program. By tok-enizing keywords, a degree of syntax independence is obtained, since the keywords can be changed without altering the N A A G grammar. Another type of action is returning numerical or string data through the external variable yylval. How are errors located? The last type of action is the processing of line and file information generated by cpp. The preprocessor inserts the following type of text into the output: # I N T S T R I N G I N T CHAPTER 5. IMPLEMENTATION 62 where the first two values are the line number and file name of the current input file, and the third value is a mode which can be ignored. The lex program can intercept these lines and update global variables which may subsequently be used to report the locations of lexical and syntax errors found in the source code. The line number is incremented every time that lex encounters a newline character. 5.1.3 Syntactic analysis Syntactic analysis (parsing) is performed by yyparseO - a function generated by yacc. What does yacc do? yacc provides a general tool for imposing structure on the input to a computer program. The yacc programmer prepares a specification of the input process; this includes rules describing the input structure, code to be invoked when these rules are recognized, and a low-level routine - the lexical analyzer - to do the basic input (yylexO). yacc then generates yyparseO - a function to control the input process. This function, called a parser, calls the programmer-supplied lexical analyzer to read tokens from the input stream. The tokens are organized according to the grammar rules; when a rule is recognized, the programmer code supplied for this rule, an action, is invoked; actions have the ability to return values and make use of the values of other actions. How do I use yacc? The input file to yacc is used to define the syntactic structure (grammar) of N A AG's little language and to create a parse tree which is later used in the code generation step. What type of values do yacc actions return? Each construct in the NAAG language has an associated data structure for storing information which describes a particular instance of that construct. The memory for the data structures is allocated dynamically - data structures are accessed through a type-cast pointer. In order for yyparseO to be able to manipulate these pointers, the associated data types (defined using the C typedef) must be included in a C union which specifies all of the types that will be used. The °/»type keyword is used to specify the type of value that a rule returns (the default type is integer). What data structures must be defined? Each primitive construct in NAAG has its own data structure. Thus, for example, the range argument type the data structure shown in Figure 5.2. The primitive data structures are combined to build composite data structures. The data structure for the argument construct, for ex-ample, is shown in Figure 5.3. The top level data structure for the entire NAAG program is shown in Figure 5.4. What kind of parse tree is built? If the source program is accepted, then yyparseO will succeed in creating the top level data structure and will pass its address (pointer) to the code generation module. How is the parse tree built? As each rule succeeds, the associated data structure is created and its fields set appropriately. Figure 5.5 shows a code seg-CHAPTER 5. IMPLEMENTATION 63 typedef struct { int integer; /* flag: is range integer or real valued? */ union { struct { int min, max, init; } ivals; struct { double min, max, init; } rvals; } va\s; } range; Figure 5.2: range argument data structure. typedef struct { int kind; union { range *range; set *set; text *text; flag *flag; object *object; } arg; char *label; char *help; } argument; Figure 5.3: argument data structure. typedef struct { char *name; char *label; char *help; list *classes; list *menus; } application; Figure 5.4: application data structure. CHAPTER 5. IMPLEMENTATION 64 range : RANGE MINIMUM INT MAXIMUM INT INIT INT { range *p = NEW(range); /* allocate a new data structure */ p->integer = 1 ; . /* se^ fields to appropriate values */ p->vals.ivals.min = $3; p->vals.ivals.max = $5; p->vals.ivals.init = $7; $$ = p; /* return pointer to newly created range data structure */ Figure 5.5: Dynamic creation of the range data structure. ment which creates a new range data structure and returns its pointer to the higher level rule which creates a complete argument data structure. The capitalized strings refer to token names. The top level rule does not return the pointer to the main ap-plication data structure (parse tree), but instead invokes the code generator, passing this pointer as a function argument. 5.1.4 Code generation Code generation is performed by a function written in C. Code generation is a difficult task, and although there are a number of useful principles, creating good code generators is still more of an art than it is a science. What does the code generator do? The final product of NAAG's code gen-erator is an executable version of an interactive application. The code generator obtains this by first creating high-level code which implements the interactive ap-plication (complete with UI), and a makefile which is used to compile this code and link in all of the necessary object modules to obtain the executable. As its final step, the code generator invokes the make program. What type of code should be generated? While the language of the gen-erated code is largely determined by the target UI, alternatives still exist. With XView, for example, the code to be generated is C source code. This however, leads to the following question. Should I generate raw code to realize every potential UI task, or should I prepare a library of functions — one function for each task? I chose the latter for it substantially reduced the size of the generated code, and consequently, the time required to compile the resulting program. In this scenario, each code burst typically generates one or two function calls with appropriate function arguments rather than the body of the function. The negative aspect of this approach, is the fact that devising a useful set of functions is a difficult task. What language should be used to implement the code generator? I chose C because it is flexible, widely available, and provides simple mechanisms to CHAPTER 5. IMPLEMENTATION 65 access other programs and operating system functions. Since code generation mostly involves tree-traversal with intermittent code burst activity, a language like Prolog may be better suited to the task of building code generation modules. However, Prolog is not as widely available or flexible, and does not have accepted standard ways for performing i/o and other operating system functions. How is the code generator implemented? Given the approach described thus far, code generation consists of two parts: generating a source program which creates a UI by invoking a set of routines packaged in a run-time library (this is done every time that an application is generated), and creating the run-time library (this is done once for each target UI). Is there any other reason for using libraries? Packaging code to manipulate common UI objects has an additional advantage. In situations where several target UIs are roughly isomorphic with respect to the types of objects which they define (e.g., windows, dialog boxes, widgets) and the method of specifying the interface (e.g., a sequence of function calls to toolkit routines), it may be possible to use a single code generation module to generate code for all UIs in the given equivalence class (e.g., current graphical direct-manipulation UI tools such as Xlib, XView, Microsoft Windows). The modification would be isolated to the library of functions which implement these common operations. What routines should be defined in the library? The routines that I found useful for manipulating common UI elements are listed in Table 5.1. Note the strong mapping between the NAAG application model and the choice of routines. The routines belong to roughly four classes according to their purpose: creating a UI element, obtaining the current value of a UI element, initializing a dynamic UI element1, and setting the value of a UI element. 1A dynamic element is one whose initial values vary during execution, by being directly depen-dent on the dimensions of a dynamic window, for example. CHAPTER 5. IMPLEMENTATION 66 Frame create_dialog(Frame, char *, Panel *); Menu create_root_menu(char *); Menu createjsub_rnenu(Menu, char *); PaneLitem create_range(Panel, char *, int, int, int); Panel-item create_text(Panel, char *, int, char *); Panel-item create_flag(Panel, char *, int); PaneLitem create_set(Panel, char *); Panel-item create_point(Panel, char *); Panel-item create_region(Panel, char *); int get_flag(Panel_item); int get_set(Panel_item); int get_range(Panel_item); int * get.point(PanelJtem); int * get.region(PaneLitem); char * get_text(Panel_item); void init_point(Panel_item, int [J, int []); void init_region(Panel.item, int [j, int []); void set_operation(Menu, char *, Frame, int (*)(), void (*)(), void (*)()); void set_stub(Menu, char *); void set_label(Frame, char *); void set_root_menu(Menu, Panel); void set_menu_list(Menu, n_menuJist_t **); void set_help(Xv_opaque, int); void set_dialog_resize(Frame, Panel); void set_dialog_hide(Frame); void set.default_value(Panel_item, int); void set_item(Panel_item, int, char *); void set.point(Panel_item, int Q); void set_region(Panel_item, int []); Table 5.1: A set of useful routines for manipulating common UI elements. Chapter 6 Discussion In this chapter we uncover some of the consequences and implications due to our approach. We refer to N A A G throughout our discussion, for it is one embodiment of our ideas. 6.1 Dialogue independence As described earlier, Dl is characterized as follows: the dialogue component (DC) and the computational component (CC) are independent. A sufficient test for Dl then, consists of checking that the following two conditions hold: 1. modify the CC; the DC should not have to be modified (it should not matter to the DC how the CC performs computational tasks), and, 2. modify the DC; the CC should not have to be modified (it should not matter to the CC how the DC interacts with the user). When using traditional UI toolkits, Dl can be achieved partially by ensuring that the code which makes up the DC is separated from the code which makes up the CC. In using N A A G , however, we are able to achieve a greater separation between the DC and the CC. Since N A A G automatically generates the UI, it automatically generates the DC. The UI is directly related to the N A A G specification which de-scribes the application structure and interactive requirements. If the application description is modified, N A A G will automatically generate an appropriate UI. Thus changing the CC does not affect the DC. The manner in which the UI realizes the interaction, is determined by how the code generation module has been prepared by the UI expert and the domain expert. Thus the DC can be freely modified without affecting the CC. 67 CHAPTER 6. DISCUSSION 68 6.2 Software reuse In this section I discuss how N A A G encourages or dictates practices which enhance our ability to reuse software. The term software reuse could refer to several classes of software. A convenient distinction for my purpose is between application software and UI software. Accordingly, I divide my discussion into two parts. I conclude this section with some comments on software sharing strategies. 6.2.1 Application software As described earlier, N A A G applications are collections of abstract data types and operations implemented as data structures and functions in a high-level language. As such, the programmer is required to make the fewest possible assumptions regarding the environment in which the application will be used. One of the most complex aspects of the environment is the UI. N A A G shields the programmer from virtually all UI considerations and provides a simple mechanism which allows application code to be used in many unrelated situations. Thus, for example, an abstract operation implemented as a function which obtains its inputs via function arguments, can be embedded in any N A A G application, as well as most non-N A A G programs. 6.2.2 UI software Another instance in which N A A G exploits software reuse is during code generation. Since a UI tool is typically used many times, the UI expert can put more effort into the creation of complex UI components. By employing an object-oriented ap-proach, the UI expert can define each component exactly once. The code generation module, however, will typically use each definition to create many instances of each component. 6.2.3 Software sharing A far too common occurrence in software development has been dubbed: reinventing the wheel - developing the same software time and time again. Although public domain software has matured and grows in popularity, several factors have prevented effective software sharing on a large scale. Competitive business practices are to a large extent responsible for our failure to share technology. Unfortunately, barring a major restructuring of our economic system, this will probably remain the case.1 If we are to make progress in this di-rection, we will probably have to proceed on another front: creating environments Although experiences in Japan have shown that a high level of cooperation can be achieved even in a competitive setting. CHAPTER 6. DISCUSSION 69 which provide simpler and more effective means for sharing software, and incentives to employ them. This will likely occur on a smaller scale - within an institution, a re-search or application area, or in a collaborative endeavour involving a heterogeneous group. Our experience with N A A G has been very positive and encouraging. The Lab-oratory for Computational Vision has provided the major testbed by maintaining an interactive vision and image processing system supporting several abstract data types and numerous operations. N A A G provides an ideal framework for cooperative software development. It was observed that once a skeletal system was set up, indi-viduals possessing varied backgrounds and programming abilities found it easy and indeed, exciting, to contribute software - typically in the form of additional oper-ations. The key to this success, is the fact that in order to create and test a new operation, a programmer simply writes a function and its associated N A A G opera-tion specification - she can take advantage of existing N A A G components without having to understand them or the intricacies of the underlying UI system. I believe that N A A G fosters this type of cooperative software development: by making it fun to write software and by encouraging experimentation. N A A G satisfies all of Krueger's general requirements for an effective software reuse technology. 1. N A A G reduces the cognitive distance between the initial conceptualization of a system and the final executable specification of the system - by simplifying UI specification for the programmer, and application generation for the composer. 2. N A A G makes it easier to reuse artifacts than to build them from scratch -by providing a broad range of services: automatic generation of UIs includ-ing complex internal dialogues and control, a simple output model including automatic window management, an automatic make utility, etc. 3. N A A G operations are self-documenting (through integrated help information) and often correspond to user-level tasks (e.g., rotate the object). As such, they are easy to understand conceptually (as the composer does not have to know how an operation is implemented in order to use it), and are thus easy to select. 4. Libraries of N A A G components can be organized according to the component's function (e.g., operations can be grouped based on the class(es) of objects upon which they operate). Thus, typically, an artifact will be located faster than it can be (re)built. 6 . 3 Levels of representation of abstract objects In this section I discuss several issues regarding abstract object formats and repre-sentations. By representation, I am referring to how an object may be represented CHAPTER 6. DISCUSSION 70 (A) File Format; how an object is stored: (AA) in a file (AB) in memory (when loaded using a standard routine e.g. TIFF images) (B) Intermediate Format (how an object is represented in memory) ( C ) Display Format (memory representation required by display services) Table 6.1: Levels of object representation. in machine readable format - not an abstract representation. Although these issues are not central to the task of generating UIs or interactive applications, they are important in the NAAG framework. The approach which I am putting forth with NAAG emphasizes the manipulation of abstract objects. Objects may be simple: numbers, text, geometric figures; or complex: fourier transforms, programs, pro-cesses. Regardless of how complicated an object is, however, it must be possible to represent it at several levels, each serving a specific purpose. I study this problem from two perspectives: 1. the NAAG point of view: what levels must be given consideration in the context of the UI tool, and, 2. the application programmer's point of view: what issues must be accounted for by the programmer. For the latter, the vision and image processing application domain serves as an example. 6.3.1 The N A A G perspective Depending on the context in which objects are used, there may be several levels of representation. Table 6.1 shows one classification. From the point of view of NAAG, we cannot impose any restrictions on (A) or (C) . (A) is chosen by the user, while (C) is a function of the given UI. This means that N A A G can only vary (B). It is the responsibility of the programmer to provide routines for input, output, and object manipulation.2 For the sake of efficiency, it would be beneficial if a library of routines would operate on (B), as this would mean that the output of a given operation could be handled by the NAAG display routine directly - a conversion would not be required. 2 A library of image processing routines, for example. CHAPTER 6. DISCUSSION 71 It is even more crucial then, that (B) is chosen carefully, so as to be general enough. Two points worth noting: 1. even though (B) is general, not all objects that can be described in (B) will necessarily be handled by N A A G (these could be added gradually); for unsup-ported types, the programmer has the option of converting the object to a supported type, and, 2. the format (C) may not be sufficient to represent some objects (e.g., colour images); the N A A G display routines could provide some conversion in these cases (e.g., if N A A G supports 24-bit colour, it would be responsible for con-verting this representation to something that both the UI and the workstation are capable of displaying). 6.3.2 The image processing perspective It would be nice if we could create a truly portable and general set of primitives for image processing. Unfortunately, in order to achieve this goal, performance would most certainly have to be sacrificed. Thus we must settle for a compromise. As mentioned above, it would be nice if the primitives operated on (B). This may or may not be practical - the best we can hope is that the format they operate on is sufficiently close to (B), so as to facilitate efficient conversion.3 A high-level interface is also important. However, since the format is now fixed, the primitives could access image data directly. The challenge is to maintain gen-erality: both in the case of the format, and in making the routines general across different types of images. This appears to be an open problem. It would also be beneficial if (AB) was the same as (B), but this isn't always practical (e.g., TIFF). This is not terribly important, however, for the file is typically read and written once. 6.3.3 Conclusions 1. In the case of the UBC Integrated Vision System, the following alternatives were chosen. (AA) = IFF (Image File Format [Hav85]) (AB) = IFF padded to 8 bit boundaries (B) = essentially (AB); but discard some unnecessary header information (other support can be added later) (C) = X Windows Pixmaps [SG86] 3As this would have to be done every time a new object is displayed, which is typically when it is created. CHAPTER 6. DISCUSSION 72 2. The read and write routines supplied to NAAG read in ( A A ) and return ( A B ) and vice versa. The conversion from ( A B ) to (B) is fast. 3. Standard image primitives operate on ( A B ) and have the option of directly accessing the data; the routines to access ( A B ) are provided by the programmer - not NAAG. These could operate on (B) , but we would have to be careful not to throw away information in the ( A B ) =>• (B) conversion. 6.4 C o n f o r m a n c e i ssues Mediocrity thrives on standardization. —Anonymous Conformance validation of graphical user interfaces is problematic. Some existing interface tools generate interfaces which conform to specific look-and-feel conven-tions, while others allow the look-and-feel to be specified independently. However, these approaches give the designer too much latitude - he may sti l l introduce incon-sistencies. I believe that it is better to prevent inconsistencies from arising in the first place, rather than having to detect them afterwards. M y approach not only simplifies the programmer's task, it guarantees that the generated interfaces exhibit a higher degree of conformance. Some tools such as the XView generate interface components which conform to specific look-and-feel conventions. Other tools such as Jade [VZM90] automatically create graphical input dialog boxes in a look-and-feel independent manner. Al though these tools guarantee that the generated interface wi l l exhibit a certain degree of look-and-feel conformance, the programmer is free to vary many aspects of the interface, and may introduce inconsistencies. For my purpose, I classify conformance as follows. 1. Look-and-feel - the appearance and behaviour of interface components. 2. Interactive facilities - standard facilities for providing help, undoing or cancelling commands, obtaining simple inputs such as text and numeric data, and direct-manipulation techniques such as rubber-banding or dragging. 3. Operation semantics - how operations are accessed, enabled, invoked, and organized. 4. System model - the user's perception of how the application functions: what are the components of the application; how are they related; and how are they manipulated. CHAPTER 6. DISCUSSION 73 The tools mentioned thus far are primarily concerned with the first aspect. NAAG, on the other hand, provides mechanisms for addressing the remaining aspects. 6.4.1 Look-and-feel Although XView ensures that interface components such as buttons, menus, or sliders conform to the Open Look GUI conventions, some aspects of interface design are still the responsibility of the programmer. One simple example, is the convention that names of menu items which cause a dialog box to be displayed should be suffixed with ellipses (...). Since XView cannot enforce this convention, it is up to the individual programmer to do so consistently. NAAG creates dialog boxes for operations which must obtain inputs from the user. Therefore it can automatically append ellipses to the corresponding operation labels. Operations which do not require inputs retain their original labels. See the menu displayed in Figure 4.5 for an example. 6.4.2 Interactive facilities Providing consistent facilities for standard tasks such as obtaining help, undoing or cancelling operations, rubber-banding, dragging, and so on, is both important to do and difficult to achieve. Furthermore, these facilities should remain uniform not only within a single application, but across many applications, making it easier for users to use existing systems and to learn new ones. As the first example, consider the common tasks of invoking or cancelling an operation. Figure 6.2 shows a dialog box generated by NAAG. Notice that the corresponding operation description shown in Figure 6.1 does not contain a definition of these tasks. NAAG automatically generates the Continue and Cancel facilities, and provides a consistent method for accessing them. Next, consider the task of obtaining an integer value from a specified range of integers. Most current interface tools provide several methods for carrying out this task - it is the programmer's responsibility to choose the most appropriate technique. XView, for example, lets the programmer use a slider panel item or a numeric text panel item. Intuitively sliders are better suited for choosing an integer from a relatively large range, while a numeric text item may be more appropriate for choosing a value from a small range. While the programmer is usually capable of selecting from a set of candidate interactions, a tool like NAAG can eliminate the need to do so. NAAG automatically choses a method based on a set of rules built into its code generation module.4 Figures 6.1 and 6.2 contain the range example. 4The rules could be seen as a set of simple heuristics derived by a human-factors expert who is familiar with both the general principles of human-computer interaction and the given application domain. CHAPTER 6. DISCUSSION 74 .operation RangeDemo { .class .none .modules { "ranges.o" } .label "Range demo" .argument { .range .minimum 0 .maximum 10 .initial 5 .label "Small range" } .argument { .range .minimum 0 .maximum 100 .initial 50 .label "Large range" } } Figure 6.1: Range Demo operation description. IS Range demo • • • • • • • • Small range 5 l * M Large range 0 I ^ B Q = : =n 100 50 (Continue ] ( Cancel ) Figure 6.2: Range Demo dialog box generated by NAAG. CHAPTER 6. DISCUSSION 75 Finally, consider common interactions such as selecting graphical elements in a window, rubber-banding, or dragging. NAAG provides consistent techniques for obtaining point and region arguments for operations. Programmer-defined event handling routines such as the rubber-banding example shown in Figure 4.11 are less restricted. However, it is hoped that a set of routines for performing standard interactions will be collected into a programmer-defined object library and will be shared among applications. This, of course, is the duty of the programmer. 6.4.3 Operation semantics Most systems provide a mechanism for context-sensitive enabling of operations - to implement conditional enabling of the form: if the user has selected an item, then enable the Copy, Move, and Delete operations; or, if the image contains signed data, then enable the ZeroCrossing operation. NAAG provides this facility in the form of its preconditions construct. This is the only mechanism provided by most current systems. Most tools do not exploit the class hierarchy information beyond implementing simple property inheritance. NAAG, on the other hand, uses this information in an additional and novel way. A NAAG operation or menu is defined to belong to an existing class. As described earlier, NAAG enforces a nesting constraint which ensures that the hierarchy of menus is valid - this provides a simple mechanism for associating root menus with objects and prevents irrelevant operations from being accessed (e.g., the user is never given an opportunity to invoke an operation which requires the input to be an image if the underlying object is a histogram). Thus the programmer does not have to build extensive checks to provide the equivalent guarantee. 6.4.4 System model Perhaps the most difficult issue to define and to evaluate is the role of the user's conceptual model of the application in determining the success or failure of a user interface. Unfortunately, the number of objective methods for ranking possible approaches appears to be nil. By appealing to more subjective criteria, some system models can be said to be better than others (as shown by the popularity of graphical direct-manipulation versus textual command-line interfaces, for example). NAAG'S object-oriented approach, which sees an application as a collection of abstract operations, is both conceptually simple and expressively powerful, and is well-suited to a variety of application domains. In this respect, NAAG differs from most current tools, for it emphasizes the creation of multiple windows each housing a single object rather than a single window containing multiple objects. Although this may not be appropriate for all application domains, it has the advantage that it eliminates the ambiguity problems associated with the selection of objects and may represent a more natural and intuitive model of the system for the user. One CHAPTER 6. DISCUSSION 76 limitation of this approach is the restriction that operations can take at most one object as input and produce at most one object as output. Finding a simple and elegant extension which would eliminate this restriction may be one of several future projects. 6.5 Relationship to existing systems As mentioned earlier, my approach is related to that of MENULAY, SYNGRAPH/MIKE, and UIDE/IDL. The common theme: the application's interface is generated auto-matically from a high-level specification of the inputs and outputs of the operations within the application. While NAAG does not diverge on this point, it differs in a number of respects. NAAG is a programming tool. The intent with NAAG is to provide a tool that aids the entire interactive application development process, not just the creation of UIs. NAAG promotes modular design and the reuse of existing artifacts with different UIs. NAAG's concept of "object" is different. The NAAG approach is to main-tain multiple windows each housing a single object, rather than a single window containing many objects. Although the merits of this distinction are debatable, I believe that the former view offers a number of advantages. For one, it eliminates ambiguity problems associated with object selection. On the other hand, it may be more difficult to manipulate elements (sub-objects) that are displayed in a single window (these would have to be defined as compound objects). NAAG uses class hierarchy information in a novel way. NAAG enforces an inheritance constraint which prevents the programmer from nesting operations and menus in a manner which would allow irrelevant operations to be accessed. This is different from the preconditions in IDL (although NAAG provides a similar mechanism for context-sensitive enabling of operations). NAAG has a simple, elegant preconditions model. Preconditions are used as a means to specify arbitrary conjunctions of user supplied functions, which are invoked prior to the enabling of commands. The user can maintain variables of the sort found in IDL to the same end. This method not only provides greater flexibility (as arbitrary tests can be carried out), it leaves the decision making to the application rather than to the UI. This choice of control is consistent with the view that the purpose of the UI is to enable communication between the user and the application to take place. NAAG employs existing interface tools to realize the interface. This practice not only increases the tool's portability, it also provides a means to exploit the features of low-level tools, and to take advantage of future technology. This differs from other tools, which typically perform all UI management internally, and are therefore harder to port or upgrade (this could require an almost complete CHAPTER 6. DISCUSSION 77 rewrite). Furthermore, as a practical aside, it is very important to support widely accepted UIs such as X Windows or the Macintosh UI, if the UI tool is to be used. The trend in software is toward standardization and open design - UI tools which do not support this trend will not be accepted by the software development community. 6 . 6 Experiences N A A G has been used to implement several interactive applications. The Laboratory for Computational Vision at UBC has developed a sophisticated image processing application for computer vision. This system contains several ob-ject classes such as images, edges, and histograms, and a variety of operations which manipulate objects belonging to these classes. A number of graduate students have used N A A G to develop additional image processing software as part of a graduate course in computer vision. A simple drawing package has also been implemented to illustrate the flexibility of N A A G . Future applications may include a general purpose 3D graphics system, a simple CAD package, and an interactive graphical editor for manipulating N A A G specifications using a pictorial representation. The experience of programmers using N A A G has been very positive. N A A G appears to have met all of our design criteria: it is easy to use and greatly simplifies the programming task; it generates applications quickly; it lets programmers add new components to an existing system; and it reduces the number of bugs and inconsistencies in the implementation. C h a p t e r 7 F i n a l remarks I hate quotations. —Ralph Waldo Emerson 7.1 Summary and conclusions UI tools simplify the creation of UIs. Sophisticated general-purpose tools are diffi-cult to use and fail to make provisions for porting the resulting applications across different UIs. Tools which generate an interactive application from a high-level description of its semantics require less effort to use and provide greater opportunity to exploit existing and future technologies. Existing tools do not take these aspects far enough: some are too low-level (TIGER), some are too limited (MENULAY), while others are overly complicated and do not utilize existing low-level tools (UIDE). My approach is based on the use of specialized models to describe the appli-cation's semantics (e.g., abstract operations, their inputs and outputs, and their relative organization within the application). The programmer specifies what type of information must be exchanged between the application and the user rather than how the UI should realize such an exchange. NAAG, a tool based on this approach, facilitates application development in a number of ways. 1. It generates the UI using the information embedded in the application model - a detailed explicit description of the UI is not required. 2. It fosters a strategy which emphasizes the creation of artifacts that are clearly separated from the UI and thus exhibit greater potential for reuse. 78 CHAPTER 7. FINAL REMARKS 79 3. It increases software portability. By modifying NAAG'S code generation mod-ule, existing applications can be recompiled to operate on different machines and to employ a variety of UIs and interactive styles. 4 . It provides a more consistent environment for the application developer and a more uniform interface for the user through the standardization of program-ming tools and interactive styles. 5. It generates applications which contain fewer bugs than hand-coded systems, and exhibit a higher degree of conformance than applications created with most other tools. 6. It facilitates the creation of integrated systems which employ arbitrary collec-tions of software artifacts. NAAG is not just another UIMS - it is a tool which addresses the entire software development cycle and is sensitive to the practical considerations of software devel-opment. For example, NAAG provides a more complete programming environment and the capability to support widely accepted UI systems at the present time and new technology in the future. Most significantly, I have demonstrated a key distinction between the traditional UI as an add-on approach, and the UI as a side-effect approach which I advocate. That is, rather than treating the UI as a component which is constructed separately and then bound to the computation component via internal dialogues, NAAG pro-duces the UI as a side-effect of generating an application. An appropriate application model captures the information which is relevant to this task. Furthermore, the use of an abstract model can simplify the design, implementation, and maintenance of interactive applications. The NAAG object-oriented operational model satisfies both of these criteria. Significant advances in UI technology will likely depend on advances in soft-ware engineering in general, and the discovery of appropriate application models in particular. The NAAG approach provides a very simple mechanism for creating interactive applications and should be important in the future. CHAPTER 7. FINAL REMARKS 8 0 7.2 Future directions I never think of the future. It comes soon enough. —Albert Einstein My interest is in the future because I am going to spend the rest of my life there. —Charles F. Kettering 7.2.1 Extensions While the NAAG application model is sufficiently rich to describe many tasks, I have hinted at several shortcomings. One of the most significant limitations is the fact that operations can be ap-plied to and produce at most one object. In theory, it is possible to accommodate this in the current framework by defining compound object classes. This, however, is not sufficient in practice, because we still want to be able to specify arbitrary combinations of existing objects rather than creating artificial compound objects. Furthermore, it is generally better to be explicit about the inputs and outputs rather than hiding this information in a compound object class. An extension which ac-commodates these requirements is the following. 1. Provide an additional operation argument type: the external object. To select an object, the user would be required to select a window which contains it. Since NAAG already knows what type of object is associated with a particular window, it could perform class checking and produce an appropriate error message in the situation where an invalid object is selected. The user could not invoke the operation without first selecting all external objects. 2. To allow the creation of multiple objects the NAAG result construct would have to be extended to allow the specification of a list of objects rather than a single object (or a special object which consists of a set of standard objects). A second drawback is the restriction that all operations must be accessed via a menu. This is especially pronounced in cases where we would like to have a more immediate method of accessing operations. In particular, suppose we would like to be able to select operations which change the way an object is displayed (e.g., to rotate a 3D model continuously). Given the highly interactive nature of such operations, a more immediate access technique would be more appropriate. For CHAPTER 7. FINAL REMARKS 81 each object class, we could define a set of operations as belonging to a special direct invocation set (e.g., such a set could be implemented as a panel containing a set of buttons which enable the user to invoke its constituent operations directly). Another limitation is the lack of the ability to obtain inputs a f t e r an operation has been invoked. This requirement arises as follows: the UI obtains an initial set of inputs and invokes an operation; the operation performs some computation and based on some intermediate results must obtain further information from the user. A simple extension could provide a set of primitives - one for each operation argument type - which the underlying function could invoke to obtain an input after it has been invoked. Since this technique retains the what vs how approach, it does not diminish the portability aspects of NAAG. Extended colour and image support would increase NAAG'S functionality. Colour graphics are very important in the context of CAD systems, while colour images will likely become the standard for desk-top publishing, image processing, and vision applications. As a further practical consideration, the drawing primitives should have a com-panion set of primitives for removing items from the display list. This is mostly a matter of efficiency and performance. Consider, for example, a CAD application which renders 3D models using on the order of 100,000 line elements. In the current model in order to remove a single element we must redisplay the entire data struc-ture and omit the chosen element. To implement the deletion capability, we would require an efficient strategy for determining the set of elements which are affected by the deletion of a particular element (rather than searching the entire display list). Maintaining temporal relationships could add further complications. Currently, NAAG does not support graphical fonts - the text output routine is only capable of displaying fixed-size text. This feature is important for many 3D graphics and desk-top publishing applications. The help facility should be enhanced to supply more detailed help at run-time, and to create user documentation (e.g., Unix man pages) automatically. 7.2.2 Graphical editors Graphical direct-manipulation editors have been used by tools such as MIKE (Section 3.4) to simplify the specification of UIs. It has been argued that using graphical editors to edit graphical representations of UIs is preferred over the use of text editors to edit textual representations of UIs, not simply because graphical editors are necessarily easier to use,1 but because it implies that the programmer does not have to learn the (textual) interface specification language. A graphical editor which enables the user to manipulate NAAG source programs using a pictorial representation, for example, could enhance the usability of NAAG. *In fact, this may not be true for programmers who are intimately acquainted with their favourite editor. CHAPTER 7. FINAL REMARKS 82 Since NAAG'S little language already deals with very high level concepts, it is unlikely that eliminating the textual specification would further simplify the programmer's task, as she must still understand the NAAG components at the conceptual level in order to construct NAAG applications. It would, however, reduce the number of bugs in the specification as the the editor rather than the programmer would be entrusted with the task of generating NAAG source code. An interesting aspect to note is that such an editor could be naturally imple-mented as a NAAG application: by defining a set of routines (operations) which manipulate NAAG programs (objects). This has two advantages: the editor would employ the same style of UI as the applications it manipulates, and it would be portable - as NAAG is ported to new environments all of the existing tools would be retained. NAAG list arguments and menus could be used to provide alternatives when building applications, and the preconditions could be used to enforce context-sensitive selection (such as enforcing class-hierarchy constraints). The file representation of the NAAG object class would simply be the NAAG source programs. The editor could then automatically invoke NAAG to create the executable version of the application. The following are additional considerations. 1. We would require a method for walking through the specification and modi-fying components at a variety of levels (menu hierarchies, classes, operations, arguments, etc.). It should be possible to save and retrieve components indi-vidually. 2. Concept of environment: user should be given all valid alternatives when prompted for a value (e.g., a list of all operations, defined within a given environment, which return a certain type of object). Environments could con-tain this type of information and could be used in much the same way as object libraries are in conventional software development - artifacts could be added, removed, or modified.2 3. A preprocessor could be used to parse the C source files containing functions which implement operations and extract input and output information. This could partially automate the preparation of operation specifications. The user would then be prompted to provide additional information (e.g., labels and help strings), and to resolve ambiguities (e.g., is an integer parameter a flag, a set, or a range argument?). 2Existing Unix tools could be integrated into the interactive system and used to manage such libraries. CHAPTER 7. FINAL REMARKS 83 7.2.3 Adaptive dynamic generation of user interfaces User modellers User or cognitive modelling is studied in psychology, artificial intelligence, and most recently, in the field of human-computer interaction. Most current approaches in HCI can be characterized as consisting of a classi-fication phase - how competent is the user - followed by a selection phase - how should the application interact with the user. The majority of the existing selection techniques are limited to simple textual dialogue modification such as responding with a degree of verbosity which corresponds to the perceived ability of the user. The information collected during the classification phase is seldom used to effect more sophisticated selection methods. In particular, it would be useful to be able to use such information to dynamically create more sophisticated UIs such as graphical direct manipulation or hypermedia UIs, which, as far as the limitations of the system allow, provide the most appropriate means for carrying out the perceived desired interaction. Application modellers An application modeller (AM) can be viewed as conceptually analogous to a user modeller (UM). Before such an analogy can take shape, however, I must first redefine what I mean by an application. While there is a lack of methodology or approach in user modelling, the spirit of such a venture can be easily grasped. By employing UMs we are attempting to obtain a more accurate guess of the user's intents and abilities so as to provide more effective interaction. Applications, however, are transparent: we shouldn't have to hypothesize what their intents might be. So what does an AM do? The answer to this question lies in the following somewhat subtle distinction. Traditionally, an application has been viewed as a rigid, static entity - an object which has a predetermined finite number of behaviours which are fixed. If, instead, we think of an application as consisting of a set of primitive operations which can be combined in a variety of ways to produce a broad range of behaviours, then an AM is precisely that part of the system which reasons about the constituent operations and plans sequences which carry out a required task. The key factor here is the existence of a certain degree of self-knowledge - the AM must somehow be able to reason about the constituent operations (what do they do and how can they be combined). The analogy then, has a symmetrical flavour which is illustrated in the following section. User interface generation Given appropriate UMs and AMs, we can begin to define an HCI component whose task is to mediate the user and application views and to dynamically construct UIs CHAPTER 7. FINAL REMARKS 84 which simultaneously satisfy the requirements of both views. Figure 7.1 shows one possible arrangement. Several points deserve mention. 1. AM is independent of the applications. 2. AM is independent of the HCl component. In particular, this subsumes Dia-logue Independence. 3. UM is independent of the HCl component. This provides a clear separation of task: the UM performs classification, while the HCl component is charged with the selection of appropriate interaction techniques. 4. UM is independent of the user. Furthermore, as illustrated in Figure 7.1, the UM can maintain history information for each user. 5. Similarly, the AM can maintain an application history. If task planning is performed by a logic program for example, a truth maintenance system could be used to maintain previously computed task sequences. 6. In an analogous fashion to the AM, a special-purpose meta-application could be supplied with knowledge about a set of applications. This could be used to create an illusion of an intelligent agent capable of performing a number of tasks and of communicating these abilities to the user. CHAPTER 7. FINAL REMARKS 85 ' \ User Modeller (a) Traditional approach (b) Proposed approach Figure 7.1: Framework for adaptive dynamic generation of human-computer inter-faces. B i b l i o g r a p h y [Ben86] J. Bentley. Programming pearls: Little languages. Communications of the ACM, 29(8):711-721, August 1986. [Bla77] J.L. Black. A general purpose dialogue processor. In National Computer Conference, pages 397-408. ACM, ACM Press, New York, NY, 1977. [BLSS83] W. Buxton, M.R. Lamb, D. Sherman, and K.C. Smith. Towards a comprehensive user interface management system. Computer Graphics, 17(3):35-42, 1983. [BR87] T. Biggerstaff and C. Richter. Reusability framework, assessment, and directions. IEEE Software, 4(2):41-49, March 1987. [Bro85] M.D. Brown. Understanding PHIGS. Megatek Corporation, San Diego, CA, 1985. [Cle88] J.C. Cleaveland. Building application generators. IEEE Software, 5(4):25-33, July 1988. [CLP84] T.T. Cheng, E.D. Lock, and N.S Prywes. Use of very high level lan-guages and program generation by management professionals. IEEE Transactions on Software Engineering, 10(5):552-563, September 1984. [FKKM89] J. Foley, W.C. Kim, S. Kovacevic, and K. Murray. Defining interfaces at a high level of abstraction. IEEE Software, 6(l):25-32, January 1989. [Fol87] J. Foley. Transformations on a formal specification of user-computer interfaces. Computer Graphics, 21(2):109—113, 1987. [GG90] D.R. Gentner and J. Grudin. Why good engineers (sometimes) create bad interfaces. In CHI '90 Conference, pages 277-282. ACM, ACM Press, New York, NY, April 1990. [GII83] Graphical input interaction techniques workshop summary. Computer Graphics, 17(l):5-30, 1983. 86 [GR83] A. Goldberg and D. Robson. SMALLTALK-80 The Language and its Implementation. Addison-Wesley, Reading, MA, 1983. [Hav85] W. Havens. A portable image processing system for computer vision. Technical Report 85-9, University of British Columbia, 1985. [Hel89] D. Heller. XView Programming Manual. O'Reilly and Associates, Se-bastopol, CA, 1989. [HH86] D. Hix and H.R. Hartson. An interactive environment for dialogue de-velopment: its design, use, and evalution. In CHI '86 Conference, pages 228-234. ACM, ACM Press, New York, NY, April 1986. [HH89] H.R. Hartson and D. Hix. Human-computer interface development: Concepts and systems for its management. ACM Computing Surveys, 21(l):5-92, 1989. [IEE84] IEEE. Special issue: Graphics kernel system. IEEE Computer Graphics, 7, 1984. [Jac83] R.J.K. Jacob. Using formal specifications in the design of the human-computer interface. Communications of the ACM, 26(4):259-264, April 1983. [JL78] S.C. Johnson and M.E. Lesk. Language development tools. Bell Tech-nical Journal, 57(6,2):2155-2176, July-August 1978. [Kas82] D.J. Kasik. A user interface management system. Computer Graphics, 16(3):99-106, 1982. [Kas85] D.J. Kasik. An architecture for graphics application development. In IEEE International Conference on Robotics and Automation, pages 365-371. IEEE Computer Society, IEEE Computer Society Press, New York, NY, 1985. [KE88] T. Koschmann and M.W. Evens. Bridging the gap between object-oriented and logic programming. IEEE Software, 5(4):36-42, July 1988. [Kru89] CW. Krueger. Models of reuse in software engineering. Technical Report CMU-CS-89-188, Carnegie Mellon University, December 1989. [KSS84] P. Kruchten, E. Schonberg, and J. Schwartz. Software prototyping using the setl programming language. IEEE Software, l(4):66-75, October 1984. [Lam86] L. Lamport. A Document Preparation System. User's Guide And Ref-erence Manual Addison-Wesley, Reading, MA, 1986. 87 [Lev86] L.S. Levy. A metaprogramming method and its economic justification. IEEE Transactions of Software Engineering, 12(2):272-277, February 1986. [MJ88] S.K. Misra and P.J. Jalics. Third-generation versus fourth-generation software development. IEEE Software, 5(4):8-14, July 1988. [ML86] J. Martin and J. Leben. Fourth-Generation Languages, volume 2. Prentice-Hall, Englewood Cliffs, NJ, 1986. [Mye89] B.A. Myers. User-interface tools: Introduction and survey. IEEE Soft-ware, 6(1):15—23, January 1989. [Nei84] J.M. Neighbors. The draco approach to constructing software reusable components. IEEE Transactions on Software Engineering, 10(5):564-574, September 1984. [Nye89] A. Nye. Xlib Programming Manual. O'Reilly and Associates, Sebastopol, CA, 1989. [OD83] D.R. Jr. Olsen and E.P. Dempsey. Syngraph: A graphical user interface generator. Computer Graphics, 17(3):43-50, 1983. [01s86] D.R. Jr. Olsen. Mike: The menu interaction kontrol environment. ACM Transactions on Graphics, 5(4):318-344, 1986. [PKP+82] T. Payton, S. Keller, J. Perkins, S. Rowland, and S. Mardinly. Ssags: A syntax and semantics analysis and generation system. In 6th Interna-tional Computer Software and Applications Conference (COMPSAC82), pages 397-408. IEEE Computer Society, IEEE Computer Society Press, Chicago, IL, November 1982. [PR088] Quintus PROWindows Manual. Quintus Computer Systems Inc., Moun-tain View, CA, 1988. [SBK86] M. Stefik, D.G. Bobrow, and K.M. Kahn. Integrating access-oriented programming into a multiparadigm environment. IEEE Software, 29(1):10-18, January 1986. [SG86] R.W. Scheifler and J. Gettys. The x window system. ACM Transactions on Graphics, 5(2):79-109, April 1986. [SHB88] J.L. Sibert, W.D. Hurley, and T.W. Bleser. Design and implementa-tion of an object-oriented user interface management system. In H.R. Hartson and D. Hix, editors, Advances in Human-Computer Interaction, volume 2. Ablex, Norwood, NJ, 1988. 88 [Str87] B. Stroustrup. The C++ Programming Language. Addison-Wesley, Reading, MA, 1987. [Tel90] M. Telles. Updating an older interface. In CHI '90 Conference, pages 243-247, Seattle, WA, April 1990. ACM, ACM Press, New York, NY. [VZM90] B. Vander Zanden and B.A. Myers. Automatic, look-and-feel indepen-dent dialog creation for graphical user interfaces. In CHI '90 Conference, pages 27-34, Seattle, WA, April 1990. ACM, ACM Press, New York, NY. [Was85] A.I. Wasserman. Extending transition diagrams for the specification of human-computer interaction. IEEE Transactions of Software Engineer-ing, 11(8), August 1985. [Wen88] E. Wenger. Glass-box technology: Merging learning and doing. Techni-cal Report 1, Institute for Research on Learning, Palo Alto CA, 1988. [Zav84] P. Zave. An operational versus the conventional approach to software development. Communications of the ACM, 27(2):104—118, February 1984. [ZS86] P. Zave and W. Schell. Salient features of an executable specification language and its environment. IEEE Transactions on Software Engi-neering, 12(2):312-325, February 1986. 89 A p p e n d i x A N A A G command line arguments NAAG may be invoked as follows (square brackets refer to optional arguments), naag [-crsP] [-Ipathname] [-Ldirectory] file -c Do not compile the generated C files. -r Do not automatically remove the generated C files after compilation. -s Silent mode. Turn off various messages. -P Only preprocess file, sending output to stdout. -Ipathname Add pathname to the list of include file directories searched by cpp. -Ldirectory Add directory to the library search path used by Id. file NAAG source file. 90 A p p e n d i x B N A A G language grammar This appendix describes the NAAG language syntax. The conventions outlined in Table B.l are used throughout the examples. The structure of the complete NAAG program is given in Figure B.l. The format of the class construct is given in Figure B.2. The structure of a menu is given in Figure B.3. Menus consist of operations and stubs. The grammar of these constructs is shown in Figures B.4 and B.5. String Meaning ID an identifier INT an integer value REAL a real value STR a string enclosed in quotation marks (") x x must appear exactly once [x] x is optional M* x may appear 0 or more times H + x must appear 1 or more times (x|y) x or y Table B.l: Coding conventions. 91 .application ID .label STR [.help STR] /* name of the executable */ /* the title of the application */ /* help information */ .classes [class construct]* /* class specification */ .menus [menu construct]* /* menu specification */ Figure B.l: A basic NAAG program. .define_class ID { .class (ID | .none) [.includes { [STR]+ }] [.modules { [STR]+ }] [.libraries { [STR]+ }] /* ID is the name of the C data structure */ /* ID refers to an existing class */ /* include file path name */ /* .o object module path names */ /* .a object library path names */ .display_routine ID .destroy_routine ID /* name of the display routine */ /* name of the destroy routine */ Figure B.2: A NAAG class. .menu { .class (ID | .none) .label STR [.help STR] /* ID refers to an existing class */ /* menu's label */ /* help information */ [menu item construct]+ /* a menu item specification */ Figure B.3: A NAAG menu. 92 .operation ID { .class (ID | .none) [.includes { [STR]+ }] [.modules { [STR]+ }] [.libraries { [STR]+ }] [.preconditions { [ID]-f }] .label STR [.help STR] [.argument { argument construct }]* [.result { .class ID }] /* /* /* /* /* /* /* /* ID is the name of a C function */ ID refers to an existing class */ include file path name */ .o object module path names */ .a object library path names */ precondition function names */ the name of the operation */ help information */ /* argument specification */ /* result specification */ /* ID refers to an existing class */ Figure B.4: A NAAG operation. .stub STR /* stub specification */ Figure B.5: A stub menu item. 93 A p p e n d i x C U B C Integrated V i s i o n System This appendix describes the UBC Integrated Vision System - a sophisticated ap-plication created with NAAG. Rather than describing all of the details, I chose to highlight the important points. C . l Utilities The set of utility functions can be divided into two groups: utilities common to all object classes, and utilities for a specific object class. Figure C.l shows the header file which contain the prototypes for the generic utilities. The ErrorO and MessageO routines are general purpose routines which can be programmed to create messages in a variety of contexts. For use with NAAG, for example, they simply invoke the NAAG message primitives to output messages via the UI. They could, however, be reprogrammed to produce messages in any other context. This allows us to reuse the underlying functions in situations other than as NAAG operations. The MemAllocO and MemFreeO routines and the related macros are used to provide a consistent memory allocation mechanism. This allows the developer to handle exceptions such as memory allocation errors in a standard manner. The Image object class is by far the most highly used one, so I will describe the utilities that are specific to it. Figure C.2 shows the header file which con-tain the prototypes for the Image object class utilities. The CreatelmageO and DestroylmageO do the expected thing. The DisplaylmageO routine invokes the NAAG n_draw_image() primitive to render the image data. The ImageArrayO rou-tine returns an array of character pointers which point to the beginning of image data rows. Thus, for example, the code segment: char **image_data = ImageArray(image) ; image_data[5] [20] = 128; MEM_FREE( image_data) ; 94 void Error( char * /* error message string */ ); void Message( char * /* message string */ ); char *MemAlloc( int /* number of bytes */ ); void MemFree( char * /* block of memory */ ); #define NEW(X) ((X *)MemA]]oc(sizeof(X))) #define MEM_FREE(P) (MemFree((char *)(P))) Figure C.l: util.h header file. sets the value of the (x,y) = (20,5) pixel to 128. A number of Image precondition functions have been implemented as well. Fig-ure C.3 shows the header file which contains the prototypes for the precondition functions. Although the type definition for the Image data structure allows a variable num-ber of bits per pixel, the majority of the image processing routines expect to oper-ate on images of depth 8. The precondition function ImageDepth8() can be used to guarantee that these operations can only be applied to 8 bit images. Similarly, the other preconditions can be used ensure that the original image contains either signed or unsigned image data. C.2 A sample image processing operation As an example of how to write an image processing operation, I describe the invert operation, invert creates a new image which is simply the original image with all of its pixel values reversed or flipped. Figure C.4 contains the C source code which implements the invert operation. This function can only be applied to 8 bit signed or unsigned images. Notice the use of the C L O N E - I M A G E () macro to create a new image of the same depth and dimensions as the original. Figure C.5 contains the NAAG operation description for the invert operation. 95 /* Physical header size in file */ /* Number of rows in image */ /* Number of columns in image */ /* Bits per pixel */ /* Signed or unsigned image */ /* Number of bytes per image row */ /* Header */ /* A pointer to the image data */ #include <ubcvsl/util.h> #define IMHDRSZE 1024 typedef struct { int rows; int cols; int depth; int sign; int row_bytes; char header [IMHDRSZE]; unsigned char *data; } Image; Image *CreateImage( int, /* width */ int, /* height */ int, /* depth */ int /* signed */ ); int DestroyImage(Image *); int Displaylmage(lmage *); unsigned char ** ImageArray(Image *); /* obtain an array of pointers to image rows */ #define CLONEJMAGE(I) (CreateImage((I)->cols,(I)->rows,(I)->depth,(I)->sign)) Figure C.2: image.h header file. #include <ubcvsl/image/image.h> int ImageDepth8(Image *); int ImageSigned(Image *); int ImageUnsigned(Image *); Figure C.3: Precondition functions for image object class. 96 #include <ubcvsl/image/image.h> Image *Invert(Image *in) { int x, y; Image *out; unsigned char *inp, *outp; /* Create a new image. */ if ((out = CLONE JMAGE(in)) == 0) return(O); /* Invert. */ inp = in->data; outp = out->data; for (y = 0; y < in->rows; y++) for (x = 0; x < in->cols; x++) *outp++ = 255 - *inp++; return(out); } Figure C.4: C source code for the invert operation. Filename Description <ubcvsl/edges/edges.cl> <ub cvsl/his togram/his togram. cl> < ub cvsl / image/image. cl> Edges Histogram Image Table C.l: Existing classes. Notice the preconditions construct which specifies that the original image must contain 8 bit data. C .3 Existing components Table C.l shows the currently implemented object classes used by the UBC Inte-grated Vision System, while Table C.2 shows the existing operations. C .4 N A A G listing of main program The following is a complete listing of the NAAG source code of the main program for the UBC Integrated Vision System. Class and operation specifications are not 9 7 Filename Description < ub cvsl/ edges / readedges. op > < ub cvsl/edges/writeedges .op > <ub cvsl/histogram/ readhistogram.op > <ubcvsl/histogram/writehistograrn.op> <ubcvsl/image/combine.op> < ub cvsl/image / contrast .op > <ub cvsl/image/ convolve.op> <ubcvsl/image/grabimage.op> < ub cvsl/ image/ his t ogr am. op > <ub cvsl/image/imageinfo.op > < ub cvsl/image/inspect .op > < ub cvsl/ image/ invert .op > < ub cvsl/image/munch.op > < ub cvsl/ image/ orient. op > <ubcvsl/image/outline.op> < ub cvsl/ image/ overlay, op > <ubcvsl/image/readimage.op> < ub cvsl/ image/ res ample. op > <ubcvsl/image/ resamplenn.op> <ub cvsl/image/ showsign.op> <ubcvsl/image/slice.op> < ub cvsl/image/ subimage.op > <ubcvsl/image/transpose.op> < ub cvsl/ image/ writ eimage .op > < ub cvsl/ image/ warp. op > < ub cvsl/ image/ xflip. op > <ubcvsl/image/yflip.op> < ub cvsl/ image/ zerocross.op > < ub cvsl/image/ zoom.op > Read edge data from a file. Write edge data to a file. Read histogram data from a file. Write histogram data to a file. Combine two images. Change contrast and brightness. Convolve image with a mask. Grab image with a camera. Obtain intensity histogram from image data. Calculate simple image data statistics. Inspect a pixel's value. Invert image data. Reduce image by averaging. Rotate image by a multiple of 90 degrees. Compute contours at a given threshold. Overlay one image on top of another. Read IFF images from a file. Scale image. Scale image (nearest-neighbour interpolation). Mark positive/negative pixels in signed image. Obtain a density slice from image data. Extract a subimage. Transpose image. Write IFF images to a file. Warp image using exponential function. Perform a left-right flip of image data. Perform a top-bottom flip of image data. Mark zero crossings and fink edges. Enlarge image by pixel duplication. Table C.2: Existing operations. 98 .operation Invert { .class Image .libraries { "-limglib" } .preconditions { ImageDepth8 } .label "invert" .help "This routine inverts the gray levels of the source image" .argument { .object } .result { .class Image } } Figure C.5: NAAG source code for the invert operation, shown - only the structure of the application. 99 /* file: ubcvs.n */ /* * Title: Application description lor a sample vision application. * Author: Emanuel G. Noik * * Synopsis: This is a sample NAAG application. It's purpose is to: * * a) Show how NAAG can be used, to create interactive applications. * b) Show how a vision system can be designed to integrate a * variety of image processing operations as well as operations * on related data types such as histograms using very-high-* level object-oriented techniques. */ .application ubcvs .label "UBC Integrated Vision System" .help "This is a sample image processing application" .classes # include <ubcvsl/histogram/histogram.cl> # include <ubcvsl/image/image.cl> # include <ubcvsl/edges/edges.cl> * Main input menu for various objects. */ .menu { .class .none .label "File" .help "Various file operations" # include <ubcvsl/image/readimage.op> # include <ubcvsl/histogram/readhistogram.op> # include <ubcvsl/edges/readedges,op> .stub "open network" .stub "open graph" .menu { .class .none .label "Camera" include <ubcvsl/image/grabimage.op> } .menu { .class Edges .label "File" 100 .help "This menu contains various f i l e operations on edges" include <ubcvsl/edges/writeedges.op> > .menu { .class Histogram .label "File" .help "This menu contains various f i l e operations on histograms" include <ubcvsl/histogram/writehistogram.op> } .menu { .class Image .label "File" .help "This menu contains various f i l e operations on images" include <ubcvsl/image/writeimage.op> } / * * Main menu for image processing operations. */ .menu { .class Image .label "Image operations" •help "This menu assembles a number of image processing operations" /* * Geometric transformation operations. */ .menu { .class Image .label "Transformations" .help "Perform geometric transformations on image data" .menu { .class Image .label "Flip" .help "Flip images" include <ubcvsl/image/transpose.op> include <ubcvsl/image/xflip.op> include <ubcvsl/image/yflip.op> > .menu { .class Image .label "Rotate" .help "Rotate images" 101 # include <ubcvsl/iraage/orient.op> .stub "general rotate" > .menu { .class Image .label "Rescale" .help "Rescale images" # include <ubcvsl/image/zoom.op> # include <ubcvsl/image/munch.op> # include <ubcvsl/image/resample.op> # include <ubcvsl/image/resamplenn.op> # include <ubcvsl/image/rescale75.op> } } .menu { .class Image .label "Statistics" .help "Obtain statistical information" # include <ubcvsl/image/histogram.op> # include <ubcvsl/image/imageinfo.op> # include <ubcvsl/image/inspect.op> } .menu { .class Image .label "Combination and windowing" .help "Combine and extract images" # include <ubcvsl/image/combine.op> # include <ubcvsl/image/overlay.op> # include <ubcvsl/image/subimage.op> } .menu { .class Image .label "Low-level" .help "Low-level image processing and enhancement" # include <ubcvsl/image/contrast.op> # include <ubcvsl/image/invert.op> # include <ubcvsl/image/outline.op> # include <ubcvsl/image/slice.op> # include <ubcvsl/image/warp.op> } 102 .menu { .class Image .label "Edge detection" .help "Convolution and edge detection" include Cubcvsl/image/convolve.op> include <ubcvsl/image/showsign.op> include <ubcvsl/image/zerocross.op> } > end ol f i l e : ubcvs.n 103 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051979/manifest

Comment

Related Items