Re: [MIT-Scheme-devel] Y combinator RTL

[Taylor R Campbell]

I think I see what's going on, although not yet how to fix it.

To evaluate (f (lambda (x) ...)), the compiler tries to reuse the
frame from the application of (lambda (g) ...) to what the compiler
knows to be itself.  So the stack currently has g followed by g
followed by the caller's continuation.  This is important -- there are
two references to g in the topmost block on the stack, one being g's
self-reference as a closure and one being the location of a normal
variable.

So the compiler computes the dependency graph of block positions for
subproblem evaluation, and determines that it is safe to evaluate the
operator expression (f) and store it in the frame's operator position
before moving on to the operand (the lambda) -- the lambda will need
the value that was in the operator position, but it's also in an
operand position, so it's OK to clobber the operator position first.

The RTL generator then obediently generates code to evaluate f and
store it in the frame's operator position, clobbering one of the
references to g in the topmost stack block but not the other
reference.  Next, the RTL generator generates code to cons a closure
for the lambda and fill it with its free variables, namely g.  To do
this, it finds the location of g in the topmost stack block using
FIND-CLOSURE-VARIABLE.

I think it would be OK if FIND-VARIABLE-CLOSURE in turn simply asked
VARIABLE-OFFSET where g lay in the block, but there's some hairy logic
in here to redirect closure references if possible which I don't
understand at all, in FIND-VARIABLE-INTERNAL.  If I change

   (and nearest-closure ...)

to #F in FIND-VARIABLE-INTERNAL, so that in this case it doesn't try
to redirect the closure reference, then LIAR generates good code for
Y.  But that probably has lots of other bad consequences, and would
probably break multiclosures.

(LIAR's approach to multiclosures is pretty kludgey; it'd be nice if
Someone^TM replaced it by a more principled approach that guarantees
space safety while maximizing sharing like I hear SML/NJ does.)