Declarative programming of graphical interfaces by visual examples.
Graphical user interfaces (GUI) provide intuitive and easy means for users to communicate with computers. However, construction of GUI software requires complex programming that is far from being intuitive. Because of the semantic gap between the textual application program and its graphical interface, the programmer himself must conceptually maintain the correspondence between the textual programming and the graphical image of the resulting interface. Instead, we propose a programming environment based on the programming by visual example (PBVE) scheme, which allows the GUI designers to program visual interfaces for their applications by drawing the example visualization of application data with a direct  manipulation interface. Our system, TRIP3, realizes this with (1) the bi-directional translation model between the (abstract) application data and the pictorial data of the GUI, and (2) the ability to generate mapping rules for the translation from example application data and its corresponding example visualization. The latter is made possible by the use of generalization of visual examples, where the system is able to automatically generate generalized mapping rules from a given set of examples.
Introduction
The advent of workstations and personal computers
with high-resolution graphics has realized graphical user
interfaces (GUI)[8], where information is visualized
with colors and movements instead of flat and flavor-
less text[2, 5, 3]. The complexity and development
cost of GUI are, however, considerably higher compared
to those of conventional text-based interfaces, primarily
due to the followings: (1) Specification of interface
components, which is inherently graphical, is achieved
with conventional programming languages, which are
inherently textual, and (2) programmers must somehow
maintain the correspondence between abstract data in
the application and its visual representation, with explicit
textual programming.
An obvious solution to problem (1) is to employ direct
manipulation in programming the GUI itself, thereby
allowing the programmer to graphically manipulate and
layout the UI components. However, direct manipulation
is inherently "concrete", i.e., it lacks the means of
"abstraction", which is essential to programming in gen-
eral. The previous approaches to utilize direct manipulation
in GUI programming, therefore, do not usually
serve as a solution to (2), i.e., programming the general
correspondence between application data and its visual
representation.
Expressing the correspondence between application
data and its visual representation declaratively is a step
towards a solution to problem (2). Our previous re-search
proposed the bi-directional translation model and
a prototype system TRIP2[25]. TRIP2 realizes bi-directional
translation between application data and its
visual representation with a set of declarative translation
(mapping) rules. Modification of the application
data is directly reflected to its visualization, and con-
versely, graphical editing is directly reflected to the application
data.
Programming in TRIP2 was, however, still confined
to the realm of text-based specification; thus, although
it was far easier and involved less coding compared to
conventional GUI programming, specification of mapping
rules for complex application data is a non-trivial
and error-prone task, especially for GUI designers who
might not have extensive programming experiences.
To overcome the problems, we propose the programming
by visual example (PBVE) scheme. PBVE generates
the declarative mapping rules from examples of
application data and its corresponding visual represen-
tation. We present a prototype system TRIP3, a GUI
programming environment that realizes PBVE via direct
manipulation. TRIP3 enables a programmer to
generate mapping rules automatically, merely by drawing
example pictures with a MacDraw-like drawing ed-
itor, and supplying the corresponding application data
example. PBVE combines the complimentary benefits
of direct manipulation and the programming by example
(PBE) paradigm in a sense that PBE provides the
abstraction capability that is lacking in direct manip-
ulation, and direct manipulation facilitates easy means
for providing the examples.
Compared to the past researches that employ PBE
in the context of GUI[18, 4], TRIP3 is unique in the
following way: such systems generalize the sequential
trace of the user's interaction to generate imperative
programs that handle low-level user dialogues. By con-
trast, TRIP3 generalizes the high-level semantic information
on visualization of application data, i.e., the
correspondence between application data and its visual
representation.
The rest of this paper is organized as follows: Section
2 presents the bi-directional translation model we
employ. Section 3 overviews the PBVE framework of
automatic generation of mapping rules, and the prototype
system TRIP3. Section 4 describes the implementation
of TRIP3. Section 5 shows further examples of
rule generation via PBVE. Section 6 reviews the related
work, and we conclude in Section 7.
2 The Bi-Directional Translation
Model - TRIP2
2.1 Four Types of Data Representation
It is non-trivial to devise a general scheme for achieving
the translation between application data and its visual
representation, because both data representations
could be arbitrary. To solve the problem, our previous
research TRIP[14] and TRIP2[25] have proposed two
additional canonical data representation layers between
the application data and its visual representation.

Figure

