Functional Programming with Immutable Data Structures

Functional Programming with
Immutable Data Structures
Why Imperative Languages are
Fundamentally Broken in a
Multi-Threaded Environment
Ivar Thorson
Italian Institute of Technology
November 2, 2010

Rigid Body Dynamics Simulations

Important abstractions of functional
programming

particularly for a 4-year old language

What I have learned from his work

Clojure: Blending theoretical abstractions +
practical know-how

Target Audience: C, C++, Java, Matlab
Programmers

Tempting to start with a feature tour!

But you won’t understand why Clojure is
cool without context

Actually, I’m going to try to knock the cup
out of your hand.

Three Outdated Concepts
1. Variables

1. Variables
2. Syntax

1. Variables
2. Syntax
3. Object Orientation

Goal is to convince you that
1. shared mutable data is now a
philosophically bankrupt idea.

2. code and data should be structured as
trees

2. code and data should be structured as
trees
3. OOP isn’t the best way to achieve
OOP’s goals

Speaking bluntly
1. everything you know is wrong (15 min)

Speaking bluntly
2. lisp parentheses are better than syntax
(10 min)

Speaking bluntly
2. lisp parentheses are better than syntax
(10 min)
3. OOP inheritance sucks (5 min)

disclaimer: some hyperbole in previous
statements

Oh noes, too many parentheses!

Good reasons for parentheses
1. Lisp is homoiconic

2. Parentheses uniquely deﬁne tree-shaped
computations

2. Parentheses uniquely deﬁne tree-shaped
computations
3. Parentheses enable structural editing

Introduction: Motivation for multi-threaded
programming

1. Last 40 years: Moore’s Law

1. Last 40 years: Moore’s Law
2. “Transistor count will double every 2
years”

# of transistors ≈ CPU performance

Constraining physical relationship between
power density, swiching time, oxide thickness

The future of hardware is increasingly parallel

The future of software will be ruled by
Amdahl’s law

Some things are sequential: Two women
cannot have a baby in 4.5 months.

1. Dividing up work is already a hard
design task

1. Dividing up work is already a hard
design task
2. Resource contention makes this problem
harder

Common multi-threaded bugs:
Invalid state

Invalid state
Race conditions

Invalid state
Race conditions
Deadlocks

Invalid state
Race conditions
Deadlocks
Livelocks

Invalid state
Race conditions
Deadlocks
Livelocks
Resource starvation

What if most bugs were merely due to the
imperative programming model?

Part 1: The Functional Programming Style

Pure functions always return the same result
when they get the same input.

Pure functions don’t...
...look outside their box

...modify anything, anywhere

...print messages to the user

...print messages to the user
...write to disk

Pure functions have no side eﬀects

Nothing would change if you ran the function
again – anywhere!

Pure functions just return a value, and do
nothing more.

Pure functions compose to other pure
functions

f (a, b, c) = (a + b)/(c ∗ 2)

Languages that emphasize the use of pure
functions are called functional languages

Imperative languages describe computation
in terms of changes to state.

C, C++, Java, and most engineering
languages are imperative.

Imperative languages describe memory
operations instead of purely functional
operations.

Imperative style: directly causing side eﬀects
on memory.

The assignment operator changes
memory...often a side eﬀect!

Could you write a C program...

without any non-local variables?

without any non-local variables?
where = is only used for initialization?

Next: Variables are fundamentally a bad
abstraction in multithreaded environments.

Claim #1. Shared mutable data is now
philosophically bankrupt

x = x + 1
x = 3 (...last time I checked!)

x = x + 1
x = 3 (...last time I checked!)
In my universe, 3 = 3 + 1 is never true

The Big Problem: the concept of variables
encourage us to forget about time.

The value of x for a given t is immutable
and unchanging!

The Most Important Slide
x is a name, an identity of a sequence of
values

values
x has diﬀerent values at diﬀerent times

values
The values of x are related by pure
functions

values
The values of x are related by pure
functions
In this case, by the increment function

The idea of a variable confuses identity and
the most current value!

Locking: a tactic for winning a battle.

What we need is a strategy to win the war.

“What if all data was immutable?” – Rich
Hickey (not the ﬁrst one to ask this question)

Keeping Old Immutable Data
x@(t=0) → 5

x@(t=0) → 5
x@(t=1) → 6

x@(t=0) → 5
x@(t=1) → 6
x@(t=13) → 7

