Composition Lens Part 2 - Runnable Specifications

← 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 customer’s 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?

Here’s 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 eect 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 eect 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?

Let’s 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”. It’s kind of the default, kind of boring,

and the only reason I’m putting it in the book is because it’s 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 the rst 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 let’s 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 coee 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. Let’s 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 let’s 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 doesn’t 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 we’ll 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), we’ve 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.

You’ll 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

Let’s 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, it’s the same as setting it once.

This is setSize(“mega”) composed with itself.

Many properties deal with an operation’s 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 dene 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 dene 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

soware 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 shop’s 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,

they’re 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. Let’s

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 it’s 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 don’t want to go nega-

tive if we hit decrement too many times. It reminds me a bit like

idempotence. Here’s 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 oen 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 there’s 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? Let’s 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 we’ve seen, we’re 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 item’s 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, let’s 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 won’t 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 you’re 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 denition for transitivity

is:

if a ⊆ b and b ⊆ c then a ⊆ c

If we generate random a, b, and c, then they likely won’t have that

relationship. If they’re 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, we’ll 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 don’t 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 specication. 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 shue 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 don’t 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 aren’t 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

Let’s take a look at examples using each method.

Using brute force

I’m saying brute force like it’s 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.

Here’s how I would do it. To implement, we need to choose a

data structure for our inventory. The inventory is a collection,

and for this example let’s evaluate arrays and objects.

If we use an array of all the inventory items we’ve seen so far,

combining two of those arrays is just concatenation:

function combineInventories(inventoryA, inventoryB) { //=> Inventory

return inventoryA.concat(inventoryB);

}

If we use an object, then we can implement combining invento-

ries using a function called mergePlus():

function combineInventories(inventoryA, inventoryB) { //=> Inventory

return mergePlus(inventoryA, inventoryB);

}

function mergePlus(o1, o2) { //=> object<number>

let copy = Object.assign({}, o1);

for(let key in o2)

copy[key] = (copy[key] || 0) + o2[key];

return copy;

}

Both of these operations (concat() and mergePlus()) have their

own identities.

• [].co n c a t(a) is a and a.co ncat([]) is a

• mergePlus({}, b) is b and mergePlus(b, {}) is b

B e c a u s e o f t h i s , b o t h i m p l e m e n t a t i o n s o f combineInventories()

have identities, [] and {}. Luckily, those identities also make

sense for what an empty inventory should be.

170 Chapter 5

Implementation of inventory operations

For reference, let’s implement all of the inventory operations,

including validation and normalization. I’m going to implement

them using a JS object. Feel free to implement them using an ar-

ray as an exercise.

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

171Composition Lens Part 2

Implementing the inventory constructor

function empty() { //=> Inventory

return {};

}

Implementing the inventory accessor

function lookup(inventory, item) { //=> number

return inventory[item] || 0;

}

Implementing the inventory mutation functions

function increment(inventory, item) { //=> Inventory

let ret = Object.assign({}, inventory);

ret[item] = lookup(inventory, item) + 1;

return ret;

}

function decrement(inventory, item) { //=> Inventory

if(lookup(inventory, item) === 0)

return inventory;

let ret = Object.assign({}, inventory);

if(lookup(inventory, item) === 1)

delete ret[item];

else

ret[item] -= 1;

return ret;

}

172 Chapter 5

Implementing the inventory combining functions

function combine(inventoryA, inventoryB) { //=> Inventory

return mergeWith((a, b) => a + b, inventoryA, inventoryB);

}

function mergeWith(f, o1, o2) { // object<number>

let ret = Object.assign({}, o1);

for(let key in o2) {

if(o1[key])

ret[key] = f(o1[key], o2[key]);

else

ret[key] = o2[key];

}

return ret;

}

function isSubset(inventoryA, inventoryB) { //=> boolean

for(let item in inventoryA) {

if(inventoryA.lookup(item) > inventoryB.lookup(item))

return false;

}

return true;

}

function isEqual(inventoryA, inventoryB) { //=> boolean

return isSubset(inventoryA, inventoryB) &&

isSubset(inventoryB, inventoryA);

}

173Composition Lens Part 2

Implementing the inventory validation and normalization

const items = [

“soy”, “almond”, “chocolate”, “hazelnut”,

“raw roast”, “burnt roast”, “charcoal roast”,

“super cups”, “mega cups”, “galactic cups”

];

function isValidItem(item) {

return items.indexOf(item) >= 0;

}

function isValidInventory(inventory) { //=> boolean

for(let item in inventory) {

if(!isValidItem(item))

return false;

if(typeof inventory[item] !== “number”)

return false;

if(inventory[item] < 0)

return false;

}

return true;

}

function normalize(inventory) { //=> Inventory

let ret = Object.assign({}, inventory);

for(let item in ret) {

if(ret[item] === 0)

delete ret[item]; // remove zeros

}

return ret;

}

174 Chapter 5

Implementing the inventory generators

For generators, I prefer not to use the other domain functions be-

cause it causes a dicult circular problem. If there are bugs in

your domain functions, and your generators use them, your tests

might pass when they shouldn’t, but you won’t know about it.

function anyItem() { //=> Item

let idx = Math.floor(Math.random() * items.length);

return items[idx];

}

function anyInventory() { //=> Inventory

let ret = {};

let count = Math.floor(Math.random() * 20);

for(let i = 0; i < count; i++) {

let item = anyItem();

ret[item] = (ret[item] || 0) + 1;

}

return ret;

}

175Composition Lens Part 2

Conclusion

The composition lens gives us the tools to reason about how oper-

ations work in composition—while still separating specication

from implementation. Algebraic properties allow us to ensure

the exibility of our operations while referring only to the func-

tion signatures. We learned how to implement operations so they

maintain the properties. And, nally, we saw how we can write

tests for our algebraic properties.

Summary

• Algebraic properties are relationships between one or more

operations, oen in composition. Algebraic properties al-

low us the exibility to express the same thing in dierent

ways. They also give us strong guarantees so we can reason

easily about the behavior of operations.

• Total properties apply unconditionally to a function and give

us stronger guarantees. Partial properties apply condition-

ally. They are still useful, but less so than total properties.

• Property-based testing allows us to generalize our tests. We

generate random values and say how our operations behave

for all values in general.

• We can discover properties in our domain by examining the

exibility we would like to ensure. Properties, like most of

the concepts, should come from the domain.

• We can implement the properties of our operations in two

ways. The rst is the hard way, with brute force. The second

way is by using an existing operation that already has that

property.

Up next . . .

We’ve learned how to reason about compositions of operations.

Those compositions happen because of user interactions over

time. As domain models mature, they typically begin to explicit-

ly model time. In the next lens, we’ll see two ways to do that. But

be sure to read through the Composition Lens Supplement, which

contains many common and powerful algebraic properties.