 |
David Fox
NYU Media Research Lab
719 Broadway, New York, NY 10003
dsf@acm.org
This work began with the desire to make modular applications using the Magic Lens metaphor, and to be able to create lenses that would compose in a natural way with a minimum of effort. We had success in certain domains where the interaction of different lenses is straightforward, such as lenses that implement database selections that can be composed using set theory, or the filtering of an image to produce another image. However, other types of applications presented difficulties. In particular, it was not clear how interactive applications should be filtered.
We made some unsuccessful attempts to solve this problem using conventional object oriented programming methods. We noticed that while these methods allow re-use of the structure of an object and the code associated with an object, they do not support building additional structure onto an existing object. For this, a less conventional type of inheritance known as delegation was found to solve the problem.
Once we adopted delegation style inheritance, the solution to the problem of generalized composable Magic Lenses emerged naturally. This result suggests that programming structures can be an important element in the design of a graphical user interface system. It also suggests that new styles of interaction can require new types of programming language support. This paper presents a technique for using delegation style inheritance to implement Magic Lenses which compose in a natural way, and which are simple to implement and amenable to reuse.
The notion of the Magic Lens was introduced in Toolglass and Magic Lenses by Eric Bier et. al. [6], and a similar idea was presented as the Portal Filter in Perlin and Fox's paper from the same conference [21]. A Magic Lens is a transparent or semi-transparent user interface element which can be placed over objects to change their appearance and/or their interactive behavior.
The promise of Magic Lenses has not been fully realized due to the lack of a suitable theoretical basis for characterizing the types of transformations these lenses perform, especially one which allows the composition of two or more lenses placed on top of one another to perform more complex operations.
Since the Bier and Perlin papers were published in 1993, a number papers have built on that work, including subsequent papers from Bier, Stone, and the Xerox group [5] [22] and Bederson and Hollan's Pad++ papers [2] [3]. Other groups have extended the idea in various directions, including the three dimensional filters in [24] by Viega et. al. and specific applications, such as the paper on debugging filters by Scott Hudson et. al. [15].
Three techniques for implementing filtering are presented in [5] . The first, Recursive Ambush, obtains from each object a procedural description of itself (for example, a PostScript program) and interprets that description using modified primitives which results in a modified appearance. For example, the draw-line primitive might be modified to always draw red lines. The authors mention three disadvantages of this approach: the need to re-implement numerous graphics primitives in order to implement a given filter is onerous; the results of composition can be mystifying; and the performance of composed filters deteriorates rapidly because the entire computation must be re-done for each pair of filters that see one other. Furthermore, because filters are placed by hand, each one usually gets at least a peek at each of the filters below it, causing a doubling of computation time per added filter.
The second technique is called Model-In Model-Out (MIMO). Here a modified copy of the original object, or a new object of a different type is created. This new object is what the user sees and interacts with through the filter. This approach trades storage space for a substantial performance advantage. It also frees the filter from the domain of the graphics language - filters can now be designed to operate in the application domain. Other advantages mentioned include performance and relative ease of authoring and debugging. Disadvantages include the high storage requirements of making complete copies of all the filtered objects, and problems associated with propagating changes made to the model back to the original object.
The third technique presented in [5] is called Reparameterize and Clip, where the filter doesn't perform the drawing itself, but instead alters the parameters and clip area of another renderer and thus directs its output. The performance of this approach is similar to the MIMO approach.
Enhanced Dynamic Queries via Movable Filters by Fishkin and Stone [12] presents a mechanism for composing filters, but because these filters are tools for making database queries the results are less general than what we seek. The lenses are simply selecting or omitting objects, not altering them, so composition is done according to boolean set operations.
Two methods for implementing filters are mentioned by Bederson and Meyer in [4]: layers and procedural objects. Layers simply reveal a different set of objects when the filter is present. The procedural object approach lets a single object implement two rendering methods, and the renderer is queried about which one is to be invoked. These techniques have the benefit of speed, but they don't provide a real framework for the composition of lenses.
It is possible to devise a mechanism which has all the advantages and none of the drawbacks of the various approaches to filtering presented in the previous section. To allow composition without an undue performance penalty, we need to maintain information about the state of the objects being filtered. The mechanism should not be limited to the domain of graphics primitives, instead it should operate in the domain of the objects which are being modelled. We want to avoid the high storage requirements of the MIMO approach. We want the filtered object to have extended capabilities over the original, but we also want to perform our operations on the original object, not a copy. And finally, we want composed filters to behave in a natural way, without the need to consider the implications of every possible filter combination.
The solution to these problems proposed here is a limited form of the object inheritance mechanism called delegation. Delegation means that instead of an object owning newly allocated storage for each slot of its super class, it contains a reference to a pre-existing instance. This pre-existing instance is known as the delegate, and in this relationship the new object is known as the principal - the principal instance delegates certain requests to the delegate super class instance. This terminology captures the working relationship between the objects well, but it does not express the ephemeral quality of the principal objects in this paper - principal instances are created as the lens is passed over an object which it considers a suitable delegate instance.
Operations on the slots inherited from the delegate super class are transparently converted to operations on the delegate instance. Cardelli and Wegner discuss type systems that allow delegation in their 1985 paper [9], and the terminological distinction between delegation and inheritance was finally established in a panel at OOPSLA 1987 known as the ``Treaty of Orlando'' [18]. This technique is not present in today's most popular programming languages but has been used in some research systems such as Self (Ungar and Smith [23]). It also turns out to be a simple matter to implement a limited form of delegation sufficient for our purposes within CLOS [7] style object oriented programming systems. It should also be noted that the ``Decorator'' design pattern described on page 175 of the book by Erich Gamma et. al. [14] uses delegation techniques, though without formal language support. The technique can also be referred to as a ``wrapper pattern''.
This object filtering technique described below has been implemented in the author's Tabula Rasa (or simply Tab) zoomable user interface system. In the object system Taboo which is used to implement Tab, normal classes are created using a macro named define-class. This macro is passed a list of slots and a list of super classes, and the resulting class has an inheritance relationship with each super class. The limited form of delegation required here is implemented as a macro named define-principal which is used in exactly the same way as define-class, except for the additional delegate-class argument. We will refer to the class that results from a call to define-principal as a principal class, and an instance of a principal class is a principal instance or simply principal. The principal class has zero or more super classes, plus one delegate class. This delegate class is also a super class of the principal class. An instance of a delegate class is a delegate instance or delegate.
When a principal instance is created, the slots that it inherits from
the delegate class are not newly allocated, but instead refer to the
slots of an existing delegate instance as shown in figure
1. When the delegate's slot values change, so do the
values of those slots in the principal, and vice versa - they are
actually the same slot. This behavior is implemented using a
``virtual slot'' mechanism which is available in the object system
whereby references to the slot are transparently converted into calls
to getter and setter functions.
|
To implement Magic Lenses using delegation we assign to the lens a delegate class and a principal class. When the lens is placed over an instance of its delegate class, it generates a corresponding instance of its principal class. A new principal is created for each delegate that becomes visible through the lens. These principal instances, with their extended functionality, are what the user sees and interacts with when working through the lens.
Figure 2 shows Tab propagating an event,
either an input event or a drawing event. The system saves each lens
the event passes through into a list. After the event hits an object
the resulting list of lenses is searched to find a lens that considers
the object to be a delegate - that is, it looks for a lens whose
delegate class is a super class of the object's class. If such a lens
is found the system requests from it the principal instance associated
with the object. The lens looks for the principal in a dictionary
keyed on the delegates and returns it, creating it if necessary. If
no lens with a suitable delegate class can be found the event is sent
directly to the object - no filtering will be performed.
 |
