Double-linked immutable classes

Purely immutable structures are inherently acyclic. One workaround is to have operations work on (pathToChild, Child) pairs rather than on Child directly.
Matthew


On 29 July 2011 17:20, Henrik Schmidt <henrik.hsm@gmail.com> wrote:

Hi there,

Say I have two classes:

case class Root(child: Child); case class Child(parent: Root)

How would I go about constructing a Root with a reference to a Child
with a reference to the "outer" Root? The use case would be to
construct an immutable tree where the parent can be reached directly
from a child.

/Henrik

--
Dr Matthew PocockVisitor, School of Computing Science, Newcastle Universitymailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozertel: (0191) 2566550mob: +447535664143

lazy val parent: Root = new Root(new Child(parent))

On Fri, Jul 29, 2011 at 6:24 PM, Runar Bjarnason wrote:
> lazy val parent: Root = new Root(new Child(parent))

Only if you have an infinite stack and an awful lot of time ;-)

Alternatively you could try this,

scala> :paste
// Entering paste mode (ctrl-D to finish)

class Root(child0: => Child) {
lazy val child = child0
}

class Child(parent0: => Root) {
lazy val parent = parent0
}

// Exiting paste mode, now interpreting.

defined class Root
defined class Child

scala> val root : Root = new Root(new Child(root))
root: Root = Root@1f23418

scala> root.child.parent.child.parent
res0: Root = Root@1f23418

Cheers,

Miles

Probably a design issue. Cross-linking entities might be a cause of many troubles.

Thanks,
-Vlad


On Fri, Jul 29, 2011 at 9:20 AM, Henrik Schmidt <henrik.hsm@gmail.com> wrote:

Hi there,

Say I have two classes:

case class Root(child: Child); case class Child(parent: Root)

How would I go about constructing a Root with a reference to a Child
with a reference to the "outer" Root? The use case would be to
construct an immutable tree where the parent can be reached directly
from a child.

/Henrik

A zipper, Path and Tree from Scales Xml, (Scalaz also has this):

http://scala-scales.googlecode.com/svn/sites/snapshots/scales/scales-xml...
http://scala-scales.googlecode.com/svn/sites/snapshots/scales/scales-xml...

Is a very good immutable structure / technique for handling immutable trees.

The only issue is to get to a child you have to go via each parent.
There are lots of easy to follow examples on the internet about
zippers, if Scales Xml's usage or Scalazs isn't appropriate for you.

On Fri, Jul 29, 2011 at 6:20 PM, Henrik Schmidt wrote:
> Hi there,
>
> Say I have two classes:
>
> case class Root(child: Child); case class Child(parent: Root)
>
> How would I go about constructing a Root with a reference to a Child
> with a reference to the "outer" Root? The use case would be to
> construct an immutable tree where the parent can be reached directly
> from a child.
>
> /Henrik

Here's an example of an immutable, doubly linked pair of classes.

https://github.com/nuttycom/scala-exercises/blob/master/solutions/Twins....

Kris

On Fri, Jul 29, 2011 at 10:20 AM, Henrik Schmidt wrote:
> Hi there,
>
> Say I have two classes:
>
> case class Root(child: Child); case class Child(parent: Root)
>
> How would I go about constructing a Root with a reference to a Child
> with a reference to the "outer" Root? The use case would be to
> construct an immutable tree where the parent can be reached directly
> from a child.
>
> /Henrik

i consider this a cheat like setting a reference via reflection at a
later time. it behaves as if its immutable, but there's this dirty
little mutable secret...

Am 29.07.2011 21:49, schrieb Kris Nuttycombe:
> Here's an example of an immutable, doubly linked pair of classes.
>
> https://github.com/nuttycom/scala-exercises/blob/master/solutions/Twins....
>
> Kris
>
> On Fri, Jul 29, 2011 at 10:20 AM, Henrik Schmidt wrote:
>> Hi there,
>>
>> Say I have two classes:
>>
>> case class Root(child: Child); case class Child(parent: Root)
>>
>> How would I go about constructing a Root with a reference to a Child
>> with a reference to the "outer" Root? The use case would be to
>> construct an immutable tree where the parent can be reached directly
>> from a child.
>>
>> /Henrik

