当前位置:首页 >> >> To Appear in UIST'94 Interactive Generation of Graphical User Interfaces by Multiple Visual

To Appear in UIST'94 Interactive Generation of Graphical User Interfaces by Multiple Visual


Interactive Generation of Graphical User Interfaces by Multiple Visual Examples
Ken Miyashita, Satoshi Matsuoka, Shin Takahashi, Akinori Yonezawa

To Appear in UIST'94

The Dept. of Information Science, The Faculty of Science, The University of Tokyo 7-3-1 Hongo, Bunkyo-ku, Tokyo 113, Japan Tel:+81-3-5800-6913 E-mail: fmiyasita, matsu, takahasi, yonezawag@is.s.u-tokyo.ac.jp
ABSTRACT

The construction of application-speci c Graphical User Interfaces (GUI) still needs considerable programming partly because the mapping between application data and its visual representation is complicated. This study proposes a system which generates GUIs by generalizing multiple sets of application data and its visualization examples. The most notable characteristic of the system is that programmers can interactively modify the mapping by \correcting" the system-generated visualization examples that represent the system's current notion of programmer's intentions. Con icting mappings are automatically resolved via the use of constraint hierarchies. Graphical User Interfaces, Programming by Example, Visual Parsing, Visualization, Constraint Hierarchies.
KEYWORDS:

modifying the rule interactively, even if the rule does not re ect the programmer's intention correctly. The only way to revise the rule is to modify it textually, which is against our original policy, i.e., we do not want to access graphical images via textual programming. A natural way to solve the problem is to enhance the system to accept multiple examples. The system should be able to extract the programmer's intention about the revision of the rules from additional examples step by step. Generally speaking, this problem, \How to modify programs generated by a PBE system?", can be decomposed into the following three sub-problems. Most existing PBE systems represent generated programs in system-speci c textual forms, which makes it dicult for programmers to understand the programs afterwards. For example, SmallStar[4] represents generated programs in a script form. Problem in PBE (2) It is impossible to perfectly infer the human intention from examples. Thus, PBE systems should o er programmers some means of revising the generated programs interactively. As described above, many systems represent programs textually, and as a result, force programmers edit the textual representation of the programs. Examples are SmallStar[4] and AIDE[11]. Problem in PBE (3) Most importantly, programmers often have diculties in deciding what examples they should provide to PBE systems . For example, in DEMO II[2], programmers themselves are responsible for deciding what sequence of examples to give, which is often more dicult than it seems mainly because: (1) it is dicult for programmers to assure themselves that \completeness" has been achieved, and (2) programmers sometimes have to produce non-intuitive examples for the system to infer their intentions correctly. In both cases, the detailed knowledge of the inner workings of the underlying inference engine is required.
Problem in PBE (1)

Although Graphical User Interfaces (GUI) have become prevalent, the complexity and development cost of application-speci c GUIs remain considerably high. To support such GUI programming, our previous work TRIP2[14] proposed the bi-directional translation model, which gave programmers a general framework to realize application-speci c GUIs. In this model, mapping rules describe how to translate between application data and its corresponding visual representation. Furthermore its descendant, TRIP3[9], employed \Programming by Example (PBE) " methodology and generated mapping rules by generalizing the pair consisting of an application data example and its corresponding picture. In testing the capabilities of the TRIP3 system, however, we have encountered the following fundamental problem: Once the system generates a mapping rule from a pair of examples, a programmer has no means of

1

INTRODUCTION

To overcome these diculties, this study presents an enhanced PBE methodology called \Programming by Interactive Correction of Examples". Our new mapping rule generation process proceeds in the following way:

When the system exhibits the generated mapping rules to programmers, it shows example visualization rather than representing the rules textually.
The Solution to Problem (1) The Solution to Problem (2) The system lets programmers correct the visualization examples, and then revises the mapping rules, re ecting the programmers' interactive correction on the pictures. This can be regarded as the indirect revisions of programs via corrections of examples.

The system generates a series of examples of application data and its corresponding visual representation autonomously, and asks programmers to correct the pictures. That is to say, the system takes the initiative in producing appropriate example pictures. Therefore, the programmers do not have to worry about what examples are suitable.
The Solution to Problem (3)

examples correspond to each other. In other words, it is dicult to determine which part of examples were altered within a sequence of examples.  When a programmer gives a series of examples to the engine, the ideal examples would be such that the engine could easily extract their common characteristics. But this is usually dicult unless the programmer has a detailed knowledge how the engine works, which is an undesirable requirement.  Although many existing PBE systems present generated programs textually, textual representation is dicult to understand intuitively for human programmers.
2.1 Programming by Interactive Correction of Examples

To verify the e ectiveness of this methodology, we also implemented a prototype system IMAGE (Interactive MApping rule GEnerator). Note that IMAGE has been built from scratch; the system is not an evolution from TRIP3. We also note that our new visual parsing and visualization engines make extensive use of the constraint hierarchy mechanism[3]. Employing the constraint hierarchy mechanism relieves the PBE-based rule generator of considering over-constrained or under-constrained situations which could occur when the generated mapping rules are applied to both visual parsing and visualization. As an underlying constraint solver, we employ the constraint solver presented in [5], which allows integration of di erent kinds of constraints in the hierarchy. The rest of this paper is organized as follows: Section 2 proposes our enhancement of PBE and compares our new methodology to the related work in the PBE eld. The section also gives an example dialogue of rule generation with the new PBE methodology. Section 3 explains the bi-directional translation model our interactive rule generator is based on, and also introduces the constraint hierarchy mechanism to our model. Section 4 describes the prototype system IMAGE, and explains the details of the interactive rule generator. Section 5 brie y describes the essential ideas of our visual parsing algorithm. Section 6 gives our perspective of this research. We conclude in Section 7.
2 INTERACTIVE RULE GENERATION WITH MULTIPLE EXAMPLES

