November 8-14, 1997

Crowne Plaza Hotel, Seattle, USA

**Alan Borning**- Dept. of Computer Science and Engineering
- University of Washington
- Box 352350
- Seattle, WA 98195-2350
- http://www.cs.washington.edu/homes/borning
**Richard Lin**- Department of Computer Science
- Monash University
- Clayton, Victoria 3168, AUSTRALIA
- http://www.cs.monash.edu.au/~rlin
**Kim Marriott**- Department of Computer Science
- Monash University
- Clayton, Victoria 3168, AUSTRALIA
- http://www.cs.monash.edu.au/~marriott

Constraints can be used to specify the desired layout of a web document, and also the behaviour of embedded applets. We present a system architecture in which both the author and the viewer can impose page layout constraints, some required and some preferential. The final appearance of the web page is thus the result of negotiation between author and viewer, where this negotiation is carried out by solving the set of required and preferential constraints imposed by both parties. We identify two plausible system architectures, based on different ways of dividing the work of constraint solving between web server and web client. Finally, we describe an implementation of a prototype constraint-based web authoring system and viewer, which also provides constraint-based embedded applets.

constraints, web, HTML

- Introduction
- Constraint-Based Page Layout
- Constraint-Based Applets
- Architecture and Implementation Issues
- Constraint Satisfaction Algorithms
- A Prototype Implementation and its Evaluation
- Related Work
- Future Work and Conclusion
- Acknowledgements
- Bibliography

The explosive growth of the web has demonstrated the power of this new medium. However, current web authoring tools allow the author to create documents using the fixed set of available HTML codes, but not to specify complex relationships among parts of the document in any convenient way. On the viewing side, web documents are often less flexible than one might like. Typically the user of a web browser has only small control over the appearance of the presented information -- the viewer can resize the browser or set default font information, but not much more. More sophisticated interactions are available, but only as a special case when provided by the author, by filling in a form, or interacting with an applet embedded in the document.

A constraint is simply a statement of a relation (in the mathematical
sense) that we would like to have hold. Constraints have been used for
many years in interactive graphical applications for such things as specifying
window and page layout, specifying relationships among parts of a drawing,
specifying animations, maintaining consistency between application data
and a view of that data, maintaining consistency between multiple views,
and representing physical laws in simulations. They allow the designer
to specify *what* are the desired properties of the system, rather
than *how* these properties are to be maintained.

It is thus natural to consider constraint-based tools to aid in authoring
web documents. We describe a system that allows web authors to employ constraints
to specify page layout, including figure placement and column widths and
spacing. Some of these constraints will be requirements that must be satisfied,
while others may be preferences of different strengths that can be relaxed
if need be. In addition, authors can use several *constraint style sheets*
to specify alternate sets of constraints to be used under different circumstances,
for example, for a one versus a two-column layout. The conditions under
which a style sheet is applicable are, of course, also specified as constraints.
Finally, constraints can also be used to specify the behaviour of applets,
allowing such applets to be created with much less effort than would be
needed to program them in the standard way.

Constraints may be imposed by the viewer as well as by the author. Like
those of the author, some of the viewer's constraints can be preferences
as well as requirements. The final appearance of the document is thus in
effect the result of a *negotiation* between the author and the viewer
-- where this negotiation is carried out by solving the set of required
and preferential constraints imposed by both parties.

This negotiation model leads to two possible system architectures. In one model, both the web authoring tool and the web viewer can perform runtime constraint solving. The web author uses the solver while constructing and testing the pages and applets, while the viewer uses a different solver (on the viewing machine) to solve the combined constraints from the author and viewer to determine the final page layout. In this case a compact representation of the constraints, along with the content of the page, additional layout information, and applets, is shipped over the network for each page. In addition, the runtime solver must be shipped (once) and saved on the viewer's machine.

In the other model, the web author again uses a powerful runtime constraint
solver, but a more restricted set of constraints is available to the viewer.
The authoring tool compiles a Java program representing a plan for satisfying
the author's constraints and the predetermined kinds of constraints that
the viewer may impose. This program is then shipped to the viewer's machine
-- so that a runtime constraint solver is not needed on the client side.
A combination of the two approaches is also possible -- and in fact our
prototype uses such a combination. These architectural considerations are
discussed in more detail in Section **Architecture
and Implementation Issues**.

The paper is organized as follows. We first demonstrate that constraints
provide important functionality for many web applications. In
Section **Constraint-Based
Page Layout** we describe constraint-based web page layout and the
negotiation model in more detail. Section **Constraint-Based
Applets** contains a discussion of constraint-based applets. Section
**Architecture and Implementation Issues**
contains an analysis of the requirements on the constraint solver, and
of different ways the constraint solving responsibilities can be partitioned
between client and server, while Section **Constraint
Satisfaction Algorithms** describes the two constraint satisfaction
algorithms we employ. Section **A Prototype Implementation
and its Evaluation** describes our prototype implementation. The
prototype has good interactive performance for both author and viewer,
and also demonstrates the feasibility of both server-side and client-side
constraint solving. Finally, Sections **Related Work**
and **Future Work and Conclusion** discuss
related work, and conclusions and directions for future work.

