On 5 February 2012 10:30, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
Thanks for the explanation frank btw (did you dd it in the class comment because it would be gorgeous). I learned something today so I'm happy. Now what is the typical use case for such persistent structure?
Indeed I made sure to write a decent class comment :) The use case is twofold: * any time you want to stop caring about whether you need to copy a collection or can safely pass it around (so avoiding the "foo copy addAll: bar; yourself" idiom) * any time you want to be able to undo changes to some structure. In particular, I wanted to add an "or unifier" to my unification library. (Unification is like bidirectional pattern matching. In particular, we build up an equivalence relation over the nodes in two structures. After that, if any partitions in the relation contain variables, we can construct a mapping from variables to concrete values, to give a most general unifier.) This would let me say "can X or Y unify against this thing?" - (Node left: (Leaf value: #x asVariable)) or: (Node right: (Leaf value: #x asVariable)) =? someRandomTree will * only do something useful if someRandomTree has exactly one child Leaf, and * will tell us what the value of that Leaf is, by telling us how to map from the variable called #x to that value. What I quickly found was that the unification algorithm - which used a normal, non-persistent (ephemeral) union-find - kept its state after attempting to unify the first disjunction clause. That meant that unifying the clause would sometimes fail. What I actually wanted was to be able to say * given some partial term relation U, * try unify the first clause to get a new term relation U1 * but if unification fails, start back with U and try calculate a new term relation U2 on the second clause's nodes Using a _persistent_ union-find lets me thus roll back or undo the term relation construction and revert to an older version. frank
Stef
On Feb 4, 2012, at 3:33 PM, Frank Shearar wrote:
On 3 February 2012 20:40, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
I wasn't sure what double-ended versus single-ended meant, and found some answer at the obvious place [1] which mentions Ada.Containers.Vectors is a dynamic array implementation which seems consistent with C++ [2]. While looking around I happened to bump into [3] which was too much for me but may be of interest to anyone playing with data structres. Â Skimming this shows it discussing efficiency of data structures in functional languages together with lazy variants of imperative language data structures. Â Would such apply to Smalltalk or is the object-oriented style of Smalltalk considered imperative rather than functional?
The standard tool set - OrderedCollection, Array, etc., are not functional at all - (myArray at: 1 put: 2) mutates myArray, - so I'd put them firmly on the "imperative" side of the fence.
There's nothing stopping one from writing functional data structures - Levente Uzonyi's written some persistent data structures, as have I. ("Persistent" means you get new versions of a data structure; if you hang onto those old versions you can roll back your changes.)
Can you explain a bit more Persistent?
Sure! A persistent data structure is an _apparently_ immutable data structure: editing the structure returns you a _new_ structure. If you can modify only the latest version of the structure, it's _partially_persistent_; if you can edit any version it is _fully_persistent_. Of course "edit" here means "get a new collection representing the edit"
For example, if you load the PersistentUnionFind package (no external dependencies) and print out this:
| p p1 p2 p3 | p := PersistentCollection initially: #(1 2 3). p1 := p at: 1 put: 4. p2 := p1 at: 2 put: 5. p3 := p at: 3 put: 0. {p. p1. p2. p3.} collect: #asArray
you get, with inline comments added:
 #("p:" #(1 2 3) "p1:" #(4 2 3) "p2:" #(4 5 3) "p3:" #(1 2 0))
So you can see the different versions of the original array: p1 is p plus one replacement; p2 is p plus two replacements (or equivalently p1 plus one replacement).
You still get efficient access to the latest version, and the old versions describe themselves as a stack of undo operations - "I'm like the latest version, but with these changes".
So if you just print out p1, you'll see:
p1 printString. 'Ref(Diff(1, 4, Ref(Diff(3, 3, Ref(Arr(#(1 2 0)))))))'
The series of Diffs tell you how to get from the latest version - p3 - to the version of p1: "take p3 ( #(1 2 0) ), at index 3 put a 3, and at index 1 put a 1".
A Ref is a delegate: it allows your reference to something to stay the same even though the thing referenced changes.
Internally, as you access the latest version of the Collection the structure rewrites itself: if it's pointing to a Diff it "reroots" itself. (This does have the issue that if you hang onto two versions of the collection and access each version alternately, the PersistentCollection will waste a lot of time constantly rerooting itself.)
You can see then that keeping a reference to an old version allows you to undo arbitrary changes to the collection.
PersistentUnionFind _should_ load cleanly into Pharo: if it doesn't, let me know and I'll fix it so it does.
frank
Tx
http://www.squeaksource.com/Nutcracker/ is my own play area for these sorts of structures - PersistentUnionFind looks like a functional data structure while internally massively using side effects. http://www.lshift.net/blog/2011/12/31/translating-a-persistent-union-find-fr... has references to the original papers I used for my translation.
Okasaki's book is really good reading, if a bit advanced. It also has a bunch of stuff beyond just showing functional data structures. (Note that the red-black tree implementation is _incomplete_ - he leaves deleting nodes as an exercise for the reader. (See http://matt.might.net/articles/red-black-delete/))
frank
[1] http://en.wikipedia.org/wiki/Double-ended_queue [2] http://en.wikipedia.org/wiki/Sequence_container_%28C%2B%2B%29 [3] http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf