No, I think Nimrod's approach is absolutely correct.
What I hope will happen is that once Nimrod's effects system matures, the compiler will be able to figure out when it can statically free references when they go out of scope, rather than always using the GC.
Rusts approach, I think, is in the entirely wrong direction. You should only have one kind of reference, but if you use it correctly the compiler should figure out how to free it. You should then be able to make an assertion that a procedure (possibly "main") does not allocate any GC memory, and have the compiler tell you what part of your code violates this constraint.
What you describe is called escape analysis, and it's Go's approach (for example). But it falls down in many situations, especially when separate compilation is desired or when you have existential types (e.g. closures). To truly have no GC with safety, you need to replicate something like Rust's machinery.
"If you use it correctly the compiler will figure out how to free it" is extremely handwavy. If you try to formalize exactly what "use it correctly" means, you will likely arrive at something very similar to Rust's system.
I think the idea is that with an effect system, function signatures and existential types will have effects that says "argument X does not escape", and "argument X can only escape through call Y" (so that you can infer bottom-up). If you have that information in the interface, you can do separate compilation and existential types.
To me this seems different enough to Rust's system, and while this won't be 100%, I think this will greatly reduce escape analysis failures, and especially this will eradicate escape analysis failures due to missed inlining. Whether it will be enough seems an open question to me (that is, to me, it doesn't seem destined to fail) and worth pursuing.
Once you're at the level of "argument X only escapes via closure Y", isn't that just a lifetime system? You're manually expressing the invariant that the closure Y cannot outlive argument X.
Rusts approach, I think, is in the entirely wrong direction. You should only have one kind of reference, but if you use it correctly the compiler should figure out how to free it.
This has been an area of intense research for four or five decades now, and it's probably not going to get better than what we have now, in the general case. In the presence of general recursive data structures, the compiler can't know when each object is going to die. I'm pretty sure you can easily reduce this to the halting problem.
To date, you've had three sorts of solutions: 1) explicit malloc/free; 2) tracing GC or reference counting + various tricks to take advantage of special cases; and 3) putting additional information in the type system to help the compiler infer when objects might become free while preserving memory safety (this is the direction taken by Rust, Cyclone, MLKit, and to an extent C++ too).
I think if your code does use references in a way that does not let you guarantee memory safety without an extremely convoluted type system, you should perhaps just be using GC.
For most code I personally know, that does not play well with GC (firmware, hard real-time, etc.), you really don't want to do much allocation after initialization anyway, and the little you do can be handled by malloc/free style manual memory management, or perhaps by escape analysis. And then I think Nimrods approach might work well, because you could declare that everything done by a proc should be verified by escape analysis, rather than manually tagging each pointer used in that procedure.
But I recognize that Rusts approach should be extremely useful in a few applications. But then again I wonder if Nimrods type-system eventually will be able to implement its most useful pointer types in a library.
So what you have is various approaches to take advantage of special cases (different forms of GC), or approaches that give the compiler more information (as in C or C++, and Rust or Cyclone or MLKit).
Pretty much. I'd also add ParaSail to the list of languages that give the compiler more information (or more precisely, restricts what is possible, and for reasons other than just memory management).
I agree in that I don't entirely buy Rust's approach, mostly because of the cognitive overhead that it puts on me, but I don't think it's plausible to think future changes to the compiler (Without the introduction of new constraints on the behaviour of pointers) will give us statically-determined deallocation points. If it were possible, it would have been done five years ago and merged into clang!
It's trivially impossible with unrestricted aliasing. No compiler can statically predict the properties of an unrestricted arbitrary graph about which, in the limit, absolutely nothing is known until runtime.
Creating arbitrary graphs in memory is not a "theoretical corner case". It corresponds to, for example, Graphviz reading in a graph from user input. Or, if you want something that could technically be done with manual memory management but might as well be an unrestricted graph for all any reasonable analysis could infer, creating a doubly-linked XML/HTML DOM.
Alias analysis failure leading to escape analysis failure is the default case, not the corner case.
I think it is valuable to research what is the best set of restrictions to get reliable escape analysis. For reliable escape analysis for unrestricted case, yes, I think it won't be possible and it isn't worth bothering with at all.
Comments
No, I think Nimrod's approach is absolutely correct.
What I hope will happen is that once Nimrod's effects system matures, the compiler will be able to figure out when it can statically free references when they go out of scope, rather than always using the GC.
Rusts approach, I think, is in the entirely wrong direction. You should only have one kind of reference, but if you use it correctly the compiler should figure out how to free it. You should then be able to make an assertion that a procedure (possibly "main") does not allocate any GC memory, and have the compiler tell you what part of your code violates this constraint.
What you describe is called escape analysis, and it's Go's approach (for example). But it falls down in many situations, especially when separate compilation is desired or when you have existential types (e.g. closures). To truly have no GC with safety, you need to replicate something like Rust's machinery.
"If you use it correctly the compiler will figure out how to free it" is extremely handwavy. If you try to formalize exactly what "use it correctly" means, you will likely arrive at something very similar to Rust's system.
I think the idea is that with an effect system, function signatures and existential types will have effects that says "argument X does not escape", and "argument X can only escape through call Y" (so that you can infer bottom-up). If you have that information in the interface, you can do separate compilation and existential types.
To me this seems different enough to Rust's system, and while this won't be 100%, I think this will greatly reduce escape analysis failures, and especially this will eradicate escape analysis failures due to missed inlining. Whether it will be enough seems an open question to me (that is, to me, it doesn't seem destined to fail) and worth pursuing.
Once you're at the level of "argument X only escapes via closure Y", isn't that just a lifetime system? You're manually expressing the invariant that the closure Y cannot outlive argument X.
Would the cognitive overhead of that be any less than lifetimes in Rust?
This has been an area of intense research for four or five decades now, and it's probably not going to get better than what we have now, in the general case. In the presence of general recursive data structures, the compiler can't know when each object is going to die. I'm pretty sure you can easily reduce this to the halting problem.
To date, you've had three sorts of solutions: 1) explicit malloc/free; 2) tracing GC or reference counting + various tricks to take advantage of special cases; and 3) putting additional information in the type system to help the compiler infer when objects might become free while preserving memory safety (this is the direction taken by Rust, Cyclone, MLKit, and to an extent C++ too).
I think if your code does use references in a way that does not let you guarantee memory safety without an extremely convoluted type system, you should perhaps just be using GC.
For most code I personally know, that does not play well with GC (firmware, hard real-time, etc.), you really don't want to do much allocation after initialization anyway, and the little you do can be handled by malloc/free style manual memory management, or perhaps by escape analysis. And then I think Nimrods approach might work well, because you could declare that everything done by a proc should be verified by escape analysis, rather than manually tagging each pointer used in that procedure.
But I recognize that Rusts approach should be extremely useful in a few applications. But then again I wonder if Nimrods type-system eventually will be able to implement its most useful pointer types in a library.
Pretty much. I'd also add ParaSail to the list of languages that give the compiler more information (or more precisely, restricts what is possible, and for reasons other than just memory management).
I agree in that I don't entirely buy Rust's approach, mostly because of the cognitive overhead that it puts on me, but I don't think it's plausible to think future changes to the compiler (Without the introduction of new constraints on the behaviour of pointers) will give us statically-determined deallocation points. If it were possible, it would have been done five years ago and merged into clang!
It's trivially impossible with unrestricted aliasing. No compiler can statically predict the properties of an unrestricted arbitrary graph about which, in the limit, absolutely nothing is known until runtime.
So, because something doesn't work in some theoretical corner cases, it isn't worth bothering with at all?
Creating arbitrary graphs in memory is not a "theoretical corner case". It corresponds to, for example, Graphviz reading in a graph from user input. Or, if you want something that could technically be done with manual memory management but might as well be an unrestricted graph for all any reasonable analysis could infer, creating a doubly-linked XML/HTML DOM.
Alias analysis failure leading to escape analysis failure is the default case, not the corner case.
I think it is valuable to research what is the best set of restrictions to get reliable escape analysis. For reliable escape analysis for unrestricted case, yes, I think it won't be possible and it isn't worth bothering with at all.