I'm afraid the memory management scheme might cause the Nimrod ecosystem to end up with too many libraries that require GC, and since the building blocks are already using it, why not use it yourself?
Either make it fully manual, or do something like Rust (No small feat). A GC you can switch on and off sounds like a good idea, but programmers don't keep half the promises they make ("It's just an MVP, I'll refactor it to use manual memory later").
I'm afraid the memory management scheme might cause the Nimrod ecosystem to end up with too many libraries that require GC, and since the building blocks are already using it, why not use it yourself?
And what would be the problem with that? The number of application domains where even soft real-time GC is inappropriate is very, very small. And designing freedom from garbage collection into a language (other than the simple option of allowing manual allocation/deallocation) is not cost-free, either, and can weigh down the design, too. You can optimize your language design for having garbage collection or for not having garbage collection, but if you try to do both at once, a language design that specifically favors one or the other will likely beat out the compromise solution for the case it's optimized for.
And yes, that means that Nimrod (or any other language) won't be perfect for everything under the sun. Which is fine: there's nothing wrong with having multiple programming languages, each of which is better suited for a different task.
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.
Still, there are times when GC is fine for a particular application. In those cases, Nimrod is pretty fantastic, especially given its metaprogramming capabilities.
Likely, yes. (Welcome to real-time programming; if you don't keep track of your time-budget, you're gonna have a bad day.)
I haven't looked at Nimrod's GC, but I believe it's indeed incremental; it won't take more time than you give it, but it will leave things uncollected if you don't give it [enough] time.
Nimrod's pointers to garbage collected memory are separate from the pointers you can allocate yourself. So you could do manual memory management on the parts that really need it - say for a game in a tight loop - and leave the collector to worry about the smaller and less time-critical stuff.
Also the GC is only triggered on a memory allocation. It doesn't run in a background thread or anything like that. So if the GC fails, then the allocation of memory fails (as I understand it) which means your scenario would be caught early.
Comments
I'm afraid the memory management scheme might cause the Nimrod ecosystem to end up with too many libraries that require GC, and since the building blocks are already using it, why not use it yourself?
Either make it fully manual, or do something like Rust (No small feat). A GC you can switch on and off sounds like a good idea, but programmers don't keep half the promises they make ("It's just an MVP, I'll refactor it to use manual memory later").
And what would be the problem with that? The number of application domains where even soft real-time GC is inappropriate is very, very small. And designing freedom from garbage collection into a language (other than the simple option of allowing manual allocation/deallocation) is not cost-free, either, and can weigh down the design, too. You can optimize your language design for having garbage collection or for not having garbage collection, but if you try to do both at once, a language design that specifically favors one or the other will likely beat out the compromise solution for the case it's optimized for.
And yes, that means that Nimrod (or any other language) won't be perfect for everything under the sun. Which is fine: there's nothing wrong with having multiple programming languages, each of which is better suited for a different task.
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.
Still, there are times when GC is fine for a particular application. In those cases, Nimrod is pretty fantastic, especially given its metaprogramming capabilities.
Also, the GC can be controlled, so you can set exactly when it is allowed to run, something like this for a game:
http://nimrod-lang.org/gc.htmlThen what happens if the GC keeps taking longer than the allowed time? Will it then not keep allocating more and more memory that will never be freed?
Likely, yes. (Welcome to real-time programming; if you don't keep track of your time-budget, you're gonna have a bad day.)
I haven't looked at Nimrod's GC, but I believe it's indeed incremental; it won't take more time than you give it, but it will leave things uncollected if you don't give it [enough] time.
in a game, detect gc pressure and schedule some slo mo candy to use as gc cover.
I guess so. This is only viable if you have enough time for garbage collection.
Nimrod's pointers to garbage collected memory are separate from the pointers you can allocate yourself. So you could do manual memory management on the parts that really need it - say for a game in a tight loop - and leave the collector to worry about the smaller and less time-critical stuff.
Also the GC is only triggered on a memory allocation. It doesn't run in a background thread or anything like that. So if the GC fails, then the allocation of memory fails (as I understand it) which means your scenario would be caught early.
Does this mean that they use different heaps?
No, they are on the same heap since the GC isn't a moving collector.
They probably use the same heap underneath.