The change in the definition of DEFINE exposed a bug in our handling of
LETREC. Since LETREC is tied up in our tail recursion requirement, we
got into a discussion about closure conversion. Closure conversion is
one of those areas where more analysis often yields better results.
That is fine, but reproducible results are important in BitC --
especially in the area of tail recursion. Because of this, it is
necessary for us to state the *minimal* degree of closure analysis that
every conforming BitC compiler is required to perform. In particular, we
need to explain why:
(define pos-fact
(letrec ((pos-fact (lambda (x)
(if ((= x 0) 1
(* x (pos-fact (- x 1)))))))
pos-fact))
[that is: any conventionally self-recursive procedure] has an empty
closure, and why in:
(define pos-fact
(lambda (x)
(letrec ((fact-accum (lambda (x accum)
(if (= x 0) accum
(fact-accum (- x 1) (* accum x))))))
(fact-accum x 1)))
the implementation of fact-accum is tail recursive even though it is
closed over fact-accum.
Rules: Given a lambda form L and some /id/ that is free in L:
PHASE I: INITIAL CLOSURE CONSTRUCTION
1. If /id/ resolves to a globally defined identifier, stop. No
globally resolved identifier is ever inserted into a closure
record.
2. If /id/ is locally bound:
A. if /id/ is mutable, it must be heap-converted, and the reference
to the heap-converted object must be included in the closure
record.
B. if /id/ is non-mutable but of non-reference type, it must be
heap-converted and the reference to the heap-converted object
must be included in the closure record.
C. if /id/ is non-mutable and of reference type, a copy of /id/
must be included in the closure record.
D. if /id/ is an immutably bound to a LAMBDA form [NOT merely to
an expression of function type], and /id/ appears
IN NON-APPLICATIVE POSITION in L then /id/ must be included
in the closure record.
PHASE II: CLOSURE SIMPLIFICATION
If the resulting closure consists exclusively of "rule 4" identifiers,
then no closure is required and the lambda form L can be emitted as a
procedure label rather than as a procedure object.
Under these rules, the /pos-fact/ bound by the first letrec is a "rule
4" entry in the initial closure, and it is the only entry. The closure
is therefore dropped and the lambda form is hoisted as a closureless
procedure.
The same is true of FACT-ACCUM.
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
