5 ms·

From the article: "A GC is necessary to provide memory safety guarantees. [...] For any programs that need heap-style memory allocations, if you want to guarant

From the article: "A GC is necessary to provide memory safety guarantees. [...] For any programs that need heap-style memory allocations, if you want to guarantee memory safety, you need a GC." The main clame to fame of Rust is providing memory safety without a GC. Is the quote wrong, or is the quote still right because using a few unsafe blocks is unavoidable in practice? I haven't used Rust yet and know almost nothing about the language, so I'd be glad if someone could enlighten me.

tel 12y ago
"To ensure memory safety [given that you can't guarantee in the language layer that the bytecode we'll be operating is safe] you need a GC" Rust invalidates the bracketed assumption. It's been known this is possible for a long time, but Rust is the first time a language with this capability has hit semi-mainstream audiences. C# sure doesn't do it, VB certainly doesn't do it! Ultimately it comes down to a promise of conceptual cleansliness from the entirety of a language Frontend. It's a big commitment.
- chinpokomon 12y ago
  Isn't this saying that because the MSIL is generated from C#, VB.Net, F#, etc, that there can be no guarantee? As far as I know, Rust isn't compiling to a CLR, so the GC in .Net is happening at a lower level than the language, it's happening in the runtime.
  - tel 12y ago
    GC is almost certainly best handled in the RTS if you're going to expect to have one. In theory, Rust could pick MSIL as a new target and then they'd pay overhead for a GC which is not useful at all. Alternatively, due to the existence of the GC as a given in the CLR, it might be that manual memory isn't exposed (as well or as nicely) in the MSIL making the idea of targeting Rust to it kind of silly. I have no personal clue.
    - ygra 12y ago
      Since you can compile C and C++ to the CLR you can completely circumvent the GC if you want/need to. Interoperability with other CLR languages might be a bit hard, then (which raises the question on why target the CLR at all).
dbaupp 12y ago
I think Rust demonstrates the quote is wrong, but the article was written in 2007, before Rust was public and well before the core system of borrow- and "lifetime"-checking was implemented for it, so it wasn't "obviously" wrong at that time. Also, Rust does provide reference counting pointers and these are sometimes necessary; this can be considered a form of GC, although I have a feeling its not in the spirit of the quote. (I believe there were some research languages around that tackled this sort of task, but I'm not sure how many tried to tackle the general heap.)
- tel 12y ago
  I'd be surprised if theories of static memory safety weren't well-developed by 2007. They merely weren't in any practical scope for the CLR.
nercury 12y ago
That's why Rust is so important. It demonstrates that it is possible to drop to the lower-level concepts which do __not__ need GC for memory safety, and then build the "easy" abstraction on top of them. I suspect that we will see more languages like Rust in future, because Rust has essentially proved the feasibility of the ownership model with working implementation.
raphaelj 12y ago
You will always need a kind of GC if you start allocating things on the heap. This is because, in some cases, it's impossible for a human or an algorithm to know statically where a memory can be deallocated (you could solve the halting problem if you had a such algorithm, yet the halting problem has been proven unsolvable). The GC can be very primitive such as in Rust ou C++11 by using reference counting. Reference counting is not a static allocation. What Rust introduces is memory safety for statically allocated data. That's, the type system will prevent you use a reference/pointer to data a which has been deallocated.
- falcolas 12y ago
  Thank you for bringing this up. Rust does indeed use GCs when it is unable to perform static lifetime analysis, or perhaps more importantly, when the restrictions imposed by the lifetime analysis prove too restrictive for the programmer to solve a given problem.
- Jweb_Guru 12y ago
  If you use Rust for any length of time, I think you will find that you almost never need reference counting. You are right that Rust's borrow checker cannot always determine when memory needs to be freed, but the point at which that occurs is much more distant than "when you need to allocate on the heap."
rayiner 12y ago
A GC is necessary to ensure memory safety in the face of arbitrary heap graphs. Rust isn't a counter-example. You can't express arbitrary structures with owning and borrowed pointers. For those cases, Rust has GC (well, reference counting, a sort of GC), as well as "unsafe" and raw pointers. For example, to code a self-managing double linked list in Rust you need either RC or use a raw pointer and a few "unsafe" blocks. This is not a criticism of Rust. I think it's a really interesting point in the design space. But there's no free lunch in memory management!
- Jweb_Guru 12y ago
  That's only somewhat true. You can express arbitrary graphs pretty easily with an arena, which has some similarities to GC in terms of how you use it but flat out isn't garbage collection (unlike reference counting) or unsafe (at least, not after an incoming Rust patch lands). There has also been discussion for some time in the Haskell community around the feasibility of a non-garbage collected implementation of Haskell (the consensus seems to be that it is doable, though perhaps not wholly practical). More generally, Rust is not the final word in type systems around data structures, and for more complex ones there are more complex type systems.
  - rayiner 12y ago
    Owning pointers, regions, arenas, etc, are various ways to take advantage of special cases in the correlation of object lifetimes. But here's no general solution that isn't GC. For example with arenas, you won't be able to reclaim any memory if your memory graph has nodes with uncorrelated lifetimes. Consider, for example, a double-linked list that grows to a certain size, then every second a random node is deleted and a new one is inserted at the beginning. You can't represent the double-linked list with owning pointers, and while you can represent the list in an arena, you can't reclaim any memory until the whole list is deleted.
    - Jweb_Guru 12y ago
      There was a reason I included the second paragraph. There are type systems that can handle intrusive data structures. However, they aren't used in any mainstream language (affine types in Rust is already a major achievement).

