Why is garbage collection required for tail call optimization?
Why is garbage collection required for tail call optimization? This is because if you were allocating memory in a function that you want to tail call, wouldn't there be a way to tail call and reclaim that memory? (Thus, the stack would have to be saved so that after the call to the tail, the memory could be reclaimed.)
source to share
Like most myths, there may be some truth to this. While GC is not required to optimize tail calls, it certainly helps in a few cases. Let's say you have something like this in C ++:
int foo(int arg) {
// Base case.
vector<double> bar(10);
// Populate bar, do other stuff.
return foo(someNumber);
}
In this case, return foo (someNumber); looks like a tail call, but since you are using RAII memory management and you need to free the bar, this line will be downgraded as follows (in unofficial pseudocode):
ret = foo(someNumber);
free(bar);
return ret;
If you have a GC, the compiler should not insert instructions into the free panel. Therefore, this function can be optimized to call the tail.
source to share
No garbage collection is required for tail call optimization.
Any variables allocated on the call stack will be reused in the recursive call, so there will be no memory leak.
Any local variables allocated on the heap and not freed prior to the tail call will leak memory regardless of whether tail call optimization is used. Local variables allocated on the heap and freed prior to the tail call will not leak memory regardless of whether tail call optimization is used.
source to share
It's true, garbage collection is really not required to optimize the tail call.
However, let's say you have 1GB of RAM and you want to filter a list of 900MB integers to keep only positive ones. Suppose about half is positive, half is negative.
In a language with GC, you just write a function. The GC will meet multiple times and you will get a 450MB list. The code will look like this:
list *result = filter(make900MBlist(), funcptr);
make900MBlist will step by step GCd since detail filter passed, nothing else is referenced
In a non-GC language, to save tail recursion, you need to do something like this:
list *srclist = make900MBlist();
list *result = filter(srclist, funcptr);
freelist(srclist);
You will end up using 900MB + 450MB before finally freeing srclist, so the program will run out of memory and crash.
If you write your own filter_reclaim, this frees up the input list as it is no longer needed:
list *result = filter_reclaim(make900MBlist(), funcptr);
It will no longer be tail-recursive and you will probably overflow your stack.
source to share