My notes from Danielle’s talk at Øredev14.
.jpg)
Inspired by Le Ton Beau de Marot – Hofstadter. Different translations of the same poem, all different, all valid.
UnionFind – categorize items into disjoint sets. Each item belongs to one, and only one set.
Makes it really fast to query each item and find out what set it is in.
E.g. which island do people live on. Can preprocess, as long as queries are really fast in the moment.
What if each has a capital? Will be really easy. But don’t, so how do we build it up?
We want to build up a representation, each has a set representative. Doesn’t matter what it is, can choose at random. When add a new item, set it’s representative.
Keep track of each set in a tree structure. Call union on each pair of nodes in the set, and join them into the same set.
Used in Open Trip Planner – in real life, graph traversing things.
Union: for each node, find it’s root. Lower rank wins, becomes the root of the whole tree.
Side effect: reform the tree so that is shallower.
Some fancy stuff this uses:
- classes
- recursion
- mutable variables
- pointers
- returning from functions
- automatic memory management
- if statements
What if we couldn’t have classes?
- Like a functional language.
- In C, just use a struct.
- Can even manage inheritance without classes.
Let’s talk about the stack
- Need them for recursion.
- Never heard of language without them.
- Someone invented it, we used to live without it.
- See: The Amsterdam Plot.
- find() won’t work without recursion.
- Loses variables, everything loses it’s state.
- What do we do?
- First, de-optimise.
- Live without shallow trees.
- Now we don’t need to preserve recursion, use tail recursion instead.
- Tail recursion becomes a loop.
Tail call optimisation – some turn it into a loop. won’t happen in python. Means you can’t do some recursion in python.
Ruby will, if you configure it.
Scala will warn you if you get in it’s way, @tailrec annotation.
Stack free recession – the purpose of a stack in recursion is to create an inverse for any function by keying in time and space – Otto J A Smith.
We could just build our own stack! Use “append” and “pop” as our inverse seeing options.
What if we had no variables?
Name for value = just means names in registers. Going to talk about mutable variables. Like erlang and haskell. Once you bind a variable to some value, you cannot change it.
Look at union – all about side effects.
Use forest (collection of trees! lol!) each method returns a forrest which is the same as the previous one, except with the changes.
Makes for an ugly API, but this is about how we would deal with stuff not how to make pretty APIs.
We must always return a new forrest because we can’t change the existing forest.
How do we make this reasonably performant?
Shallow trees can approximate arrays (like Clojure’s persistent vectors).
Bit-partitioned tries. Copying persistent vectors easier, lots of shared memory.
The forrest can keep an “array” of items, and update it as it goes along.
… oh hey, we invented pointers.
(if something else wasn’t keeping track of where things were and how to access, we would have to keep track of it).
What if we couldn’t return from functions?
Never go home again, just had to go deeper deeper deeper until the call stack finally landed.
Continuation passing style. (see Djiksta, Goto Considered Harmful).
Does it actually work? Not in python. Because no tail code optimisation. Each time you add another frame to the stack, eventually you run out.
Use a trampoline.
What have we accomplished?
Replaced 3 lines of code with a bunch of gibberish.
It is used, mostly in compilers.
Let it go! We don’t need that stuff anyway. Don’t need variables, stack, return… we can always build it up again if we need to.