On Saturday, 21 May 2016 at 18:25:46 UTC, Walter Bright wrote:
On 5/20/2016 11:18 PM, poliklosio wrote:
I have an Idea of reproducible, less-than-exponential time
mangling, although I
don't know how actionable.
Leave mangling as is, but pretend that you are mangling
something different, for
example when the input is
foo!(boo!(bar!(baz!(int))), bar!(baz!(int)), baz!(int))
pretend that you are mangling
foo!(boo!(bar!(baz!(int))), #1, #2)
Where #1 and #2 are special symbols that refer to stuff that
was **already in
the name**, particularly:
#1: bar!(baz!(int))
#2: baz!(int)
This is what LZW compression does, except that LZW does it in
general rather than just for identifiers.
That's true, but a general compression algorithm requires a
stream of chars as input, so to compress something of exponential
size you still need exponential runtime in order to iterate
(while compressing) on the exponential input.
The idea was to avoid such exponential iteration in the first
place by doing some sort of caching.
My thinking is that if you only reduce size but keep exponential
runtime, you are going to have to revisit the issue in a few
months anyway when people start using things you enabled more
heavily.
Anyway I wish you good luck with all this!
