Re: An example of substituability test that is recursive

[Karen Kinnear]

Actually - I was unclear - apologies. K

> On Jan 31, 2019, at 3:54 PM, fo...@univ-mlv.fr wrote:
> 
> 
> 
> De: "Karen Kinnear" 
> À: "Remi Forax" 
> Cc: "John Rose" , "valhalla-spec-experts" 
> 
> Envoyé: Jeudi 31 Janvier 2019 21:36:09
> Objet: Re: An example of substituability test that is recursive
> Option #1 was what I was suggesting in the meeting two weeks ago - if this 
> starts
> to recurse too deeply, create a worklist - which should give you the same 
> result.
> 
> If you switch to .Equals - you might get a different result …
> 
> yes, you are right, i did not understand what you mean by "expected 
> behavior", my bad on that.
> 
> 
> thanks,
> Karen
> 
> regards,
> Rémi
> 
> 
> On Jan 31, 2019, at 1:46 PM, fo...@univ-mlv.fr 
> wrote:
> 
> 
> 
> De: "John Rose" mailto:john.r.r...@oracle.com>>
> À: "Remi Forax" mailto:fo...@univ-mlv.fr>>
> Cc: "Karen Kinnear"  >, "valhalla-spec-experts" 
>  >
> Envoyé: Jeudi 31 Janvier 2019 19:05:33
> Objet: Re: An example of substituability test that is recursive
> On Jan 31, 2019, at 6:34 AM, fo...@univ-mlv.fr  
> wrote:
> 
> The other solution is to say that == should do an upcall to equals (after the 
> null checking and the class checking), if equals throw a StackOverflow, it's 
> the expected behavior because the user is in control of that behavior.
> 
> What you are doing here, I think, is exposing a requirement
> that we *don't* use the control stack for recursion on subst.
> testing (or hashing).  That's a reasonable requirement.
> It leads to a worklist algorithm for doing this tricky thing,
> just like we had to do many times in the JIT.
> 
> 
> 
> IMO that the other solution,
> solution 1: you use a worklist (and also perhaps a marking algorithm to avoid 
> to crawle the DAG)
> solution 2: you claim it's too complex and you just let the user deal with it 
> by calling equals() (and provide a way for a user to call the default subst).
> 
> Rémi

Re: An example of substituability test that is recursive

[forax]

> De: "Karen Kinnear" 
> À: "Remi Forax" 
> Cc: "John Rose" , "valhalla-spec-experts"
> 
> Envoyé: Jeudi 31 Janvier 2019 21:36:09
> Objet: Re: An example of substituability test that is recursive

> Option #1 was what I was suggesting in the meeting two weeks ago - if this
> starts
> to recurse too deeply, create a worklist - which should give you the same
> result.

> If you switch to .Equals - you might get a different result …

yes, you are right, i did not understand what you mean by "expected behavior", 
my bad on that. 

> thanks,
> Karen

regards, 
Rémi 

>> On Jan 31, 2019, at 1:46 PM, [ mailto:fo...@univ-mlv.fr | fo...@univ-mlv.fr ]
>> wrote:

>>> De: "John Rose" < [ mailto:john.r.r...@oracle.com | john.r.r...@oracle.com 
>>> ] >
>>> À: "Remi Forax" < [ mailto:fo...@univ-mlv.fr | fo...@univ-mlv.fr ] >
>>> Cc: "Karen Kinnear" < [ mailto:karen.kinn...@oracle.com |
>>> karen.kinn...@oracle.com ] >, "valhalla-spec-experts" < [
>>> mailto:valhalla-spec-experts@openjdk.java.net |
>>> valhalla-spec-experts@openjdk.java.net ] >
>>> Envoyé: Jeudi 31 Janvier 2019 19:05:33
>>> Objet: Re: An example of substituability test that is recursive

>>> On Jan 31, 2019, at 6:34 AM, [ mailto:fo...@univ-mlv.fr | fo...@univ-mlv.fr 
>>> ]
>>> wrote:

 The other solution is to say that == should do an upcall to equals (after 
 the
 null checking and the class checking), if equals throw a StackOverflow, 
 it's
 the expected behavior because the user is in control of that behavior.

>>> What you are doing here, I think, is exposing a requirement
>>> that we *don't* use the control stack for recursion on subst.
>>> testing (or hashing). That's a reasonable requirement.
>>> It leads to a worklist algorithm for doing this tricky thing,
>>> just like we had to do many times in the JIT.