You equate deferred evaluation to mutation?


Randall Schulz

Single Assignment is supposed to be a safe thing.

Thanks,
-Vlad


On Fri, Jul 29, 2011 at 1:44 PM, HamsterofDeath <h-star@gmx.de> wrote:

i consider this a cheat like setting a reference via reflection at a
later time. it behaves as if its immutable, but there's this dirty
little mutable secret...

Am 29.07.2011 21:49, schrieb Kris Nuttycombe:
> Here's an example of an immutable, doubly linked pair of classes.
>
> https://github.com/nuttycom/scala-exercises/blob/master/solutions/Twins.scala
>
> Kris
>
> On Fri, Jul 29, 2011 at 10:20 AM, Henrik Schmidt <henrik.hsm@gmail.com> wrote:
>> Hi there,
>>
>> Say I have two classes:
>>
>> case class Root(child: Child); case class Child(parent: Root)
>>
>> How would I go about constructing a Root with a reference to a Child
>> with a reference to the "outer" Root? The use case would be to
>> construct an immutable tree where the parent can be reached directly
>> from a child.
>>
>> /Henrik

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

There is a wiki entry on uniqueness types.
http://en.wikipedia.org/wiki/Uniqueness_type

(See also the Clean programming language).

On 30/07/11 18:36, Vlad Patryshev wrote:
> Single Assignment is supposed to be a safe thing.
>
> Thanks, -Vlad
>
>
> On Fri, Jul 29, 2011 at 1:44 PM, HamsterofDeath
> wrote:
>
>> i consider this a cheat like setting a reference via reflection
>> at a later time. it behaves as if its immutable, but there's this
>> dirty little mutable secret...
>>
>> Am 29.07.2011 21:49, schrieb Kris Nuttycombe:
>>> Here's an example of an immutable, doubly linked pair of
>>> classes.
>>>
>>>
>>
https://github.com/nuttycom/scala-exercises/blob/master/solutions/Twins....
>>>
>>>
>>
Kris
>>>
>>> On Fri, Jul 29, 2011 at 10:20 AM, Henrik Schmidt
>>>
>> wrote:
>>>> Hi there,
>>>>
>>>> Say I have two classes:
>>>>
>>>> case class Root(child: Child); case class Child(parent:
>>>> Root)
>>>>
>>>> How would I go about constructing a Root with a reference to
>>>> a Child with a reference to the "outer" Root? The use case
>>>> would be to construct an immutable tree where the parent can
>>>> be reached directly from a child.
>>>>
>>>> /Henrik
>>
>>
>

The fact that the tricks listed work at all was quite surprising to me, so I dug a bit further and I think this is the secret mutation he refers to:
scala> val what:Root = new Child(what).parent what: Root = null
scala> val w2:Root = new Root(new Child(w2)).child.parentw2: Root = null
Basically, "what" is secretly mutable because it is accessible before it is initialized.  So when you write:
scala> val root : Root = new Root(new Child(root))
root: Root = Root@1f23418
You get something like:
val root : Root = null root = new Root(new Child(=> root))  <--- oops we have to mutate the val now because it is accessible before it is initialized!
I suppose for whatever reasons Scala puts a val in scope before it is initialized.  Seems awfully weird and un-intuitive to me, but I guess it does allow some interesting hacks with cyclic lists that "look" like there's no mutation going on by deferring their immutability a little bit.  Maybe that is why they allow this?
On Sat, Jul 30, 2011 at 4:36 PM, Vlad Patryshev <vpatryshev@gmail.com> wrote:

Single Assignment is supposed to be a safe thing.

Thanks,
-Vlad


On Fri, Jul 29, 2011 at 1:44 PM, HamsterofDeath <h-star@gmx.de> wrote:

i consider this a cheat like setting a reference via reflection at a
later time. it behaves as if its immutable, but there's this dirty
little mutable secret...

