[MIT-Scheme-devel] Very curious problem

[Joe Marshall]

I just added code to implement LETREC*, which expands like this:

(let ((name1 (make-unassigned-reference-trap))
      (name2 (make-unassigned-reference-trap)))

  (set! name1 (lambda (a b) ...))
  (set! name2 (lambda (c d) ...))

   body)

It is just like an internal define, except the names are bound as
required variables rather than as aux variables in the enclosing form.

I also changed the existing LETREC to expand like this:
(let ((name1 (make-unassigned-reference-trap))
      (name2 (make-unassigned-reference-trap)))

  (let ((temp1 (lambda (a b) ...))
        (temp2 (lambda (c d) ...)))

    (set! name1 temp1)
    (set! name2 temp2)) ; inner let ends here

   body)
Which basically delays the assignments until all the values are evaluated.

I did not change internal defines.

Everything continued to work, with one bizarre exception.  The compiler goes
into an infinite loop when compiling "compiler/rtlbase/rtlcon.scm" and aborts
with an `out of memory' exception.

A little poking around revealed that the problem comes from the `package'
form near the end of rtlcon.scm.  `Package' is a simple macro that defines
some names at top level and wraps a block in a let expression.  The
`define/export' macro
expands into a SET! which assigns the top level names to some values
that are closed in the let expression.  It is very simple.

The package form does not use LETREC or LETREC*, but there are some
uses of NAMED-LET.

NAMED-LET can be expanded in several ways depending on a switch.  The
default value of that switch was `LETREC', so the expansion of NAMED-LET
changed slightly:
((letrec ((foo (lambda (arg1 arg2) (body))))
      foo) init1 init2)
which then expanded to:
((let ((foo (make-unassigned-reference-trap)))
     (let ((foo-value (lambda (arg1 arg2) (body))))
       (set! foo foo-value))
     foo) init1 init2)

I use the past tense here because I added other values for that switch.
You can set it to LETREC*, in which case named let expands like this:
((letrec* ((foo (lambda (arg1 arg2) (body))))
      foo) init1 init2)

  ((let ((foo (make-unassigned-reference-trap)))
     (set! foo  (lambda (arg1 arg2) (body)))
     foo) init1 init2)
or you can set it to 'internal-define, in which case you get this expansion:
((let ()
  (define (foo arg1 arg2) (body))
  foo) init1 init2)
the define is scanned out and you get something very much like the LETREC*,
except it is an aux variable being assigned, so you get a compound lambda, etc.

So, here's the mystery.  If I set the named-let expansion to anything other
than LETREC, everything works.  If I remove the `package' macro around the
forms, everything works.  It only goes into an infinite loop if I have the outer
package form, AND expand named-let into LETREC.

It should be easy to see that the LETREC form:
((let ((foo (make-unassigned-reference-trap)))
     (let ((foo-value (lambda (arg1 arg2) (body))))
       (set! foo foo-value))
     foo) init1 init2)

ought to be equivalent to the LETREC* form
  ((let ((foo (make-unassigned-reference-trap)))
     (set! foo  (lambda (arg1 arg2) (body)))
     foo) init1 init2)

in the particular case of binding exactly one name.  In any case,
either expansion
works just fine for the entire rest of the Scheme system.  So the question is:
what is it about this particular use site that causes the compiler to go into an
infinite loop?

(I'm suspicious of the value analysis.  The compiler tends to generate closure
creation code in the LETREC case, while it can avoid it in the LETREC* or
internal define case.)
---
As an aside:  I changed the default expansion of named-let to be
'internal-define,
so the only change to semantics is if you explicitly use LETREC.  In any case,
it is difficult to detect the change unless the values being bound in the letrec
capture a continuation while being evaluated.

-- 
~jrm