x@(t=0) → 5
x@(t=1) → 6
x@(t=13) → 7
x@(t=15) → 8

x@(t=0) → 5
x@(t=1) → 6
x@(t=13) → 7
x@(t=15) → 8
...

The old values of the data are kept and
indexed by time

indexed by time
Data is immutable once created – we
cannot/will not change it!

indexed by time
Data is immutable once created – we
cannot/will not change it!
Values only destroyed when unneeded

Doesn’t keeping old copies of data consume
too much memory?

(a b c) + d = (a b c d)
What if the input and output shared
structure?

(a b c) + d = (a b c d)
structure?
Sharing structure is dangerous for
mutable data

(a b c) + d = (a b c d)
structure?
Sharing structure is dangerous for
mutable data
...but sharing structure is safe if the
data is immutable.

The Trick: Represent the list as a tree

input tree → pure function → output tree

both trees are immutable but distinct

Same approach works also for insertions,
modiﬁcations, deletions, and all other list
operations.

a million threads, a million trees, a million
references to trees, zero locks

If you want a more current worldview, just
get its reference

Advantages of immutable trees:

No locking required

No locking required
No ’stopping the world’ to see (readers
don’t block writers)

No locking required
Worldview never becomes corrupted

No locking required
Minimizes memory use while
maintaining multiple copies

No locking required
Minimizes memory use while
maintaining multiple copies
Unused nodes are garbage-collected

We’ve gone a long way, but we’re only half
way to real concurrency

Immutability lets us read concurrently, but
not write concurrently to a single piece of
data

How can we coordinate the actions of
diﬀerent threads working on the same data
at the same time?

”Treat changes in an identity’s value as a
database transaction.” – Rich Hickey

Database Details:
Software Transactional Memory (STM)

Database Details:
Software Transactional Memory (STM)
Multi-Version Concurrency Control
(MVCC)

The STM Guarantees:
Atomicity (All or nothing)

The STM Guarantees:
Consistency (Validation before commits)

The STM Guarantees:
Consistency (Validation before commits)
Isolation (Transactions can’t see each
other)

Transactions are speculative and may be
retried if there is a collision.

For even more concurrency:
Sometimes you don’t care about the
order of function application

Commutative writers won’t need to retry

Commutative writers won’t need to retry
Writers don’t interfere with other
writers!

STMs exist for other languages...

STMs exist for other languages...
... but Clojure is ﬁrst to have built-in
STM with pervasive immutability

Part 1 Summary: In Clojure...
...Readers don’t block anybody

...Writers don’t block anybody

...Writers retry if conﬂicting

...Writers retry if conﬂicting
...Writers don’t retry if commutative

Variables couldn’t do this because:

Confuse identity and values

Are mutable and can be corrupted

Assume a single thread of control, no
interruptions

Assume a single thread of control, no
interruptions
Maintain only the last written copy

”Mutable stateful objects are the new
spaghetti code” – Rich Hickey

”We oppose the uncontrolled mutation of
variables.” – Stuart Halloway

”Mutable objects are a concurrency
disaster.” – Rich Hickey

”The future is a function of the past, but
doesn’t change it.” – Rich Hickey

”Many people can watch a baseball game,
but only one can be at bat.” – Rich Hickey

Claim #2: Your language’s syntax is
unneccesarily complex

Now we’ll explain why lisp has parentheses!

Pure functions represent computation as
trees

Reason 1: The tree structure is made
explicitly visible by the parentheses

Sorry, Haskell/Erlang/OCaml/ML/etc!

With preﬁx notation, you can forget about
the rules of precedence.

Lisp code’s tree of computation is
exceptionally visible and regular.

Homoiconic = Homo + icon = ”same” +
”representation”

The property where code & a language
primitive look the same.

An example: Writing C with XML

for (i=0; i<100; i++) {
printf("%dn", i);
dostuff();
}

Imagine how simple it would be to use an
XML generator to emit compilable source
code.

We could modify our code programmatically.

In lisp, you can write programs that write
programs.

(list ’+ 1 2 3) -> (+ 1 2 3)
(+ 1 2 3) -> 6