Am 29.07.2011 21:49, schrieb Kris Nuttycombe:
> Here's an example of an immutable, doubly linked pair of classes.
>
> https://github.com/nuttycom/scala-exercises/blob/master/solutions/Twins.scala
>
> Kris
>
> On Fri, Jul 29, 2011 at 10:20 AM, Henrik Schmidt <henrik.hsm@gmail.com> wrote:
>> Hi there,
>>
>> Say I have two classes:
>>
>> case class Root(child: Child); case class Child(parent: Root)
>>
>> How would I go about constructing a Root with a reference to a Child
>> with a reference to the "outer" Root? The use case would be to
>> construct an immutable tree where the parent can be reached directly
>> from a child.
>>
>> /Henrik

> val root : Root = null
> root = new Root(new Child(=> root))  <--- oops we have to mutate the val now
> because it is accessible before it is initialized!
> I suppose for whatever reasons Scala puts a val in scope before it is
> initialized.  Seems awfully weird and un-intuitive to me, but I guess it
> does allow some interesting hacks with cyclic lists that "look" like there's
> no mutation going on by deferring their immutability a little bit.  Maybe
> that is why they allow this?

This seems awfully weird and un-intuitive because you are not familiar
with the scala's by-name parameters. (=> root) is a by-name parameter,
it will not be evaluated when invoking the constructor, it will be
evaluated later, when it is accessed.
Scala does not mutate vals or put vals in scope before they are
initialized. What you see is a combination of deferred evaluation
using by-name parameter (not deferred immutability) and a lazy val,
which is initialized the first time it is accessed. Both by name
parameters and lazy vals are the standard Scala features, so there are
no hacks or any compiler magic involved.

Perhaps set up a Tree class with an inner Root object, and an inner
Child class. Make the constructer for Tree accept a 'type Node =
(String, List[Node])' (is that valid?) and then construct the tree
based on that? Or am I just crazy? :)

On Jul 29, 9:20 am, Henrik Schmidt wrote:
> Hi there,
>
> Say I have two classes:
>
> case class Root(child: Child); case class Child(parent: Root)
>
> How would I go about constructing a Root with a reference to a Child
> with a reference to the "outer" Root? The use case would be to
> construct an immutable tree where the parent can be reached directly
> from a child.
>
> /Henrik

Ok I'm crazy. 'type Node = (String, List[Node])' isn't valid. Any
ideas how to make it valid?

On Jul 30, 1:43 pm, Joshua Gooding wrote:
> Perhaps set up a Tree class with an inner Root object, and an inner
> Child class.  Make the constructer for Tree accept a 'type Node =
> (String, List[Node])' (is that valid?) and then construct the tree
> based on that?  Or am I just crazy? :)
>
> On Jul 29, 9:20 am, Henrik Schmidt wrote:
>
>
>
>
>
>
>
> > Hi there,
>
> > Say I have two classes:
>
> > case class Root(child: Child); case class Child(parent: Root)
>
> > How would I go about constructing a Root with a reference to a Child
> > with a reference to the "outer" Root? The use case would be to
> > construct an immutable tree where the parent can be reached directly
> > from a child.
>
> > /Henrik

On Saturday 30 July 2011, Joshua Gooding wrote:
> Ok I'm crazy. 'type Node = (String, List[Node])' isn't valid. Any
> ideas how to make it valid?
>
> ...

class Node(name: String, children: List[Node])

Randall Schulz

On Sat, Jul 30, 2011 at 11:40 PM, Lex <lexn82@gmail.com> wrote:

> val root : Root = null
> root = new Root(new Child(=> root))  <--- oops we have to mutate the val now
> because it is accessible before it is initialized!
> I suppose for whatever reasons Scala puts a val in scope before it is
> initialized.  Seems awfully weird and un-intuitive to me, but I guess it
> does allow some interesting hacks with cyclic lists that "look" like there's
> no mutation going on by deferring their immutability a little bit.  Maybe
> that is why they allow this?

Scala does not mutate vals or put vals in scope before they are
initialized.

