Designing Constraint Maintainers for User Interaction Lambert Meertens Kestrel Institute, Palo Alto, CA & Utrecht University PSD 2005 1 Examples of Maintained Constraints 1 Spreadsheet Qty Item Cost Cost 2 12.99 25.98

3 6.35 19.05 ----45.03 edit Qty Item Cost Cost 2 12.99 25.98 33 6.35 209.55 -----235.53 Constraints:

Cost = Qty * Item Cost Total Cost = SUM Cost PSD 2005 2 Examples of Maintained Constraints 2 UNIX make @book{AristoCat, author = Aristotle, title = Category, @book{AristoCat, author = Aristotle, title = Categories, edit

[5] Aristotle. Category. Athens Academic Press. 350 BCE. [5] Aristotle. Categories. Athens Academic Press. 350 BCE. Constraints: %.dvi: %.tex *.bib latex $* bibtex $* latex $* PSD 2005 3 (unidirectional

) Examples of Maintained Constraints 3 Rename file edit Constraint: prez.name = prez.file.name (bidirectional!) PSD 2005 4 Maintained Constraints General Case A constraint is a relation between objects

Structured documents Presentations are also structured documents External agents (user editing, mail delivery, clock) may change the value of some object A value change may violate a constraint A violated constraint must be restored by changing the value of some other linked object If that is not possible, the original change was unlawful PSD 2005 5 Issue: At Most Constraint Physical embodiment:

For any given value of A, there are many values B such that A B Which one to choose? PSD 2005 6 Designing Constraint Maintainers Constraints operate like the Laws of Physics of a virtual universe For a constraint-driven system to be usable, it must behave in a predictable way The way in which constraints are restored must follow from simple principles Potential bonus: automatic derivation for declaratively specified constraints PSD 2005 7

Semi-Maintainers We define a (unidirectional) semi-maintainer ; a (bidirectional) maintainer is then just a pair of semi-maintainers, one for each direction For now, ignore unlawful changes and constraints involving more than two objects Call the object that was changed by an external agent the source, and the linked object is target The semi-maintainer knows the new value of the source and the old value of the target PSD 2005 8 Definition of Semi-Maintainer For a relation R : S ~ T, a semi-maintainer is

a function : ST T satisfying, for all x : S and y : T, (EST) x R (x y) (SKIP) x R y xy y EST states that after an update x : x y the constraint x R y holds SKIP states that an update x : x y has no effect if the constraint x R y already holds PSD 2005 9 The Principle of Least Change Dont make a larger change than is needed to restore the constraint

A A 2.5 5.0 edit PSD 2005 10 3.5 2.5

edit B A B 5.0 B 5.0

In Symbols: From the EST requirement x R (x y) we have that x y is an element of the set F(x) def { y' | x R y' } The Principle of Least Change means that among all elements y' F(x) we pick one as close as possible to the old value y of the target Note that the SKIP requirement xRy xy y is a special case of PLC when y F(x) PSD 2005 11 Distance To give meaning to as close as possible we

need to define a metric on each type of interest For numeric types this is obvious For structured types in general, the edit distance is a reasonable choice For sets, we can take the size of the symmetric set difference s t def (s t ) U (t s) PSD 2005 12 Example: Is Subset Of Constraint Relation : Set(a) ~ Set(a) We want to determine t' s t Put d t t' , so that t' t d EST is then s t d The smallest solution of EST is d s t

This gives us: s t t' t d t (s t ) s U t PSD 2005 13 Tie Breaking What if there are several solutions of EST that are all as close as possible to the old value of the target? Suggested approach for each type of interest, define a well-ordering (i.e., a total linear ordering such that each nonempty set has a least element) using as ordering principles that small comes before large, left before right and positive before negative and pick the least allowed element

PSD 2005 14 Example: Converse Abs Constraint Relation abs : Z ~ N , where n abs i abs ( i ) n We want to determine i' n i The possible values are: { n, n} Normally one is closer to i than the other, but if i = 0 while n 0 there is a tie Positive before negative: in that case pick i' n PSD 2005 15 Further Reading Steven Pemberton. The VIEWS Application

Environment. CWI Report CS-R9257, 1992. http://www.cwi.nl/ftp/CWIreports/AA/CS-R9257.p df Lambert Meertens, Steven Pemberton. The Ergonomics of Computer Interfaces Designing a System for Human Use. CWI Report CS-R9258, 1992. http://www.cwi.nl/ftp/CWIreports /AA/CS-R9258.pdf Lambert Meertens. Designing Constraint Maintainers for User Interaction. http://www.kestrel.edu/home/people/meertens/ dcm. PSD 2005 16 ps