As an example, consider a class text, representing a text buffer
with no interactive features, but with primitive methods to modify and
display the buffer's content. We can derive from the text class
a principal class text-being-edited which adds slots for the row
and column position of the cursor and overrides the delegate's
draw method so the cursor is drawn after the delegate draws the text.
In figure 2 the principal object is shown with a cursor
box around the ``s'' in ``sentence'' to indicate this. The principal
class would also add event handling methods which would respond to
keyboard input, translating them into cursor motion and calls to the
text modification primitives of the underlying text class.
Figure 3 shows the resulting screen output.
 |
Note that the class is called text-being-edited, rather than text-editor. It is the lens that is the text-editor, and the text-being-edited objects are created by the lens. If the lens sits over several text objects, it will create one text-being-edited object for each.
Lenses affect the appearance of objects by creating principals which override the delegate's draw method. For example, the draw method of the text object might simply draw black text on a white background. The draw method of the text-being-edited object first fills the background with light gray and cursor area with orange. It then invokes a text method which draws the text but doesn't fill in the background. In this way not only is the cursor added but a distinctive background color indicates that the object is being edited. One might then put a spell checker lens on top of the text editor lens to highlight misspelled words. The spell checker principal would override the draw method and directly invoke the primitive drawing methods of the text class.
Now let us consider how these lenses will compose. We would like a lens which is placed on top of the text-editor lens to use the text-being-edited objects as delegates for its own principal type (if it knows how.) Lenses you would place over a text editor lens might implement various input methods for international character sets, or otherwise augment the text editor.
 |
