User loginNavigation |
Safe interior references in the presence of mutationSuppose like Rust & C/C++, we want to support references that point to the inside of another value. A reference<t> is something that can be dereferenced (deref : reference<t> -> t). A reference may also be mutable, so that we can set its value. It may also support other operations, such as walking a data structure. Examples:
Note that "reference" in the sense I'm using is not necessarily just a pointer. A tree iterator may maintain a stack of parent nodes in order to be able to traverse a singly linked tree. There's one nasty problem with references, which is that in the presence of mutation they can lead to memory unsafety or run time errors. Examples:
As you can see, it's not just a problem with pointers. Even in a language like Java, you have problems with iterators when the underlying data structure is mutated. At run time they may throw ConcurrentModificationException. Rusts type system attempts to prevent these kind of errors statically, but Rusts type system isn't fully finalized yet and it is quite complicated. I was wondering if there is existing literature on this problem and perhaps there is some elegant way to prevent this with types. It would probably involve linear types and capabilities. If such a thing does not exist yet, one thing I can think of is to require a linear capability in order to mutate the value, and in order to obtain a reference to the inside of the value you must give up this capability. In return you get a capability that allows you to read the references. If you later want to mutate again, you have to give up the capability to read the references. Is this a good approach? Why/why not? By Jules Jacobs at 2014-05-19 21:09 | LtU Forum | previous forum topic | next forum topic | other blogs | 3177 reads
|
Browse archives
Active forum topics |
Recent comments
22 weeks 6 days ago
22 weeks 6 days ago
22 weeks 6 days ago
45 weeks 21 hours ago
49 weeks 2 days ago
51 weeks 13 min ago
51 weeks 17 min ago
1 year 1 week ago
1 year 6 weeks ago
1 year 6 weeks ago