[Chicken-hackers] [PATCH] [LONG] Fix (hopefully) for #1068

[Peter Bex]

Hi all,

After the letrec behaviour was changed, we noticed a new bug which
only occurred under very specific circumstances: so far only the
testcase for the kanren egg exhibited the error.  See #1068 for
more information.

It turned out that this was due to its heavy use of combinators, inside
letrecs.  As you can see in the ticket, I tried to pinpoint the error
and at first thought it was due to bogus "returnvar" handling in the
CPS conversion code.  However, after fixing this, the error in Kanren
disappeared, only to uncover a second error in Kanren.

It turned out that the returnvar handling was a red herring: it only
masked the real underlying problem, which is that the optimizer marks
variables as "replacable" without paying attention to scoping.  This
means that it blindly assumes that when a variable refers to another
variable, the original one can be replaced with the one that refers to
it (or the other way around, whichever it happens to prefer).

This is incorrect, as it may cause variables to be used outside the
lexical scope where they are introduced.  As complex variables are
only replacable if they're lambdas I decided to add a complicated check
to ensure it didn't happen in case of lambdas which contained free
variables (patch number 2 in the ticket).  Neither I nor Felix
understand why this hasn't caused problems before, as it could really
cause a lot of trouble when variables get moved around blindly.

Because this stuff is extremely hairy, I wasn't sure whether my fix
was correct, or would break other things, so I asked Felix for some
advice.  He declared that this code was pretty bogus, but didn't see
much we could do about it either.  According to him, my patch is okay
in principle, but a little heavyweight, so he came up with a simpler
check: if the variable is marked as being "captured" (used outside its
home scope), it should not be replaced.

I think the patch for the returnvar code should still be applied, as
it simplifies the CPS conversion code a little.  It won't fundamentally
change anything else, though.  I've tested both patches and it
introduces no problems and fixes the Kanren issue (#1068), so I think it
should probably go in.

Since I'm having some problems with my laptop I'm on a slow machine
right now, so I can't do extensive testing or benchmarking.  It would
be great if someone looking at this patch could perform a quick
Salmonella run to see if no other eggs are broken, and run a few
benchmarks comparing it against current master or 4.8.0.5 (you could
use the one from https://github.com/mario-goulart/chicken-benchmarks).
Please remember that you should compare optimized builds.  That means,
without DEBUGBUILD, because this has been changed to check more things
now.

Cheers,
Peter
-- 
http://www.more-magic.net

0001-Fix-1068-partially-by-removing-returnvar-passing-fro.patch
Description: Text document

0002-Fix-for-1068-2-don-t-allow-captured-lambdas-to-get-r.patch
Description: Text document