# An example of substituability test that is recursive

forax at univ-mlv.fr forax at univ-mlv.fr
Thu Jan 31 18:41:48 UTC 2019

```> De: "John Rose" <john.r.rose at oracle.com>
> À: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "Karen Kinnear" <karen.kinnear at oracle.com>, "valhalla-spec-experts"
> <valhalla-spec-experts at openjdk.java.net>
> Envoyé: Jeudi 31 Janvier 2019 19:03:13
> Objet: Re: An example of substituability test that is recursive

> On Jan 31, 2019, at 3:19 AM, Remi Forax < [ mailto:forax at univ-mlv.fr |
> forax at univ-mlv.fr ] > wrote:

>> here is an example that recurse to its death with the current prototype

> Fun fact: Change the Link to a Tree and you go from
> linear to exponential in the depth. *Just* a fun fact;
> it doesn't change Remi's point, which is that we can
> construct value object instances that have large
> "interiors".

you mean like this:

private final int value;
private final Object next;
private final Object next2;

public Link(int value, Object next) {
this.value = value;
this.next = next;
this.next2 = next;
}
}

yes, i creates a DAG that will be too long to traverse :(
you basically, DDOS yourself if you do a ==.

> (Definition of the day: The "interior" of a value
> object instance is the set of variables that determine
> its substitutability equality and substitutability hash.)

> To me this takes on a different shade of urgency
> when I think about turning arrays into values.
> Suppose we had Arrays.valueCopyOf to take an
> immutable value-typed snapshot of an array.
> Very useful! (Sort of like frozen arrays.) You
> can make a size 1_000 value-array very quickly
> and easily, and its interior would be as large
> as Remi's laboriously constructed list.

Facebook skip [1] has an operation like this, data structure are mutable (for the runtime, from the user POV everything is non mutable) inside a function and frozen when publish outside.

[1] [ http://www.skiplang.com/ | http://www.skiplang.com/ ]

Rémi
```