3 ms·
The question you ask is a bit vague, so pardon me for only answering one form of it. When it comes to memory management of particular data structures, a langua
by cwzwarich 11y ago
The question you ask is a bit vague, so pardon me for only answering one form of it.
When it comes to memory management of particular data structures, a language like Rust can only safely distinguish between the presence of aliasing and the total lack of aliasing; it can't reason about memory locations that have bounded amounts of aliasing like doubly linked lists or trees with parent pointers. If the pattern of aliasing can be described by a regular language, then there exist decidable formalisms that can reason about it, but none of these formalisms have made it into practical programming languages.
If you go further and allow arbitrary directed graphs as data structures, then there is no decidable system for safe manual memory management (and depending on the definitions you use, this is provable). It's also often difficult to write (unproven) safe code in languages like these, so in practice people tend to just use region allocation (allocate your graph, temporarily leak it, and then free it all at once) or they implement a poor garbage collector.
Garbage collection also simplifies concurrent programming greatly, because it allows separate threads of execution to have no knowledge of the memory management strategy used by each other. If you try hard enough you can write a solution by hand that avoids the use of a general GC for any particular use case, but it eventually starts to feel like implementing a special-purpose GC.
- Rusky 11y ago> If the pattern of aliasing can be described by a regular language, then there exist decidable formalisms that can reason about it That sounds really interesting, is there a good place to read more on the subject?
- pcwalton 11y agoA little digging (as this is interesting to me as well) brought up the Pointer Assertion Logic Engine: http://www.brics.dk/RS/00/39/BRICS-RS-00-39.pdf http://www.brics.dk/RS/00/39/BRICS-RS-00-39.pdf