I disagree.  If a val was not in scope during its initializer, then saying:
val r:Root = new Root(new Child(r))
Would return a compile error: "undeclared variable ``r''" because the name "r" would not be available until after it was initialized.  That is what I meant when I said "r" is in scope.
For me, such an error would be intuitive and the current behavior is not, because vals are supposed to be constant.  I do remember that during my earlier experimentation I tried:
val r = new Root(new Child(r))
In which case Scala complained "Recursive value needs a type".  Aha!  So things are in scope during their declaration to support recursion.  Seems odd for a "val" but makes sense for a method, so perhaps this is just because vals and methods are treated similarly by the compiler.  With a bit more probing I find that vals are actually in scope BEFORE their declaration, too, in a class (just like a method would be):
scala> :pasteclass Foo {val bar = x+1val x = 5}
And just like a local val, they have different values at different times - they initialize to zero or null and are only set to a value on their first assignment.
scala> foo.barres0: Int = 1 // <--- I expected to get 5, but in fact I get zero
Although this isn't a disaster it could cause some confusion from time to time.  It's hardly intuitive to allow use of a val at a time where it doesn't have its "value" set yet.

What you see is a combination of deferred evaluation
using by-name parameter (not deferred immutability) and a lazy val,
which is initialized the first time it is accessed. Both by name
parameters and lazy vals are the standard Scala features, so there are
no hacks or any compiler magic involved.

I understand the use of deferred evaluation and by-name parameters; I guess when I used the word "hack" I just meant a tricky way to work around the a conflict between the desire to use immutable objects AND have cyclic data structures by exploiting a design quirk of the language / compiler.

On 31/07/11 13:00, Dobes Vandermeer wrote:
> I understand the use of deferred evaluation and by-name parameters
Then you would understand the termination semantics under certain
conditions of mutual recursion for different evaluation strategies. I
have some exercises that point out the problems here, but they are
quite involved. Nevertheless, Scala is strict by default, which
carries implications for termination -- there is no "hack".

Java does similar (see vmspec around section 5 iirc):

abstract class Eggs {
  abstract void m();

  Eggs() {
    m();
  }
}

class Toast extends Eggs {
  private int x = 2;

  Toast() {
    x = 3;
  }

  public void m() {
    System.out.println("x = " + x);
  }

  public static void main(String[] args) {
    new Toast();
  }
}






--
Tony Morris
http://tmorris.net/

On Sun, Jul 31, 2011 at 11:06 AM, Tony Morris <tonymorris@gmail.com> wrote:

On 31/07/11 13:00, Dobes Vandermeer wrote:
> I understand the use of deferred evaluation and by-name parameters
Then you would understand the termination semantics under certain
conditions of mutual recursion for different evaluation strategies

Hmm, no I don't think that follows.  The explanation of by-name parameters and lazy vals seems to come without any discussion of " termination semantics under certain conditions of mutual recursion for different evaluation strategies".  Perhaps you can tell me where I can learn more about that.  

Scala is strict by default, which
carries implications for termination -- there is no "hack".

Perhaps we're using a different definition of the word "hack". 

Java does similar (see vmspec around section 5 iirc):

I'm not particularly interested in rolling a discussion of Java's own language quirks into this thread.  It seems like a separate issue to me.
I originally posted to expand on why "HamsterOfDeath" would have considered this a cheat or a hack, and thus probably a technique to avoided.
I suspect this technique should probably also be avoided on the basis of its memory/performance implications.  Presumably the lazy val technique creates one or more additional objects and classes as part of its implementation, whereas using a "var" would just create a regular java field.
So, if you *really* need a cyclic data structure my approach (and suggestion) would be to use a private var in each node and only assign it once.  Less hackish, no extra classes/object created, and less head-scratching for a novice Scala coder like myself to figure why the hell your code doesn't throw a compile error in the first place.
Regards,
Dobes


 

On 31/07/11 14:00, Dobes Vandermeer wrote:
> On Sun, Jul 31, 2011 at 11:06 AM, Tony Morris
> wrote:
>
>> ** On 31/07/11 13:00, Dobes Vandermeer wrote:
>>> I understand the use of deferred evaluation and by-name
>>> parameters
>> Then you would understand the termination semantics under
>> certain conditions of mutual recursion for different evaluation
>> strategies
>>
>
> Hmm, no I don't think that follows.

What doesn't? Understanding lazy evaluation is all about understanding
program termination. A formal definition might help here (or not):

f _|_ != _|_

f is said to be non-strict in its argument.

We can observe this easily:

scala> def bottom = sys.error("bang! _|_")
bottom: Nothing

scala> false && bottom
res0: Boolean = false

