Bx Examples Repository

Title: meertensIntersect

Version: 0.1

Type: Precise


Example from Meertens, used by Cheney et al. to illustrate arbitrary resolution of a free choice in a least change setting.


$M = {\cal P}(\mathbb N) \times {\cal P}(\mathbb N)$

$N = {\cal P}(\mathbb N)$


$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)$


Correct and hippocratic; satisfies Meertens' notion of least change.


There was some choice in the definition of $\overleftarrow{R}((s,t),n)$. It must:

  1. add to both $s$ and $t$ any element of $n$ that is not already present;
  2. preserve in both $s$ and $t$ any element of $n$ that is already present;
  3. 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.


This is Example 4.6 from

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 = {},
publisher = {},
series = {CEUR Workshop Proceedings},
volume = 1396

adapted from Example 5.2d of

author = {Lambert Meertens},
title = {Designing constraint maintainers for user interaction},
note = {Unpublished manuscript, available from},
month = {June},
year = 1998


Perdita Stevens



Unless otherwise stated, the content of this page is licensed under GNU Free Documentation License.