To overcome these problems, we propose a new methodology called \Programming by Interactive Correction of Examples ", and apply it to the generation of mapping rules, which specify the mapping between application data and its corresponding visual representation on GUIs. Once the mapping rules are generated, end-users can enjoy the application-speci c GUIs to manipulate application data. The rule generation process based on this methodology has the following features:  Once the initial examples are provided by the programmer, the system itself constructs a series of examples of both application data and its corresponding visual representation, while a programmer corrects such example pictures to inform the system of his intention.  Because the system itself constructs example pairs, it knows how to re ect the correction of pictures performed by the programmer onto the revision of mapping rules.  The programmer no longer has to worry about what sequence of examples would be suitable for the inference engine. The system takes the initiative in presenting examples rather than the human programmer.  When the system exhibits the extracted mapping rule, it presents visual examples of bi-directional translation controlled by the rule rather than presenting the rule textually. Not only that pictures are direct and intuitive means for the programmer to obtain the resulting mapping, but he can also directly convey his ideas in the correction of the examples via direct manipulation. Although there have been several attempts to allow programmers to correct programs by giving additional examples, these systems require the programmers to decide what examples are appropriate, and as a result, they are more cumbersome and potentially error-prone compared to our system: DEMO II[2] is a system which generates GUIs by asking programmers to give multiple visual examples. However, DEMO II makes the programmers decide what sequence of examples to give. Kurlander's work[7] proposes a method of specifying geometrical constraints implicitly, through multiple snapshots. In this system, programmers themselves have to decide what sequence of snapshots to show as well. Tinker[8] is a PBE system aiming to help novice pro-

There have been many attempts to generate programs or speci cations by generalizing a series of examples. Most such research employed a methodology in which a series of examples were given to an inference engine at once, and the engine compares these examples to extract common characteristics among them. However, such strategy has the following drawbacks:  Without additional information, it is sometimes dif cult for an inference engine to nd out how multiple

This means that a man has a name, and an organization grammers generate programs. Its characteristics is that consists of a boss and an arbitrary number of sta mempartially speci ed programs could be executed. The bers. Due to space limitations, rule generation dialogue system asks the programmer what to do next when it for the man type is omitted here, and we now follow the reaches the end of a branch. In this way, the programinteraction to generate the rule for the organization mers can easily understand what examples are necestype. sary, i.e., they are supposed to show what actions to take next at branching points. The elimination of vagueness in what examples are appropriate at certain moments is 2. The system generates the simplest application data example, i.e., where the number of elements in staff is so important in PBE systems that it is the main focus two, and displays it in the application data window as in our system as well as Tinker. The advantage over follows: Tinker is that our system incorporates several heuristics in the rule generator and automatically generates programs inferring the programmers' intentions on the application-data(organization, #10){ boss = #1; corrections, while Tinker employs no inference engine staff = [#2, #3]; and merely generates pure traces of what the program} mers do in the demonstration mode.
2.2 Interactive Rule Generation Process
Drawing Editor

3. The system initializes the drawing editor, displaying three man objects (gray rectangles) assuming that the visual representation should include them. (Figure 2 (1)) 4. The programmer draws the initial visual representation corresponding to the application data example (Figure 2 (2)), and the system generates the initial mapping rule for the organization type. 5. The system then presents another application data example which is more complicated than the rst one; here the number of elements in staff is set to be three. The system simultaneously visualizes the data example, applying the generated rule. (Figure 2 (3)) 6. Assume that this visualized picture in Figure 2 (3) is different from what the programmer had expected in the following way: (1) The boss and the entire sta should be aligned horizontally at their top edges instead of being aligned this way; (2) there must be a line connecting the boss and the third sta member. The programmer corrects the picture according to his intention (Figure 2 (4)). The system then infers the programmer's intention from the correction of the picture and modi es the mapping rule accordingly.

Data Type Definitions

Application Data Examples

Figure 1: Snapshot of the IMAGE System

In this section, we illustrate the interaction between a programmer and our prototype system IMAGE with the interactive rule generation process for an organization diagram. Figure 1 shows a snapshot of IMAGE. In this gure, the upper left window is the drawing editor, in 7. Again, the system presents a pair of examples; the apwhich a programmer draws example pictures; the lower plication data and its corresponding picture generated left window shows the application data type de nitions; with the modi ed mapping rule (Figure 2 (5)). This in the lower right window, the system shows a series of time, the programmer is satis ed with the visualization application data examples. The interaction proceeds as and noti es the system of the completion of the rule follows: generation process. 1. The programmer inputs the type de nitions in the application data type de nition window as follows:
data-type(man){ name : word; } data-type(organization){ boss : man; staff : list-of man; }