&& is said to be non-strict in its second argument.

> The explanation of by-name parameters and lazy vals seems to come
> without any discussion of " termination semantics under certain
> conditions of mutual recursion for different evaluation
> strategies". Perhaps you can tell me where I can learn more about
> that.


Actually, every definition of by-name parameters should include a
discussion about termination semantics, since that is the entire point
of lazy evaluation (emphasis on entire).

I refer to mutual recursion because that is the nature of the original
problem, and one which termination can easily be altered by evaluation
strategy.

Try writing a monadic parser for zero-or-many elements and one-or-many
elements. Notice how they can be defined in terms of each other with a
choice combinator in one case and an applicative functor in the other:

* zeroOrMany(p) = oneOrMany ||| succeed(Nil)
* oneOrMany(p) = for { a <- p; as <- oneOrMany(p) } yield (a::as)

Now fiddle with the evaluation semantics. This is an interesting
exercise that points out how easy it is to fail termination with a
slight bout of over-strictness.


>
>
>> Scala is strict by default, which carries implications for
>> termination -- there is no "hack".
>>
>
> Perhaps we're using a different definition of the word "hack".

Perhaps. I am referring to the well-established constraints of
computability theory, which are to be accepted when Scala's evaluation
model is accepted. To accept that, then call it a "hack" is a hack.

>
> Java does similar (see vmspec around section 5 iirc):
>>
>
> I'm not particularly interested in rolling a discussion of Java's
> own language quirks into this thread. It seems like a separate
> issue to me.
>
> I originally posted to expand on why "HamsterOfDeath" would have
> considered this a cheat or a hack, and thus probably a technique to
> avoided.
>
> I suspect this technique should probably also be avoided on the
> basis of its memory/performance implications. Presumably the lazy
> val technique creates one or more additional objects and classes as
> part of its implementation, whereas using a "var" would just create
> a regular java field.
>
> So, if you *really* need a cyclic data structure my approach (and
> suggestion) would be to use a private var in each node and only
> assign it once. Less hackish, no extra classes/object created, and
> less head-scratching for a novice Scala coder like myself to figure
> why the hell your code doesn't throw a compile error in the first
> place.
>
> Regards,
>
> Dobes
>

This is very oddballs.

--
Tony Morris
http://tmorris.net/

Put it in an object rather than using it at the top scope?

On Sat, Jul 30, 2011 at 6:12 PM, Joshua Gooding <skavookie@gmail.com> wrote:

Ok I'm crazy.  'type Node = (String, List[Node])' isn't valid.  Any
ideas how to make it valid?

On Jul 30, 1:43 pm, Joshua Gooding <skavoo...@gmail.com> wrote:
> Perhaps set up a Tree class with an inner Root object, and an inner
> Child class.  Make the constructer for Tree accept a 'type Node =
> (String, List[Node])' (is that valid?) and then construct the tree
> based on that?  Or am I just crazy? :)
>
> On Jul 29, 9:20 am, Henrik Schmidt <henrik....@gmail.com> wrote:
>
>
>
>
>
>
>
> > Hi there,
>
> > Say I have two classes:
>
> > case class Root(child: Child); case class Child(parent: Root)
>
> > How would I go about constructing a Root with a reference to a Child
> > with a reference to the "outer" Root? The use case would be to
> > construct an immutable tree where the parent can be reached directly
> > from a child.
>
> > /Henrik

On Jul 31, 2011 6:00 AM, "Dobes Vandermeer" <dobesv@gmail.com> wrote:
>
> On Sun, Jul 31, 2011 at 11:06 AM, Tony Morris <tonymorris@gmail.com> wrote:
>>
>> On 31/07/11 13:00, Dobes Vandermeer wrote:
>> > I understand the use of deferred
>

Snip, as others answered the rest and this may be of interest to others...

>
>
> I suspect this technique should probably also be avoided on the basis of its memory/performance implications.  Presumably the lazy val technique creates one or more additional objects and classes as part of its implementation, whereas using a "var" would just create a regular java field.
>

It's written in many other places but worth repeating: lazy vals add a single volatile int to an instance. Performance wise this forces the smallest possible overhead for thread safety of that evaluation.

That int is shared for all lazy vals in that instance, which is pretty cool.