>> IMO that the other solution,
>> solution 1: you use a worklist (and also perhaps a marking algorithm to 
>> avoid to
>> crawle the DAG)
>> solution 2: you claim it's too complex and you just let the user deal with 
>> it by
>> calling equals() (and provide a way for a user to call the default subst).

>> Rémi

Re: An example of substituability test that is recursive

[Karen Kinnear]

Option #1 was what I was suggesting in the meeting two weeks ago - if this 
starts
to recurse too deeply, create a worklist - which should give you the same 
result.

If you switch to .Equals - you might get a different result …

thanks,
Karen

> On Jan 31, 2019, at 1:46 PM, fo...@univ-mlv.fr wrote:
> 
> 
> 
> De: "John Rose" 
> À: "Remi Forax" 
> Cc: "Karen Kinnear" , "valhalla-spec-experts" 
> 
> Envoyé: Jeudi 31 Janvier 2019 19:05:33
> Objet: Re: An example of substituability test that is recursive
> On Jan 31, 2019, at 6:34 AM, fo...@univ-mlv.fr  
> wrote:
> 
> The other solution is to say that == should do an upcall to equals (after the 
> null checking and the class checking), if equals throw a StackOverflow, it's 
> the expected behavior because the user is in control of that behavior.
> 
> What you are doing here, I think, is exposing a requirement
> that we *don't* use the control stack for recursion on subst.
> testing (or hashing).  That's a reasonable requirement.
> It leads to a worklist algorithm for doing this tricky thing,
> just like we had to do many times in the JIT.
> 
> 
> 
> IMO that the other solution,
> solution 1: you use a worklist (and also perhaps a marking algorithm to avoid 
> to crawle the DAG)
> solution 2: you claim it's too complex and you just let the user deal with it 
> by calling equals() (and provide a way for a user to call the default subst).
> 
> Rémi
> 

Re: An example of substituability test that is recursive

[forax]

> De: "John Rose" 
> À: "Remi Forax" 
> Cc: "Karen Kinnear" , "valhalla-spec-experts"
> 
> Envoyé: Jeudi 31 Janvier 2019 20:43:33
> Objet: Re: An example of substituability test that is recursive

> On Jan 31, 2019, at 10:41 AM, [ mailto:fo...@univ-mlv.fr | fo...@univ-mlv.fr ]
> wrote:

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

> The complexity is exponential in depth, and
> can be more than linear in heap allocation,
> because of the risk of repeat traversals.

> A worklist algorithm could make use of the
> secret implementation identity of heap nodes
> to push the complexity back down to heap
> allocation size. A portable algorithm could
> not. This is one more bit of evidence it should
> be a system intrinsic rather than a vanilla library
> function.

yes, 
i buy that ! 
it will be always more expensive in Java, 

Rémi 

Re: An example of substituability test that is recursive

[John Rose]

On Jan 31, 2019, at 10:52 AM, Brian Goetz  wrote:
> 
> Let’s not do this to Java, shall we?
> 
> https://twitter.com/seldo/status/1090931182227861508 
> 
> 
>> solution 2: you claim it's too complex and you just let the user deal with 
>> it by calling equals() (and provide a way for a user to call the default 
>> subs).

That one motivated this:

https://twitter.com/JohnRose00/status/1091046489256644608

Re: An example of substituability test that is recursive

[John Rose]

