About linkedlist
Locked
12
12
 
|
On Feb 3, 2012, at 10:54 PM, Igor Stasenko wrote: > On 3 February 2012 21:42, Stéphane Ducasse <[hidden email]> wrote: >> lukas may be you should send that to the vm mailing-list. >> If you need we can ask igor :) (even if he is busy right now). >> > implementing it wont be a big deal. > > i just trying to understand, what is "destructive" vs > "non-destructive" behavior in > replaceFrom:to:with:startingAt: > Destructive: slots 3-5 all contains originals value from slot 2. Non-Destructive: slots 3-5 contains originals values from slots 2-4. > is it right in my understanding that you want to always meet a > following criteria: > > receiver replaceFrom: a to: b with: replacement startingAt: c. > > a to: b do: [:i | > self assert: (receiver at: i) == (replacement at: c + i - 1) ] > > ? (irrespectible, of course if receiver == replacement or not ) Yes. Basically the same thing you ensure in C by using memmove instead of memcpy. Cheers. Henry |
|
|
In reply to this post by Stéphane Ducasse
On 3 February 2012 20:40, Stéphane Ducasse <[hidden email]> 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-from-ml-to-smalltalk >> 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 >>> >> > > |
|
|
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? Stef On Feb 4, 2012, at 3:33 PM, Frank Shearar wrote: > On 3 February 2012 20:40, Stéphane Ducasse <[hidden email]> 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-from-ml-to-smalltalk >>> 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 >>>> >>> >> >> > |
|
|
On 5 February 2012 10:30, Stéphane Ducasse <[hidden email]> 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 <[hidden email]> 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-from-ml-to-smalltalk >>>> 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 >>>>> >>>> >>> >>> >> > > |
|
In reply to this post by Stéphane Ducasse
Hi Stef,
Thanks for the explanation frank Immutable data structures are used extensively in functional languages in which data structures are immutable by default. One benefit of the approach is when multi-threading you don't need to synchronise changes to such structures or objects containing them. For example all Clojure's data-structures are immutable by default [1]. There's been a lot of interesting work on providing performance guarantees so that creating copies avoids scaling with linear time [2], while still having sensible access and iteration performance.
[2] http://clojure.org/functional_programming#Functional%20Programming--Immutable%20Data%20Structures
Apologies if I'm stating the obvious Nick |
|
|
The term Mutable means "can change" and Immutable means "cannot change". An Immutable Object means that the state of the Object cannot change after its creation. Here the String is immutable means that you cannot change the object itself, but you can change the reference to the object. Changing an object means to use its methods to change one of its fields or the fields are public (and not final ), so that you can be updated from outside without accessing them via methods. Once string object is created its data or state can't be changed but a new string object is created. An important point to note here is that, while the String object is immutable, its reference variable is not. More...Interview Questions
Mark |
«
Return to Pharo Smalltalk Developers
|
1 view|%1 views
| Free forum by Nabble | Edit this page |