Composition Lens Supplement - Runnable Specifications

← Contents · Runnable Specifications by Eric Normand · Work in progress · Comments

177

Supplement

Composition Lens

In this supplement, we detail various algebraic properties that

are commonly found in operations in real-world domains. Prop-

erties are common compositional structures that we analyze

from domains. For each property, we indicate its mathematical

notation and a notation in code, and an example property-based

test.

You can use this supplement in two ways. Firstly, you can

use it as a reference for the compositional structures to look for

when analyzing a domain. And, secondly, you can use the prop-

erties within as inspiration for your own properties, since the

real-world oen deviates from the clean, mathematical proper-

ties algebraists appreciate. Feel free to modify these properties

as needed.

Properties

Closure Property: nest operations 150

Associative Property: rebalance the call tree 152

Commutative Property: reorder the arguments 154

Mutual commutativity: apply functions in any order 156

Inverse: undo operations 158

Zero or terminal value: stop a calculation early 160

Identity or initial value: where to start a calculation 162

Idempotence: don’t need to keep track of calls 164

Last write wins: forget the past 166

First write wins: ignore the future 168

178 Chapter 6

Closure Property: nest operations

The closure property means that a function returns the same

type as it accepts as arguments. We say a function is closed over

that type. When you have several functions that are closed over

the same type, you can nest them arbitrary. This gives you huge

amounts of expressivity.

Example in math

Many functions in math have the closure property, including ad-

dition and multiplication of integers. However, it is certainly not

all of them. The closure property is what lets you nest arithmetic

expressions:

7a + 8b + c(3 + x) + d(4 + 5y + (2 + zw))

We want to tap into that same expressivity. To do that, you have

to nd a powerful type with good t, organize the domain oper-

ations into layers, and ensure the operations are closed over that

type.

Addition and multiplication close over numbers. Since they

both take numbers as arguments and they return numbers, we

can nest multiplications and additions (and numbers) arbitrarily.

Nesting is a powerful kind of composition because it adds a sec-

ond dimension to sequential composition. Achieving multiple op-

erations closed over the same type will enhance expressivity.

e f

Math notation

f : (A) => A

g : (A, A) => A

Property-based test

This property is not testable. It

is based solely on the types of

the arguments and return val-

ue.

179Composition Lens

Examples in code

In the Composition Lens chapter, we developed the idea of a pre-

senter. The presenter represented anything we could display on

the GUI, from a small component, all the way to the full GUI itself.

We then had operations that combined presenters into composite

presenters, and we built the GUI up by combining basic elements

like images and text.

Presenters

function image(state) //=> HTML

function text(state) //=> HTML

Functions closed over presenters

function frame(presenter) //=> Presenter

function horizontal(presenters) //=> Presenter

function vertical(presenters) //=> Presenter

We could then build GUIs by composing these functions in a nest-

ed way:

let GUI = vertical([

horizontal([

frame(text("Top Left")),

frame(text("Top Right"))

]),

horizontal([

frame(text("Bottom Left")),

frame(text("Bottom Right"))

])

]);

Top Le Top Right

Bottom RightBottom Le

180 Chapter 6

Associative Property: rebalance the call tree

The associative property gives you the exibility to change the or-

der of operations. We can’t always control the order. For instance,

if we’re running things in parallel, it’s hard to control when things

run. If there’s any property that will change your game, it’s the

associative property.

Example from math

The associative property for addition looks like this:

a + (b + c) = (a + b) + c

Notice that the parentheses change, but the order of a, b, and c do

not. Changing the order of the arguments is the commutative

property.

⊙

b c

⊙

associativity makes

these two equivalent

a ⊙ (b ⊙ c) (a ⊙ b) ⊙ c

Math notation

a ⊙ (b ⊙ c) = (a ⊙ b) ⊙ c

f(a, f(b, c)) = f(f(a, b), c)

Property-based test

let a = anyString();

let b = anyString();

let c = anyString();

assert(

a + (b + c) ===

(a + b) + c

);

Quick note

Anything with the associative

property has the closure prop-

erty because it has to return

the same type it takes as argu-

ments.

If an operation is associative

and it has an identity, mathe-

maticians call it a monoid.

181Composition Lens

Examples in code

Here are some example operations that have the associative

property:

String concatenation

"Hello" + (", " + "World!") === ("Hello" + ", ") + "World!";

The parentheses don’t matter, but the order of the strings really

does! Because of the associative property, we usually don’t write

the parentheses at all:

"Hello" + ", " + "World!"

Combine AddIns

We might make an operation that takes two sets of add-ins and

combines them into one. Here’s the signature:

function combineAddIns(addIns, addIns) //=> AddIns

And here’s the statement of the associative property:

let a = anyAddIns();

let b = anyAddIns();

let c = anyAddIns();

assert(_.isEqual(a.combineAddIns(b).combineAddIns(c),

a.combineAddIns(b.combineAddIns(c))));

associativity lets us rebalance call trees. these two trees

calculate the same thing.

⊙

a ⊙ (b ⊙ (c ⊙ d))

⊙

(a ⊙ b) ⊙ (c ⊙ d)

182 Chapter 6

Commutative Property: reorder the arguments

Commutativity is a very common property. It’s one that you likely

learned in high school. It means the order of arguments doesn’t

matter.

Why we use it

The commutative property gives us the exibility to change the

argument order while still getting the same answer. There are

many situations where we can’t control the order or we want the

order not to matter.

Example in math

One of those situations is when we’re adding numbers. Here is a

statement of the commutativity of addition:

a + b = b + a

⊙

a ⊙ b b ⊙ a

Note

Here we’re using inx notation

(where the operation goes be-

tween the arguments) for clari-

ty. We will switch between pre-

x (f(x, y)), inx (x

⊙ y), and

dotted notation (x.f().g()),

depending on which one illu-

minates the pattern better.

Math notation

a ⊙ b = b ⊙ a

f(a, b) = f(b, a)

Property-based test

let a = anyNumber();

let b = anyNumber();

assert(f(a, b) ===

f(b, a));

183Composition Lens

Example in code

We can write a similar property in JavaScript:

let a = anyNumber();

let b = anyNumber();

assert(a + b === b + a);

We can assert this of any function. Let’s do it for a function called

f() that takes two numbers.

let a = anyNumber();

let b = anyNumber();

assert(f(a, b) === f(b, a));

In our contacts syncing scenario from the Operation Lens chap-

ter, we couldn’t control the order that devices connected to the

internet. Regardless of the order, we want to have the same result

at the end. We can express the commutative property like this:

let a = anyContact();

let b = anyContact();

assert(isSameContact(syncContacts(a, b), syncContacts(b, a)));

{

phone: "444-4444"

}

{

phone: "444-4444"

}

{

phone: "444-4444"

}

{

phone: "222-2222"

}

{

phone: "222-2222"

}

old number

new number

syncContacts()

setPhone(patricia, "444-4444")

184 Chapter 6

Mutual commutativity: apply functions in any order

There’s another property called mutual commutativity. It means

that two operations can be called in any order.

Why we use it

Like with the commutative property, we want the exibility to

apply operations in any order. We can’t always control when they

happen (as in what sequence the customer asks for add-ins) but

we want the result to be the same.

Example in math

We can add and subtract numbers in any order and they’ll always

come out to the same number. The two operations are plus and

minus.

1 + 3 - 4 - 3 + 2 = 3 - 3 + 2 + 1 - 4

Reordering it gives us the exibility to add and subtract the num-

bers in a convenient order.

Here is the more general formula:

f(g(x)) = g( f(x))

f(g(x))

g( f(x))

Property-based test

let x = anyNumber();

assert(f(g(x)) ===

g(f(x)));

Math notation

f(g(x)) = g( f(x))

185Composition Lens

An example in code

Let’s start with a simple case:

let coffee = anyCoffee();

let size = anySize();

let roast = anyRoast();

let coffeeSizeFirst = coffee.setSize(size).setRoast(roast);

let coffeeRoastFirst = coffee.setRoast(roast).setSize(size);

assert(sameCoffee(coffeeSizeFirst, coffeeRoastFirst));

We can set the size rst or the roast rst. It doesn’t matter.

setSize() and setRoast() are mutually commutative.

We see a special case of this property when we’re dealing

with the same function with dierent arguments. For example,

we know in our coee order domain, the order we add add-ins

doesn’t matter. We can enforce that with a property:

let coffee = anyCoffee();

let addInA = anyAddIn();

let addInB = anyAddIn();

let coffeeAFirst = coffee.addAddIn(addInA).addAddIn(addInB);

let coffeeBFirst = coffee.addAddIn(addInB).addAddIn(addInA);

assert(sameCoffee(coffeeAFirst, coffeeBFirst));

This may seem very dierent, but it is just another form of the

same property. We can always dene:

let f = coffee => coffee.addAddIn(addInA);

let g = coffee => coffee.addAddIn(addInB);

assert(isSameCoffee(f(g(coffee)), g(f(coffee))));

The assert() has the same form as the mathematical notation above.

I will use dot notation to make it

easier to read

add the add-ins in reverse order

186 Chapter 6

Inverse: undo operations

Some operations “undo” another operation. In that case, we say

that they are inverses. Inverses give you the exibility to go back

and forth, either undoing an operation or moving between rep-

resentations.

Example in math

Increment and decrement are inverses of each other:

a + 1 - 1 = a

a - 1 + 1 = a

We say that two operations are inverses of each other when:

f(g(x)) = x and g(f(y)) = y

But inverses can be one-sided. For example, with integers, divi-

sion is the inverse of multiplication. But multiplication is not the

inverse of division.

3 × 2 = 6, 6 / 2 = 3 but 3 / 2 = 1, 1 × 2 = 2

That is, for integer operations:

i × j / j = i but not i / j × j = i

That’s why we have to check both sides of the inverse, if they exist.

f(g(x))

g( f(y))

Math notation

f(g(x)) = x

g(f(y)) = y

Property-based test

let c = anyCoffee();

let a = anyAddIn();

assert(

_.isEqual(

c.addAddIn(a)

.removeAddIn(a),

)

);

Deep question

Is stringify the inverse of

parse? Write out the test for

that. Try to nd cases where

the test passes and cases where

the test fails.

187Composition Lens

Example in code

JSON.parse() is the inverse of JSON.stringify():

let object = anyObject();

let asString = JSON.stringify(object);

let parsed = JSON.parse(asString);

assert(_.isEqual(object, parsed));

In the coee shop orders, removeAddIn() is the inverse of

addAddIn():

let coffee = anyCoffee();

let addIn = anyAddIn();

assert(_.isEqual(coffee.addAddIn(addIn).removeAddIn(addIn),

coffee));

Does the reverse hold? is addAddIn() the inverse of

removeAddIn()? Let’s write the test:

let coffee = anyCoffee();

let addIn = anyAddIn();

assert(_.isEqual(coffee.removeAddIn(addIn).addAddIn(addIn),

coffee));

If we can nd a single test case where this doesn’t hold, the prop-

erty doesn’t hold. What if coee has no add-ins?

let coffee = { size: "mega", roast: "burnt", addIns: {}};

Now when you remove an add-in, it’s a no-op (it does nothing).

But when you add the add-in aerwards, then it will have it. The

result will be:

{ size: "mega", roast: "burnt", addIns: { almond: 1 }}

When the coee does not have the add-in, the property does not

hold. But it does hold when it does have the add-in. This means we

can write a partial property:

let coffee = anyCoffee();

let addIn = anyAddIn();

if(coffee.hasAddIn(addIn))

assert(_.isEqual(coffee.removeAddIn(addIn)

.addAddIn(addIn),

coffee));

else assert(true);

We prefer total properties, but

this is probably as good as

you can get for this property.

Another option is to allow for

negative add-ins, which would

allow you to go below zero.

However, I don’t recommend

this because the resulting cof-

fee isn’t meaningful anymore.

What does it mean to have -3

soy milks?

188 Chapter 6

That is, if I have a long list of numbers to multiply, if my interme-

diate result is ever 0, I can stop. There’s no point in continuing

because no matter what I multiply aer a zero, the answer will

still be zero.

5 × 45 × 9 × 7 × 0 × 7 × 2 × 4 × 3 × 100 × ...

⊙

z ⊙ (b ⊙ (c ⊙ d))

⊙

((d ⊙ c) ⊙ b) ⊙ z

Zero or terminal value: stop a calculation early

Some operations have an end. That is, a value where you know

you can stop.

Example in math

Multiplication has a value that means it’s the end of the calcula-