With current document markup languages, such as HTML, the layout of the page is rather static and fixed by the designer. In principle the client has the ability to change fonts and size of fonts and to resize the document. In practice, however, this freedom is limited, since if they are significantly changed from what the designer intended the document's appearance will often be unsatisfactory. The problem is that current markup languages do not provide the designer with the capability to control precisely how the layout of the document should change if these parameters are modified.

A solution to this problem is to use constraints to specify the core aspects of the design layout. The constraints capture the ``semantics'' of the design, those aspects that must hold true for the layout to be appealing. The designer can specify placement of the document elements using linear arithmetic equalities and inequalities. Such constraints allow easy specification of table, column, and image placement in a way that scales gracefully.

As an example, consider the page layout shown in Figure 1a. We require that the text is arranged in two columns, that figures A and B are centered in the first and second columns respectively, and that the tops of the two figures are aligned horizontally. These layout constraints are captured by the following equalities and inequalities:

(1) *PW = LG + MG + RG + CW _{1} + CW_{2}*

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

Constraint (1) states that the page width, *PW*, is the sum of
the widths of the left, middle and right gutters *LG*, *MG*,
and *RG*, and the two columns, *CW _{1} *and

For a given value of the page width *PW* we can find a solution
to the other variables that satisfies these constraints and that gives
us a layout. For instance, if *PW* = 21.7 cm then *LG* = *RG*
= *MG* = 0.5 cm and *CW _{1} = CW_{2 }*= 10 cm.
Conversely, if

This model is, however, a little too simple. In particular it does not
allow the designer to state preferences for values. Thus in the above example,
for a given *PW* the equations do not constrain the vertical placement
of Figures A and B. Allowing preferred values permits the designer
to specify that they should be placed as closely as possible to the first
reference to these figures in the text. Preferred values also allow the
designer to give default values for parameters in the layout. (In future
versions of our system we will also use them for non-numeric attributes,
allowing the designer or viewer to state preferred values for fonts, text
size and colours.)

We therefore extend our model to allow the user to specify that an inequality
or equality is preferred but not required, so that the constraint should
be satisfied when possible but does not need to be. Constraint hierarchies
[Borning 92] formalize
such preferences. A constraint hierarchy consists of collections of constraints
each labelled with a strength. There is a distinguished strength label
*required*: such constraints must be satisfied. The other strength
labels denote preferences. There can be an arbitrary number of such strengths,
and constraints with stronger strength labels are satisfied in preference
to ones with weaker strength labels. In our example, the equalities and
inequalities given earlier are required constraints and we have used *weak*
to label non-required constraints. Given a system of constraints and preferred
values, the constraint solver must find a solution to the variables that
satisfies the required constraints and which is as close as possible to
the preferred values.

In the previous example, we have required that the columns be wide enough for Figures A and B. If they are not, then this is not an appropriate layout. For instance, if the width of Figure A and B is 10 cm, then we cannot solve the constraints when the page width is less than 21.3 cm. The obvious question now is: what happens if the constraint system is unsatisfiable for a given page width? There are two possibilities. The first is to use a scroll bar which allows the viewer to scroll over the smallest valid layout. A better solution is for the designer to provide an alternative design for the case when the page with is too small.

In this case the designer might wish to use a single column with the following constraints:

*PW = LG + CW + RG
LG = RG = 0.6 *cm

FigB.leftx = LG

FigA.width <=CW

FigB.width <=CW

PW <=26

An example layout is shown in Figure 1b.
These capture that the page has a single column of width *CW*, with
left and right gutters of width 0.6 cm, and that Figures A and B are aligned
on the left gutter, and that the column has to be wide enough to fit the
figure in. This design is valid for 12.2 <= *PW *<= 26.

To accommodate such situations, our model allows the designer to provide
multiple *constraint style sheets*. Each style sheet includes linear
arithmetic constraints that define the layout of the design and that dictate
when the design is appropriate. Constraints can be required or annotated
with a strength such as ``weak'' indicating that they are preferred. During
manipulation by the viewer, the viewing tool will choose the appropriate
style sheet and lay out the document subject to the constraints in the
sheet. As the viewer changes the requirements, the document will be redisplayed
using the current style sheet until the constraints are inconsistent with
the viewer's desires. In this case the viewing tool will choose another
style sheet for the document which is consistent with the viewers constraints.

For instance, if the viewer of our example document originally displays the document in a window of width 28 cm, then resizes the window to 20 cm, the design will change from two column to one column. If the viewer now resizes it back to 28 cm, the design will change back to two column.

