Jonathan S. Shapiro wrote:
> On Thu, 2008-07-17 at 17:19 -0400, Swaroop Sridhar wrote:
>>> Good! How much problem do you anticipate with implementing the
>>> change? :-)
>> This is not hard to implement, but re-writing the
>> (define (f x) <body>) as
>>
>> (define f (letrec ((f (lambda (x) <body>))) f))
>>
>> where body actually uses `f' will introduce closure construction for the
>> lambda being bound, since the lambda is now capturing a non-global
>> non-local variable `f'.
>>
>> I guess we can recognize this case by hand, but I wanted to note the
>> issue.
>
> Don't we already recognize self-recursion as a special case?
>
>
> I tend to think that we should handle (recognize) the self-binding case
> specially in any case.
Here is a proposal for recognizing functions defined at let/letrec that
need not be closure converted. Functions that can be directly hoisted
and written as function labels (in the C sense) do not require closure
conversion.
An identifier f defined at a let/letrec is considered to be a label if:
1) It is bound to a function. That is, it is of the form:
(letrec ((f (lambda ... )) ...)
2) It has immutable type
3) All of the variables used in the definition of f are either
a) locals b) globals, or c) labels.
This rule will allow both functions f and g below to be declared labels:
Example 1:
(define top
(letrec ((f (lambda (x)
(let ((g (lambda (y) (f y))))
(g x)))))
f))
Example 2:
(define top
(letrec ((f (lambda (x) (g x)))
(g (lambda (x) (f x))))
f))
- - - - - - - - - - - - - - - - - - - - -
> In any case, the rewrite specification was intended as a specification
> of semantics, not a specification of the intended implementation. This
> definitely should NOT induce a closure construction.
Not sure if the following is necessary, but we can handle the special
case of define easily as an interim measure.
We can make a distinction between the define ASTs written in the form
(define f ...) and (define (f x) ...), and treat the first similar to
let and the second one similar to letrec in the resolver and type
checker. As far as I can tell, no other passes will require any change.
- - - - - - - - - - - - - - - - - - -
* TAIL RECURSION *
I think that the tail recursion rule must be updated to be required
only for immutable function bindings:
For example, the following function is not a self application:
(let ((q 10))
((letrec ((p (lambda (x) q (p x))))
(letrec ((f (lambda (y) (set! f p) (f y)))) ... )
The closure environment for f and that of p are different. Yet,
they are assignment compatible. The call to f within f's body
cannot use the same environment it received, since 'f' changes during
its execution.
Tail recursion is currently being checked after closure conversion, and
only safe functions are implemented in a tail recursive way. This
handles less cases than what is specified.
Swaroop.
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