tel 12y ago

"To ensure memory safety [given that you can't guarantee in the language layer that the bytecode we'll be operating is safe] you need a GC" Rust invalidates the bracketed assumption. It's been known this is possible for a long time, but Rust is the first time a language with this capability has hit semi-mainstream audiences. C# sure doesn't do it, VB certainly doesn't do it! Ultimately it comes down to a promise of conceptual cleansliness from the entirety of a language Frontend. It's a big commitment.

chinpokomon 12y ago
Isn't this saying that because the MSIL is generated from C#, VB.Net, F#, etc, that there can be no guarantee? As far as I know, Rust isn't compiling to a CLR, so the GC in .Net is happening at a lower level than the language, it's happening in the runtime.
- tel 12y ago
  GC is almost certainly best handled in the RTS if you're going to expect to have one. In theory, Rust could pick MSIL as a new target and then they'd pay overhead for a GC which is not useful at all. Alternatively, due to the existence of the GC as a given in the CLR, it might be that manual memory isn't exposed (as well or as nicely) in the MSIL making the idea of targeting Rust to it kind of silly. I have no personal clue.
  - ygra 12y ago
    Since you can compile C and C++ to the CLR you can completely circumvent the GC if you want/need to. Interoperability with other CLR languages might be a bit hard, then (which raises the question on why target the CLR at all).

dbaupp 12y ago

I think Rust demonstrates the quote is wrong, but the article was written in 2007, before Rust was public and well before the core system of borrow- and "lifetime"-checking was implemented for it, so it wasn't "obviously" wrong at that time. Also, Rust does provide reference counting pointers and these are sometimes necessary; this can be considered a form of GC, although I have a feeling its not in the spirit of the quote. (I believe there were some research languages around that tackled this sort of task, but I'm not sure how many tried to tackle the general heap.)

tel 12y ago
I'd be surprised if theories of static memory safety weren't well-developed by 2007. They merely weren't in any practical scope for the CLR.

nercury 12y ago

That's why Rust is so important. It demonstrates that it is possible to drop to the lower-level concepts which do __not__ need GC for memory safety, and then build the "easy" abstraction on top of them. I suspect that we will see more languages like Rust in future, because Rust has essentially proved the feasibility of the ownership model with working implementation.

raphaelj 12y ago

You will always need a kind of GC if you start allocating things on the heap. This is because, in some cases, it's impossible for a human or an algorithm to know statically where a memory can be deallocated (you could solve the halting problem if you had a such algorithm, yet the halting problem has been proven unsolvable). The GC can be very primitive such as in Rust ou C++11 by using reference counting. Reference counting is not a static allocation. What Rust introduces is memory safety for statically allocated data. That's, the type system will prevent you use a reference/pointer to data a which has been deallocated.

falcolas 12y ago
Thank you for bringing this up. Rust does indeed use GCs when it is unable to perform static lifetime analysis, or perhaps more importantly, when the restrictions imposed by the lifetime analysis prove too restrictive for the programmer to solve a given problem.
Jweb_Guru 12y ago
If you use Rust for any length of time, I think you will find that you almost never need reference counting. You are right that Rust's borrow checker cannot always determine when memory needs to be freed, but the point at which that occurs is much more distant than "when you need to allocate on the heap."

rayiner 12y ago

A GC is necessary to ensure memory safety in the face of arbitrary heap graphs. Rust isn't a counter-example. You can't express arbitrary structures with owning and borrowed pointers. For those cases, Rust has GC (well, reference counting, a sort of GC), as well as "unsafe" and raw pointers. For example, to code a self-managing double linked list in Rust you need either RC or use a raw pointer and a few "unsafe" blocks. This is not a criticism of Rust. I think it's a really interesting point in the design space. But there's no free lunch in memory management!

Jweb_Guru 12y ago
That's only somewhat true. You can express arbitrary graphs pretty easily with an arena, which has some similarities to GC in terms of how you use it but flat out isn't garbage collection (unlike reference counting) or unsafe (at least, not after an incoming Rust patch lands). There has also been discussion for some time in the Haskell community around the feasibility of a non-garbage collected implementation of Haskell (the consensus seems to be that it is doable, though perhaps not wholly practical). More generally, Rust is not the final word in type systems around data structures, and for more complex ones there are more complex type systems.
- rayiner 12y ago
  Owning pointers, regions, arenas, etc, are various ways to take advantage of special cases in the correlation of object lifetimes. But here's no general solution that isn't GC. For example with arenas, you won't be able to reclaim any memory if your memory graph has nodes with uncorrelated lifetimes. Consider, for example, a double-linked list that grows to a certain size, then every second a random node is deleted and a new one is inserted at the beginning. You can't represent the double-linked list with owning pointers, and while you can represent the list in an arena, you can't reclaim any memory until the whole list is deleted.
  - Jweb_Guru 12y ago
    There was a reason I included the second paragraph. There are type systems that can handle intrusive data structures. However, they aren't used in any mainstream language (affine types in Rust is already a major achievement).