On Jan 31, 2019, at 10:41 AM, fo...@univ-mlv.fr wrote:
> 
> yes, i creates a DAG that will be too long to traverse :(
> you basically, DDOS yourself if you do a ==.

The complexity is exponential in depth, and
can be more than linear in heap allocation,
because of the risk of repeat traversals.

A worklist algorithm could make use of the
secret implementation identity of heap nodes
to push the complexity back down to heap
allocation size.  A portable algorithm could
not.  This is one more bit of evidence it should
be a system intrinsic rather than a vanilla library
function.

Re: An example of substituability test that is recursive

[Brian Goetz]

Let’s not do this to Java, shall we?

https://twitter.com/seldo/status/1090931182227861508

> solution 2: you claim it's too complex and you just let the user deal with it 
> by calling equals() (and provide a way for a user to call the default subs).

Re: An example of substituability test that is recursive

[forax]

> De: "John Rose" 
> À: "Remi Forax" 
> Cc: "Karen Kinnear" , "valhalla-spec-experts"
> 
> Envoyé: Jeudi 31 Janvier 2019 19:05:33
> Objet: Re: An example of substituability test that is recursive

> On Jan 31, 2019, at 6:34 AM, [ mailto:fo...@univ-mlv.fr | fo...@univ-mlv.fr ]
> wrote:

>> The other solution is to say that == should do an upcall to equals (after the
>> null checking and the class checking), if equals throw a StackOverflow, it's
>> the expected behavior because the user is in control of that behavior.

> What you are doing here, I think, is exposing a requirement
> that we *don't* use the control stack for recursion on subst.
> testing (or hashing). That's a reasonable requirement.
> It leads to a worklist algorithm for doing this tricky thing,
> just like we had to do many times in the JIT.

IMO that the other solution, 
solution 1: you use a worklist (and also perhaps a marking algorithm to avoid 
to crawle the DAG) 
solution 2: you claim it's too complex and you just let the user deal with it 
by calling equals() (and provide a way for a user to call the default subst). 

Rémi 

Re: An example of substituability test that is recursive

[forax]

> De: "John Rose" 
> À: "Remi Forax" 
> Cc: "Karen Kinnear" , "valhalla-spec-experts"
> 
> 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:fo...@univ-mlv.fr |
> fo...@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: 

static value class Link { 
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 

Re: An example of substituability test that is recursive

[John Rose]

On Jan 31, 2019, at 6:34 AM, fo...@univ-mlv.fr wrote:
> 
> The other solution is to say that == should do an upcall to equals (after the 
> null checking and the class checking), if equals throw a StackOverflow, it's 
> the expected behavior because the user is in control of that behavior.

What you are doing here, I think, is exposing a requirement
that we *don't* use the control stack for recursion on subst.
testing (or hashing).  That's a reasonable requirement.
It leads to a worklist algorithm for doing this tricky thing,
just like we had to do many times in the JIT.

Re: An example of substituability test that is recursive

[John Rose]

On Jan 31, 2019, at 3:19 AM, Remi Forax  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".

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

Re: An example of substituability test that is recursive

[forax]

- Mail original -
> De: "Brian Goetz" 
> À: "Remi Forax" 
> Cc: "Karen Kinnear" , "valhalla-spec-experts" 
> 
> Envoyé: Jeudi 31 Janvier 2019 17:56:47
> Objet: Re: An example of substituability test that is recursive

> Currently, `==` is almost useless on lambdas, as we disclaim nearly all
> promises.  What this would mean is that `==` becomes slightly less useless and
> slightly more expensive.  It’s not obvious this is a bad trade (or that it
> really matters, because people are discouraged from using `==` on lambdas
> anyway.)
> 

I agree.
and it's still useless because there is no guarantee that with
  Runnable r1 = () -> {};
  Runnable r2 = () -> {};
r1 and r2 use the same proxy, so r1 == r2 can still return false.


I'm just saying that having recursive value types are more frequent that what i 
was thinking before.

Rémi


>> On Jan 31, 2019, at 11:53 AM, Remi Forax  wrote:
>> 
>> Thinking a little more about this example,
>> i think it will be more common if we retrofit lambdas to be value type 
>> because a
>> series of composition of lambdas is a kind of linked list in term of data
>> structure in memory.
>> 
>> For the composition of lambdas, a stack overflow is unlikely because 
>> otherwise
>> calling the lambda will stack overflow too but it means that == will be slow
>> (because it does a recursive comparison).
>> 
>> Rémi
>> 
>> - Mail original -
>>> De: "Remi Forax" 
>>> À: "Karen Kinnear" 
>>> Cc: "valhalla-spec-experts" 
>>> Envoyé: Jeudi 31 Janvier 2019 12:19:32
>>> Objet: An example of substituability test that is recursive
>> 
>>> Hi Karen,
>>> here is an example that recurse to its death with the current prototype
>>> 
>>> import java.lang.invoke.ValueBootstrapMethods;
>>> import java.util.stream.IntStream;
>>> 
>>> public class Substituable {
>>> static value class Link {
>>>   private final int value;
>>>   private final Object next;
>>> 
>>>   public Link(int value, Object next) {
>>> this.value = value;
>>> this.next = next;
>>>   }
>>> 
>>>   static Object times(int count) {
>>> return IntStream.range(0, count).boxed().reduce(null, (acc, index) -> 
>>> new
>>> Link(index, acc), (l1, l2) -> { throw null; });
>>>   }
>>> }
>>> 
>>> 
>>> public static void main(String[] args) {
>>>   var l = Link.times(1_000);
>>> 
>>>   //System.out.println(l == l);
>>>   System.out.println(ValueBootstrapMethods.isSubstitutable(l, l));
>>> }
>>> }
>>> 
>>> 
> >> Rémi

Re: An example of substituability test that is recursive

[Remi Forax]

Thinking a little more about this example,
i think it will be more common if we retrofit lambdas to be value type because 
a series of composition of lambdas is a kind of linked list in term of data 
structure in memory.

For the composition of lambdas, a stack overflow is unlikely because otherwise 
calling the lambda will stack overflow too but it means that == will be slow 
(because it does a recursive comparison).

Rémi  

- Mail original -
> De: "Remi Forax" 
> À: "Karen Kinnear" 
> Cc: "valhalla-spec-experts" 
> Envoyé: Jeudi 31 Janvier 2019 12:19:32
> Objet: An example of substituability test that is recursive

> Hi Karen,
> here is an example that recurse to its death with the current prototype
> 
> import java.lang.invoke.ValueBootstrapMethods;
> import java.util.stream.IntStream;
> 
> public class Substituable {
>  static value class Link {
>private final int value;
>private final Object next;
>
>public Link(int value, Object next) {
>  this.value = value;
>  this.next = next;
>}
>
>static Object times(int count) {
>  return IntStream.range(0, count).boxed().reduce(null, (acc, index) -> new
>  Link(index, acc), (l1, l2) -> { throw null; });
>}
>  }
>  
>  
>  public static void main(String[] args) {
>var l = Link.times(1_000);
>
>//System.out.println(l == l);
>System.out.println(ValueBootstrapMethods.isSubstitutable(l, l));
>  }
> }
> 
> 
> Rémi

Re: An example of substituability test that is recursive

[Brian Goetz]

Currently, `==` is almost useless on lambdas, as we disclaim nearly all 
promises.  What this would mean is that `==` becomes slightly less useless and 
slightly more expensive.  It’s not obvious this is a bad trade (or that it 
really matters, because people are discouraged from using `==` on lambdas 
anyway.)

> On Jan 31, 2019, at 11:53 AM, Remi Forax  wrote:
> 
> Thinking a little more about this example,
> i think it will be more common if we retrofit lambdas to be value type 
> because a series of composition of lambdas is a kind of linked list in term 
> of data structure in memory.
> 
> For the composition of lambdas, a stack overflow is unlikely because 
> otherwise calling the lambda will stack overflow too but it means that == 
> will be slow (because it does a recursive comparison).
> 
> Rémi  
> 
> - Mail original -
>> De: "Remi Forax" 
>> À: "Karen Kinnear" 
>> Cc: "valhalla-spec-experts" 
>> Envoyé: Jeudi 31 Janvier 2019 12:19:32
>> Objet: An example of substituability test that is recursive
> 
>> Hi Karen,
>> here is an example that recurse to its death with the current prototype
>> 
>> import java.lang.invoke.ValueBootstrapMethods;
>> import java.util.stream.IntStream;
>> 
>> public class Substituable {
>> static value class Link {
>>   private final int value;
>>   private final Object next;
>> 
>>   public Link(int value, Object next) {
>> this.value = value;
>> this.next = next;
>>   }
>> 
>>   static Object times(int count) {
>> return IntStream.range(0, count).boxed().reduce(null, (acc, index) -> new
>> Link(index, acc), (l1, l2) -> { throw null; });
>>   }
>> }
>> 
>> 
>> public static void main(String[] args) {
>>   var l = Link.times(1_000);
>> 
>>   //System.out.println(l == l);
>>   System.out.println(ValueBootstrapMethods.isSubstitutable(l, l));
>> }
>> }
>> 
>> 
>> Rémi

Re: An example of substituability test that is recursive

[Karen Kinnear]

Remi,

Thank you. So there were two kinds of “recurse to its death” we talked about
1) expected behavior
2) surprise

This strikes me as the expected behavior - where we can set expectations.

If we were to always return false - how would you make this kind of example 
work?

thanks,
Karen

> On Jan 31, 2019, at 6:19 AM, Remi Forax  wrote:
> 
> Hi Karen,
> here is an example that recurse to its death with the current prototype
> 
> import java.lang.invoke.ValueBootstrapMethods;
> import java.util.stream.IntStream;
> 
> public class Substituable {
>  static value class Link {
>private final int value;
>private final Object next;
> 
>public Link(int value, Object next) {
>  this.value = value;
>  this.next = next;
>}
> 
>static Object times(int count) {
>  return IntStream.range(0, count).boxed().reduce(null, (acc, index) -> 
> new Link(index, acc), (l1, l2) -> { throw null; });
>}
>  }
> 
> 
>  public static void main(String[] args) {
>var l = Link.times(1_000);
> 
>//System.out.println(l == l);
>System.out.println(ValueBootstrapMethods.isSubstitutable(l, l));
>  }
> }
> 
> 
> Rémi
>