3 ms·
How do Ada and Modula-3 let you implement doubly-linked lists without unsafe code? I'd guess they don't enforce the constraint Rust does that mutable references
by geofft 10y ago
How do Ada and Modula-3 let you implement doubly-linked lists without unsafe code? I'd guess they don't enforce the constraint Rust does that mutable references must be unique, but my experience with both C and C++ is that you want this rule anyway for your code to have any chance of being correct.
In particular, removing a node from a doubly-linked list has three steps: repoint prev->next at next, repoint next->prev at prev, deallocate. If you can write this in safe code, it's equally possible to write a procedure that fixes prev->next and deallocates, but leaves next->prev dangling. What do Ada and Modula-3 do to prevent this?
(If you're willing to sacrifice efficiency, you can always use reference-counting or actual GC. Or you can just stuff each node in a dynamically-allocated vector, and have the prev and next pointers be indexes into that vector, instead; you'll have semantically-dangling numbers, but you won't have memory unsafety. Both of these approaches can be done in safe Rust with the normal standard library.)
- moosingin3space 10y agoIf I'm not mistaken, Modula-3 is garbage-collected, so doubly-linked lists are implemented with GCed pointers like in Go.
- nickpsecurity 10y agoI can't remember if it bounds-checks the pointers or just arrays. However, SPARK lets you prove conformance of code to specs and absence of specific error conditions. Here's a linked list example: http://www.spark-2014.org/entries/detail/spark-2014-rationale-formal-containers http://www.spark-2014.org/entries/detail/spark-2014-rational... There's also formal verification work on linked lists. If any have simple VC's, they could be encoded in containers like above as well. Tools exist to do similar stuff for C, too.