On 24 March 2011 09:55, Jonathan S. Shapiro <[email protected]> wrote: > It occurs to me that the problem with my length example isn't really about > mutability or purity at all. It's about the fact that the type system is > insufficiently precise about lifetime analysis. Let's see if I can explain > what I mean by that: > > We had our structure, and a length computation that depended on the "next" > field, which was init-only, and then an operation that overwrote the > structure as a whole, following which the length computation was stale. The > problem isn't the overwrite per se, nor it is the staleness per se. It's > that we aren't able to say anything about the relationship between the two. > > Which leads me to notice that purity is just an extreme case of effect > analysis. We have a computation (length) that sources (reads) certain > regions. We have an action (the mutation) that sinks (writes) one of the > regions sourced by the length computation. We have a flow of control on > which that update can cause the value computed by length() to become stale.
Without going deep into the specifics, this manner of inferring the purity of a reference is sensible, but there are some important things to keep in mind. The first is that, in the presence of separate compilation, for a reference to be stable across a call to an external function, the object in question must not be reachable by external code following a mutable path. That seems to be the common case, but it does take significant work to infer. The second is that anything that enforces updates from other threads needs to be considered if the region may be visible there; I presume you want to enforce sequential consistency for data-race free programs so you do need to think about how this interacts with either your memory model or your implementation of it. The general idea is that local lifetime analysis often gives you enough information to infer interesting things about the immutability of a region over a given domain (dynamic extent). Pypy-effects has machinery to deal with the cases where you don't have enough information, but these are probably not applicable without promotion, and we have also partially sidestepped the concurrency issue for now. -- William Leslie _______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
