+1 for the remark that compilers should be able to do it better than humans.

This (not the others) is the correct answer, but I doubt OP will understand it. If they did, they’d never have needed to ask the question.

That compilers should do as well as humans or better is exactly why I asked this question. @KonradRudolph could you provide me a bit more context to understand this answer? What heuristics exists to solve this problem? What are their limitations? What limitations can we introduce in a language to help solve this? Yes, I know about Rust but I'm not interested in languages that make the programmer do more work.

@MiltonSilva It’s not about heuristics at all. The problem is that the information when a variable is no longer needed is not usually contained within the source code. You need external knowledge to decide that, and the compiler has only the source code to decide, it doesn’t possess this external knowledge. But there are (imperfect) ways of encoding the external knowledge in the source code — and in these cases the compiler does auto-generate the necessary free statements (e.g. C++’ std::unique_ptr).

@KonradRudolph So, programmers have information that is not explicit in the source code? Could you provide an example? I don't understand the one provided in the answer, possibly because it is not specific enough.

@MiltonSilva A linked list is implemented as a list of pointers, where every node points to its successor. Now, how should the compiler know whether/when to free the successor node of a given node x? That is, where should the compiler insert free(x->next)? There is literally no way of knowing, because x->next needs to be freed when either the whole list is deallocated, or when the specific node referenced by x->next is deleted from the list due to some user action.

Programmers can preferentially write programs in which they do know when to free memory, because there are some higher level rules about how the memory chunks are used. There is no need for a programmer to solve the general free problem.

To some extent, I think this answer's example is an artificial one using a buggy program. At least I would consider a REPL that admits UB by the implementation as a result of some input to be a buggy one.

@R.. Yeah, examples for stuff like this are usually pretty contrived to make the point as apparent as possible. More generally, you'll get this problem whenever an external or even internal-but-indirect event would inform you that memory (or other system resource) will no longer be accessed. This problem can exist even in garbage-collected languages, e.g. .NET has an I_Disposable interface to address the problem, which is sorta like a deallocation mechanism for .NET.

@PatriciaShanahan I agree that programmers will tend to avoid writing programs where efficient deallocation placement is tricky to determine. I see at least two ways in which this observation might connect to the topic, so I'm not sure which you were interested in expressing; you could elaborate?

@ChemicalEngineer I was only interested in expressing the idea that programmer controlled release does not require programmer ability to solve the release problem for arbitrary programmers.

@ChemicalEngineer: What I'm saying is that, if there is any possible external input that could cause the memory to be accessed again, then a program which considers the memory unreferenced and frees it is buggy, because it invokes undefined behavior for at least one possible input.

@R.. I love your point as it's very interesting to think about. C compilers are programs that allow external input to cause released memory to be accessed again, so by that logic, C compilers are buggy programs. Would you agree?

@ChemicalEngineer: No. The compiler can produce a binary that invokes undefined behavior, but if the compiler itself, as part of compiling the program, invokes undefined behavior, that's a bug in the compiler. If you want to think about it as an interpreter instead then your question makes more sense.

@R.. So then interpreters and compilers/IDE's that allow users to build-and-run would qualify as buggy programs? Forgive me, I don't mean to make too much of this, it's just that your point really sounds sensible, though it seems too easy to think of counter-examples. I'm interested in how this line of thought resolves.

@ChemicalEngineer: Your IDE example is not invoking UB because the program that is the IDE is just producing an output file and starting it as a separate process (in some manner outside the scope of the C language but in the scope of POSIX, Win32, or similar). Everything in the IDE program itself is well-defined.

@ChemicalEngineer: In the interpreter case, you can make a C interpreter without UB, but you have to refrain from having the interpreter call free on possibly-reachable objects in the interpreted context and instead perform its own memory management and secure address translation of some sort (i.e. where even a maliciously-altered pointer in the interpreted context can't cause the interpreter to access outside of the interpreted context).

@R.. Awesome, I think that I see where you're coming from - that it's desirable to create only C programs that can't perform undefined operation no matter what the external environment does. Then, if we assume that all compiled C programs are within this subset of possible C programs, it's in principle possible for a compiler to determine when allocated memory will no longer be accessed through examination of the source code alone. Right?

@R.. I think that you're right, in principle. So long as programmers rigorously ensure that no type of external action could cause them to perform undesired operation, then the source code must somehow police itself such that it won't access deallocated memory. An analysis of the source code could then determine when this policing will no longer allow access to allocated memory; then, once that point is reached, it could be deallocated. It'd be an incredibly complex analysis in some cases as some back-calculations are extremely expensive (e.g. as asymmetric encryption methods leverage);[..]

@R.. but, it seems like it might be technically possible. Then, having that property of being unable to access deallocated memory might be a sufficient criteria for determining that source code is... "complete", I guess? I think that it'd be too computationally inefficient to realistically implement in the near-term, though it's a neat theoretical problem.

@ChemicalEngineer: Consider a program that 60 times per second allocates 1,000 regions of 1,000,000 bytes each, writes some data to parts of each region, shows all the pointers as hex values (fitting 1,000 on the screen should be feasible), and then overwrites those pointers with the next set. After doing that awhile, the program asks the user to input a pointer and shows what's at that address.

@ChemicalEngineer: If the user uses a camera or screen grabber to capture one or more of the pointer values and enters the captured value, behavior would be defined as showing whatever was stored in that object. There is no way the machine could know what pointers might have been captured, however, and if the program ran for a minute before accepting a pointer from the user, the computer would need more than 3,600,000,000,000 bytes of storage to handle all possible inputs correctly, well beyond the range of most implementations.