Bx Examples Repository
Title: meertensIntersect
Version: 0.1
Type: Precise
Overview
Example from Meertens, used by Cheney et al. to illustrate arbitrary resolution of a free choice in a least change setting.
Models
$M = {\cal P}(\mathbb N) \times {\cal P}(\mathbb N)$
$N = {\cal P}(\mathbb N)$
Consistency
$R((s,t), n)$ iff $s \cap t = n$
Consistency Restoration
$\overrightarrow{R}((s,t),n) = s \cap t$ (no choice, if we wish to be correct)
$\overleftarrow{R}((s,t),n) = (n \cup (s \setminus t), n \cup t)$
Properties
Correct and hippocratic; satisfies Meertens' notion of least change.
Discussion
There was some choice in the definition of $\overleftarrow{R}((s,t),n)$. It must:
- add to both $s$ and $t$ any element of $n$ that is not already present;
- preserve in both $s$ and $t$ any element of $n$ that is already present;
- delete from at least one of $s$ and $t$ any element of their intersection that is not in $n$.
As far as correctness goes, it is also at liberty to add any element that is not in $n$ to just one of $s$, $t$, provided it is not already present in the other. But intuitively this would be unnecessarily disruptive (in the extreme case where the arguments are already consistent it will violate hippocraticness).
If we take as distance between $(s,t)$ and $(s',t')$ the sum of the sizes of the symmetric differences of the components, we have language in which to express that that behaviour would give a larger change than necessary. Similarly, we justify that in the third case above, the offending element should be removed from just one set, not both. The choice is arbitrary; Meertens uses the concept of bias to explain how it is resolved by the bx language or programmer. Given one choice of resolution, his calculations produce the result given above.
References
This is Example 4.6 from
@inproceedings{cheney15:bx,
author = {James Cheney and Jeremy Gibbons and James McKinna and Perdita Stevens},
title = {Towards a Principle of Least Surprise for Bidirectional Transformations},
booktitle = {Proceedings of {Bx} 2015},
year = 2015,
ee = {http://ceur-ws.org/Vol-1396/p66-cheney.pdf},
publisher = {CEUR-WS.org},
series = {CEUR Workshop Proceedings},
volume = 1396
}
adapted from Example 5.2d of
@Unpublished{Meertens,
author = {Lambert Meertens},
title = {Designing constraint maintainers for user interaction},
note = {Unpublished manuscript, available from http://www.kestrel.edu/home/people/meertens/},
month = {June},
year = 1998
}
Author(s)
Perdita Stevens