An example of substituability test that is recursive

[John Rose]

(FYI, offline comment with my reply.)

Begin forwarded message:

From: John Rose <john.r.rose at oracle.com>
Subject: Re: An example of substituability test that is recursive
Date: January 31, 2019 at 11:48:53 AM PST
To: Palo Marton <palo.marton at gmail.com>
Cc: Rémi Forax <forax at univ-mlv.fr>, Brian Goetz <brian.goetz at oracle.com>

On Jan 31, 2019, at 11:28 AM, Palo Marton <palo.marton at gmail.com <mailto:palo.marton at gmail.com>> wrote:
> 
> (Sorry to bother you with direct email, I'm only on observer list...)
> 
> Here is a possible solution for "infinitive recursion/DDOS" problem with cmp:
> Make values that might be affected by this problem singletons on the heap, so compare function will be just fast pointer comparison (but at the cost of much slower creation).
> 
> Larger values will likely be on the heap anyway, so this will just add another "way" of how values are stored. 
> 1) flattened
> 2) heap
> 3) heap+forced singleton
> 
> Palo

Not bad.  By forced singleton I think you mean a structural intern,
kind of like string interning?  (Long ago for lists it was called
hash-consing.)  The whole point of forcing subst into acmp
is to create a virtual emulation of such semantics.

So we could switch implementation tactics for problem spots
like polymorphic value fields.

— John