with thanks to
Le Ton Beau de Marot
by Douglas Hofstadter
Hofstadter, Le Ton Beau de Marot
So, let's pick our poem - or rather, algorithm -
implement it in the conventional way, then go through weirder and
weirder problems and variations
Union Find
Union Find is a beautiful little algorithm for categorizing items
into disjoint sets. I know, what?
How can we tell if two addresses are
on the same island?
let's say we have a database of all the addresses and streets (not
counting bridges and tunnels) in the world, and we want to be able
to really easily check if two addresses are on the same island.
...or in their case, continent!
So, how can I tell if my awesome coworker Jeff and I live on the
same island?
What if each island had a capital city! Then if we just asked each address what its capital city is, we could
really easily tell if they're on the same island.
so we want to somehow elect a capital city for each island - that is
to say, we want to have some identifier for each set that every
member of the set knows about - something that will be the same
for every member of the set, and different for members of different
sets
Union Find lets us elect a
random but consistent
representative for each set
it doesn't matter that the representative was chosen randomly,
since it's still doing what we need it to do - it's the same for all
members of a given set, and members of different sets will have
different representatives
Union Find
class DisjointSetItem:
def __init__(self, payload):
self.payload = payload
self.parent = self
self.rank = 0
def find(self):
# ...
def union(self, other):
# ...
first, we go through all addresses & wrap each in a DSI
our island-counting program
items = {}
for node in nodes:
items[node] = DisjointSetItem(node)
for node in nodes:
dsi = items[node]
for edge in node.outgoing_edges:
end_node_dsi = items[edge.end_node]
dsi.union(end_node_dsi)
first we go through and call union for on pair of connected nodes,
what does this mean for our island question, though?
joining two nodes
def union(self, other):
my_root = self.find()
their_root = other.find()
if my_root == their_root:
return
elif my_root.rank < their_root.rank:
my_root.parent = their_root
elif my_root.rank > their_root.rank:
their_root.parent = my_root
else:
their_root.parent = my_root
my_root.rank += 1
we're going to keep track of our sets as
trees, so we can join two nodes into the same set by putting them
into the same tree structure
so, here are our 3 nodes again. We can see the edges, but they haven't
been joined into any sets yet
...now we have a tree! the one we picked has a higher rank now,
and its the parent of both! We can tell because the blue house has a
red roof now (okay, and also because of the arrow)
Here we go. We compare the green house to the blue one because they're
connected by an edge - a road.
finding a node's root
def find(self):
if self.parent != self:
self.parent = self.parent.find()
return self.parent
as I mentioned, we're going to keep track of our sets by holding
each set in a tree structure, so find can just tell us what the root is for the tree an item is in,
and will return the same root for every node in a given set
here, let's say we call find on the bottom node.
its parent is set to that middle node (as you can see by its blue roof)
we return red, which is the root of the tree and thus
the representative member of the set
and there's also this side effect - we actually rejigger our tree
and set our initial node's parent to be the root of the tree, which
is red.
Some of the fancy stuff this uses
classes
recursion
mutable variables
pointers
returning from functions
automatic memory management
if statements
What if we strip some of that stuff away?
What if we couldn't have classes?
We could say, we only have dumb records (or structs)
Structs will do just fine
struct DisjointSetItem {
struct DisjointSetItem *parent;
void *payload;
int rank;
};
Let's pretend we're writing in C...
and functions that operate on pointers to structs
struct DisjointSetItem *DSI_find(
struct DisjointSetItem *item) {
if (item->parent != item)
item->parent = DSI_find(item->parent);
return item->parent;
}
So now we have these families of functions, which operate on and
return pointers to structs, no big deal
We can even manage inheritance without classes
struct DSISubclass {
struct DisjointSetItem item;
int stuff;
};
this is not super important, but it's a kinda cool sidenote
Let's talk about the stack
We need this for recursion to work!
the Amsterdam plot
Someone had to invent the idea of the stack -
variously attributed to Turing, Bauer, Dijkstra, and Grace Hopper - the usual superheroes
our original find implementation
def find(self):
if self.parent != self:
self.parent = self.parent.find()
return self.parent
"But this isn't recursive! You're calling a method by the same name,
but it's a different method defined on a different object!"
find, re-written as a function
def find(item):
if item.parent != item:
new_parent = find(item.parent)
item.parent = new_parent
return item.parent
this is the same code as our original method, but it should be easier
to read as a function, so we can see really easily when we're passing
the item's parent into the same find() function.
memory clobbered, without the stack
def find(item):
if item.parent != item:
new_parent = find(item.parent)
# aw hell, item now points to
# the original item.parent!
(item.parent).parent = new_parent
return (item.parent).parent
Once upon a time, the idea was that each function would have some fixed
area of memory that was that function's own area. And so you couldn't
do recursion, because when you called the function from within itself,
the second call's variables would clobber over the first call's.
find, as a function, de-optimized
def find(item):
if item.parent == item:
return item
else:
return find(item.parent)
earlier, we looked at the fancy version of find,
which does what's called "path compression". It had this side effect
- updated the item's parent whenever we called find and discovered
that the item's root was different than it's current parent.
tail recursion can be transformed into a loop
def find(item):
current = item
while current.parent != current:
current = current.parent
return current.parent
Here's the new version!
We've just replaced tail recursion with a loop. No stack needed!
Tail Call Optimization
(some compilers will transform recursive functions into loops for you!)
Some smart compilers will do that for you, which is called "tail
call optimization".
gcc will supposedly even do this for some non-tail recursive
functions! How weird and cool is that?
via http://ridiculousfish.com/blog/posts/will-it-optimize.html
python won't
“
in many cases... the elimination of stack frames doesn't do anything for the algorithmic complexity of the code, but it does make debugging harder
”
- Guido van Rossum,
http://neopythonic.blogspot.com/2009/04/
Python won't - Guido is very explicitly opposed to tail call optimization,
and you can read the blog post he wrote explaining why he won't include
it in Python
ruby will, if you configure it to do so
RubyVM::InstructionSequence.compile_option = {
:tailcall_optimization => true,
:trace_instruction => false
}
MRI (standard) Ruby will do tail call optimization, but only if you
explicitly configure it to do so.
scala can warn you if you get in its way
import scala.annotation.tailrec
@tailrec def find = {
if (parent == this) {
this
} else {
parent.find
}
}
Scala will not only do tail call optimization for you, it has an
annotation you can use to have the compiler throw an error if the annotated
method can't be transformed into a loop!
back to our original find, as a function
def find(item):
if item.parent != item:
item.parent = find(item.parent)
return item.parent
Let's look at original, nicely optimized find implementation.
It has to do something *after* the inner call to find returns, so
it's not tail recursive
with path compression, transformed into a loop
def find(item):
items = [item]
# find the root
while items[-1].parent != items[-1]:
items.append(items[-1].parent)
root = items[-1]
# set each node's parent as the root
for i in items:
i.parent = root
return root
The basic idea of this code is that we just keep a list of all of the
items that need updating, and then once we know what the final result
is (after going through our loop), we go back and update them.
But could we do actual recursion without having a stack?
(instead of translating it into a loop)
we could just build our own stack
def find(item):
return find_recursive(item, [])
def find_recursive(item, children):
if item.parent != item:
children.append(item)
root = find_recursive(item, children)
item = children.pop()
item.parent = root
return item.parent
So what if we create an explicit inverse for our find function?
What if we had no variables?
Variable can just mean: a name for a value. So, "no variables" would
mean, "assembly language", which just has registers and memory
locations.
our original union implementation
(this is all about the side effects!)
def union(self, other):
my_root = self.find()
their_root = other.find()
if my_root == their_root:
return
elif my_root.rank < their_root.rank:
my_root.parent = their_root
elif my_root.rank > their_root.rank:
their_root.parent = my_root
else:
their_root.parent = my_root
my_root.rank += 1
The first question is: if our union function can't change anything,
then how do we later notice that it's happened?
an api that accomodates immutable data
class DisjointSetForest:
def make_set(self, new_item_payload):
# ...
return DisjointSetForest(*args)
def union(self, item_1_id, item_2_id):
# ...
return DisjointSetForest(*args)
def find(self, item_id):
# ...
return item_root, DisjointSetForest(*args)
We need a new method make_set, which takes the place of our old
constructor.
every change returns
an entirely new forest
If we can't mutate the old forest, with each change, we have to return a new
forest incorporating that change!
make_set takes the forest and a new node, wraps the new node in a
new DisjointSetItem, and returns a new forest that is the same as
the original forest except it also includes the new node
union takes the forest and the IDs of two items in that forest,
and retuns a new forest that is the same as the original forest
except that the two nodes identified by those IDs have been joined
into the same set
performance in an immutable world
whoa, that's a lot of copying stuff around! how can we live this this way?
Shallow Trees
can approximate
Arrays
(like Clojure's persistent vectors!)
We're going to go with arrays.
the abstract data type, not "a consecutive sequence of mutable memory
cells". So, immutable lists indexed by number that can be accessed by arbitrary
index in approximately O(1) time.
Bit-partitioned Tries
Clojure implements these with 32-ary trees. Arrays, of
course, are O(1) to read from an arbitrary index or write to an
arbitrary index. Trees aren't O(1) for anything.
copying persistent vectors
(lots of shared memory!)
Cool, what does that get us?
You can read more about
Clojure's persistent vectors here
http://hypirion.com/musings/
For now, rather than switching to a distractingly different syntax,
I'll just keep using Python. We can pretend that Python's tuples are Clojure's
persistent vectors, immutable and rather beautifully implemented.
our immutable items
class DisjointSetItem:
def __init__(self, payload, parent, rank):
self.payload = payload
self.parent = parent or self
self.rank = rank
we're going to pretend that once we assign these fields, they can never be modified. When we need to make changes,
we just make a new DSI
losing track of things...
since we're no longer passing
around DisjointSetItems, how do we keep track of changes in an item's parent?
whoops!
Before it was easy, each node held a pointer to its parent, so if the parent
changed, its children would still be referencing the changed parent and it'd be
no big deal.
Now, if a node's parent changes, we just have a totally new object, and the old
pointer isn't helpful anymore! We're facing approximately the same problem as if
we didn't have pointers at all!
the forest can keep an "array" of items
(with indices as their IDs!)
We could do something fancy with a dictionary (which we might implement as a
search tree), but to keep the slides short, let's stick with this "array" idea
(which is really a 32-ary tree anyways).
make_set, without variables
def max_id(self):
len(self.items) - 1
def make_set(self, payload):
new_item = DisjointSetItem(payload,
None), # parent
0) # rank
new_items = self.items + (new_item,)
return DisjointSetForest(new_items)
So we can see now how make_set has to work!
union, without variables
def union(self, item_1_id, item_2_id):
# ...
if root_1.rank < root_2.rank:
return replace(item_1_id, root_2)
elif root_1.rank > root_2.rank:
return replace(item_2_id, root_1)
else:
return replace(item_2_id, root_1, 1)
Our new union functions starts about the same as the old one,
but instead of changing any existing data structure, it returns
a new updated DisjointSetForest
def replace(self, index, root_index, incr=0):
existing = self.items[index]
new_root = DisjointSetItem(
existing.payload,
root_index,
existing.rank + incr)
new_items = (self.items[:index] +
(new_root,) + self.items[index + 1:])
return DisjointSetForest(self.max_id,
new_items)
And here's the actual replacement function.
In the roof of each item, the number you see is the index of its parent -
since we can't hold onto a reference to a mutable object, we're holding onto
the index of the parent in that array of items in the forest.
...oh hey, we've invented pointers!
If we didn't have pointers, we'd have to do something similar - create
and hold onto a data structure that we could index into, and use
those indices to refer to object's locations in out data structure.
What if we couldn't return from functions?
This whole time, we've been assuming that you call a function, and
when you're done, you return from that function, clutching a bloody
return value in your clenched fist. But what if you could never go home again?
We'd just go on and on, my friend...
def Constructor(self, some_args, continuation):
self.var1 = var1
self.var2 = var2
continuation(self)
Let's take a simple constructor...
Continuation Passing Style
Actually, in some sense, it's simpler than ordinary function
calling.
“
we should... make the correspondence between the program (spread out in text space) and the process (spread out in time) as trivial as possible.
”
- Dijkstra, Goto Considered Harmful
our original island-counting program
items = {}
or node in nodes:
items[node] = DisjointSetItem(node)
for node in nodes:
dsi = items[node]
for edge in node.outgoing_edges:
end_node_dsi = items[edge.end_node]
dsi.union(end_node_dsi)
let's look at our island-counting program again
let's just look at the first part...
items = {}
for node in nodes:
items[node] = DisjointSetItem(node)
Now let's translate this to CPS.
without iteration or mutable variables
def process_node(items, nodes, index):
if index == len(nodes):
return items
node = nodes[index]
items = items.add(node,
DisjointSetItem(node))
return process_node(items,
nodes,
index + 1)
# process all the nodes:
items = process_nodes({}, nodes, 0)
straightforward if long-winded:
in continuation passing style
def process_node(items, nodes, index, k):
if index == len(nodes):
k(items)
node = nodes[index]
def add_and_continue(item):
add_item(items, node, item, rest)
def rest(items):
process_node(items, nodes, index+1, k)
DisjointSetItem(node, add_and_continue)
And now we get to the batshit insane continuation-passing style version
when we're done, we just go deeper
def process_node(items, nodes, index, k):
if index == len(nodes):
k(items)
# ...
So, here, where we would have returned, we just pass our map onto the
next bit bit of code, this continuation (which, by convention, is
called k).
our first helper function
node = nodes[i]
def add_and_continue(item):
add_item(items, node, item, rest)
The first helper function can't call add on the map, because this time it has to
pass in a continuation as the last argument.
our second helper function, which contains the recursion
def rest(items):
process_node(items, nodes, index + 1, k)
The second continuation does the recursion, which was at the end of
our original function.
we pass a node & a continuation to our constructor
DisjointSetItem(node, add_and_continue)
Finally, we call our constructor with the first helper function, to get this
show on the road
def process_node(items, nodes, index, k):
if index == len(nodes):
k(items)
# node = nodes[index]
# def add_and_continue(item):
# add_item(items, node, item, rest)
# def rest(items):
# process_node(items, nodes, index+1, k)
# DisjointSetItem(node, add_and_continue)
So let's walk through how this would get execute in the case of
one-element list.
def process_node(items, nodes, index, k):
# if index == len(nodes):
# k(items)
node = nodes[index]
# def add_and_continue(item):
# add_item(items, node, item, rest)
# def rest(items):
# process_node(items, nodes, index+1, k)
DisjointSetItem(node, add_and_continue)
We're not, so we look at the first node.
def process_node(items, nodes, index, k):
# if index == len(nodes):
# k(items)
# node = nodes[index]
def add_and_continue(item):
add_item(items, node, item, rest)
# def rest(items):
# process_node(items, nodes, index+1, k)
# DisjointSetItem(node, add_and_continue)
add_and_continue creates a new map containing only a mapping
from this node to the item, and passes it to rest.
def process_node(items, nodes, index, k):
# if index == len(nodes):
# k(items)
# node = nodes[index]
# def add_and_continue(item):
# add_item(items, node, item, rest)
def rest(items):
process_node(items, nodes, index+1, k)
# DisjointSetItem(node, add_and_continue)
rest passes the map into a recursive call to process_node, with index = 1.
def process_node(items, nodes, index, k):
if index == len(nodes):
k(items)
# node = nodes[index]
# def add_and_continue(item):
# add_item(items, node, item, rest)
# def rest(items):
# process_node(items, nodes, index+1, k)
# DisjointSetItem(node, add_and_continue)
And since we're at the end this time, since index = 1 and we only had 1 node to
process, we finally call k, which is the rest of our program, passing in the
new items map.
Does continuation passing style
actually work?
Does this CPS stuff actually work?
avoiding stack overflow
A common way to work around this is to use a a trampoline!
avoiding stack overflow
def trampoline(k):
while hasattr(k, '__call__'):
k = k.call()
return k
The idea is that instead of each function calling the continuation, it returns
(I know, oh cheating sadness! - let's say, "bounces back") a function to the
trampoline, which is a loop that calls all of the continuations for us.
so, what have we accomplished?
Well, we've replaced two perfectly good lines of code
with a mess of incomprehensible gibberish. Win!
Let it go!
(We don't need that stuff, anyway!)
Most of all, though, this showed us that even if we get rid of most of our
programming tools: mutable variables, the stack, and returning from
functions, we can still do everything we want.
Don't Take it for Granted
(thank you!)
@DanielleSucher dsucher@gmail.com http://daniellesucher.com
Go ahead, take it for granted! If we lost all this stuff that we rely on in the
languages we use every day, so what? We'd get over it. We could rebuild what
we lost (and make it bigger, stronger, faster! &c)
