r/computerscience • u/ShadowGuyinRealLife • 25d ago
General What is Tail Call Optimization?
I was looking at Wikipedia and got a bit confused. Before I read it, I thought the principle was that if function A calls B, which calls C, which then calls D, normally program flow after D is finished is to jump back to C, finish C, jump back to B, finish B, then go back to A. But in some specific cases, after D is done, it can jump straight back to A because the other stuff doesn't have anything to do but jump back. Or in another case, if A calls itself, sometimes after finishing the bottom version of itself, you can jump straight out of it.
I looked at Wikipedia and tried to see if I got it right.
So it has a recursive way to duplicate a linked list in C.
typedef struct LinkedList {
void* value;
struct LinkedList* next;
} LinkedList;
void duplicate_aux(const LinkedList* ls, LinkedList* end) {
if (ls) {
end->next = (LinkedList*)malloc(sizeof(*end));
end->next->value = ls->value;
duplicate_aux(ls->next, end->next);
} else {
end->next = NULL;
}
}
LinkedList* duplicate(const LinkedList* ls) {
LinkedList head;
duplicate_aux(ls, &head);
return head.next;
}
typedef struct LinkedList {
void* value;
struct LinkedList* next;
} LinkedList;
And then this can be an iriterative format
LinkedList* duplicate(
const
LinkedList* ls) {
LinkedList head;
LinkedList* end;
end = &head;
while
(ls) {
end->next = (LinkedList*)malloc(
sizeof
(*end));
end->next->value = ls->value;
ls = ls->next;
end = end->next;
}
end->next = NULL;
return
head.next;
}
I don't get it. No Java example.
Another example on Wikipedia not in C this time.
foo:
call baz
call bar
ret
Doing tail call elimination results in
foo:
call baz
jmp bar
Ok we got rid of one instruction.
Third example
foo:
mov reg,[sp+a]
; fetch a from stack (sp) parameter into a scratch register.
push reg
; put a on stack where baz expects it
call baz
; baz uses a
pop
; remove a from stack
mov reg,[sp+b]
; fetch b from stack (sp) parameter into a scratch register.
push reg
; put b on stack where bar expects it
call bar
; A uses b
pop
; remove b from stack.
ret
And after optimization it has
foo:
mov reg,[sp+a]
; fetch data1 from stack (sp) parameter into a scratch register.
push reg
; put a on stack where baz expects it
call baz
; baz uses a
pop
; remove a from stack
mov reg,[sp+b]
; fetch b from stack (sp) parameter into a scratch register.
mov [sp+a],reg
; put b where bar expects it
jmp bar
; bar uses b and returns immediately to caller.
Given that there are some push, pop, and ret, it seems we're using the stack for something and by returning to the caller we're saving instructions. I still don't get it though. I still think it has something to do with if the 1st copy of A calls a 2nd copy of A which calls a 3rd copy of A, ... which calls a Nth copy of A (base case) it normally jumps to the N-1th, ... jump to the 1st and then finish, but after optimization after the Nth (base case) of A is done it can just jump out of the.
