On Wed, 2008-03-12 at 12:00 +0000, Sam Mason wrote:
> On Tue, Mar 11, 2008 at 05:54:01PM -0400, Swaroop Sridhar wrote:
> > The by-ref operator is a limited form of the address (&) operator. There
> > is actually no problem as long as the reference does not escape its
> > definition.
>
> Then I'm confused, I thought that was the point of shap's original
> email---the fact that by-refs can escape.
Swaroop later corrected me, though now that I think about it again I am
not convinced that he had it right.
Ignoring BY-REF, any stack-allocated closed-over variable is forced into
the heap so that the stack frame is not aliased by the closure. This is
done automatically by the compiler. Swaroop and I sometimes refer to
this process as "heapification".
If a by-reference parameter could be treated in all respects as an
argument passing optimization, then it would follow that the by-ref
parameter should be heapified in exactly the same way. When Swaroop
argued yesterday that the [internal] make-closure operation copies its
parameters, I think this is what he was saying. Note that this would
eliminate the dangling reference into the stack frame that is created by
using a BY-REF parameter.
Unfortunately -- and this is the part I did not consider yesterday -- a
BY-REF parameter CANNOT be treated in all respects as an argument
passing optimization. In particular, a parameter of type
(BY-REF (MUTABLE T))
creates an alias whose presence is observable. Consider:
(defun (f x : (mutable int32))
(defun (g xref: (by-ref (mutable (int32))))
(pair xref (begin (set! x (+ x 1)) xref)))
(g x))
which, when invoked as (f 1), should return (pair 1 2). This example is
okay because the capture of x by xref does not escape.
[Swaroop: can you add this as a test case?]
But the following variation is NOT okay:
(defun (f x : (mutable int32))
(defun (g xref: (by-ref (mutable (int32))))
(pair xref (begin (set! x (+ x 1)) xref)))
g)
because x is on the stack frame and x gets captured.
I no longer understand Swaroop's explanation for how this is handled.
Swaroop: can you explain again what currently happens in my second
example? I suspect that this example is actually okay, because the inner
capture of x forces it to be heapified, and once it is heapified the
subsequent alias created by xfef is okay.
Hmm. I *think* I may see what is going on here and why it is okay
generally, but I would appreciate a clear explanation from Swaroop. Here
is my theory:
1. If the BY-REF emerges as a *parameter* of an escaping closure, it is
still a parameter and no harm has been done.
2. All of the problem cases arise when an inner procedure having a
by-ref parameter is applied in such a way that the by-ref parameter
aliases a stack-allocated variable. All such cases are syntactically
observable, and it is possible to back-propagate the capture of the
by-ref formal parameter onto the actual parameter.
Is this about it?
> > The by-ref model is actually a degenerate form of region
> > typing, since we do not allow escape at all (rather than allowing it as
> > long as the target region is guaranteed to be in a later activation).
>
> If you're already doing some sort of region typing then this should be
> being checked for and everything should be OK. I guess I'm missing
> something then!
We are not doing region typing, except perhaps in the most trivial
sense. We are exploiting the fact that by-ref can only appear in
argument position and never in return position. Because of this, escape
can only occur by copy, and the *copy* does not reference anything
dangerous.
The only tricky bit is the closure construction issue that we are
discussing above.
Actually, there is another tricky bit that I bet Swaroop may not have
noticed yet.
*Because* a by-ref parameter can only escape by copy, there is an
ill-advised but legal one-way copy compatibility:
(by-ref T) <- (mutable T) ; where T is immutable
This is "safe" because (1) the resulting by-ref is strictly less mutable
than the original parameter, and (2) it can only escape by copy, and
T ~= (mutable T) ; is copy compatible.
In spite of this, I do NOT think that we should allow this unification.
In BitC, an immutable type is supposed to be immutable through any
alias, and the compiler is entitled to assume such. If we allow this
unification, then in the following procedure:
(defun (f x : (mutable int32))
(defun (g xref: (by-ref (mutable (int32))))
(pair xref (begin (set! x (+ x 1)) xref)))
(g x))
the compiler cannot assume that the value of xref is unchanged between
the first and second use occurrences, because the relaxed unification
has violated the deep immutability constraint.
For this reason, we should NOT allow this unification.
In other words, I am arguing that preservation of deep immutability is a
safety property of the language.
> As an aside, shap spelt the inner expression (pair y,x) and I'm not sure
> why; I thought it would be either (y,x) or (pair y x).
Early on we used comma as an infix pair operator. Later that was
dropped, but shap's fingers haven't internalized the change.
shap
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