This constraint-based document design model is interesting for at least two reasons. First, the content of a document is separated from its design. Indeed, a document can have more than one design, and applicability of a particular design is detailed by its constraints. When the server is queried for a document, the content and designs are sent to the client. This gives designers considerable flexibility when designing the appearance of a document, allowing them to vary the layout depending on the clients' capabilities.

Second, the layout of the document on the client is now a negotiation between the viewer and the designer, each of whom adds constraints dictating the final layout. The designer provides constraint style sheets and preferred values, while the viewer can add constraints or preferences as well. Currently such preferences are only on numeric quantities such as page width; in future versions the viewer will be able to express preferences regarding nonnumeric quantities such as colour or font family as well. These preferences might reflect either the capabilities of the viewer's terminal, such as size or whether it is monochrome, or particular needs of the viewer, for instance of a colour blind or otherwise sight impaired person.

As a more complex example of constraint-based page layout, consider the web page shown in Figure 2a and Figure 2b. These figures show two constraint style sheets, the first for a narrow page with one column layout and the second for a wider page with two column layout. In each, layout constraints ensure that the central abacus figure is centered and that the surrounding labels remain appropriately aligned as the window is resized or other edits performed. Each style sheet contains approximately 110 constraints.

In addition to using constraints for the layout of the web pages themselves,
another important application of constraints is to specify the behaviour
of applets used in web pages. Providing applets for animations, simulations,
and other kinds of interactive information is an exciting prospect. However,
currently such applets are usually produced by writing Java code. This
is a time-consuming process. A number of researchers have used constraints
for producing simulations and animations without hand-coding the program
(see Section **Related Work**). These results
are all applicable to generating applets.

The layouts of the abacus pages shown in Figure 1a and Figure 1b include two such applets, one for a Chinese abacus and another for a Japanese abacus. The constraints require each bead to remain on its respective rod, to not pass through another bead, and to remain within the boundaries established by the bars of the abacus.

The screen snapshot in Figure 3 includes another constraint-based applet, in addition to appropriate layout constraints. The applet demonstrates a theorem about quadrilaterals: given an arbitrary quadrilateral, if one bisects each side and draws lines between the midpoints the result is a parallelogram. The interactive applet allows the user to drag any corner or midpoint and see that in fact the figure in the middle remains a parallelogram. In addition to the midpoint constraints, the figure includes inequality constraints that all points must remain inside the window. Figure 4 shows four successive snapshots of the drawing. This example is a traditional demonstration of constraint-based interactive graphics -- although typically without the inequality constraints that the points lie within the window, since these inequality constraints are beyond the capabilities of most solvers, particularly when they occur in conjunction with cyclic constraints.

The Java constraint satisfaction code for the three applets was produced
automatically from the list of constraints using our recent projection-based
algorithm for constraint compilation (Section **A Projection-Based
Constraint Compilation Algorithm**). The text in
Figure 3 is in fact the first part of a paper describing this algorithm in
more detail [Harvey 97]. The algorithm takes
as input an arbitrary collection of linear equality and inequality constraints
of different strengths, which may include simultaneous equations and inequalities.
It produces straight-line, constraint-free code that repeatedly solves
the constraints for different input parameters (in this case, the position
of the mouse). An output module makes it convenient to produce code for
a variety of target languages, in this case Java.

In this section we outline the architecture of a system which supports
constraint-based document layout and constraint-based applets, and the
requirements that these place on the constraint solver. Then, in Section
**A Prototype Implementation and its Evaluation**
we describe how our prototype implementation meets these requirements.

The constraint-based document layout model has three main components: the document authoring tool, the viewing tool, and the constraint solver.

A constraint-based authoring tool is used by the designer to construct the constraint style sheets and document contents. Ideally the designer should not need to think in terms of arithmetic constraints or even be aware of the real nature of the constraints. To the designer, they are implicit in various templates and tools such as the ``horizontal alignment'' tool provided by the authoring tool.

The authoring tool should allow the designer to manipulate the document in exactly the same way as the viewer does, by resizing, changing font size, and so forth. If the designer is unhappy with the design for this choice of values then the designer should be able to provide an alternative constraint style sheet.

The viewing tool should integrate constraints from the designer with those of the viewer, check which design is appropriate, resolve the constraints, and then display the document contents using the values from the solution to place elements in the layout.

The constraint solver is a key component of this architecture. Authors use the constraint solver while laying out and testing the pages, and perhaps in constructing constraint-based applets. Viewers use the constraint system while viewing the page and interacting with constraint-based applets. The demands on the constraint solver, however, are different for authors and viewers.

Authors need the full interactive capabilities of the system. They must be able to add or delete constraints from constraint style sheets and directly manipulate elements of document.