There is one final bit of complexity to be noted here - how principals are created. If an event arrives before either of the principal objects in figure 4 have been created, the lower principal p1 must be created before p2, so that p2 can use p1 as its delegate. This is accomplished by a recursive call to the principal creation procedure.
Now suppose we place one text-editor lens on top of another. The topmost lens will see the principals of class text-being-edited, but it will treat them as text principals and generate its own text-being-edited principals. Each lens will manage its own cursor for each text object, and events sent to each principal will perform modifications on the underlying text object. The two editors can co-exist and modify the text as long as the methods in the underlying text object are called atomically.
It should also be noted that composed filters are able to build on the results of other filters, but also co-exist peacefully if they lack knowledge of one another. This technique has all the advantages of the MIMO (Model In - Model Out) approach without the drawbacks of wasted storage and the difficulties of propagating changes back to the original object. The delegation technique also subsumes the Recursive Ambush technique, which is equivalent to overriding the render method in the principal class.
Tab is implemented primarily in the Scheme programming language, and
uses an object system named Taboo, which was derived by
the author from Erick Gallesio's
STklos.[13]![[*]](foot_motif.gif)
The Taboo object
system differs from STklos primarily in the fact that it is not tied
to any particular implementation of Scheme, and in particular can be
used with some of the non-proprietary Scheme compilers which are now
available.[1][11]
First, the slot list is constructed and the class is defined. Before the delegate class is added to the list of super classes, an initialize method is created so that initialization will not re-initialize the pre-existing delegate instance - it must be created using the original class precedence list. Next, the delegate class is added to the class object's list of direct super classes and the class precedence list (CPL) is re-computed and stored in the CPL slot. Now the new class is a subclass of the delegate class with respect to method dispatch, but it does not change the way instances are allocated.
One deficiency of the implementation shown is that any attempt to replace the initialize method and call next-method will produce a method that does re-initialize the delegate instance, with unfortunate results. One work-around is to derive another class from the principal class and override its initialize method. It should also be possible to perform this second class creation transparently.
In abstract terms, the problem is that the principal class of the top lens is not a subclass of the principal class of the lens below it. Instead, it is a subclass of the delegates at the bottom level. We need the delegate class of the top lens to be a subclass of the principal class of the lens below it, so it can then further extend the functionality of the principals the lower lens produces.
This problem can be solved by using the ability of a CLOS-style object systems to create new classes at run time. Instead of creating a single principal class for a lens, we create a new one whenever we see an object which is of an unfamiliar subclass of the delegate class. These (delegate-class, principal-class) pairs can be stored in a hash table associated with the class of the lens. Now a new class will be created to represent a text-being-edited object which has a spell checker lens over it, a ``text being edited being spell checked'' class. The render method of this new class will invoke the text-being-edited render method before making its annotations.
The dynamic creation of principal classes allows lenses which were not specifically designed to work with each other to cooperatively produce combined views. The performance considerations of this approach are discussed in the Performance section below.
As presented above, lens composition is essentially object inheritance made visible, and interesting examples can be constructed by applying the same techniques as those used in object oriented design. In the Tab system, a file object can be created to represent a file, and this object simply displays a rectangular background and the file's name. It also provides versions of the standard input/output functions to access the file's content.
Various lenses can then be applied to a file. For example, an image viewing lens would examine the file's content, decide whether it was an image file and of what format, and then construct and display a visual representation of that image. Besides providing the image rendering method, the principal class for this lens would also provide methods to access the pixels and dimensions of the image.
Lenses could then be placed on top of this basic image display lens to allow interactive manipulation of the image. Note that these lenses need have no knowledge of the format of the image file - the underlying image display lens hides the details of the JPEG or TIFF format and provides a uniform set of methods for accessing the image data. Some image formats carry a text annotation field along with the image information. Replacing the image lens with a text lens would display the file as text, and provide methods for text access and manipulation. An editing lens could then be applied to alter the text. Thus, lens composition can be used as a type of layered design discipline.
Good performance is crucial to the practicality of this system. There are several areas of concern which can be identified and addressed:
The cost of using the virtual slot mechanism is more specific to this system. To access such a slot requires evaluating a Scheme function. The cost of this will vary from implementation to implementation, but theoretically it should compile to an array access and a slot reference. Finally, there is also a cost associated with searching the lens stack for principals, which involves a dictionary search of each lens based on the delegate. While this is a more complex operation than those above, it is only done once per event processed or per redraw, and because there is no practical use for huge stacks of lenses, it may not have a great impact. However, the best way to assess these problems is to gain more experience building and using this type of Magic Lens.
Dynamic creation of principal classes is even less frequent, and thus less likely to degrade performance. It is only done when a the standard search for a principal class fails, which is only once per new delegate subclass encountered. The final point, using instances of such classes, is more of a concern, and we envision several approaches to solving this problem. These include (1) identifying and pre-compiling common combinations, (2) ``just in time'' compilation, and (3) exploiting the similarities of the new class with the classes from which it is generated. Because all that is new about the dynamically generated class is the class precedence list, only the method dispatch and the implementation of next-method need to be different.
The most important goal of our future research is to gain experience implementing different types of delegation based Magic Lenses. Issues of performance and portability will also be addressed. Several improvements to the object system need to be implemented, including a perfect hashing technique for slot lookup and caching for method dispatch. The performance of various Scheme implementations should be evaluated; while the Scheme->C compiler [1] currently used is much faster than a Scheme interpreter, there are newer Scheme compilers which incorporate features which might benefit Tab's performance.
Portability is also important, so that users of non-Unix platforms (notably Microsoft Windows 95 and Windows NT) can have convenient access to this software. The Scheme->C compiler does run on the Windows platforms, but the underlying graphics libraries are based on the X Windows library. Work is underway to devise a compatibility library for Tab which is similar to that used in the Tk system.[20]
There is a well worn saying that if the only tool you have is a hammer, every problem will start to look like a nail. Once the delegation mechanism is added to our toolbox, the problem of implementing Magic Lenses that compose naturally becomes fairly simple. Without it, the problem remains quite difficult. This indicates how much programming language constructs can influence the programs written.
The lens metaphor presented here provides an application-level analogue to the code-reuse benefits conferred by object-oriented programming techniques, and encourages the creation of software systems with a smaller granularity. By providing a way for applications to cooperate, and a visual metaphor to help users intuit how to make them do so, the tendency towards monolithic applications we see in today's software market can be reduced. However, the technique is dependent on programming language constructs which are not present in the most common languages of the day.
In [10] Brooks Conner describes in general terms how delegation and multi-methods can be used to produce simpler and more general implementations of interactive computer graphics systems, and presents specific cases of how the lack of these features leads to unnecessary complexity in several real-world cases. In addition to delegation and multi-methods, we believe that multiple inheritance confers similar benefits, such as allowing the easy mixing and matching of the various features of a lens. The popularity of Java's ``Interface'' mechanism, which can be seen as a limited form of multiple inheritance where the classes are not allowed to have slots, supports our claim of this feature's importance.
There are many factors that affect one's choice of language for implementing a system, including the stability of the language's definition and the quality and quantity of its implementations. The developer's personal familiarity with the language can also be important. If the language will also be used as the system's extension language, the acceptability of its syntax to end users also becomes a factor. Often, the actual features the language provides comes relatively low on an implementor's list of considerations. This paper has presented a technique which solves some of the problems which have plagued the implementors of Magic Lenses and work-through interfaces. Although the solution uses language features which are not present in the most popular programming languages of today, they are present in languages for which implementations are available on nearly every computing platform.[8] Perhaps in the future these language features will begin to rise towards the top of the list of implementor's considerations.
My appreciation to Ken Perlin, Cliff Beshers, Jon Meyer, and Matthew Fuchs, who helped in many ways.
