Double-linked immutable classes

[Henrik Schmidt]

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

[Matthew Pocock]

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

Matthew

--

Dr Matthew Pocock

Visitor, School of Computing Science, Newcastle University

mailto: turingate...@gmail.com

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

tel: (0191) 2566550

mob: +447535664143

[Runar Bjarnason]

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

[Miles Sabin]

On Fri, Jul 29, 2011 at 6:24 PM, Runar Bjarnason <runar...@gmail.com> 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

--
Miles Sabin
tel: +44 7813 944 528
gtalk: mi...@milessabin.com
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

[Vlad Patryshev]

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

Thanks,
-Vlad

[Chris Twiner]

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

http://scala-scales.googlecode.com/svn/sites/snapshots/scales/scales-xml_2.9.0-1/0.0.1/doc/index.html#scales.utils.Tree
http://scala-scales.googlecode.com/svn/sites/snapshots/scales/scales-xml_2.9.0-1/0.0.1/doc/index.html#scales.utils.Path

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.

[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

[HamsterofDeath]

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...

[Randall Schulz]

You equate deferred evaluation to mutation?


Randall Schulz

[Vlad Patryshev]

Single Assignment is supposed to be a safe thing.

Thanks,
-Vlad

[Tony Morris]

-----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).

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk4zwvsACgkQmnpgrYe6r61QcgCcDkKTc6O+A9VFrP6IfYA4i9Yh
XLkAn0yXyfFaYfnAJRcU6QYehzvbAh++
=9wYW
-----END PGP SIGNATURE-----

[Dobes Vandermeer]

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.parent

w2: 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?

[Lex]

> 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.

[Joshua Gooding]

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? :)

[Joshua Gooding]

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

[Randall R Schulz]

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

[Dobes Vandermeer]

On Sat, Jul 30, 2011 at 11:40 PM, Lex <lex...@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> :paste

class Foo {

val bar = x+1

val 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.bar

res0: 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.

[Tony Morris]

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();

[Dobes Vandermeer]

On Sun, Jul 31, 2011 at 11:06 AM, Tony Morris <tonym...@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

 

[Tony Morris]

On 31/07/11 14:00, Dobes Vandermeer wrote:

> On Sun, Jul 31, 2011 at 11:06 AM, Tony Morris
> <tonym...@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.

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.

[Naftoli Gugenheim]

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

[Chris Twiner]

On Jul 31, 2011 6:00 AM, "Dobes Vandermeer" <dob...@gmail.com> wrote:
>
> On Sun, Jul 31, 2011 at 11:06 AM, Tony Morris <tonym...@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.

[y]

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