Concurrency.

Monoids.

*(Yes, we're hiring)*

Ptolemy Project

"The Problem With Threads" Edward A. Lee, 2006

- Concurrency research project
- Ran fine for 4 years...
- ...Till it deadlocked. No one knew why
- Experts can't get this right

Gig I was on a few years ago

- Heavily concurrent Java system
- 2x
*single core*CPUs - Ran flawlessly for 3 years
- Then upgraded to 2x
*multi core*CPU... - And it
**DIED HORRIBLY**every few hours - 2 weeks of debugging, concurrency bug found in
*"threadsafe"*code

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are semigroups with identity

Suppose that S is a set and • is some binary operation, S × S → S, then S with • is a monoid if it satisfies the following two axioms:

## Associativity

For all a, b and c in S, the equation (a • b) • c = a • (b • c) holds.

## Identity element

There exists an element e in S such that for every element a in S, the equations e • a = a • e = a hold.

`1 + 1 # 2 `

`[:a :b] + [:c] # [:a, :b, :c]`

`{a: 1, b: 2}.merge({c: 3, a: 4}) # {a: 4, b: 2, c: 3}`

- immutable values that are members of some collection
- associative binary operator that
*"appends"*values - an identity value that doesn't change another value
- (may or may not be commutative)

- Operator is
`+`

- Identity is
`0`

```
0 + 1 == 1
1 + 0 == 1
(1 + 2) + 3 == 6
1 + (2 + 3) == 6
```

- Operator is
`*`

- Identity is
`1`

```
1 * 2 == 2
2 * 1 == 2
(2 * 3) * 4 == 24
2 * (3 * 4) == 24
```

- Operator is
`+`

- Identity is empty list
`[]`

```
[] + [:a, :b] == [:a, :b]
[:a, :b] + [] == [:a, :b]
([:a, :b] + [:c]) + [:d] == [:a, :b, :c, :d]
[:a, :b] + ([:c] + [:d]) == [:a, :b, :c, :d]
```

- Operator is
`#merge()`

- Identity is empty hash
`{}`

```
{}.merge({a: 1}) == {a: 1}
{a: 1}.merge({}) == {a: 1}
{a: 1}.merge({b: 2, c: 3}).merge({d: 4, a: 5}) == {a: 5, b: 2, c: 3, d: 4}
{a: 1}.merge({b: 2, c: 3}.merge({d: 4, a: 5})) == {a: 5, b: 2, c: 3, d: 4}
```

- Operator is
`#mappend()`

- Identity is
`.mempty()`

*(names stolen from Haskell)*

```
class MyFoo < Struct.new(:list, :number)
def self.mempty
new([], 0)
end
def mappend(other)
MyFoo.new(self.list + other.list, self.number + other.number)
end
# NOTE object is immutable!
private :list=, :number=
end
f1 = MyFoo.new([:a, :b], 1)
f2 = MyFoo.new([:c], 2)
f3 = MyFoo.new([:d], 3)
f1.mappend(MyFoo.mempty) == f1
MyFoo.mempty.mappend(f1) == f1
f1.mappend(f2).mappend(f3) == f1.mappend(f2.mappend(f3))
```

```
def scary
value = []
a = Thread.new do
sleep rand
value << :a
end
b = Thread.new do
sleep rand
value << :b
end
a.join
b.join
value
end
```

```
def not_scary
a = Thread.new do
sleep rand
[:a]
end
b = Thread.new do
sleep rand
[:b]
end
a.value + b.value
end
```

```
# build the query bit by bit
# in practice these get really complicated, and are each their own class
basic_query = Query.mempty() #empty query as starting point
basic_query = basic_query.mappend(Query.new(term: term))
# ...
```

```
# AHA! We can get a transformed copy of the query to do other subqueries with it,
# all while leaving the original alone for later use. And we can safely do it async!
max_sales_thread = Thread.new do
basic_query.mappend( Query.new(aggregate: :max_sales)).execute!
end
# and again!
avg_price_thread = Thread.new do
basic_query.mappend( Query.new(aggregate: avg_price)).execute!
}
# combine the results with monoid operator
basic_query = basic_query.mappend(max_sales_count: max_sales_thread.value)
basic_query = basic_query.mappend(avg_price: avg_price_thread.value)
```

```
results = basic_query.execute!
```

```
related_search_threads = results.related_searches.map do|search_term|
Thread.new do # start a thread for each separate term in parallel
# remember basic_query? Still it's same immutable self :)
related_query = basic_query.mappend(Query.new(term: related_search_term)
related_query = related_query.mappend(Query.new(aggregate: :exists)
related_query.execute!
end
end
# remove related ones that don't have any results
related_search_terms = related_search_threads.select{|t| t.value.exists? }
# TADA! Done
final_result = result.mappend(Results.new(related: related_search_terms)
```

- Monoids are fun!
- If you've done primary school maths, you're already using them
- Just the same thing you're already doing -
**with constraints** - Great way to isolate logic
- Lets you compose transformations
- Immutable
- Immutability, isolation, and composition are awesome used with concurrency