Finally, Figure 3 shows the snapshot of the generated organization diagram editor. An end-user inputs application data about an organization in the left \Application Data" window, while the right \Drawer" window shows the visualized organization diagram. If the enduser modi es the picture and invokes \Visual Parsing" in the menu, the application data is updated to re ect this modi cation. Figure 4 and Figure 5 present a tree diagram editor and a set diagram editor generated with IMAGE.

#2 #1 #2 #3 #3 #4 #1 #2 #1 #3

(1)

(2)

(3)

#1 #1 #2

#2 #3

Figure 5: Set Diagram Snapshot

#3 #4 #4 #5

(4)

(5)

Figure 2: Snapshots of Drawing Editor in Rule Generation for \organization"

structure of visual representation in terms of geometrical constraints among graphical elements in a picture. Mapping rules represent how to translate between application data and its corresponding visual representation.
Application Data
boss Alex Brad Chas staff [Brad,Chas,Dave] [Eliz] [Fred]

Constraints Visualization
(offset Alex Brad 20 0) (offset Brad Chas 0 10) ......

Visual Parsing Control
Alex

Constraint Satisfaction Visual Representation
Brad Chas Dave Eliz Fred

Mapping Rule

Figure 3: Organization Diagram Snapshot
3 THE BI-DIRECTIONAL TRANSLATION MODEL

(define-mapping organization (level0 (offset boss staff) ..... )

As a prerequisite, we rst overview our bi-directional translation initially presented in [14] (the speci cation as well as the inner working of the implementation has been considerably re ned from [9] and [14]).

Figure 6: Bi-Directional Translation Model

Figure 6 illustrates our bi-directional translation model with an example of organization diagram data. Application data space consists of a series of structured data. Each data has its type de nition, which is similar to structured data-type de nitions in the C language. Visual representation is a picture which is constructed from a set of graphical elements, each of which corresponds to application data. Constraints represent the

Each application data is an instance of a type de nition, which consists of an arbitrary number of typed elds. Each eld has one of the following types: (1) integer, (2) word, (3) user-de ned type, (4) list type, whose elements are of a user-de ned type, or (5) combination of any number of above-mentioned types, where the value of the eld should be of one of these enumerated types. Examples are the two application data types man and organization introduced in Section 2.2 .
3.2

3.1

Application Data

The visual representation consists of a series of graphical objects and geometrical constraints among graphical reference points of these objects, such as the upper left corner of an object. The graphical objects supported in our model are: (a) Rectangles, ellipses, and words, (b) lines, (c) composites, which are aggregates of graphical objects. The reference points of respective objects are illustrated in Figure 7. (Composites are de ned in terms of the bounding box of their constituents.) For geometrical constraints, our current implementation supports (x-offset obj1 ref1 obj2 ref2 dx), which signi es that the horizontal gap between the reference point ref1 of object obj1 and the reference point ref2 of object obj2 is dx. We also support y-offset and offset which

Visual Representation

Figure 4: Tree Diagram Snapshot

is a shorthand form of the combination of x-offset and y-offset.
lt lc lb ct cc cb (a) rt rc rb sp (b) lt lc lb ct cc cb (c) rt rc rb

ep

Figure 7: Reference Points
3.3

A mapping rule expresses the correspondence between an application data type de nition and a series of constraint templates. When the system visualizes an instance of a data type de nition, all the constraint templates in the mapping rule are instantiated, and the constraint solver determines the visual representation by solving the constraints. On the other hand, the visual parsing proceeds by checking whether all constraint templates speci ed in the mapping rule can be satis ed in a given picture. If they are all satis ed, the corresponding data type de nition is instantiated. The most notable characteristic of the mapping rules is that they are declarative, i.e., constraint templates in a mapping rule only represent what kinds of geometrical constraints should hold among graphical objects, not how to draw the pictures. This characteristic enables mapping rules to be applied both to visualization and to visual parsing as described above. In comparison to our past work, although TRIP2[14] and TRIP3[9] are both based on the bi-directional translation model described here, both systems did not provide a complete visual parsing algorithm. They required two complementary mapping rules: one for visualization, and the other for visual parsing. This problem is solved in this study by introducing a new visual parsing algorithm described in Section 5.
mapping-rule level object-def

Mapping Rules

Figure 8 shows the BNF de nition of the mapping rule syntax, and Figure 9 shows the mapping rules generated as a result of the interactive rule generation process described in Section 2.2. (Note that the mapping rules are only used internally in the IMAGE system; the programmers do not have to write any mapping rules at all.) Mapping rules are categorized into levels, each of which holds a series of constraint templates which are extracted from an example picture; For example, level 0 of the mapping rule for organization type in Figure 9 (line 7 { 18) includes constraint templates extracted from the initial sample picture the programmer draws (Figure 2 (2)), whereas level 1 holds the ones extracted from the rst corrected picture in Figure 2 (4). Each level consists of the following three parts: (a) the graphical object de nition part, which declares graphical objects such as rectangles appearing in the picture corresponding to a typed application data; (b) the constraint de nition part, which declares geometrical constraint templates that hold among the graphical objects. For example, (offset boss rt staff lt 20 0) in line 21 of Figure 9 represents that object boss and composite object staff are separated by horizontal gap 20 and vertical gap 0, with respect to the speci ed reference points (Figure 10); (c) the loop de nition part, which speci es constraint templates involving an arbitrary number of list elements using for-each-in expressions. A series of constraint templates are speci ed among particular list elements satisfying a declared loop control expression, such as member representing \every element", and adjacent representing \every pair of two adjacent elements". For example, line 15 { 18 of Figure 9 represents that every pair of two adjacent elements in staff list are separated by horizontal gap 0 and vertical gap 020, that is, all elements are aligned vertically. When constraint templates in a mapping rule are instantiated, some of the instantiated constraints might be contradictory. Because of the manner the rules are generated via the interactive correction as will be described in Section 4, in such cases the constraint template extracted from the latest example picture should be employed whereas the older ones should be ignored. Intuitively, this stems from the observation that additional example pictures are given to the system in order to correct the mapping rules the system has generated, invalidating the old constraint templates. Our requirement is that the system should be able to nd the best set of substitutions for any set of constraints even when some of the constraints are potentially contradictory. To solve the problem, we employ the constraint hierarchy mechanism proposed in [3] in the following way:  Mapping rules are categorized into a series of levels, each of which holds a set of constraint templates. The higher level a constraint template belongs to, the stronger it is.  The weakest level, level 0, holds a set of constraint templates extracted from the initial example picture the programmer draws. The role of the constraint templates
3.4 Constraint Hierarchies

! ! ! ! ! !

constraint-def

loop-def

rule-name level?) (level-name (object-def?) (constraint-def?) (loop-def?)) (rectangle obj-id ) j (word obj-id ) j (line obj-id ) (x-o set obj-id1 ref1 obj-id2 ref2 dx) j (y-o set obj-id1 ref1 obj-id2 ref2 dy) j (o set obj-id1 ref1 obj-id2 ref2 dx dy) (for-each-in relevant-list

(de ne-mapping

loop-control-exp

(object-def?) (constraint-def?)) (member element relevant-list) j (adjacent element1 element2 relevant-list)

loop-control-exp

Figure 8: The BNF De nition of the Syntax

1: (define-mapping man layout in man 2: (level0 3: ((rectangle rect0)) 4: ((offset rect0 lb rect0 rt 50 20) 5: (offset rect0 cc name cc 0 0)))) 6: (define-mapping organization 7: (level0 8: ((line line0) 9: (line line1)) wrong layout of boss and staff 10: ((offset boss lb staff lb 70 -40) 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: (offset line0 sp boss rc 0 0) (offset line0 ep (staff 0) lc 0 0) (offset line1 sp boss rc 0 0) (offset line1 ep (staff 1) lc 0 0)) list generalization (( for-each-in staff (adjacent staff1 staff2 staff) () ((offset staff1 lb staff2 lt 0 -20))))) (level1 right layout of boss and staff () ((offset boss rt staff lt 20 0)) (( for-each-in staff generalization for lines (member el0 staff) (( line rep-obj-id )) ((offset rep-obj-id sp boss rc 0 0) (offset rep-obj-id ep el0 lc 0 0))))))

Given an application data type de nition, this module generates application data examples.
Example Generator Drawing Editor

This module provides MacDraw-like editing facilities for the programmers to correct visualized pictures the system shows.
Rule Generator

Given a pair of example data, i.e., application data and its corresponding picture, this module generates a mapping rule for translation. This module also modi es already-generated rules, given additional example pairs.

Bi-Directional Translator Given a series of mapping rules, this module realizes the bi-directional translation between application data and its visual representation, using the hierarchical constraint solver proposed in [5].

Figure 9: Mapping Rules for Organization Diagram

50 20

20

staff staff1
20

boss

IMAGE system has two phases of usage: one is the rule generation phase, and the other is the rule application phase. In the rule generation phase, the system produces mapping rules incrementally by letting programmers correct system-generated example pictures. In the rule application phase, the system realizes the bi-directional translation between application data and its visual representation controlled by mapping rules. This phase provides \free-hand" interfaces for end-users to manipulate application data visually.
Generation Phase
Application Data Definition Example Generator

40 70

staff2

Application Phase
Application Data

Figure 10: Organization Diagram Layout

in level 0 is that they guarantee that all coordinates of graphical objects are determined. In other words, under-constrained situations will not occur.  When programmers correct system-generated example pictures, constraint templates extracted from these corrected pictures are categorized into higher levels than level 0. In this way, constraint templates to correct the ill-inferred layout have a higher priority over the ones extracted from the initial picture. Note that the constraint hierarchy mechanism helps the interactive rule generator drastically; all the rule generator has to do is to extract new constraint templates from corrected example pictures, and add them into the mapping rules. The rule generator does not have to worry about under-constrained or over-constrained situations which could occur with the constraints instantiated from these templates. Instead, level 0 of rules guarantees no under-constrained situations occur, and the constraint hierarchy mechanism handles overconstrained situations in a \correct" way.
4

Application Data Example

Picture Example Drawing Editor

Bi-Directional Translator (visualizer & visual parser) Mapping Rules Visual Representation

Rule Generator

Units

Mapping Rules

Figure 11: System Architecture of IMAGE
4.1

Figure 11 shows the system architecture of IMAGE. It consists of four main modules:

PROTOTYPE SYSTEM IMAGE

The example generator has two roles: It rst generates the simplest application data example, given the de nition of an application data type. Throughout the rule generation process, it then revises application data examples to make them more complicated step-by-step using the following strategies: (1) integer elds are initialized with pre-de ned constant values, and incremented later, (2) word elds are initialized with constant strings, such as \word0", and then lengthened, (3) elds of userde ned types have IDs referring to dummy application data, (4) list elds are initialized with two dummy IDs. The number of elements is then increased.

Example Generator

Application data which were generated automatically often does not re ect the programmer's intention exactly. In such cases, programmers can correct the data so that it is meaningful from the semantical viewpoint. For example, if the system generates an example application data which says \the man is one thousand years old", the programmer can change the age. However the system should guarantee that some conditions are satis ed even after the modi cation by programmers. For example, the number of list elements should be two in the initial example because this condition is vital for the rule generator in charge of list generalization. The rule generator is driven by a set of units, which specify how to re ect the programmer's operations in the drawing editor onto the revision of mapping rules (See Figure 11). Since units are independent from each other, the rule generator has rich extensibility. The units currently implemented are of the following three categories:  Units which generate initial mapping rules, i.e., level 0 of rules, given the initial pair of examples.  Units which modify the mapping rules according to the programmers' correction on system-generated example pictures, such as movement or transformation of graphical objects.  A unit which adds new for-each-in expressions into mapping rules when new graphical objects are added in pictures by the programmers. The following sections explain these units in detail using the sample rule generation process for the organization diagram. Note that Figure 9 shows the resulting mapping rules generated via the interactive rule generation process.
4.2.1 Units for Generation of Level 0 in Rules As described in Section 3.4, the most important role of level 0 in mapping rules is to provide sucient number of constraint templates to determine the layout of graphical objects. To satisfy the requirement, the rule generator maintains the stability table to keep track of which coordinates are determined by the generated mapping rules. The table consists of tuples hobject ID, size, positioni, and is initialized with tuples hobject ID = , size = unstable, position = unstablei for graphical object in the initial example picture the programmer has drawn. If a unit adds to level 0 a constraint template which determines the size of object , the unit updates the tuple for object to be hsize = stablei. After all the units that generate level 0 in rules are invoked, all the tuples in the table should be hsize = stable, position = stablei, which is guaranteed by the unit for object size stabilization and the unit for object position stabilization described below.

constraint template between the two elements, and then generalizes the constraint template by wrapping it in a for-each-in expression. In the organization rule, lines 15 { 18 of Figure 9 are generated. Note that the horizontal o set value of the offset constraint template is truncated to zero since the actual o set value in the example picture is nearly zero. This technique provides a simple \beauti cation" facility, which let programmers draw example pictures in a rough manner. We employ special heuristics about the treatment of lines based on our experiences with TRIP3. We assume that usual graphical objects such as rectangles have the tendency that their sizes are xed whereas their positions depend on the positions of other objects. On the other hand, lines tend to connect other graphical objects rather than to be placed alone. In other words, we assume the sizes of lines are calculated from their positions, which depend on the positions of other objects. This di erence drove us to introduce a special unit which generates offset constraint templates to attach both ends of lines to other objects.
Unit for Line Attachment Unit for Object Size Stabilization

4.2

Rule Generator

After invoking the preceding units, some graphical objects could remain whose sizes are not stable. This unit generates offset constraint templates to x their sizes. For example, given a rectangle, the unit generates an offset constraint template between its lower left corner and upper right corner.

Unit for Ob ject Position Stabilization When n graphical objects are left position-unstable after invoking the units described above, this unit generates n 0 1 offset constraint templates to determine their relative positions with respect to their lower left corners to x its size.
4.2.2 Units to Modify Geometrical Constraints Assume that a programmer modi es an example picture presented by the system, and some geometrical constraint templates declared in a mapping rule no longer hold. In this case, the rule generator searches for alternative constraint templates which are satis ed in all the situations given as multiple examples.

It is generally dicult to infer the programmer's intention about how to lay out an arbitrary number of elements in a list. Recall that the initial example picture should include just two elements for each list, which had to be guaranteed as mentioned in Section 4.1. This unit generates an offset
Unit for List Generalization

For example, take the rule generation process for the organization diagram mentioned in Section 2.2. The system generates an initial mapping rule (level 0 of Figure 9) inferring the programmer's intension from the initial example picture (Figure 12 (1)). The units described in Section 4.2.1 create a constraint template (offset boss lb staff lb 70 -40) in line 10 of Figure 9, which xes the relative position of boss and staff with respect to their lower left corners. When the system visualizes the second application data example whose staff has three elements, the generated picture looks as in Figure 12 (2). Assume that the programmer's real intention about layout is that boss and staff should be aligned horizontally at their top edges. In that case, he will modify the picture as shown in Figure 12 (3).

To re ect the modi cation of the picture onto the mapping rule, the system adds a new constraint template (offset boss rt staff lt 20 0) as shown in line 21 of Figure 9, which aligns the top right corner of boss to the top left corner of staff. 1.
staff staff1 staff boss
40 70

regarding the number of lines. The algorithm to generate for-each-in expressions is described below, again using the example case of organization diagram. Choose an arbitrary list as a relevant list, and collect relevant objects which satisfy the following two conditions: (1) Their types should be that of the object the programmer has added, (2) there should be some constraint templates which include the relevant objects and the relevant list. In the example case, assuming staff is the relevant list, two objects, line0 and line1, are chosen. This is because there are offset constraint templates including staff, line0, and line1 in level 0 of the mapping rule being generated such as (offset line0 ep (staff 0) lc 0 0) as shown in line 12 of Figure 9. (Note that (staff 0) represents the rst element of staff.)

staff1 staff2 (1)
20 40

boss

staff2 staff3

70

(2) staff staff1 staff2

boss

2. Choose an arbitrary representative object from the relevant objects, and collect all constraint templates that include the representative object. Those constraint temstaff3 plates serve as a basis for generating a for-each-in ex(3) pression. In the example case, the system chooses line0 Figure 12: Modifying Constraint Templates as the representative object, and nds the constraint templates (offset line0 sp boss rc 0 0) and (offset line0 ep (staff 0) lc 0 0) in level 0 (line We emphasize that this new constraint template is added 11 and 12 of Figure 9). into level 1, not into level 0. This distinction informs the constraint solver that this additional constraint template should be prioritized higher than the one which no 3. Select a loop control expression which holds true among the relevant list and its elements appearing in the collonger holds. One may ask; \Why doesn't the system lected constraint templates. Candidates are (1) (member delete the outdated constraint templates?" If the sys(staff 0) staff), which means (staff 0) is an eletem simply deleted the outdated constraint templates, ment of staff, (2) (adjacent (staff 0) (staff 1) however, the constraint system could turn out to be eistaff), which means (staff 0) and (staff 1) are adther under-constrained, or not re ecting the programjacent in staff. In the example case, member is selected mer's intentions correctly, due to the deletion. The desince there is only (staff 0) in the collected constraint cision whether the templates could be safely deleted or templates. not is dicult since such situations are detected only when constraint templates are instantiated and the gen- 4. Substitute a new ID template rep-obj-id for the reperated constraints are solved by the constraint solver. resentative object and ID templates el0, el1, : : : for elTo overcome this problem, the rule generator does not ements of the relevant list. This substitution in the coldelete any constraint templates and always generates lected constraint templates is the core of generalization, enough constraint templates to make the constraint sysand the result is shown below: tem over-constrained to be resolved by the constraint hierarchy mechanism. ; the reference point sp of rep-obj-id
4.2.3

When a ; rc of boss. (offset rep-obj-id sp boss rc 0 0) programmer adds new objects in pictures the system vi; The ep of rep-obj-id is attached to sualizes, the rule generator adds new for-each-in ex; the lc of el0 as well. pressions in the generated mapping rule to account for (offset rep-obj-id ep el0 lc 0 0) the occurrence of the new objects. For example, the system adds a new for-each-in expression for a newly 5. Enclose the substituted constraint templates in a added line, given the additional example picture shown for-each-in expression with the generated loop control in Figure 2 (4). expression. As a result, the following new for-each-in expression is generated: Generally speaking, when a PBE system generates a loop structure by generalizing multiple examples, there (for-each-in staff must be some conditions to restrict the number of the ; for each member of staff, iteration of the loop. IMAGE employs the length of (member el0 staff) lists in application data as the loop condition, and des; a new line is generated, ignates the lists which control the number of loops as ((line rep-obj-id)) ; and it connects boss and relevant lists. In this example, staff is the relevant list
Unit to Generalize the Number of Objects

; is attached to the reference point

; the staff member. ((offset rep-obj-id sp boss rc 0 0) (offset rep-obj-id ep el0 lc 0 0)))

6. Check if this new for-each-in expression could be generated when other relevant objects are used as the rep- 1. All the possibilities are enumerated. According to the resentative object. In the example case, the selection object de nition part, the initial table includes all the of line1 as the representative object leads to the same word object IDs for variable name and all the rectangle for-each-in expression, and passes the test. object IDs for variable rect-id. (Figure 13 (2-a)) 7. If the above-mentioned checking fails, choose another 2. The x-offset constraint template is checked. At this list as the relevant list and try the generation process point, the binding table includes some invalid tuples again. such as hname = Alex, rect-id = #2i. (Figure 13 (2b))
5 VISUAL PARSING

picture in Figure 13 (1) with the mapping rule in Figure 14. Figure 13 (2) shows a sequence of changes in the variable binding tables through the following parsing process:

There are two major categories of visual parsing algo- 3. The y-offset constraint template is checked. The binding table eventually includes the valid four tuples. Note rithms: One is top-down parsing such as a LL(1) parser that this table represents four independent parts as canfor traditional programming languages. The other is didates. (Figure 13 (2-c)) bottom-up parsing such as a naive query engine in deductive databases[15]. We employ bottom-up parsing, because of the following reasons: Comparing our algorithm to the related work, DR  Bottom-up parsers leave no graphical element in a pic- parser[1] is an attempt to extend the BNF syntax description to adapt to 2D layout. Its limitation is that its ture unparsed. This characteristic is useful when a picsyntax can only represent pictures whose abstract structure is comprised of some independent parts.  By invoking a mapping rule repetitively, bottom-up ture is parsed as a tree. This limitation is serious since the bulk of useful visual representations include cycles, parsers can parse recursive data. e.g., ER-diagram, petri-net, etc.
#1 Alex #2 #4 Brad Dave #3 Chas name Alex Brad Chas Dave rect-id

X

#1 #2 #3 #4

(1)
name Alex Alex Brad Brad Chas Dave rect-id #1 #2 #1 #2 #3 #4 name Alex Brad Chas Dave

(2-a)

rect-id #1 #2 #3 #4

(2-b)

(2-c)

Figure 13: Example of Visual Parsing

(define-mapping man (level0 ;; object definitions ((word name) (rectangle rect-id)) ;; constraint definitions ((x-offset rect-id cc name cc 0) (y-offset rect-id lb name lb 5)))) Figure 14: Simple Mapping Rule

When a mapping rule is applied, all possibilities are rst enumerated in a binding table, and these possibilities which are contradictory to constraint templates declared in the rules are eliminated. For example, let us parse a

Although this study has proposed a new interaction paradigm in the context of PBE, much work still remain. For IMAGE, we rst need to enhance the expressive power of the system. The current system supports only very \regular" visualizations. For example, the visualization of a list in multi-column form, the visualization of complex family diagram, and bar charts are not supported in the current system. To handle those cases, we are now considering the following four options:  Given multiple visual examples, the system autonomously programs conditional branching. Since it is generally considered dicult to infer the conditions of branching, we must devise a natural interaction technique that allows easy but powerful extraction of the programmer's intention about the branching conditions. For example, our previous work TRIP3[9] has a special graphical component to represent the recursive occurrences of example pictures in the sample pictures.  The system has ready-made parameterized templates of commonly-used visualizations, such as a tree diagram, an organization diagram, etc. In this case, the PBE mechanism is used to determine the values of parameters. This practical approach was pursued by Marquise[10].  Employing intelligent visualization methods such as FishEye[12] relieves mapping rules from representing complex layout policies. As a result, a PBE engine does not have to worry about complex layout policies such as conditional branching. The problem here is how to let the system deduce which visualization policies are appropriate.

6

FUTURE WORK



The system should realize visualization using integer data. For example, bar charts can be realized using rectangles whose sizes are proportional to integer data elds. Second, we need a better communication method between computation modules and the GUI modules that IMAGE generates. We are currently planning to adopt active values[13] in the short term, but a better approach is needed for complex interactions.

5. Hosobe, H., K. Miyashita, S. Takahashi, S. Matsuoka, and A. Yonezawa, \Locally Simultaneous Constraint Satisfaction," in Proceedings of the Second Workshop on the Principles and Practice of Constraint Programming, May 1994, pp. 48{57. 6. Hudson, S. E. and A. K. Yeatts, \Smoothly Integrating Rule-Based Techniques Into A Direct Manipulation Iterface Builder," in Proc. of ACM User Interface Software and Technology (UIST), 1991, pp. 145{153. 7. Kurlander, D. and S. Feiner, \Inferring Constraints from Multiple Snapshots," Technical Report CUCS 008-91, Columbia University Computer Science, May 1991. 8. Lieberman, H., \Tinker: A Programming by Demonstration System for Beginning Programmers," in Watch What I Do: Programming by Demonstration (A. Cypher, ed.), ch. 2, pp. 49{66, MIT Press, 1993. 9. Miyashita, K., S. Matsuoka, S. Takahashi, A. Yonezawa, and T. Kamada, \Declarative Programming of Graphical Interfaces by Visual Examples," in Proc. of ACM User Interface Software and Technology (UIST), 1992, pp. 107{116. 10. Myers, B. A., R. G. McDaniel, and D. S. Kosbie, \Marquise: Creating Complete User Interfaces by Demonstration," in ACM Human Factors in Computing Systems, 1993, pp. 293{300. 11. Piernot, P. P. and M. P. Yvon, \The AIDE Project: An Application-Independent Demonstrational Environment," in Watch What I Do: Programming by Demonstration (A. Cypher, ed.), ch. 18, pp. 383{ 402, MIT Press, 1993. 12. Sarkar, M. and M. H. Brown, \Graphical Fisheye Views of Graphs," in ACM Human Factors in Computing Systems, 1992, pp. 83{91. 13. Szekely, P. A. and G. A. Myers, \A User Interface Toolkit Based on Graphical Objects and Constraints," in Proc. of ACM Object-Oriented Programming Systems, Languages, and Applications, 1988, pp. 36{45. 14. Takahashi, S., S. Matsuoka, A. Yonezawa, and T. Kamada, \A General Framework for BiDirectional Translation between Abstract and Pictorial Data," in Proc. of ACM User Interface Software and Technology (UIST), 1991, pp. 165{174. 15. Ullman, J. D., Principles of Database and Knowledge-Base Systems Volume II: The New Technologies. Computer Science Press, 1989.

Finally, the drawing editor can be improved to give more interactive feedback to programmers in the rule generation process. For example, when a programmer moves a rectangle, the editor could snap the rectangle onto a certain position so that it is aligned with other graphical objects in the manner employed by snap-dragging[6]. To realize this kind of intimate interaction, real-time communication between the drawing editor and the constraint solver is indispensable. To help programmers create application-speci c GUIs rapidly, this study has proposed an enhanced PBE methodology called \Programming by Interactive Correction of Examples ", and also implemented a prototype system IMAGE. This methodology has the following features: (1) A PBE system exhibits programs to programmers by showing visual examples rather than representing programs textually. (2) The system lets programmers correct visual examples and then revises programs, re ecting the programmers' modi cations on pictures. (3) The system takes the initiative in presenting visual examples, and guides the programmers to be on the right track in giving the examples. I appreciate the TRIP framework that Tomihisa Kamada proposed. I am also thankful to Hiroshi Hosobe for his powerful constraint solver[5].
REFERENCES ACKNOWLEDGEMENTS 7 CONCLUSION

1. Costagliola, G. and S.-K. Chang, \DR Parser: A Generalization of LR Parsers," IEEE Workshop on Visual Languages, 1990, pp. 174{180. 2. Fisher, G. L., D. E. Busse, and D. A. Wolber, \Adding Rule-Based Reasoning to a Demonstrational Interface Builder," Proc. of ACM User Interface Software and Technology (UIST), 1992, pp. 89{ 97. 3. Freeman-Benson, B. N., J. Maloney, and A. Borning, \An Incremental Constraint Solver," Comm. ACM, vol. 33, no. 1, Jan. 1990, pp. 54{63. 4. Halbert, D. C., \SmallStar: Programming by Demonstration in the Desktop Metaphor," in Watch What I Do: Programming by Demonstration (A. Cypher, ed.), ch. 5, pp. 103{124, MIT Press, 1993.


更多相关文档:

LeafView A User Interface for Automated Botanical Species ....pdf

To appear in ACM UIST 2006 Conference Companion ...] User InterfacesGraphical user interfaces. ... "Toolkit Design for Interactive Structured Graphics...

Interfaces and Presentation] User InterfacesGraphical.pdf

and Presentation] User InterfacesGraphical_专业...UIST '04, October 24-27, 2004, Santa Fe, ...A pie menu appears with choices containing ...

BLUI Low-cost Localized Blowable User Interfaces.pdf

- Graphical user interfaces. General terms: Design...UIST’07, October 710, 2007, Newport, Rhode...screen to directly control interactive applications....

ABSTRACT Improving User Interface Personalization.pdf

[User Interfaces]: Graphical User Interfaces (GUIs...UIST ’04, October 2427, 2004, Santa Fe, ...user interface generation and adaptation as a ...

...User Interfaces for the Authoring and Delivery of Slide ....pdf

Dissertation Title Zoomable User Interfaces for the...UIST 2000, ACM Symposium on User Interface ...System and Method for Interaction of Graphical ...

All in a Day’s Work User Interface Design for Multitasking, ....pdf

UIST’06, October 1518, 2006, Montreux, ... in window-based graphical user interfaces. ...9499. 14. Smith, G., Baudisch, P., ...

Multi-user, multi-display interaction with a single-user, ....pdf

- Graphical user interfaces. General terms: Design...UIST'06, October 1518, 2006, Montreux, ...appear in the correct location on all machines. ...

POSITION PREVIOUS POSITIONS EDITORIAL POSITIONS XEROX ....pdf

Conference Companion of CHI 2003, to appear. Ol...Proceedings of UIST'94, ACM Symposium on User ... for Knowledge-Based Graphical User Interfaces. ...

General Terms Algorithms.pdf

Automatic UI Generation, Optimization, Supple, ...INTRODUCTION Graphical user interfaces (GUIs) for ...In Proceedings of UIST’05, Seattle, WA, 2005....

Interfaces for Managing Applications and Input in Multi-....pdf

Bailey In our interfaces, users manipulate a 2D ...Figure 2. Our graphical construction tool enables ...UIST, 2002, 227-234. Johanson, B., Ponnekanti...

The ScrollSearcher Technique Using Scrollbars to Explore ....pdf

rk PLAY, Interactive Institute, Box 620, SE-405... of components used in graphical user interfaces....In Proc. of UIST '94, pp. 119-120, ACM ...

CHI2006: What Is the Next Generation of Human-Computer ....unkown

If we consider command-line interfaces as the first generation, then direct manipulation and the graphical user interface define the second generation of ...

...of Software Architecture for Multimodal Interactive ....unkown

Interactive Systems: Voice-Paint and a Voice-...of graphical user interfaces, natural language ...generation of output data: values along this axis...

Groupware Benjamin.unkown

and a single visual present users to collaborate...graphical user interfaces, techniques for managing ...User Interface and Software Technology: UIST 96 (...

The next generationof graphicaluserinterfaces:infkmation ....unkown

ELSEVIER Displays 17 (1997) 125-129 The next generationof graphicaluserinterfaces:infkmation visualization and better window management Ben Shneiderman ...

Supporting Creativity in Distributed ScientificCommunities.unkown

generation, one antidote appears to be dissent [...Proceedings ACM UIST. Vancouver, 2003, 21-30. ...Creating Creativity: User Interfaces for Supporting ...

Automatic Generation of Graphical User Interfaces in Studier....unkown

Bakkalaureatsarbeit Automatic Generation of Graphical User Interfaces in Studierstube ausgefu¨hrt am: Institut fu¨r Softwaretechnik und Interaktive Systeme...

Test Generation for Graphical User InterfacesBased on ....unkown

Test Generation for Graphical User Interfaces Based on Symbolic Execution Svetoslav Ganov The University of Texas at Austin Laboratory of Experimental Software ...

DSL-driven generation of Graphical User Interfaces.unkown

10.2478/s13537-014-0210-9 Central European Journal of Computer Science DSL-driven generation of Graphical User Interfaces Michaela Bacˇíková, ...

Sun LSI 106x RAID User’s Guide.unkown

39 39 To Create IS Volumes Creating a Second ...94 95 95 Deleting a Virtual Disk To Delete...(MSM) program provides you with graphical user ...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com