(defmacro and
([] true)
([x] x)
([x & rest]
‘(let [and# ~x]
(if and# (and ~@rest) and#))))

Why lispers go nuts:
Macros in lisp are far more powerful
than in other languages.

You can build new constructs that are
just as legitimate as existing constructs
like if

You can build new constructs that are
just as legitimate as existing constructs
like if
You can abstract away boilerplate code

Aside
If Java used parentheses properly, XML
wouldn’t exist

Aside
wouldn’t exist
Lisp parentheses describe structure

Aside
wouldn’t exist
Most languages use ad-hoc syntax, data
formats

Aside
wouldn’t exist
Most languages use ad-hoc syntax, data
formats
Simplicity is elegance

Good editors let you work with code in
blocks and forget about the parentheses.

Hard-to-show Examples
When you type (, emacs adds the )

Indentation is automatic

You can easily navigate heirarchically

You can easily navigate heirarchically
Take next three expressions, apply them
to a function

Summary of Lisp Parentheses
Parentheses render explicit the
tree-structure of your program

Homoiconicity lets you write programs
with programs

Homoiconicity lets you write programs
with programs
Structural Editing is fun and easy

Syntax is bad because
It hides the program’s structure

It destroys homoiconicity

It destroys homoiconicity
It is needlessly complex

”Things should be made as simple as
possible – but no simpler.” – Albert Einstein

Part 3: OOP isn’t the only path to
Polymorphism and Code Reuse

OOP has good goals
1. to group objects together

OOP has good goals
2. to encapsulate

OOP has good goals
2. to encapsulate
3. to dispatch polymorphically

OOP has good goals
2. to encapsulate
3. to dispatch polymorphically
4. to reuse code

These are all good ideas and good goals.

However, OOP is not the only way to reach
these goals.

Claim #3: ”Functions compose better than
objects.”

The fundamental mechanism of OOP – the
inheritance of data, interfaces, type, or
methods from a parent – is often more
diﬃcult to use in practice than techniques
that use functions to achieve the same eﬀect.

Functions are simpler than objects.

Objects are semantic compounds of types,
data, and methods.

Implementation inheritance is bad:

Forces “is-a” relationship instead of
“has-a”, and “has-a” is almost always
better

better
Heirarchical nominalization is diﬃcult

better
Heirarchical nominalization is diﬃcult
Changes to a class aﬀect all the
subclasses

Balls
Ball class (presumably round)

Balls
rollingBall subclass

Balls
rollingBall subclass
bouncingBall subclass

Problems
What happens if we want to make a ball
that both rolls and bounces?

Problems
Do/Can we inherit from both?

Problems
What if our ball cracks and loses its
bounciness?

Problems
What if our ball cracks and loses its
bounciness?
Is a non-round rugby ball a subclass of
ball too?

Interfaces are Simpler
Deﬁne functional interfaces, but don’t
inherit the implementation

If you want to use another object’s
function to accomplish a task, just use it

No need to encapsulate their function in
an object

No need to encapsulate their function in
an object
Multiple interfaces are simpler than
multiple inheritance

FREE THE VERBS!! Separate your object
methods from your objects!

Example: Single vs Multiple Dispatch

Making Drum Noises
Drum, cymbal and stick classes

Making Drum Noises
When I hit something with the stick, it
makes a noise

Making Drum Noises
makes a noise
Single Dispatch:
drum.makeNoise(drumstick)

Making Drum Noises
makes a noise
Single Dispatch:
drum.makeNoise(drumstick)
cymbal.makeNoise(drumstick)

The verbs are owned by the nouns.

But what happens when I add a diﬀerent
stick class?

Now I will need to modify the drum and
cymbal classes and add new methods to
handle the mallets!

When two objects hit, the sound is function
of both objects.

With multi-method functions
hit(drumstick, cymbal) = crash

hit(mallet, cymbal) = roar

hit(drumstick, drum) = bam

hit(mallet, drum) = bom

hit(drumstick, drumstick) = click

hit(drumstick, drumstick) = click
hit(cymbal, cymbal) = loud crash

IMPORTANT: hit() is not a single function,
but a collection of functions. (It is called a
multi-method or generic function)

The particular function that is called is
determined by the type of both of its
arguments.

As you add more classes, just add more
deﬁnitions of hit().

Part 3 Conclusion
Polymorphism is better done through
interfaces than subtype inheritance.

Part 3 Conclusion
Functions do not require a heirarchy

Part 3 Conclusion
Functions do not require a heirarchy
Functions allow simple multiple dispatch

Functional Programming with Immutable Data Structures

Recommended

More Related Content

What's hot (20)

Similar to Functional Programming with Immutable Data Structures (20)

More from elliando dias (20)

Recently uploaded (20)

Functional Programming with Immutable Data Structures