On 2011-02-12 1:52 AM, Jonathan S. Shapiro wrote:
> let r = dup(#Nil)
> in
> deref(r) := cons(x, nil)
>
> the cons cell occupies storage, the assignment is performed by byte
> copy, and the bytes have to go somewhere. So the target of ref(#Nil) has
> to occupy storage unless we can show that it is not a target of
> assignment.
Ok, now we're on the same page. I agree that the optimization also
depends on the mutability of the reference. As you say, if it's mutable
then it must behave as a C union with all the storage available. Iwas
taking ref(#List) to mean an immutable struct List * from C. I suppose
the latter instead would be: const ref(#List), since mutability seems to
be the default.
> Yes. But the fact that you need to do that is a qualitative change in
> the behavior of dup(). In fact, it requires that dup() be automatically
> instantiated with a distinct implementation for each type!
Yes, I thought this clear when I said dup would be provided by a type
class. You can make a compiler-provided implementation with certain
tagging tricks as well to eliminate most type class instances, ie.
partition the tag values around C, where all nullary constructors are
below C. Then only a single implementation is required. Only types with
manually specified tag values would then require a type class, I think.
Whether a new heap value is produced also depends on the mutability of
the value being duplicated, as explained above. The dup'd Nil would
occupy new storage if we're duping mutable storage.
> I take it AddressOf products a ref(List('a))? So I would say yes to the
> question, where Nil is ref(#Nil).
>
> So you are saying that the value returned by AddressOf a structure
> element may not always name a byte that falls within the span of the
> containing structure.
No, I don't think so. Perhaps I should unpack my reasoning a bit more.
There are various transformations applied and corner cases to handle. So
assuming the optimization I described at the top, call it I, there are
two cases to handle for a ref(#List):
1. ref to a mutable or unboxed structure, ie. a C-union
2. ref to a heap value where I applies
So an EQ on ref(#List) would look something like this in pseudo C:
// 1-bit tag for nullary constructors to distinguish from pointers
#define is_int_tag(x) (x & 1)
bool eq(List* lhs, List* rhs) {
var ltag = is_int_tag(lhs) ? lhs >> 1 : lhs->tag;
var rtag = is_int_tag(rhs) ? rhs >> 1 : rhs->tag;
return ltag == rtag
&& (ltag == TAG_NIL || ltag == TAG_CONS
&& eq(lhs->value, rhs->value));
}
This representation might not be possible in BitC since you may have
unaligned pointers. These are also a few more comparisons than is ideal,
which is why the ZAM used the same representation for nullary and
non-nullary constructors, but only allocated one of the nullary
instances. So dup would have to return the static instance for each
nullary constructor where possible, ie. not for mutable refs, and eq
would instead look like this:
bool eq(List* lhs, List* rhs) {
var ltag = lhs->tag;
var rtag = rhs->tag;
return ltag == rtag
&& (ltag == TAG_NIL || ltag == TAG_CONS
&& eq(lhs->value, rhs->value));
}
You can no longer check for NIL by simple pointer comparison, it must
always dereference the pointer. Overall, it's probably better to reduce
the number of comparisons than reduce the indirections since branch
mispredicts are much more costly than cache misses.
> That type has locations only if the tag is #Cons.
>
> No! That is precisely the mistake here. The decision about whether a
> reference denotes a location is (necessarily) a consequence of its type,
> not a consequence of its value. The optimization that allows unary
> elements of natively-boxed types to have no storage is exactly that: an
> optimization. If it is possible to apply deref() to such values, then
> the assumptions that admit that optimization no longer hold, and the
> optimization ceases to be legal.
It depends on the semantics of ref. I was assuming all this time that we
are dealing with immutable values where the optimization is valid. I
suspect you are grappling with the pervasive mutability, which is
backing you into the C corner with C union semantics.
Sandro
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
