An example of substituability test that is recursive

John Rose john.r.rose at
Thu Jan 31 23:03:35 UTC 2019

(FYI, offline comment with my reply.)

Begin forwarded message:

From: John Rose <john.r.rose at>
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>
Cc: Rémi Forax <forax at>, Brian Goetz <brian.goetz at>

On Jan 31, 2019, at 11:28 AM, Palo Marton <palo.marton at <mailto:palo.marton at>> 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

More information about the valhalla-spec-observers mailing list