The needs of viewers are much more easily met in the simplest case.
Here, the kinds of interaction viewers can have with the constraint system
are limited to resizing the browser or a frame, moving objects around in
the window, and perhaps interacting with an applet. However, the set of
constraints would be fixed; all that the viewers would change would be
constants in the constraints (e.g. browser width). In this case it is possible
to pre-compile constraint satisfaction plans using the projection-based
algorithm discussed in Section **A Projection-Based
Constraint Compilation Algorithm**, and just ship compiled Java code
to the client and not use a runtime solver. This has the advantages that
``constraint solving'' on the client will be extremely fast and that the
client does not need to download a complex runtime solver from the server.

A more sophisticated constraint-based browser allows the viewer to edit the constraints on the document, for example by adding additional constraints, or by editing the constraints in an applet. This case requires runtime constraint solving by the viewer as well as by the author. It also means that the viewer will need to download the constraint solver the first time it is used. (It can then be stored locally for subsequent reuse.)

In any case it is essential that constraint solving be fast. For example, each time a browser is resized (by either an author or a viewer), the constraints must be resatisfied. This requires that systems of up to several hundred constraints are solved in fractions of a second. For such performance to be possible, the solver needs to recompute a solution incrementally to the same system of constraints. It should also be fast for the designer to add or remove constraints from the design. Again, this requires an incremental approach.

It is also essential that the constraint solver handle underconstrained and overconstrained systems. One situation in which this arises is when moving one component of a web page: we want other components to remain where they are if possible (rather than gyrating wildly and arbitrarily), but at the same time we don't want them to be rigidly locked in place. If a component does need to move, it should move as little as possible. Complex layout problems with conflicting preferences are another cause of overconstrained systems.

As we have seen, the kind of constraints that arise in page layout are
primarily linear arithmetic equalities and inequalities. Our experience
with other interactive graphical constraint-based systems indicates that
simultaneous linear equalities and inequalities frequently arise. In some
cases these cyclic collections are inherent in the problem. In others the
cycles come about when the author added redundant constraints -- a cycle
*could* have been avoided by careful analysis. However, this is an
added burden on the author. Further, it is clearly contrary to the spirit
of the whole enterprise to require web authors -- particularly nonprogrammers
-- to be constantly on guard to avoid cycles and redundant constraints;
after all, one of the goals in providing constraints is to allow users
to state what relations they want to hold in a declarative fashion, leaving
it to the underlying system to enforce these relations.

Nonlinear numeric constraints arise less frequently, but are useful for constraining such attributes as angles and areas.

Another useful class of constraints are over non-numeric domains, such as fonts, colours, and strings. In contrast to the numeric constraints, however, cycles are less likely to arise in web-based applications. Also, such constraints can be more easily enforced by standard programming techniques -- thus supporting them in the constraint solver is useful but not as important as good support for numeric constraints.

We now briefly describe the two constraint satisfaction algorithms used in the work reported here, namely Cassowary and projection-based compilation. Both algorithms handle linear arithmetic equality and inequality constraints. Some of these constraints may be requirements and others preferences, where the preferences can be of different strengths. In addition, the collection of constraints may include cycles (i.e. simultaneous equalities and inequalities), redundant constraints, and incompatible preferences. Neither of the current algorithms handle nonlinear or non-numeric constraints, although we hope to provide these capabilities in future versions of our system.

Cassowary is an incremental version of the simplex algorithm, specialized for user interface applications. Details of this algorithm are given in reference [Borning 97b]. This reference also presents a closely-related algorithm, QOCA, which computes solutions based on an alternate way of trading off conflicting preferential constraints.

The simplex algorithm is a well-known and heavily studied algorithm
for finding a solution to a collection of linear equality and inequality
constraints that minimizes the value of a linear expression called the
*objective function*. However, commonly available implementations
of the simplex algorithm are not really suitable for UI applications such
as the one described in this paper.