That said if you are using lazy vals to cache results in a presumed hotspot make sure the calculation is far slower than the lookup (by profiling it).  By the same token if the call would be fast enough to repeat via a def then you will save on both the int and resulting vals memory usage.

I had exactly that issue when profiling and performance tweaking (memory and cpu) Scales Xml.  Swapping lazy vals for defs brought a reduction of 30Mb for a 12Mb raw xml and a speed up of 8-10%. That speed increase is important in an xml parser but might not be for another given application.

Either way, rule of thumb (as ever) is to profile and see if it really is a problem. Lazy vals have a great semantic and shouldn't be dismissed unless they are a proven issue for your code.

some context to Tony's point:
http://blog.tmorris.net/a-fling-with-lazy-evaluation/

On Jul 31, 12:59 am, Tony Morris wrote:
> On 31/07/11 14:00, Dobes Vandermeer wrote:
>
> > On Sun, Jul 31, 2011 at 11:06 AM, Tony Morris
> > wrote:
>
> >> ** On 31/07/11 13:00, Dobes Vandermeer wrote:
> >>> I understand the use of deferred evaluation and by-name
> >>> parameters
> >> Then you would understand the termination semantics under
> >> certain conditions of mutual recursion for different evaluation
> >> strategies
>
> > Hmm, no I don't think that follows.
>
> What doesn't? Understanding lazy evaluation is all about understanding
> program termination. A formal definition might help here (or not):
>
> f _|_ != _|_
>
> f is said to be non-strict in its argument.
>
> We can observe this easily:
>
> scala> def bottom = sys.error("bang! _|_")
> bottom: Nothing
>
> scala> false && bottom
> res0: Boolean = false
>
> && is said to be non-strict in its second argument.
>
> > The explanation of by-name parameters and lazy vals seems to come
> > without any discussion of " termination semantics under certain
> > conditions of mutual recursion for different evaluation
> > strategies". Perhaps you can tell me where I can learn more about
> > that.
>
> Actually, every definition of by-name parameters should include a
> discussion about termination semantics, since that is the entire point
> of lazy evaluation (emphasis on entire).
>
> I refer to mutual recursion because that is the nature of the original
> problem, and one which termination can easily be altered by evaluation
> strategy.
>
> Try writing a monadic parser for zero-or-many elements and one-or-many
> elements. Notice how they can be defined in terms of each other with a
> choice combinator in one case and an applicative functor in the other:
>
> * zeroOrMany(p) = oneOrMany ||| succeed(Nil)
> * oneOrMany(p) = for { a <- p; as <- oneOrMany(p) } yield (a::as)
>
> Now fiddle with the evaluation semantics. This is an interesting
> exercise that points out how easy it is to fail termination with a
> slight bout of over-strictness.
>
>
>
> >> Scala is strict by default, which carries implications for
> >> termination -- there is no "hack".
>
> > Perhaps we're using a different definition of the word "hack".
>
> Perhaps. I am referring to the well-established constraints of
> computability theory, which are to be accepted when Scala's evaluation
> model is accepted. To accept that, then call it a "hack" is a hack.
>
>
>
>
>
>
>
>
>
>
>
> > Java does similar (see vmspec around section 5 iirc):
>
> > I'm not particularly interested in rolling a discussion of Java's
> > own language quirks into this thread. It seems like a separate
> > issue to me.
>
> > I originally posted to expand on why "HamsterOfDeath" would have
> > considered this a cheat or a hack, and thus probably a technique to
> > avoided.
>
> > I suspect this technique should probably also be avoided on the
> > basis of its memory/performance implications. Presumably the lazy
> > val technique creates one or more additional objects and classes as
> > part of its implementation, whereas using a "var" would just create
> > a regular java field.
>
> > So, if you *really* need a cyclic data structure my approach (and
> > suggestion) would be to use a private var in each node and only
> > assign it once. Less hackish, no extra classes/object created, and
> > less head-scratching for a novice Scala coder like myself to figure
> > why the hell your code doesn't throw a compile error in the first
> > place.
>
> > Regards,
>
> > Dobes
>
> This is very oddballs.
>
> --
> Tony Morrishttp://tmorris.net/