1 shows the four data representations and their
examples. Application's Data Representation (AR)
is the application-dependent abstract data. Abstract
Structure Representation (ASR) is a canonical data representation
with which a programmer expresses application
data. Visual Structure Representation (VSR) is a
canonical data representation with which visual images
are represented. ASR and VSR are represented as Prolog
clauses. Pictorial Representation (PR) refers to the
actual visual images which correspond to the description
in VSR. Figure 1 shows an organization diagram
(PR) and its corresponding ASR and VSR. (Through-
out this paper, the example in Figure 1 is used to explain
the process of generating mapping rules.)
TRIP2 focuses on the translation between ASR and
VSR, and between VSR and PR. (The translation be-
Application's Data Representation (AR)

Abstract

Structure Representation (ASR)
Visual Structure Representation (VSR)
Pictorial Representation (PR)
" Hogan is the boss of Heinlein, Clarke, and
Herbert in an organization. "
organization(hogan,
[heinlein,clarke,herbert]).
horizontal([hogan,heinlein]).
vertical([heinlein,clarke,herbert]).
connect([hogan],
[heinlein,clarke,herbert]).
heinlein
herbert
clarke
hogan
COOL Spatial Parser
COnstraint based
Object Layout system
Inverse
Mapping Rule
Mapping Rule
Application dependent Application dependent

Figure

1: The Bi-Directional Translation Model and its
Four Data Representations
Modification in the picture is
reflected to the application data.
The application data is visualized.
Declarative Mapping
Rules

Figure

2: The TRIP2 System[25]
tween AR and ASR is left as application-programmer's
responsibility.) TRIP[14] incorporates COOL (COn-
straint based Object Layout system), that converts
VSR clauses into PR images. TRIP2 also incorporates
the spatial parser, which infers geometrical relationships
among graphical objects in PR images, and generates
the VSR clauses.
Employing canonical data representation layers enables
us to formalize the translation between application
data and its visual representation. Mapping rules
perform the translation from ASR to VSR, whereas inverse
mapping rules perform the translation from VSR
to ASR. Actual rules are represented as Prolog clauses.
A mapping rule which converts ASR to VSR in Figure 1
is presented below:
organization-rule :-
clause is unified.
clause horizontal is generated.
horizontal([X,H]),
clause vertical is generated.
vertical([H-L]),
clause connect is generated.
connect([X],[H-L]),
% (5) This line invokes the backtrack
% for further database search.
fail.
The Prolog database contains the ASR data represented
as Prolog clauses (i.e., database facts)
such as organization(hogan, [heinlein, clarke,
herbert]) in this example. When the rule
organization rule is applied, Prolog interpreter first
unifies line (1) with a fact that matches this line. (Note
that capitalized letters such as X represent variables
and square brackets, i.e., "[" and "]", represent list
structures.) In this example, the variable X is unified
with hogan and the list structure [H-L] is unified
with [heinlein, clarke, herbert], whereby H
is instantiated with the head of the list, heinlein,
and L with the remainder, [clarke,herbert]. With
these unified variables, lines (2) - (4) generate the VSR
clauses. For example, line (2) generates a VSR clause
horizontal([hogan, heinlein]) as a result of unifi-
cation, representing a geometrical relationship between
the two objects. Line (5) invokes the backtrack mechanism
of Prolog and forces enumeration of all matching
ASR clauses to be converted to VSR clauses.
Note that this rule is entirely declarative, i.e., there
are no imperative expressions, facilitating clear and concise
specification of visualization of application data.
The corresponding inverse mapping rule is almost
equivalent to the mapping rule above - the only difference
is that, for the inverse rule, the ASR clause
comes after the VSR clauses.
(This difference is due to the execution order of Prolog
being left-to-right.) As a result of this minor modifi-
cation, the VSR clauses are unified first with the VSR
facts, from which the ASR clauses are generated.
Declarative mapping rules are surprisingly powerful
in their expressiveness despite their conciseness. They
basically support two kinds of layout policies: one is
the geometrical layouting using VSR clauses such as
horizontal and vertical (examples are family diagram
and organization diagram), and the other is the
topological layouting using the VSR clause adjacent
(an example is ER diagram). Furthermore, the mapping
rules support recursive structures (an example is
tree diagram). For details, see [14].

Figure

