← Contents · Runnable Specifications by Eric Normand · Work in progress · Comments
141
We’ve worked with operations in composition and learned how to
increase the expressivity of those operations, especially by lever-
aging the closure property. In this chapter, we will explore how to
add exibility to the operations by encoding important behaviors
when they are composed together.
Chapter objectives
Learn to encode exibility into your model with properties.
Discover how to adapt generic properties to meet specic
needs.
Understand how to encode the properties as tests.
Learn to implement the properties of your operations.
141
Chapter 5
Composition Lens Part 2
Important terms
algebraic properties
total property
partial property
property-based testing
you’ll learn these
terms in this chapter
142 Chapter 5
The GUI needs to be exible
The barista is under a lot of pressure. Customers are throwing out
orders in arbitrary ways, mixing up the roast, the size, and the
add-ins. Plus they change their minds halfway through ordering.
We want the GUI to allow as much or more exibility as the cus-
tomer feels they have in ordering. That exibility includes:
1. Specifying the attributes (size and roast) in arbitrary order.
2. Specifying the add-ins in arbitrary order.
3. Making corrections to anything said previously.
In addition, the barista will make mistakes in hearing and mis-
takes in tapping the touchscreen. They need to correct those
mistakes as well. For instance, they might tap almond twice by
mistake and have to remove an almond. Or they might develop
adaptive habits, like setting the size twice because sometimes
the screen is a little aky. We want to allow for those things. In
the end, we want to get the customers order correct, as if they
told it to us perfectly with no mistakes.
We could build the exibility into the UI. But what would that
look like? It would require us to build another model, where you
could touch set size to galactic” twice, or be able to correct add-
ing too much almond by removing the extra almond. Then we
would convert this into the “real” order encoding. Why not build
it into the model itself when it makes sense?
Heres another way to think about it. The if statements (condi-
tionals) that implement these behaviors need to live somewhere.
Do they live in the GUI or in the domain model? Are they intrinsic
properties of the domain? Or are they eeting choices for how the
GUI works? We must make these design decisions for ourselves.
However, here are some factors to help you choose:
Does the behavior allow for total functions?
Are there plausible GUIs that wouldn’t want the behavior?
Do the choices prohibit the GUI from adding new behavior?
In the case of the orders GUI, the domain operations remain total,
I can’t imagine a GUI that wouldn’t want these behaviors, and we
can always make a GUI that throws errors if you set the size twice.
We’ll return to this idea in more detail in the Layers Lens.
143Composition Lens Part 2
Finding relationships between operations in composition
The prior sequence of operations has some interesting structure
baked into it. For instance:
coffee = setSize(coffee, "galactic");
coffee = setSize(coffee, "mega"); // set size again
The second ca ll to setSize() overr ides t he rst ca ll to setSize().
We can call this last-write-wins.
Here’s another example:
coffee = addAddIn(coffee, "almond");
coffee = removeAddIn(coffee, "almond"); // undo adding almond syrup
In this case, removeAddIn() reverses the eect of addAddIn().
We would say that removeAddIn() is the inverse of addAddIn().
Here’s a nal example:
coffee = removeAddIn(coffee, "almond");
coffee = removeAddIn(coffee, "almond"); // second removal has no effect
In this case, the second call to removeAddIn() has no eect be-
cause there is no almond to remove.
These properties of the operations might seem very obvious.
But notice that we haven’t even implemented the operations,
yet we can talk about their behavior when they work to-
gether. These behaviors are called algebraic properties and they
let us formalize the behavior of operations in composition. By
formalizing them, we can easily reason about how the composi-
tions work as the compositions get more complex.
144 Chapter 5
What is an algebraic property?
Lets take another look at the pair of setSize() calls:
coffee = setSize(coffee, "galactic");
coffee = setSize(coffee, "mega");
The setSize() operation has a common (and obvious) property
called “last write wins”. Its kind of the default, kind of boring,
and the only reason Im putting it in the book is because its a
good example to introduce the idea of properties.
An algebraic property is a statement about an operation that
holds true for any valid arguments.
One of therst questions I get aer I use the term is,why alge-
bra?”, including groans about boring high-school math class. Let
me answer that with an example.
To make sure we get a last write wins property, we could
write a test:
let coffee = newCoffee(); // start with a default coffee
coffee = setSize(coffee, "galactic");
coffee = setSize(coffee, "mega");
assert(getSize(coffee) === "mega");
Now, this test is very specic. It only tests one unique scenario:
Starting from a fresh coee, setting the size to galactic then to
mega will mean the size is mega. We want to test all scenarios, if
possible, to show that this property always holds. So lets gener-
alize it.
First, we can generalize the creation of the coee:
let coffee = anyCoffee(); // generalize to any coffee
coffee = setSize(coffee, "galactic");
coffee = setSize(coffee, "mega");
assert(getSize(coffee) === "mega");
Now we are testing not just fresh coee values, but any valid cof-
fee value. But we’re not done. We can generalize more.
Documentation
anyCoffee()
Return a random, valid coee.
145Composition Lens Part 2
Here’s the code we had on the last page:
let coffee = anyCoffee();
coffee = setSize(coffee, "galactic");
coffee = setSize(coffee, "mega");
assert(getSize(coffee) === "mega");
Now we want to generalize the rst size we set. Lets dene a vari-
able to hold that and initialize it to a random size:
let coffee = anyCoffee();
coffee = setSize(coffee, anySize()); // generalize to any size
coffee = setSize(coffee, “mega”);
assert(getSize(coffee) === “mega”);
Now lets generalize the nal size we set. Remember, this is the
one that the size will be set to in the nal coee (last write wins):
let coffee = anyCoffee();
coffee = setSize(coffee, anySize());
const lastSize = anySize(); // generalize to any size
coffee = setSize(coffee, lastSize);
assert(getSize(coffee) === lastSize);
This is a very general test. It says that for any random, valid cof-
fee, we can set the size to any size, then set it again, and no matter
what, it will be that last size we set. We can wrap it in a for loop
so that it doesnt test just one scenario, it can test one hundred
dierent scenarios:
for(let i = 0; i < 100; i++) { // test 100 random scenarios
let coffee = anyCoffee();
coffee = setSize(coffee, anySize());
const lastSize = anySize();
coffee = setSize(coffee, lastSize);
assert(getSize(coffee) === lastSize);
}
This test gives us reasonable condence that our property holds.
And if we want more condence, we can loop more.
This property is a variation on idempotence (which well see
soon ) that we can call last write wins.
Documentation
anySize()
Return a random, valid size.
146 Chapter 5
By generalizing all of the specic, known values to variables (un-
known values), weve moved into the realm of algebra. Compare
it to a property you might have learned in high school algebra
class. We all know that:
2 + 5 = 5 + 2
This states only that you can change the order of 5 and 2, but it
says nothing about other values we could add with +. To speak
about all values, in algebra class we replace the values with vari-
ables:
for all real numbers a and b, a + b = b + a
This is the same thing we’ve done with the setSize() example.
We’ve replaced all specics with variables (unknown values) and
asserted the statement is true. There are too many combinations
to think through every scenario. You need to think at a more ab-
stract level. Thinking about algebraic properties instead of spe-
cic scenarios lets you reason at a higher level.
147Composition Lens Part 2
Total and partial properties
In the Operation Lens chapter, we learned about total functions.
Youll remember that total functions are functions that give a val-
id return value for every combination of valid arguments. They
have no corner cases, so it is easy to reason about their behavior.
I want to introduce the idea of total properties, which are al-
gebraic properties that hold for all valid combinations of argu-
ments. Most algebraic properties are dened as total. A partial
property holds only for a subset of valid combinations of argu-
ments.
Here’s an example from math. Normally, multiplication is the
inverse of division:
(a ÷ b) × b = a
Lets write it out in code:
let a = anyNumber();
let b = anyNumber();
assert((a / b) * b === a);
But there’s a problem. What happens when b is zero? The division
will fail, and this property won’t hold. We can add a check for
zero:
let a = anyNumber();
let b = anyNumber();
if(b !== 0)
assert((a / b) * b === a);
This conditional makes the property partial. It’s still useful, but
more complicated. In this case, we don’t have a choice. We didn’t
invent division! But in our own code, we want to prefer total prop-
erties if we do have the choice.
Documentation
anyNumber()
Return a random number.
148 Chapter 5
Use property-based testing to test properties
The tests we developed are called property-based tests (PBT). They
use random values to sample the huge space of possible scenarios.
The sample is much better than the handful of examples a human
would write. Property-based tests nd bugs, oen in corner cases
we didn’t consider.
There are libraries for developing PBTs in most languages that
do a more sophisticated job than we did. Teaching how to use
those libraries would be a book in itself. We will stick with sim-
ple, hand-rolled tests. But I will give some vocabulary to help put
some shape to this idea.
Property
Unsurprisingly, the entire test is called a property consisting of
generated values and assertions.
Generator
The functions that create random values are called generators.
PBT libraries come with built-in generators for the built-in data
types like integers, strings, and collections. You can build custom
generators out of the built-in ones.
Size
Generators can create a value of a given size, a relative measure
per data type. Numbers are bigger if they are farther from zero.
Longer arrays are bigger than shorter ones. Properties are tested
from smaller to larger sizes.
Shrinkage
The test may nd a big failing case—for instance an array of ten
thousand elements. The testing library will shrink the value in
tiny steps to the smallest version that still fails. For instance, it
will remove one element from the array then test if it still fails. If
it does, it will continue until if nds the smallest array that still
fails. Typically, this minimal test case is easy to understand. The
shrinkage could be drastic, like from 10k elements to 2.
Our hand-rolled tests won’t have size or shrinkage.
Smaller
0, 1, -2
[], [1], [1, 2]
Bigger
10e5, 234321
[3,2,3,5,4,1,2,3,4,5,2]
Built-in generators
anyArrayOf()
Custom generators
anyCoffee()
anySize()
PBT Libraries by
language
JavaScript - fast-check
Java - jqwik
Python - Hypothesis
C# - FsCheck
C++ - RapidCheck
Google “property-based testing
<language> for other languag-
es.
149Composition Lens Part 2
Types of properties
We can categories common properties into three groups based
on how they are dened. Knowing these groupings can help you
develop your own properties because you can identify which cat-
egory you want to work in.
Properties of special values
Some properties describe the behavior of an operation when one
of the arguments is a certain value. For instance, 1 is a special
value for multiplication because it is its identity. Special value
properties include:
identity
zero
Properties of self-composition
Ma ny properties are a bout an operation in composition with itself.
For instance, there is an idempotence property of setSize():
isEqual(coffee.setSize(“mega”).setSize(“mega”),
coffee.setSize(“mega”))
That is, if I set the same size twice, its the same as setting it once.
This is setSize(“mega”) composed with itself.
Many properties deal with an operations composition with
itself. And these are surprisingly useful properties, given their
simplicity. Properties that are about self-composition include:
idempotence
last-write-wins
Properties of multiple composition
Finally, there are some properties that dene how two or more
operations compose with each other. Multiple composition prop-
erties include:
inverse
closure
mutual commutativity
References
You can nd these properties
and more in the Composition
Lens Supplement.
150 Chapter 5
Discovering properties in our domain
Before we dene or implement our operations, we should spend
time analyzing the kind of exibility they have in the domain. We
encode the exibilities as algebraic properties.
For these examples, we will use a scenario where we have to
inventory the storage shelves of our coee shop. Workers will go
through the shelves, incrementing the items they see on an inven-
tory. The inventories from all of the workers will be combined at
the end. We’ll learn more about the domain in the next sections.
Each section has a question to ask yourself about your opera-
tions that will help you think of the properties you want and need
for your model. Remember, these properties, like the exibilities
they represent, should exist in the domain. We don’t want to add
anything new. Instead, we are analyzing the domain for exibili-
ty and encoding it as properties.
Here are the operations in the inventory domain:
Constructor
function empty() //=> Inventory
Accessor
function lookup(inventory, item) //=> number
Mutation functions
function increment(inventory, item) //=> Inventory
function decrement(inventory, item) //=> Inventory
Combining functions
function combine(inventoryA, inventoryB) //=> Inventory
function isSubset(inventoryA, inventoryB) //=> boolean
function isEqual(inventoryA, inventoryB) //=> boolean
151Composition Lens Part 2
Discovering properties: What is the plain behavior?
One of the easiest and sometimes most important properties to
write is the one that captures the expected behavior of the oper-
ation. For example, as a worker goes through the shelves, they
need to count each item they see in the inventory. They do this
with our increment() operation. We expect it to increment the
item! Here is a test that expresses that expectation:
let inventory = anyInventory();
let item = anyItem();
assert(inventory.increment(item).lookup(item) ===
inventory.lookup(item) + 1);
This test looks like a basic “unit test” that you would see in many
soware systems, except projected into the property-based test-
ing space where we can assert things about all values at once.
This test is interesting because it relates increment() with
lookupItem(). That’s important because we want the result of a
lookup to change aer we increment it. But it also shows a com-
mon pattern: a mutation function (increment()) and an acces-
sor function (lookup()) related together in a test.
The behavior for decrement is a little more complicated. We
cannot go below zero for our count:
let inventory = anyInventory();
let item = anyItem();
if(inventory.lookup(item) === 0)
assert(inventory.decrement(item).lookup(item) === 0);
else
assert(inventory.decrement(item).lookup(item) ===
inventory.lookup(item) - 1);
This test is correct and complete, and all of the complication is
necessary. But because it isn’t very simple, I would also throw in
another simple test to make sure that decrement() never goes
below zero:
let item = anyItem();
assert(anyInventory().decrement(item).lookup(item) >= 0);
Documentation
anyInventory()
Return a random, valid inven-
tory.
anyItem()
Return a random, valid item.
152 Chapter 5
Discovering properties: Are there any special values?
The two most common special values we encounter are identities
and zeros. They both are only applicable to combining functions.
The only combining function above is combine(). It takes two
inventories and adds all of the items from both and returns that
as a new inventory.
Can we think of an identity value for this function? Is there
some value that is empty? Is there a place where we can start
counting the inventory? The answer is yes. An empty inventory,
one in which nothing has been counted.
Identities have two sides, so we write the both down:
// Left Identity
let inventory = anyInventory();
isEqual(combine(empty(), inventory), inventory)
// Right Identity
let inventory = anyInventory();
isEqual(combine(inventory, empty()), inventory)
You might wonder why we would want this property. Let’s imag-
ine an inventory process using pen and paper on clipboards.
Someone walks down the three aisles of the shops storage and
writes a tick mark on the paper for each item on the shelves.
This process takes three hours. To speed it up, someone pro-
poses getting one person to walk down each aisle, then their pa-
pers could be combined. This should take about one third the
time.
Then the programmer, not to be outdone, proposed having one
person work on each section of the shelves in the three aisles.
There were three sections each, so that would require nine peo-
ple. But some sections could be empty--we just don’t know which
until we go there. When they turn in their papers to be combined,
theyre turning in a blank inventory paper. The combining opera-
tion needs to be able to handle them.
153Composition Lens Part 2
Discovering properties: Does order matter?
Order is a super important idea that aects things both in se-
quence and in parallel. In our domain, we don’t know what order
we will encounter items, so we want to be able to increment them
in any order but get the same result. This is called mutual com-
mutativity:
let inventory = anyInventory();
let itemA = anyItem();
let itemB = anyItem();
assert(isEqual(inventory.increment(itemA).increment(itemB),
inventory.increment(itemB).increment(itemA)));
Several properties pertain to one kind of order or another. For
instance, commutativity is about the order of arguments, and as-
sociativity is about the order of operations. Here are some things
to consider when thinking about order:
order of arguments
order of elements in a collection argument
order of operations
order in sequence with itself with dierent arguments
order in sequence with other operations
154 Chapter 5
Discovering properties: How does it compose with itself?
Consider how an operation composes with itself. In our domain,
we want to be able to combine the inventories as they come back,
and they will come back on arbitrarily order as the workers n-
ish. So we want the exibility to combine them in arbitrary ways,
but still get the same answer. That is:
let inventoryA = anyInventory();
let inventoryB = anyInventory();
let inventoryC = anyInventory();
assert(isEqual(inventoryA.combine(inventoryB.combine(inventoryC)),
(inventoryA.combine(inventoryB)).combine(inventoryC)));
Two common examples of properties that are about self-compo-
sition are idempotence and associativity. Here are some things to
consider when thinking about self-composition:
what happens when you do the same operation twice in a row?
what must always be true when you do an operation twice in a row?
what happens if you vary the arguments to the operations?
155Composition Lens Part 2
Discovering properties: How does it compose with others?
Consider how an operation composes with other operations. Lets
say we nished our work, we combined all of the inventories into
one. But then we nd an unopened box. We want to be able to
increment all of the items in the box into the nal, combined in-
ventory and know that its the same as incrementing it into one
of the inventories a worker did as if they hadn’t missed that box.
let inventoryA = newInventory();
let inventoryB = newInventory();
let item = newItem();
assert(isEqual(inventoryA.combine(inventoryB).increment(item),
inventoryA.increment(item).combine(inventoryB)));
Two common examples of properties that are compositions with
other operations are inverse and mutual commutativity. Here are
some things to consider when thinking about composition with
others:
do any operations come in opposite pairs, such as add/remove, increase/decrease, etc?
what is always true when you do operation A then operation B?
can you say the same when B comes before A?
are there ways to arrange two operations to arrive at a special value?
do any operations distribute over other operations?
156 Chapter 5
Discovering properties: Would existing properties apply if
you changed some of the values?
We can look at existing properties and modify the values in the
formula slightly to adapt them to our needs. For instance, we
want to be able to decrement an item from the inventory if we
accidentally hit the wrong button. But we dont want to go nega-
tive if we hit decrement too many times. It reminds me a bit like
idempotence. Heres the code for idempotence, which is not cor-
rect. But we will correct it:
// not correct
let inventory = anyInventory();
let item = anyItem();
assert(isEqual(inventory.decrement(item).decrement(item),
inventory.decrement(item)));
There’s something about this that has potential. If we decrement
to zero, any further decrement should do nothing. Using this
idempotence code as a inspiration, we can change the values a
bit to make it work.
let item = anyItem();
let inventory = empty().increment(item);
assert(isEqual(inventory.decrement(item).decrement(item),
inventory.decrement(item)));
This property is not incredibly useful, but this question does ap-
ply oen enough to try it out. For instance, the last write wins
property we developed for setSize() is idempotence with var-
ied values.
157Composition Lens Part 2
Discovering properties: Would existing properties apply if we
varied the comparator?
We’ve been using equality for all of our comparisons in assertions,
but theres no reason to always use it. We can compare values any
way we like.
In our domain, we want to know that as we combine invento-
ries, the resulting inventory gets bigger. We’d hate to nd a bug
that made them smaller!
How can we ensure that? How do we write that property? We
can start with he identity property for combine():
let inventoryA = anyInventory();
let inventoryB = empty();
assert(isEqual(inventoryA, combine(inventoryA, inventoryB)));
This is a ne property, but what happens if we let inventoryB be
any inventory, not just the empty inventory?
// not correct
let inventoryA = anyInventory();
let inventoryB = anyInventory();
assert(isEqual(inventoryA, combine(inventoryA, inventoryB)));
This property is no longer true. How can we make it true? We
can try to change the comparator isEqual(). What comparator
would make sense? Lets try subset:
let inventoryA = anyInventory();
let inventoryB = anyInventory();
assert(isSubset(inventoryA, combine(inventoryA, inventoryB)));
And that works! It means just what we want: as we combine in-
ventories, the result is bigger than the original. We have to make
sure isSubset() is in our list of operations.
158 Chapter 5
Discovering properties: Would existing properties apply if
they were partial?
There are some properties that apply only to a certain subset of
valid arguments. As weve seen, were calling these partial prop-
erties. Although we prefer total properties, partial properties can
be useful, too.
We want the exibility to undo a mistaken increment by dec-
rementing. This is usually achieved with an inverse property.
On the surface, it appears that increment() and decrement()
should be inverses:
let inventory = anyInventory();
let item = anyItem();
// Left inverse
assert(isEqual(inventory.increment(item).decrement(item), inventory));
// Right inverse -- not correct
assert(isEqual(inventory.decrement(item).increment(item), inventory));
The le inverse is true, but the right inverse is not. If we decre-
ment an item when the items count is zero, then the decrement
does nothing. Then when we increment it, it will be one.
empty().decrement(item).increment(item).lookup(item) === 1
But when the count is not zero, the right inverse property should
be true. We can make the right inverse partial and capture that:
let inventory = anyInventory();
let item = anyItem();
// Left inverse -- total
assert(isEqual(inventory.increment(item).decrement(item), inventory));
// Right inverse -- partial
if(inventory.lookup(item) > 0) // this conditional makes it partial
assert(isEqual(inventory.decrement(item).increment(item), inventory));
We now only check the property when the count is positive, and it
provides useful information.
159Composition Lens Part 2
Property-based tests of inventory operations
For reference, lets put in one place all of the property tests for
our inventory functions, including validation and normalization.
Some of these have not appeared in the chapter before. Here are
all of our functions:
Constructor
function empty() //=> Inventory
Accessor
function lookup(inventory, item) //=> number
Mutation functions
function increment(inventory, item) //=> Inventory
function decrement(inventory, item) //=> Inventory
Combining functions
function combine(inventoryA, inventoryB) //=> Inventory
function isSubset(inventoryA, inventoryB) //=> boolean
function isEqual(inventoryA, inventoryB) //=> boolean
Validation and normalization
function isValidInventory(inventory) //=> boolean
function isValidItem(item) //=> boolean
function normalize(inventory) //=> Inventory
Generators
function anyInventory() //=> Inventory
function anyItem() //=> Item
160 Chapter 5
Properties of inventory constructor
function empty() //=> Inventory
// plain behavior
let item = anyItem();
assert(empty().lookup(item) === 0);
// total
assert(isValidInventory(empty()))
Properties of inventory accessor
We wont develop many properties for the accessor because it will
be tested when asserting properties of other operations.
function lookup(inventory, item) //=> natural number
// total
let inventory = anyInventory();
let item = anyItem();
assert(typeof inventory.lookup(item) === “number”);
assert(inventory.lookup(item) >= 0);
161Composition Lens Part 2
Properties of inventory mutation functions
function increment(inventory, item) //=> Inventory
// plain behavior
let inventory = anyInventory();
let item = anyItem();
assert(inventory.increment(item).lookup(item) ===
inventory.lookup(item) + 1);
// left inverse of decrementItem()
let inventory = anyInventory();
let item = anyItem();
assert(isEqual(inventory.increment(item).decrement(item), inventory));
// mutual commutativity
let inventory = anyInventory();
let item1 = anyItem();
let item2 = anyItem();
assert(isEqual(inventory.increment(item1).increment(item2),
inventory.increment(item2).increment(item1)));
// increment distributes over combination
let inventoryA = anyInventory();
let inventoryB = anyInventory();
let item = anyItem();
assert(isEqual(inventoryA.combine(inventoryB).increment(item),
inventoryA.increment(item).combine(inventoryB)));
// total
assert(isValidInventory(anyInventory().increment(anyItem())));
162 Chapter 5
function decrement(inventory, item) //=> Inventory
// plain behavior
let inventory = anyInventory();
let item = anyItem();
if(inventory.lookup(item) === 0)
assert(inventory.decrement(item).lookup(item) === 0);
else
assert(inventory.decrement(item).lookup(item) ===
inventory.lookup(item) - 1);
// plain behavior
let item = anyItem();
assert(anyInventory().decrement(item).lookup(item) >= 0);
// partial left inverse of increment()
let inventory = anyInventory();
let item = anyItem();
if(inventory.lookup(item) > 0)
assert(isEqual(inventory.decrement(item).increment(item), inventory));
// total
assert(isValidInventory(anyInventory().decrement(anyItem())));
163Composition Lens Part 2
Properties of inventory combining functions
function combine(inventoryA, inventoryB) //=> Inventory
// plain behavior
let inventoryA = anyInventory();
let inventoryB = anyInventory();
let item = anyItem();
assert(combine(inventoryA, inventoryB).lookup(item) ===
inventoryA.lookup(item) + inventoryB.lookup(item));
// monotonically increasing
let inventory = anyInventory();
assert(isSubset(inventory, inventory.combine(anyInventory())));
// commutative
let inventoryA = anyInventory();
let inventoryB = anyInventory();
assert(isEqual(inventoryA.combine(inventoryB),
inventoryB.combine(inventoryA)));
// associative
let inventoryA = anyInventory();
let inventoryB = anyInventory();
let inventoryC = anyInventory();
assert(isEqual(inventoryA.combine(inventoryB.combine(inventoryC)),
(inventoryA.combine(inventoryB)).combine(inventoryC)));
// identity
let inventory = anyInventory();
assert(isEqual(inventory.combine(empty()), inventory)); // right
assert(isEqual(empty().combine(inventory), inventory)); // left
// total
assert(isValidInventory(anyInventory().combine(anyInventory())));
164 Chapter 5
function isSubset(inventoryA, inventoryB) //=> boolean
// special value
assert(isSubset(empty(), anyInventory()));
When youre making properties where the generate values relate
to each other, you usually want to generate values that you guar-
antee the relationship. For example, the denition for transitivity
is:
if a b and b c then ac
If we generate random a, b, and c, then they likely won’t have that
relationship. If theyre not related the test of the if won’t be true,
so we won’t test the important part.
The solution is to generate b that is guaranteed to be a superset
of a and a c that is guaranteed to be a superset of b. That way, the
test will always be true and the important part will get tested.
To do that, well combine a with a random inventory to gen-
erate b. That guarantees that a is a subset of b. Likewise, we’ll
combine b with a random inventory to generate c.
// transitive
let inventoryA = anyInventory();
let inventoryB = inventoryA.combine(anyInventory()); // superset of a
let inventoryC = inventoryB.combine(anyInventory()); // superset of b
assert(inventoryA.isSubset(inventoryC));
// reflexive
let inventory = anyInventory();
assert(inventory.isSubset(inventory));
// total
assert(typeof anyInventory().isSubset(anyInventory()) === “boolean”);
165Composition Lens Part 2
function isEqual(inventoryA, inventoryB) //=> boolean
One could argue that we dont need to test all of the properties of
isEqual() because it is a denition (as opposed to an implementa-
tion). It is its own runnable specication. However, we also know
that programmers can introduce regressions. For that reason
and for completeness, we’ll list the properties here.
Transitivity of equality has the same issue it did for subset. We
want to generate three inventories that maintain equality rela-
tionships, so we generate the rst using a random array of items.
Then we shue the list to create another order for the same items.
We could create another inventory from that which is equal to the
rst but could be represented dierently in memory. Then we do
it again for the third inventory.
// transitive
let listA = anyArrayOf(anyItem);
let inventoryA = listA.reduce(increment, empty());
let listB = shuffle(listA);
let inventoryB = listB.reduce(increment, empty()); // A = B
let listC = shuffle(listB);
let inventoryC = listC.reduce(increment, empty()); // B = C
assert(inventoryA.isEqual(inventoryC));
// reflexive
let inventory = anyInventory();
assert(inventory.isEqual(inventory));
// commutative (also called symmetric when applied to equality)
let inventoryA = anyInventory();
let inventoryB = anyInventory();
assert(inventoryA.isEqual(inventoryB) === inventoryB.isEqual(inventoryA));
// total
assert(typeof anyInventory().isEqual(anyInventory()) === “boolean”);
166 Chapter 5
Properties of inventory validation and normalization
function isValidInventory(inventory) //=> boolean
// total
assert(typeof isValidInventory(anyValue()) === “boolean”);
assert(isValidInventory(anyInventory()));
function normalize(inventory) //=> Inventory
// plain behavior -- normalize doesn’t affect equality
let inventory = anyInventory();
assert(isEqual(inventory, inventory.normalize()));
We want to say that two equal inventories will normalize to the
same value. Instead of generating a random inventory, we gener-
ate a random array of items. We increment each of those items
into a empty inventories, once le-to-right, once right-to-le. The
two inventories should be equal but perhaps not represented the
same way in data. Normalizing them should make them the same
in data.
// plain behavior -- generating inventories in different order
let items = anyArrayOf(anyItem);
let inventoryA = items.reduce(increment, empty());
let inventoryB = shuffle(items).reduce(increment, empty());
assert(_.isEqual(inventoryA.normalize(), inventoryB.normalize()));
We use _.isEqual() (from lodash) because it does a deep com-
parison between any two values. We want to assure that the data
structures are equivalent.
// idempotence
let inventory = anyInventory();
assert(_.isEqual(inventory.normalize(),
inventory.normalize().normalize()));
// total
assert(isValidInventory(anyInventory.normalize()));
167Composition Lens Part 2
Properties of our normalization strategy
There are two normalization strategies. The rst is that we only
normalize when we need to compare values (using isSubset()
or isEqual()). In that case, we dont have to test anything. The
second is normalizing the output of all functions before they re-
turn so that we always have a normalize value. I’ll write a couple
of tests for this strategy. You can write the rest as an exercise.
// increment() is normalized
let inventory = anyInventory().increment(anyItem());
assert(_.isEqual(inventory, inventory.normalize()));
// combine() is normalized
let inventory = anyInventory().combine(anyInventory());
assert(_.isEqual(inventory, inventory.normalize()));
Testing the generators
It is an important part of property-based testing to test your gen-
erators. We want to test that they always generate valid values.
We have two generators, anyItem() and anyInventory().
// anyItem() is always valid
assert(isValidItem(anyItem()));
// anyInventory is always valid
assert(isValidInventory(anyInventory()));
Remember that these properties will be run hundreds or thou-
sands of times in a loop.
168 Chapter 5
Implementing operations with properties
Even though we arent implementing now, we will have to imple-
ment eventually. Knowing how to implement our operations will
help us constrain the data model. There are two main ways to
ensure that an operation’s implementation has properties.
1. Using brute force
2. Using an existing operation with that property
Lets take a look at examples using each method.
Using brute force
I’m saying brute force like its a bad thing, but it simply means
writing out all of the cases carefully to make sure the property
holds.
For example, we could implement the identity property of
combine() using special cases:
function combine(a, b) { //=> Inventory
// Left identity
if(isSubset(a, empty())) // if a is the identity
return b;
// Right identity
if(isSubset(b, empty())) // if b is the identity
return a;
...
}
We can always use brute force coding to ensure a property. This
is simple coding, but it is not as elegant as the other way. However,
sometimes we don’t have another choice.
169Composition Lens Part 2
Using an existing operation with that property
The more elegant way is to map the operation you are implement-
ing to existing operations that already have that property. For ex-
ample, if we want to implement combineI() and ensure that emp-
ty() is its identity, we could choose a data model for inventories
such that combining them already has that property.
Heres how I would do it. To implement, we need to choose a
data structure for our inventor