tion. You know it, but you might not have thought about it as such.

The zero value of multiplication is the number called zero.

Math notation

Le: z ⊙ a = z

Right: a ⊙ z = z

Le: f(z, a) = z

Right: f(a, z) = z

Property-based test

// Left

let a = anyNumber();

assert(isNaN(NaN + a));

// Right

let a = anyNumber();

assert(isNaN(a + NaN));

Le zero

0 × a = 0

Right zero

a × 0 = 0

189Composition Lens

Examples in code

JavaScript uses oating point numbers, which have the value

NaN (Not a Number). Once you get a NaN, every operation re-

turns NaN.

let n = anyNumber();

assert(isNaN(NaN + n));

assert(isNaN(n + NaN));

That’s kind of a weird case. Let’s try the cartesian product, which

makes pairs of values from two arrays:

function cartesianProduct(as, bs) { //=> Array<Pair<a, b>>

let ret = [];

for(let a of as)

for(let b of bs)

ret.push([a, b]);

return ret;

}

If either of the two arguments is an empty array, then the return

value will also be an empty array:

cartesianProduct([], [1, 2, 3, 4, 5]) //=> []

cartesianProduct([1, 2, 3, 4, 5], []) //=> []

T he emp t y a r r ay is t he le  a nd r i g h t z e ro of cartesianProduct():

Le zero

let a = anyArray();

assert(_.isEqual(cartesianProduct([], a), a));

Right zero

let a = anyArray();

assert(_.isEqual(cartesianProduct(a, []), a));

190 Chapter 6

Identity or initial value: where to start a calculation

The identity is an interesting property. It gives you a value to start

with, before you’ve begun the work. For example, an empty add-

ins set would be the initial value, before you start adding the add-

ins to an order.

Example in math

Where do you start counting or summing from? That is, before

you have begun, what number do you initialize with? Zero, which

is the identity for addition.

The identity, like inverse, has two sides, le and right.

Math notation

Le: i ⊙ a = a

Right: a ⊙ i = a

Le: f(i, a) = a

Right: f(a, i) = a

Property-based test

// Left

let a = anyString();

assert("" + a === a);

// Right

let a = anyString();

assert(a + "" === a);

Le identity

0 + a = a

Right identity

a + 0 = a

0 is the identity of addition. What is the identity of multiplication?

Le identity

1 × a = a

Right identity

a × 1 = a

If an operation is associative

and it has an identity, mathe-

maticians call it a monoid.

⊙

i ⊙ a

⊙

a ⊙ i

191Composition Lens

Le identity

let a = anyString();

assert("" + a === a);

Right identity

let a = anyString();

assert(a + "" === a);

We can use identities to return empty values. For instance, in-

stead of returning null to mean “no answer”, we could return

the empty array, which still works ne with the append function.

Identities let you safely and easily represent empty values.

Let’s say you have a billion coee orders to analyze. You want to

know how many coees had soy milk, but there are too many to

go through on one machine. You split up the work among 100 ma-

chines, each machine taking a fraction of the orders. Most ma-

chines will have some soy milk orders, but some, by chance, will

have none. The identity of counting (or adding) is zero, so those

machines with no soy milk orders can return zero, which can

easily be added up like any other number.

It may seem obvious, but we oen forget to account for an identity

when developing our own operations. We might rely on null to

reprsent an empty value, but then the null is not a valid input to

our other operations. Use this property to nd an identity, be-

cause it will simplify your code.

⊙

i ⊙ (b ⊙ (c ⊙ i))

⊙

b c

b ⊙ c

Example in code

What is the identity of string concatenation? It is the empty string.

It is both the le and right identity.

192 Chapter 6

Idempotence: don’t need to keep track of calls

Idempotence means that calling a function once yields the same

value as calling it twice or more in composition. For example,

sorting a list twice is the same as sorting it once. The rst time is

important, the second time is a waste.

Idempotent functions give you the exibility to not keep track

of whether you’ve already called the function. It’s safe to call it

again any way.

Example in math

Absolute value, written as |x|, gives you the distance of a number

from zero. But calling it twice is the same as calling it once.

|x| = | |x| |

Dening it this way also means that three or more calls do the

same thing, too.

|x| = | | | x | | |

which gives us:

| x | = | | x | |

We can do this with any number of calls to absolute value, reduc-

ing it down to the original equation.

f(f(x)) f(x)

Math notation

f(a) = f(f(a))

Property-based test

let n = anyNumber();

assert(

Math.abs(n) ===

Math.abs(Math.abs(n))

);

193Composition Lens

Example in code

In our coee shop order example, setting the size to a particular

size twice is the same as setting it once:

let coffee = anyCoffee();

let size = anySize();

assert(_.isEqual(coffee.setSize(size),

coffee.setSize(size).setSize(size)));

In practical terms, it allows the barista the exibility to hit the

size button twice without a problem. This is an example of idem-

potency of a calculation.

Imagine another scenario where we need to send emails to our

customers, telling them that the next seasonal avor is coming

out next week. We don’t want to send the same email twice to the

same person. We have several lists:

• Our customer list

• Our loyalty member list

• Our newsletter

We could develop an algorithm to gure out the list of unique

email contacts. However, another option is to use a data structure

that already has an idempotent add operation—the set. When we

add the same value to a set twice, only the rst value is added.

All we have to do then is loop through all of our lists, blindly

calling set.add() for each email in the list. When we’re all done,

we will have a collection of all of our contacts with no duplicates.

194 Chapter 6

Last write wins: forget the past

Last write wins is so common in soware that it is considered the

default. We don’t even notice it is there. Every mutable variable

has a last write wins policy: The last value you assign to the vari-

able is the one that it keeps. Values you assign before the last one

are forgotten.

Example in math

Last write wins is similar to idempotency. You could call it a vari-

ation on it. But whereas idempotency calls the same function

twice with the same arguments, last write wins calls the same

function twice but with dierent arguments. The call that hap-

pens second is the one that is kept.

I couldn’t actually think of an example from math, but here’s

how you would express the property:

f(f(a, x), y) = f(a, y)

Notice that the second call (with y as the argument) is the one

that “wins.”

f(a, y)

f(f(a, x), y)

a x

Math notation

f(f(a, x), y) = f(a, y)

Property-based test

let v = undened;

let rst = anyNumber();

let last = anyNumber();

v = rst;

v = last;

assert(v === last);

195Composition Lens

Example in code

All of the coee attributes have a last write wins discipline. Here

is the size as an example:

let coffee = anyCoffee();

let rstSize = anySize();

let lastSize = anySize();

assert(_.isEqual(coffee.setSize(rstSize).setSize(lastSize),

coffee.setSize(lastSize)));

You can try it for roast as well.

Because this property is so common, it might be helpful to see

when the property doesn’t hold. It certainly doesn’t hold for add-

ing add-ins:

let coffee = anyCoffee();

let rstAddIn = anyAddIn();

let lastAddIn = anyAddIn();

// these are denitely different

coffee.addAddIn(rstAddIn).addAddIn(lastAddIn);

coffee.addAddIn(lastAddIn);

196 Chapter 6

First write wins: ignore the future

We can play with another variation on idempotency called rst

write wins. This is an uncommon one, but it’s fun to see how far

we can take it. In this variation, the rst time you call a function

is what counts forever. No matter how many times you call that

function on the value later, it has no eect.

Example in math

When you compose a function with itself but with dierent argu-

ments, the rst call is the one that sticks. Here’s how you would

express the identity:

f(f(a, x), y) = f(a, x)

a x

f(a, x)

f(f(a, x), y)

a x

Math notation

f(f(a, x), y) = f(a, x)

Property-based test

let v = new FWW();

let one = anyNumber();

let two = anyNumber();

v.set(one);

v.set(two);

assert(v.get() ===

one);

197Composition Lens

Example in code

Despite it being very rare, I do have a good example. Let’s say

MegaBuzz is signing contracts with suppliers of paper cups. Once

the supplier has clicked the button to sign, the button should do

nothing aer that. This sounds like idempotence, but is subtly

dierent because we pass in the time to the sign() function.

let contract = anyUnsignedContract();

let time = anyTime();

let otherTime = anyTime();

assert(_.isEqual(contract.sign(time),

contract.sign(time).sign(otherTime)));

In practical terms, this prevents a person from signing the same

document twice. They might accidentally click the button again,

or they might not remember that they have already signed it.