2 shows a snapshot of TRIP2 in action, realizing
a simple family-tree diagram editor: the ASR data
in the left window, such as generation(parents(taro,
hanako), children([ichiro, jiro, saburo])), are
translated into the family-tree diagram and vice versa.
When the user edits ASR data, the system redraws the
diagram in the right window to reflect the modification;
conversely, when the user modifies the diagram with
a generic MacDraw-like editor, the system regenerates
ASR data to be consistent with the modified diagram.
2.2 Problems in TRIP2
Our previous works (TRIP[14], TRIP2[25]) assumed
that the mapping rules are textual and provided by the
programmers. It is not, however, a trivial task for non-programmers
to program the mapping rules for interfaces
of complex application data (although it is easier
compared to imperative programming). Upon analy-
sis, we have encountered the following problems: (1)
A programmer cannot immediately see what his mapping
rules would generate during programming; thus, it
is difficult for the programmer to decide on which set
of VSR data would correspond to his desired visualiza-
tion, and to determine the appropriate parameters such
as the width of boxes. (2) It is not immediately obvious
whether the geometric constraints imposed by the
set of the translated VSR data such as horizontal and
vertical would be sufficient for all conceivable cases; in
other words, the programmer must make sure that the
resulting constraint system is neither underconstrained
nor overly contradictory.
3 Programming by Visual Ex-
ample
To solve these problems, we propose the programming
by visual example (PBVE) scheme, whereby the de-
signer's intended visualization of application-dependent
data is constructed by generalizing on the actual visualization
examples of concrete application data. In our
case, "PBVE" refers to the process of generating the
mapping rules that can translate application data into
its proper visual representation and vice versa, so long
as the style of data conforms to the one inferred from
the example data. (In a sense, the system "mimics" an
experienced GUI programmer's programming skills.)

Figure

3 overviews our scheme with an example. The
left two rounded rectangles show a pair of designer-
supplied example data: the example application data
and its example visual representation. To create the
mapping rules, an experienced GUI programmer would
rely on the following a-priori knowledge of visualization:
ffl Names on rectangles in the example picture indicate
the correspondence between parameters in the
application data and these rectangles.
ffl The left rectangle would represent the boss and
the right rectangles connected to the boss would
represent the workers.
ffl Because there could be any number of workers
managed by a boss, the rules must be able to align
any number of workers. In this example, the workers
should be aligned vertically with a certain vertical
gap between each rectangle.
Mapping rules are generated automatically via PBVE
in our TRIP3 system in a similar way. First, the designer
provides the sample ASR clauses and draws its
corresponding picture using a MacDraw-like drawing
editor in the pict editor view: in this example, he draws
the figure depicted in the upper-left rectangle in Figure
3. While the designer draws the sample picture in
the pict editor view, the system converts the picture
into VSR clauses which reflect his intention regarding
the layout of objects (Step 1 in Figure 3). Every time
the designer draws a new object, the spatial parser infers
the geometrical relationships such as horizontal
extract intended
geometrical relationships
PR Example
heinlein
herbert
clarke
hogan
VSR Example
horizontal([hogan,heinlein]).
vertical([heinlein,clarke,
herbert]).
connect([hogan],
[heinlein,clarke,
herbert]).
ASR Example
organization(hogan,
[heinlein,
clarke,
herbert]).
Variables
clarke,
assign variables
to each parameter
generate the
mapping rule
Mapping Rule
rule :-
horizontal([V1,V2]),
vertical([V2|V3]),
connect([V1],[V2|V3]),
fail.

Figure

3: Rule Generation from Visual Examples

Figure

4: Pict Editor
Relations
Similar
Objects
Confirmation
Horizontal
Average
Contain

Figure

5: Confirmation
Panel
and vertical that are "likely" to match his intention.
The system heuristically determines which geometrical
relationship is likely to reflect the designer's intention
by computing the "weight" of each inferred relationship.
For example, the smaller the difference between the Y
coordinates of two objects is, the greater the weight of
a horizontal relationship between the two objects be-
comes. Alternatively an adjacent relationship between
two objects is inferred and a certain weight is attached
if a line connects the two.
After inferring all "likely" geometrical relationships,
the system displays the inference to the designer in two
ways: (1) In the pict editor view, colored dotted lines
indicate the inferred geometrical relationships - in Fig-
Figure

ure 4, for example, dotted horizontal lines indicate that
graphical objects along the lines are aligned horizon-
tally. (2) In the confirmation panel (Figure 5), the system
displays its inference explicitly as textual annota-
tions, where relationships are sorted according to their
weight so that "likely" relationships are displayed first.
Color indicators next to the text show the correspondence
between annotations in the confirmation panel
and colored dotted lines in the pict editor view. The
designer selects his intended geometrical relationships
in the confirmation panel with checkboxes. Further-
more, the natural geometrical relationships will have
been pre-selected and thus the designer does not usually
have to alter the selection. Only when the system's
inference is different from his intention, he has to alter
the selections in the panel. 1
The designer then inputs the sample ASR data that
would correspond to the example visualizations into the
ASR sample editor. The editor is merely a pair of text-input
panels, which could be edited at any time by the
designer (Figure 6).
Then, the designer selects the "Generate Rule" command
from the menu, and the automated rule generation
starts: First, the variables are assigned to each
parameter in the ASR clauses (Step 2 in Figure 3).
Some of the variables are generalized so that they accept
arbitrary number of arguments. By all means,
it is not possible to determine which part in a given
example should be generalized, without any assumptions
or explicit clues. For this purpose, in TRIP3 we
assume that a list structure in a sample ASR clause
indicates that the data there should be generalized.
In our organization diagram example, generalization is
applicable to the list structure [heinlein, clarke,
herbert] so that there could be arbitrary number of
workers managed by a boss. This clue allows the system
to generate the mapping rules which can align any
number of workers vertically in the visual representa-
tion. More specifically, the first parameter hogan is
replaced with a variable V1 (recall that capitalized letters
represent variables in Prolog), and the second list
parameter [heinlein, clarke, herbert] with a list
variable [V2-V3].
The system then generates the mapping rules such
that appropriate parameters in the ASR and VSR
1 Note that this scheme is advantageous over Peridot[18] in
that multiple relationships can be specified at once, whereas in
Peridot one has to go through a series of modal dialogues.
clauses are replaced with variables (Step 3 in Figure 3).
In this step, global generalization of VSR clauses is
also performed. In this example, three connect VSR
clauses, each of which represents a line between the boss
and a worker, are combined into one generalized VSR
clause connect([V1],[V2-V3]).
As mentioned above in Subsection 2.1, when the rule
is applied to other data, the variables V1 and [V2-V3]
are unified with the actual ASR clause parameters so
that the VSR clauses are generated with the values
associated with the variables. Figure 7 and Figure 8
show the snapshot of the system applying the above-mentioned
mapping rule to a more complex instance of
the organization data and visualizing its corresponding
organization diagram.
The inverse mapping rules are also similarly generated
so as to allow the user to edit the picture and
reflect the modification of the picture to the application
data. In this organization diagram example in

Figure

8, if the user draws a new person george next
to edward, two new ASR clauses, person(g,george),
organization(e,[g]) will be added to the application
data, reflecting the user's intention. This feature is directly
inherited from TRIP2[25], in that the interface is
not a structured editor for some specific data - rather,
the users simply draw rectangles or circles as if they
were using freehand, object-oriented drawing systems
such as MacDraw.

Figure

7: ASR Data of an
Organization (Editable)

Figure

8: The Visualized
Organization Diagram
4 Implementation of TRIP3 -
A PBVE System
4.1 System Overview
We have implemented our prototype system TRIP3
that realizes the PBVE framework on NeXTStation
using Objective-C and Prolog. Figure 9 illustrates
the system overview of TRIP3.
The system supports two phases: the rule generation
phase and the rule application phase. In the rule generation
phase, a designer provides the sample ASR clauses
and draws its corresponding picture using a MacDraw-
like editor. 3 The spatial parser converts the picture into
2 NeXT is a trademark of NeXT, Incorporated.
3 In the current prototype system, we employ the same editor
for both rule generation and rule application.
Visual
Mapping
Inverse Visual
Mapping
Spatial
Parser
COOL
Mapping
Rule
Inverse
Mapping Rule
Rule Generation Phase
Spatial
Parser
ASR Example
VSR Example
PR Example
ASR
VSR
PR
Inference
Engine
Rule Application Phase

Figure

9: TRIP3 System Overview
VSR clauses which reflect the designer's intention about
the geometrical relationship of visual objects. The inference
engine generates the mapping rules from the
example VSR clauses the spatial parser generates and
the example ASR clauses the designer inputs.
The rule application phase is an enhanced version of
our TRIP2 system[25]. The user applies the generated
rules to convert application data into its visual representation
and vice versa. COOL solves the geometrical
constraints in VSR and generates the PR. Conversely
the spatial parser converts the PR images into VSR
clauses, which are converted to ASR by the generated
inverse mapping rules.
The system generates mapping rules from sample
ASR and VSR clauses through the process overviewed
in Section 3. In order to achieve such a functionality,
the actual implementation must support the followings:
1. Before generating the mapping rules, the system
must check whether it has enough VSR clauses
(i.e., geometrical constraints) to ensure that all objects
are sufficiently constrained.
2. The system must be able to generate two styles of
mapping rules: one for non-recursive data struc-
tures, and the other for recursive data structures.
The following subsections discuss the implementation
of TRIP3, focusing on the above two issues.
4.2 Checking for Object Stability
When the system generates visual images (PR) corresponding
to the VSR clauses, the constraint solver
COOL solves the simultaneous equations extracted
from the VSR clauses. For instance, a horizontal
relationship generates the constraints "object[0].y
meaning that all
the objects must have the same Y-coordinates. Here the
VSR clauses must supply sufficient equations so that
the system is not underconstrained. 4 If some objects
are not sufficiently constrained, their positions are indeterminate
- we refer such "floating" objects as being
unstable. To be more specific, we refer to the objects
whose X- (or, Y-) coordinate is geometrically sufficiently
constrained but Y- (respectively, X-) coordinate
is underconstrained as x-stable (or correspondingly, y-
stable). Stable objects have both X- and Y-coordinates
geometrically sufficiently constrained.
To ensure that a mapping rule generates only stable
objects, it is necessary to check that there are enough
VSR relationships for the system to generate the mapping
rules from the examples. The algorithm for checking
whether all objects are stable is described below in
an Objective-C-like pseudocode:
select startObject;
/* '-' denotes a set. */
do-
for each anObject in stableObjects do
for each aRelation that includes anObject do
if([aRelation checkStableObjects:anObject])
The key to the algorithm is the message expression
[aRelation checkStableObjects:anObject].
ARelation is one geometrical relationship object that
a stable object anObject is involved with. The
method transfers the objects that are involved with
this relationship among the sets unstableObjects,
xStableObjects, yStableObjects, and stableObjects,
depending on the class of each relationship, e.g.,
horizontal; that is to say, the action of the method
checkStableObjects: is different, depending on the
class of the receiver aRelation, thereby facilitating different
sufficient conditions for achieving object stability
for each relationship. For example, since the relationship
horizontal constrains all the Y-coordinates of
the objects involved with the relationship to be equiv-
alent, [horizontal checkStableObjects:anObject]
roughly performs the followings:
ffl if an object that is involved with the relationship
is in the unstableObjects set, transfer the object
to the yStableObjects set.
ffl if an object that is involved with the relationship
is in the xStableObjects set, transfer the object
to the stableObjects set.
Another example is the relationship x-center, which
constrains the X-coordinate of an object to be at the
center of the X-coordinates of all other objects involved
with the relationship. In this case, the X-coordinate
of the object could be determined only
when the X-coordinates of all the other objects are
stable. If so, the object is transferred from the set
4 Note that COOL gracefully handles overconstrained situations
to some degree by distributing the errors using the least
square method[14].
unstableObjects to the set xStableObjects, or from
the set yStableObjects to the set stableObjects ac-
cordingly. In this way, the loop continues while there
remains an object that can be transferred.
When the loop terminates, the system checks
whether unstableObjects, xStableObjects, and
yStableObjects are empty. If any of these sets are non-
empty, then not all objects are stable, and the system
attempts to heuristically generate new VSR clauses to
enforce these objects to be stable. In the organization
diagram (Figure 3), the rectangle heinlein is stable
with horizontal and vertical, whereas the rectangles
clarke and herbert are only x-stable with vertical.
There must be, therefore, a constraint which determines
the Y-coordinates of these rectangles. TRIP3 adds the
necessary VSR clauses as if a human designer would
when he was offered this example picture and asked to
draw another diagram with a different number of objects

Given this particular example picture, a human designer
would generalize the picture such that the worker
rectangles in the column are aligned vertically with certain
vertical gaps, because there are no other assumptions
which can determine the Y-coordinates for arbitrary
number of objects. TRIP3 attempts similar generalization
at this (VSR) level: in this case, the system
determines that the number of objects in a column
should be generalized, and generates a new VSR
clause y-order assuming that these objects are aligned
with a vertical gap extracted from the example pic-
ture. As a result, a VSR clause y-order([heinlein,
clarke, herbert], 20) is added, meaning that the
objects heinlein, clarke, and herbert are vertically
aligned with 20 unit vertical gaps.
If there are any unstable objects remaining even after
such additions, the system informs the designer that it
is not provided with enough examples to make all the
objects be stable. In this case, the designer must specify
geometrical relationships explicitly according to his
intended layout with the relationship browser shown in

Figure

10. For instance, if the designer has to specify
that the horizontal gap between two objects is con-
strained, he selects the objects in the pict editor and
specifies the x-order relationship in the menu of the
relationship browser.
Average
Contain
Horizontal
Delete
Center
Generate

Figure

10: Relationship Browser
4.3 Generation of Mapping Rules
For the actual generation of the mapping rules, TRIP3
employs 'templates', which serve to define common
styles of the mapping rules. The current implementation
provides two types of templates: one for non-recursive
data structures such as the organization example
in Section 3, and the other for recursive data
structures such as trees.
4.3.1 Generating Mapping Rules for Non-Recursive
Data Structure
The style of mapping rules for non-recursive data structure
is as follows:
mapping-rule :-
fail.
As mentioned above in Subsection 2.1, when this rule
is invoked, variables in ASR clauses (line (1),
are unified with parameters of the ASR facts in the
Prolog database. Lines (3),
then generate VSR
clauses with these unified variables. Line (5) (i.e., fail)
invokes the backtrack mechanism of Prolog and forces
enumeration of all matching ASR clauses to be converted
to VSR clauses.
4.3.2 Generating Mapping Rules for Recursive
Data Structure
The process of generating mapping rules for recursive
data structures is different from that for non-recursive
data structures. It is difficult to generally infer which
part in a sample picture is recursive: in fact, inferring
recursion is the most difficult problem in PBE. In
TRIP3, we take the advantage of the fact that our system
is interactive, and let the designer specify the recursion
explicitly when he draws the example picture.
This is not only pragmatic, but we find that it is in
fact easier for the designer to specify the example picture
that includes explicit clues for recursion, since he
would already have the idea of how his data would be
visualized recursively in the first place.
For clarity, we describe the process of generating
mapping rules for trees. First, when the designer draws
sample pictures, he shows explicitly which part of the
sample picture is recursive, i.e., specifies which part
could include recursive occurrence of the diagram itself

Figure

11 shows the interior node of a tree; the
two dotted rectangles represent recursive occurrences
of the diagram. Second, the designer shows how the
recursive data structure terminates, i.e., he draws the
terminal case of the recursive structure. Figure 12 is the
terminal case of a tree, which is the leaf. The designer
then inputs sample ASR data as in Figure 13. Note
that recursive occurrences in the sample ASR clauses
are represented as rec0 and rec1 - the actual ASR
data would have the recursive occurrences of itself in
place of these terms as shown in Figure 14. Third, the
system employs the template for recursive data struc-
tures. The generated mapping rule for the tree diagram
is as follows: 5
5 The rule is simplified for brevity from the rule actually
generated.
%% Rule for the recursive case
recursive([H-L]),
horizontal([H-L]),
fail.
%% Rule for the terminal case
fail.
The mapping rule consists of two subrules: one for
the recursive case, and the other for the terminal case.
Line (1) invokes the recursive application of the rule to
the recursive occurrences of term tree() in [H-L]. Line
(2) and (6) generate nodes corresponding to X. Lines (3)
to (5) generate VSR clauses that constrain geometrical
relationships among the nodes.

Figure

14 is an instance of ASR data that represents
a tree, and the mapping rules generated above converts
it into a tree diagram shown in Figure 15.
rec1
rec0

Figure

11: PR Example
for a Tree Diagram (Re-
cursive)
obj6

Figure

12: PR Example
for a Tree Diagram (Ter-
minal)

Figure

13: ASR Example
for a Tree

Figure

14: ASR Data
5 Further Examples
We present further examples of generation of graphical
interfaces via PBVE using TRIP3: (1) a visual editor
for the ER diagram, that is widely employed to represent
database schema, and (2) a visualizer for the cons-
cell diagram, often used to illustrate data structures of
S-expressions in Lisp.

Figure

15: The Tree Diagram

Figure

and Figure 17 are snapshots of when a designer
inputs sample database schema and draws a sample
picture of the corresponding ER diagram. In this
example, geometrical relationships such as horizontal
or vertical are not important, and instead topological
relationships such as adjacent (line connection) are
essential. 6 Figure 19 shows an ER diagram that corresponds
to a more complex database schema in Figure
generated with the rules. The layout of entities is automatically
determined by the graph layout module[13]
in COOL.

Figure

shows a sample picture of the cons-cell diagram
that the designer has drawn. The two dotted
rectangles represent recursive occurrences of the diagram
itself. Note the shaded rectangle: this indicates
that the designer has constructed a group of objects
by specifying that the small rectangle and the left dotted
rectangle form a group. With this grouping mech-
anism, the designer indicates that the bounding box
of the group (the shaded rectangle) and the right dotted
rectangle must be aligned horizontally with a fixed
gap. (Without this specification, the two recursive occurrences
could overlap each other.) Figure 20 is the
corresponding sample ASR data. The mapping rules
generated from this example convert the ASR data in

Figure

22 into the cons-cell diagram in Figure 23.

Figure

Example
Database Schema

Figure

17: Example ER
Diagram
6 Note that in the current implementation, geometrical relationships
have greater weight than topological ones in the inference
engine, and the designer has to approve topological relationships
in the confirmation panel explicitly.

Figure

Schema

Figure

19: Actual ER
Diagram

Figure

20: Sample Cons-
Cell Data
rec1
rec4

Figure

Cons-Cell Diagram
6 Related Work
Here we review the previous work related to TRIP3 in
direct manipulation, programming by example (PBE),
and constraints among graphical objects.
Many researchers have proposed sophisticated ways
of integrating direct manipulation into programming
environments. Unidraw[27] provides a framework
for building domain-specific graphical editors. The
framework abstracts direct manipulation, properties
of graphical objects, their behavior, and their inter-
communications into an extensible C++ class library.
Tree/Graph Editor[15] provides a flexible direct manipulation
graph editor that can be easily integrated into
applications. Many user interface management systems
(UIMS) employ direct manipulation to let programmers

Figure

22: Actual Cons-
Cell Data

Figure

23: Actual Cons-
Cell Diagram
manipulate the layout of widgets, their properties, reactions
to the users when the programmers define new
windows, and so forth[10, 11, 21, 22, 26].
Compared to these systems, TRIP3 has an innovative
advantage: direct manipulation graphical editors
integrated to applications are customized according to
specific application data with extensive procedural pro-
gramming. Instead, TRIP3 offers one generic direct
manipulation graphical editor, and realizes interactive
GUI solely with declarative mapping rules, which can
be programmed easily, compared to conventional procedural
programming. Furthermore, TRIP3 overcomes
the disadvantages of text-based programming of rules
by employing direct manipulation in its programming
environment.
ffl With direct manipulation, it is easy to determine
various kinds of parameters of objects such as the
width of box. A designer can see the exact images
that generated rules will create.
ffl Generating relationships among objects by drawing
the picture prevents unintended specification of
conflicting constraints. A designer can easily realize
his intended visualization of application-specific
data.
To compensate for the lack of the abstraction capability
with direct manipulation, which is essential to
programming, we employ the programming by example
(PBE) paradigm extended to handle visual examples.
Although PBE is not necessarily adequate for all general
programming, it can nevertheless provide sufficient
means for specifying certain types of programs intended
for non-programmers, especially in GUI programming.
The use of PBE in GUI programming can be roughly
categorized into those by the end-user, and those by
the GUI designer/programmer. The former is usually
an elaborate macro facility of the UIMS: for example,
Eager[4] uses this paradigm to create macro programs
for HyperCard 7 on a Macintosh 8 . Metamouse[17] is a
system enabling the user of a drawing program to specify
graphical procedures by supplying example execution
traces - the system generalizes the traces with
inductive inference and generates generalized drawing
procedures. Demonstrational text formatter[20] allows
the user to directly manipulate the textual formatting
of one example, and then the system automatically generates
the macro by generalizing the example.
The latter case is seen in systems such as Peridot[18],
where programmers can generate widgets, e.g., menus,
by drawing their sample pictures, and UofA*[24] UIMS,
which infers the programmer's intention on the layout of
widgets. Both Peridot and UofA* generalize the trace of
drawing action by the programmer or the layout of widgets
to create imperative programs and simple geometrical
constraints for realizing low-level widgets and/or
their layouts. By contrast, TRIP3 generalizes the correspondence
between high-level application data and its
visual representation and generates declarative translation
rules between them. DEMO[28] enables creation of
GUI by demonstrating the behavior with an enhanced
7 HyperCard is a registered trademark of Apple Computer,
Incorporated.
8 Macintosh is a registered trademark of Apple Computer,
Incorporated.
drawing editor, but does not provide a generalization
mechanism for abstractions. Oak[26] facilitates creation
of widgets by composing primitive constraints via direct
manipulation, but the scope of its generalization is confined
to repetitive patterns in widget geometry.
The novelty of TRIP3 over the systems in both PBE
categories is that these systems employ demonstration
for programming of relatively low-level aspect of GUI
programming, whereas TRIP3 concentrates on demonstrational
programming of high-level application semantics

TRIP3 also employs constraints to express relationships
among graphical objects[14, 12]. ThingLab[1,
6, 7] is a graphical simulation laboratory which uses
constraints to represent relationships among objects.
Juno[23] is a constraint-based graphics system, that
enables users to manipulate graphical objects directly.
The interactive graph layout system[9] employs hierarchical
layout algorithms with constraints - users can
emphasize a certain part in a large graph by employing
the most suitable layout algorithm for that part. Many
UIMS's, including Peridot[19, 18], Garnet[21, 22], Pen-
guims UIMS[10, 11], and Oak[26] employ constraints to
location, their behavior and handle
propagation of values.
7 Conclusion and Future Work
We have focused on the difficulty in creating GUI of
high-level application data. To solve the problem, we
propose an automatic generation of declarative translation
rules from examples. To emphasize that examples
are visual images, we call this paradigm programming
by visual example.
Our prototype system TRIP3 lets the designer draw
visual examples of application GUI with direct manip-
ulation. The designer does not need to declare the relationships
among the objects explicitly. Instead, the
system infers the relationships and the designer merely
needs to check the inference. The system generalizes
the visual examples and the example application data,
and generates the appropriate visual mapping and the
inverse visual mapping rules.
To conclude the paper, here are some of the future
work under consideration. First, we have a strong motivation
to extend the applicability of the system. Because
the current implementation predefines the style
of mapping rules, the system supports only a certain
style of visualization, such as generalization on the list
of items. By devising a more powerful generalization
mechanism, the system would be able to handle more
complex application data. Another approach is to incorporate
the meta-rules feature that determines how
the mapping rules are generated in the rule generation
phase.
Second, TRIP3 does not redraw objects to satisfy all
the constraints after a designer confirms each new re-
lationship. Since the current implementation realizes
the communication between the Objective-C process
(which handles the drawing editor), and the Prolog process
(which serves as the inference engine), with files,
TRIP3 is not fast enough to achieve real-time redraw.
With a faster communication mechanism, this problem
could be solved.
Third, TRIP3 does not support incremental refinement
of the mapping rules: that is, once the designer
generates the mapping rules, he cannot refine
the rules by providing additional examples. Kurlander
and Feiner's multiple snapshots scheme[16] could be
employed for extracting geometrical constraints from a
series of examples, and we are currently investigating
its applicability in the context of our framework.
Fourth, and the most important issue, the bi-directional
translation model of TRIP2[25] needs to be
improved. TRIP[14] originally focused on the translation
from application data to pictorial data and its
model was originally intended for one-way transla-
tion. The model we devised in TRIP2 is derived from
this one-way model, and hence has some rough edges,
thereby requiring separate rules for visual mapping and
its inverse[25]: for example, the inverse mapping rules
are deliberately modified so that the size of graphical
object is ignored when converting the objects into ASR
clauses. We are refining the model so that a single rule
would suffice for both directions.



--R


The Information Visualizer
Visualizing Concurrent Computations

Worlds in Worlds
A Module Mechanism for Constraints in Smalltalk
An Incremental Constraint Solver

Interactive Graph Layout
Interactive Specification of Flexible User Interface Displays
Smoothly Integrating Rule-Based Techniques Into A Direct Manipulation Iterface Builder
Visualizing Abstract Objects and Rela- tions
An Algorithm for Drawing General Undirected Graphs
A General Framework for Visualizing Abstract Objects and Relations
Requirements for an Extensible Object-Oriented Tree/Graph Editor
Inferring Constraints from Multiple Snapshots
Inducing Programs in a Direct-Manipulation Environment
Creating User Interfaces by Demonstra- tion
Creating User Interfaces Using Programming by Example
Text Formatting by Demonstration

Creating Graphical Interactive Application Objects by Demonstration

Automating the Lexical and Syntactic Design of Graphical User Interfaces

Creating Visual Objects by Direct Manipulation
Unidraw: A Frame-work for Building Domain-Specific Graphical Editors
A Demonstrational Technique For Developing Interfaces With Dynamically Created Objects
--TR
Constraint-based tools for building user interfaces
Creating user interfaces by demonstration
Human-computer interface development: concepts and systems for its management
An algorithm for drawing general undirected graphs
Inducing programs in a direct-manipulation environment
Creating graphical interactive application objects by demonstration
Unidraw: a framework for building domain-specific
A module mechanism for constraints in Smalltalk
An incremental constraint solver
Creating user interfaces using programming by example, visual programming, and constraints
Garnet
Worlds within worlds: metaphors for exploring n-dimensional virtual worlds
Requirements for an extensible object-oriented tree/graph editor
Interactive specification of flexible user interface displays
A general framework for visualizing abstract objects and relations
Automating the lexical and syntactic design of graphical user interfaces
EAGER
The information visualizer, an information workspace
Text formatting by demonstration
Interactive graph layout
Smoothly integrating rule-based techniques into a direct manipulation interface builder
A general framework for Bi-directional translation between abstract and pictorial data
A demonstrational technique for developing interfaces with dynamically created objects
Juno, a constraint-based graphics system
Visualizing Abstract Objects and Relations

--CTR
Douglas C. Kohlert , Dan R. Olsen, Jr., Pictures as input data, Proceedings of the SIGCHI conference on Human factors in computing systems, p.464-471, May 07-11, 1995, Denver, Colorado, United States
Ken Miyashita , Satoshi Matsuoka , Shin Takahashi , Akinori Yonezawa, Interactive generation of graphical user interfaces by multiple visual examples, Proceedings of the 7th annual ACM symposium on User interface software and technology, p.85-94, November 02-04, 1994, Marina del Rey, California, United States
Pierre Dragicevic , Stphane Chatty , David Thevenin , Jean-Luc Vinot, Artistic resizing: a technique for rich scale-sensitive vector graphics, Proceedings of the 18th annual ACM symposium on User interface software and technology, October 23-26, 2005, Seattle, WA, USA
Satoshi Matsuoka , Shin Takahashi , Tomihisa Kamada , Akinori Yonezawa, A general framework for bidirectional translation between abstract and pictorial data, ACM Transactions on Information Systems (TOIS), v.10 n.4, p.408-437, Oct. 1992
Margaret M. Burnett , Herkimer J. Gottfried, Graphical definitions: expanding spreadsheet languages through direct manipulation and gestures, ACM Transactions on Computer-Human Interaction (TOCHI), v.5 n.1, p.1-33, March 1998
Shin Takahashi , Satoshi Matsuoka , Ken Miyashita , Hiroshi Hosobe , Tomihisa Kamada, A Constraint-Based Approach for Visualization and Animation, Constraints, v.3 n.1, p.61-86, April 1998
Margaret Burnett , John Atwood , Rebecca Walpole Djang , James Reichwein , Herkimer Gottfried , Sherry Yang, Forms/3: A first-order visual language to explore the boundaries of the spreadsheet paradigm, Journal of Functional Programming, v.11 n.2, p.155-206, March 2001
constraints;graphical user interface;direct manipulation;visualization;layouts;programming by example