The principal issue is incrementality. We need to solve similar problems
repeatedly, rather than solving a single problem once, and to achieve interactive
response times, very fast incremental algorithms are needed. There are
two cases. First, when moving an object with a mouse or other input device,
we typically represent this interaction as a one-way constraint relating
the mouse position to the desired *x* and *y* coordinates of
a part of the figure. For this case we must resatisfy the same collection
of constraints, differing only in the mouse location, each time the screen
is refreshed. This situation arises for both web authors and viewers, since
both will be manipulating the web document (or at least resizing the browser).
Second, when we first begin a movement, we add a constraint relating the
object being moved to the mouse position, and when the movement is completed
we remove this constraint. We may also add or remove constraints when interactively
editing a layout or applying a new constraint style sheet, and again we
would like to make these operations fast by reusing as much of the previous
solution as possible. Authors will need this last capability in any event;
viewers may or may not, depending on how much flexibility is given to the
viewer. The algorithm is fully incremental, and can be used for both the
authoring and viewing tools. (In this case a runtime constraint satisfier
is needed by the viewer's browsing program.)

The performance requirements are considerably more stringent for resolving a given set of constraints for a new mouse input position than for incrementally adding or deleting a constraint, since in the first case we need to resatisfy the constraints for every screen refresh.

To provided the needed performance, the constraint solver keeps the constraints in a normal form closely related to the basic feasible solved form employed in the simplex algorithm. An incremental version of Gauss-Jordan elimination is used if an equation is added, while an incremental version of the first phase of the simplex is used when an inequality is added.

Constraint deletion is handled by keeping track of how equations and inequalities have been used to create the normal form. That is which variables they have been used to eliminate. This ensures that removal of a constraint requires only a single pivot.

Non-required constraints are handled by use of a quasi-linear objective
function. For instance, imagine that we are editing the variable *x*
and wish to change its value to 50, and the other variables *y* and
*z* currently have the values 30 and 60. Then the solution we are
interested in minimizes the objective function

*s|x-50 | + w|y-30| + w|z-60|*

where *s* and *w* are fixed weights which ensure the strong
constraint is always strictly more important than solving any combination
of weak constraints.

Unfortunately the simplex algorithm cannot directly be used to solve optimization problems with a quasi-linear objective function. However, it is possible to transform such problems into an equivalent linear programming problem which can be solved with the second phase of the simplex algorithm.

Resolving of the constraint system for suggested values is done by first
identifying which values will be changed (in effect, incrementally adding
constraints relating these values to the *x* and *y* positions
of the mouse or to an input field). The algorithm then produces a data
structure that identifies exactly what parts of the normal form need to
be updated for changed inputs. In most cases -- typically, when the mouse
movement doesn't result in one object colliding with another -- this update
simply involves changing a small number of constants in the normal form.
When one object does first collide with another, or moves out of collision,
then one or more pivots will usually be required to restore the data structures
to their normal form. These pivots are done using a variant of the dual
simplex algorithm.

The projection-based compilation algorithm solves the same class of constraints -- namely, collections of linear equality and inequality constraints, some of which are required and others only preferred. In contrast to Cassowary, however, the algorithm uses compilation techniques to produce Java code that can be run on the viewer's machine; no runtime constraint satisfaction is needed by the viewer. The code solves the given constraints for different user inputs -- in other words, the algorithm is used to write a procedure for each part of a constrained object that the user can manipulate with the mouse. The resulting code is very efficient. However, the viewer cannot otherwise add or delete constraints. Also, on the author's side, the algorithm is a batch one -- if the collection of constraints is changed the algorithm must be run again from scratch to produce new procedures.

For example, for the quadrilateral applet shown in Figure 3 and Figure 4, the projection algorithm was used to produce eight Java procedures, one for each of the four corners of the quadrilateral and one for each of the four midpoints. Each of these procedures accepts as input the new desired position of the point being moved, along with the current positions of all the points, and updates the locations of each point to find a solution to the given constraints that exactly satisfies all of the required constraints, and that satisfies the preference that the moved point follow the mouse and the weaker preferences that each point remain at its old location.

Details of the algorithm are given in [Harvey
97]. In brief, the original set of constraints is converted into a
normal form in which the only kind of preferential constraints are ones
of the form *v*=*b* for a variable *v* and constant *b*;
all other constraints are required (i.e. we must satisfy them in any solution).
It is easy to convert any collection of linear equality and inequality
constraints into this form. We then repeatedly perform variable elimination
using a variant of Fourier's algorithm to find the permitted range of values
for the variables, given the required constraints.

A variable elimination step involves taking a set *C* of linear
equality and inequality constraints, where one of the variables in *C*
is *v*. We then produce a new set of constraints *C*', which
is free of *v*. This new set has the property that if *s* is
a solution to *C*', there exists a value for *v* such that *s*
along with this value for *v* is a solution to the original set *C*.

The elimination is performed in such an order that the *last* variable
eliminated, say *v _{n}*,
has the strongest preferential constraint

We have built a prototype of the constraint-based design model. It consists
of the three components discussed in Section **Architecture
and Implementation Issues**: document authoring tool, constraint
solver, and viewing tool. All are written in Java.

The document authoring tool allows the designer to edit the content of document which consists of text, images and figures. At any particular instant the designer views the document through a constraint style sheet consisting of linear arithmetic constraints. The designer can add or delete constraints from the style sheet and use direct manipulation to move objects around in the design. The constraint solver ensures that the placement of the objects satisfies the current constraints.

The designer can manipulate the document in exactly the same way as the viewer does. If at some point the designer is unhappy with the style sheet for this choice of values, then he or she can initiate an alternate style sheet. Initially this is a copy of the last style sheet, but by changing and removing constraints the designer constructs the new style sheet.

To indicate how to move between style sheets the designer can annotate constraints within a particular style sheet with the number of another style sheet for that page. If this constraint becomes unsatisfiable during interaction with the reader, perhaps after resizing, the other style sheet is tried. The designer is then free to move among the different style sheets.

Currently the viewing tool is derived from the document authoring tool by simply turning off some of the options. When a document is first downloaded from a server, the viewing tool and constraint solver are also downloaded. Using parameters from the viewing window, the viewer selects a design, uses the constraint solver to solve the constraints and then displays the document contents according to that design. Layout is performed by first determining the placement of the figures and images, and then placing the text around them.

The core of the implementation is the constraint solver, a Java implementation
of the Cassowary algorithm (Section **An Incremental
Simplex Algorithm**). Interaction with the constraint solver can
occur in three ways. First, a required constraint may be added to the current
set of constraints. Second, a required constraint may be deleted from the
current set of constraints. Finally, the current solution may be manipulated
by moving objects within the layout, thus providing preferred values for
several of the variables.

The performance of our prototype is very encouraging. The authoring tool provides direct manipulation of document elements with style sheets involving one hundred or more constraints at interactive speeds. This accords with our recent results for user interface construction using a Smalltalk implementation of Cassowary [Borning 97b].

A more interesting question is the performance of the prototype viewer.
To give some feel for its behaviour we have measured the performance of
our system on two benchmark documents. The first document, *simple*,
is the sample document from Figure 1a and
Figure 1b. It has two constraint style
sheets (for two-column and one-column layouts), with 27 and 23 constraints
respectively. The second document, *complex*, is the second example
shown in Figure 2a
and Figure 2b. Again it has two constraint
style sheets, with 115 and 108 constraints
respectively. We feel that *complex* is about as complex as a single
page is likely to become.

We have evaluated the performance of the viewer from a number of viewpoints. Our results are shown in Table 1. All times are in milliseconds running Netscape Gold on a Pentium 166 with 64M memory. First we give the size of the document in Kbytes and the time taken to download both the applet and the document over the local area network. The document consists of the contents plus the style sheets. In addition to the total size of the document, we also give the size of just the images in the document (which account for nearly all of the size). The viewer also needs a copy of the viewer applet. Its size is 184K, of which 65K is the runtime solver. Of course this viewer applet only needs to be downloaded once, and never if it is provided as part of the browser library. We can see that even with runtime constraint solving by the viewer, downloading the document and applet is reasonably quick.

Next we consider how long it takes to display the document the first time. This involves parsing the constraint information shipped over the network, solving the constraints, and then displaying the document. These times are satisfactory for the simple document, but not for the complex one -- however, we believe the speed of the solver can still be increased substantially. (The current performance of the Java implementation of the solver, used for these timings, is much slower than that of either our Smalltalk or C++ implementations [Borning 97b], making us optimistic that it can in fact be made substantially faster). Finally we consider how long it takes to redisplay the document after it is resized. We detail the time taken to compute the placement of objects and the time taken to actually draw the document. We also see that the redrawing speed, even when moving between style sheets, is satisfactory, with constraint solving taking roughly the same time as redrawing.

Finally, in Table 2 we give some measurements for the abacus and quadrilateral constraint-based applets. For each applet we give the size of the byte code for the animation itself and for the associated applet. We also give the time taken to resolve and redraw. These figures show that using precompiled constraint satisfaction code is extremely fast. We would expect that using precompiled code for documents (in addition to using it for applets) would result in much faster solving times as compared with using a runtime solver, at a cost in flexibility.

Regarding the web and HTML, constraint style sheets are closely related to cascaded style sheets [Lie 96], which have been recommended for adoption by the World Wide Web Consortium. Cascaded style sheets allow both the author and reader to provide rules that specify various attributes of a web document. Rules can be given weights, which are used to resolve conflicts among rules from different style sheets. A class mechanism provides inheritance of specifications. The fundamental difference between cascaded style sheets and constraint style sheets is that cascaded style sheets allow one to specify a particular value for a given attribute (or in some cases a percentage), while constraint style sheets allow general constraints, i.e. partial specifications, to be given for these attributes. For example, a cascaded style sheet can include a rule specifying that the left margin of a layout element is a particular value. On the other hand, a constraint style sheet can include an arbitrary linear constraint on the left margin, which might constrain it to be less than twice some other value. (Constraining it to have a particular value is just a special case of the general constraint mechanism.) Another difference is that we allow the appearance to change interactively as the viewer resizes the page. This means that the server must provide multiple style files, and the viewer must choose the style file that is compatible with the reader's requirements, and change this choice dynamically. In addition, we also support figure layout (although a similar extension to cascaded style sheets is expected [Lie 96] in future versions). On the other hand, cascaded style sheets include a class and inheritance mechanism, which isn't provided in our current design.

The `<table>` environment in HTML 3.0 can be viewed as
providing certain constraints, including preferences as well as requirements,
for example, desired cell width expressed either as an absolute quantity
(in pixels) or as a percentage of the total table width; again, however,
there is no general constraint capability.

Regarding constraints, there is a long history of using constraints in user interfaces and interactive systems, beginning with Ivan Sutherland's pioneering Sketchpad system [Sutherland 63]. Most of the current systems use one-way constraints (e.g. [Myers 96b]), or local propagation algorithms for acyclic collections of multi-way constraints (e.g. [Sannella 93, Vander Zanden 96]). UI systems that handle simultaneous linear equations include DETAIL [Hosobe 96] and Ultraviolet [Borning 95]. Two systems that handle simultaneous linear equalities and inequalities are QOCA [Borning 97b, Helm 92a, Helm 92b] and Cassowary [Borning 97b]. Systems such as ThingLab [Borning 81] have also used constraints for constructing interactive simulations. Systems that support constraint-based animation include Animus [Duisberg 87] and Amulet [Myers 96a].

IDEAL [Van Wyk 82] is an early system specifically designed for page layout applications. Harada, Witkin, and Baraff [Harada 95] describe the use of physically-based modelling for a variety of interactive modelling tasks, including page layout. Their system allows mixed continuous/discrete models, in which a given set of constraints is used until an object being dragged is blocked by geometric constraints; at this point a local search is performed for a nearby state in which all constraints are again satisfied. The U-term language [Cruz 93] is a more recent constraint-based visual language for specifying the display of data. The DOODLE Visualization Tool [Averbuch 96] provides visualizations of information in an object-oriented database, using U-terms to specify selection and presentation criteria. The interface is implemented in Java, making it accessible from Java-capable web browsers. Another Java-based system is subArctic [Hudson 96], which provides a one-way constraint solver as part of its Java toolkit (more sophisticated solvers are planned).

Weitzman and Wittenburg [Weitzman 93, Weitzman 94] have investigated the use of relational grammars for document design. Their work is closely related to ours since in effect they use a grammar which details a class of constraint layout styles. However their interest is in specifying and recognizing layout styles rather than constraint solving. They only consider rather weak constraint solving techniques based on local propagation. Indeed, it seems rather natural to combine their work with ours.

The work reported here differs from this prior work on constraints and relational grammars in two respects: first, through its support of a negotiation model in which author and reader both contribute constraints that determine the appearance of the document; and second, in the integration of constraints with web documents.

Our plans for future work include the following projects.

First, we want to support a wider range of constraints for web authors and viewers to use. These will include constraints on non-numeric attributes such as fonts and colours. This will require us to extend our Java constraint solver to include a local propagation component, so that we can solve constraints on non-numeric as well as numeric attributes. For this extension we will use an architecture derived from the Ultraviolet constraint solver [Borning 97a] to integrate the local propagation solver with the simplex-based solver. We also want to support constraints on frames.

Second, we plan to design and evaluate better user interfaces for the document authoring tool. The current interface is primitive. Our goal here is to find good metaphors for designing with constraints, and to identify constraint-based design templates that the designer can readily understand and yet provide access to the full power of the constraint solver -- a challenging task.

Third, we plan to design a constraint-based animation authoring tool, which we hope will allow authors to construct animations more easily than using present techniques. The initial purpose of this tool will be to provide animations to complement the more static images in our constraint-based web documents, but in the longer term it should be useful for other tasks as well. Constraints will be used to specify trajectories, start and stop times for a movement, and relationships among different objects in the animation.

Fourth and finally, we want to explore how HTML (or other standard markup languages) can be extended by providing statements within the markup language itself to specify constraints, resulting in e.g. CHTML.

In conclusion, we have described an initial foray into applying constraint technology to the web. The results so far are preliminary but very encouraging, and we believe this will be a promising area for future research and subsequent real-world application.

We gratefully acknowledge the help of Andrew Kelly, who programmed the Java version of the Cassowary algorithm. Thanks also to Corey Anderson and the referees for comments on the drafts. This project has been funded in part by the National Science Foundation under Grants IRI-9302249 and CCR-9402551 and in part by a grant from the Australian Research Council. Alan Borning's visit to Monash University and the University of Melbourne was sponsored in part by a Fulbright award.

- [Averbuch 96]
- Michael Averbuch, Isabel F. Cruz, Wendy T. Lucas, and Melissa Radzyminski. As you like it: Tailorable information visualization. Technical Report DBVIS-TR-2, Database Visualization Research Group, Tufts University, Medford, MA, October 1996.
- [Borning 81]
- Alan Borning. The programming language aspects of
ThingLab, a constraint-oriented
simulation laboratory.
*ACM Transactions on Programming Languages and Systems*, 3(4):353-387, October 1981. - [Borning 92]
- Alan Borning, Bjorn Freeman-Benson, and Molly Wilson. Constraint hierarchies.
*Lisp and Symbolic Computation*, 5(3):223-270, September 1992. - [Borning 95]
- Alan Borning and Bjorn Freeman-Benson. The OTI constraint solver:
A constraint library for constructing interactive graphical user interfaces.
In
*Proceedings of the First International Conference on Principles and Practice of Constraint Programming*, pages 624-628, Cassis, France, September 1995. - [Borning 97a]
- Alan Borning and Bjorn Freeman-Benson. Ultraviolet: A constraint satisfaction
algorithm for interactive graphics. To appear in
*CONSTRAINTS: An International Journal*, 1997. - [Borning 97b]
- Alan Borning, Kim Marriott, Peter Stuckey, and Yi Xiao. Solving
linear arithmetic constraints for user interface applications. In
*Proceedings of the 1997 ACM Symposium on User Interface Software and Technology*, October 1997. - [Cruz 93]
- Isabel Cruz. Expressing constraints for data display specification:
A visual approach. In Vijay Saraswat and Pascal Van Hentenryck, editors,
*Principles and Practice of Constraint Programming: The Newport Papers*, pages 443-468. MIT Press, 1995. - [Duisberg 87]
- Robert Duisberg. Animation using temporal constraints: An overview
of the Animus system.
*Human-Computer Interaction*, 3(3):275-308, 1987. - [Harada 95]
- Mikako Harada, Andrew Witkin, and David Baraff. Interactive physically-based
manipulation of discrete/continuous models. In
*SIGGRAPH '95 Conference Proceedings*, pages 199-208, Los Angeles, August 1995. ACM. - [Harvey 97]
- Warwick Harvey, Peter Stuckey, and Alan Borning. Compiling constraint
solving using projection. In
*Proceedings of the 1997 Conference on Principles and Practice of Constraint Programming (CP97)*, October 1997. - [Helm 92a]
- Richard Helm, Tien Huynh, Catherine Lassez, and Kim Marriott. A linear
constraint technology for interactive graphic systems. In
*Graphics Interface '92*, pages 301-309, 1992. - [Helm 92b]
- Richard Helm, Tien Huynh, Kim Marriott, and John Vlissides. An object-oriented
architecture for constraint-based graphical editing. In
*Proceedings of the Third Eurographics Workshop on Object-oriented Graphics*, Champery, Switzerland, October 1992. - [Hosobe 96]
- Hiroshi Hosobe, Satoshi Matsuoka, and Akinori Yonezawa. Generalized
local propagation: A framework for solving constraint hierarchies. In
*Proceedings of the Second International Conference on Principles and Practice of Constraint Programming*, Boston, August 1996. - [Hudson 96]
- Scott E. Hudson and Ian Smith. SubArctic UI toolkit user's manual. Technical report, College of Computing, Georgia Institute of Technology, 1996.
- [Lie 96]
- Hakon Wium Lie and Bert Bos. Cascading style sheets, level 1. W3C Recommendation, December 1996. http://www.w3.org/pub/WWW/TR/PR-CSS1
- [Myers 96a]
- Brad Myers, Robert Miller, Rich McDaniel, and Alan Ferrency. Easily
adding animations to interfaces using constraints. In
*Proceedings of the 1996 ACM Symposium on User Interface Software and Technology*, pages 119-128, Seattle, November 1996. - [Myers 96b]
- Brad A. Myers. The Amulet user interface development environment.
In
*CHI'96 Conference Companion: Human Factors in Computing Systems*, Vancouver, B.C., April 1996. ACM SIGCHI. - [Sannella 93]
- Michael Sannella, John Maloney, Bjorn Freeman-Benson, and Alan Borning.
Multi-way versus one-way constraints in user interfaces: Experience with
the DeltaBlue algorithm.
*Software--Practice and Experience*, 23(5):529-566, May 1993. - [Sutherland 63]
- Ivan Sutherland. Sketchpad: A man-machine graphical communication
system. In
*Proceedings of the Spring Joint Computer Conference*, pages 329-346. IFIPS, 1963. - [Van Wyk 82]
- Christopher J. van Wyk. A high-level language for specifying
pictures.
*ACM Transactions on Graphics*, 1(2):163-182, April 1982. - [Vander Zanden 96]
- Brad Vander Zanden. An incremental algorithm for satisfying hierarchies
of multi-way dataflow constraints.
*ACM Transactions on Programming Languages and Systems*, 18(1):30-72, January 1996. - [Weitzman 93]
- L. Weitzman and K Wittenburg. Relational grammars for interactive
design. In
*IEEE Symposium on Visual Languages*, pages 4-11, 1993. - [Weitzman 94]
- L. Weitzman and K Wittenburg. Automatic generation of multimedia
documents using relational grammars. In
*Proceedings of 2nd ACM Conference on Multimedia*, 1994.