Table 1: Empirical results -- Constrained Document
November 8-14, 1997
Crowne Plaza Hotel, Seattle, USA
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
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 + CW1 + CW2
(2) CW1 = CW2
(3) LG = RG = 0.05 *CW1
(4) MG = 0.7 cm
(5) FigA.midx = LG + 0.5 * CW1
(6) FigB.midx = LG + CW1+ MG + 0.5 * CW2
(7) FigA.top = FigB.top
(8) FigA.width <=CW1
(9) FigB.width <=MG + CW2+ RG
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, CW1 and CW2. Constraint (2) states that the two columns have equal width; (3) states that the left and right gutters are equal and are 1/20 of the width of the columns; (4) states that the middle gutter is of fixed size (0.7 cm); (5) states that the x value of the midpoint of Figure A is at the center of the first column; (6) states that Figure B is centered in the second column; while the last equality (7) enforces that the two figures are horizontally aligned. The inequalities (8) and (9) enforce that the columns are wide enough for Figures A and B.
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 CW1 = CW2 = 10 cm. Conversely, if PW = 42.7 cm then LG = RG = 1.0 cm, MG = 0.7 cm and CW1 = CW2 = 20 cm. Note how the left and right margins scale with respect to the page size while the middle gutter has an absolute size.
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
FigA.leftx = LG
FigB.leftx = LG
FigA.width <=CW
FigB.width <=CW
PW <=26 cm
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 vn, has the strongest preferential constraint vn=bn associated with it. We can then set vn to that value that best satisfies the preferred constraint (knowing that the value will satisfy the required constraints). Next, we set vn-1 to the value that best satisfies its preferential constraint vn-1=bn-1, and so on. The remaining wrinkle is that we don't do a single computation to find the values for the vi; rather, we compile code that can repeatedly find such values, given values for the constants bi as inputs. This allows us to compile efficient, straight-line code to solve the same set of constraints repeatedly for different inputs.
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.