Where do base cases fit into tail call optimization?

Questions / Help
,
1

I’m doing some review. I understand last call optimization, with the last call in the function being a pure recursive function call. Overwrites are done to the arguments in the call stack. But what happens with the base cases? How are the sum([]) → 0; function clauses treated?

Is there some sort of rough conversion to a recursive function in non-functional languages? Base cases at the top in if statements and recursive call below?

2

“Tail recursion optimisation” is somewhat misleading.
It’s “last call optimisation”.
Basically, the idea is that ALL calls are
put the arguments where the callee expects them
GOTO the beginning of the calle
except that some calls are preceded by
save the current continuation
So in the case of
f(N) when N > 0 → f(N-1);
f(0) → g(99).
the call to

3

continued (curse this laptop and its hallucinatory
keypresses):
the call to g/1 is just as much a last call as the
call to f/1. The equivalent in a conventional
language would be
f__1:
if (GTR(arg1, ZERO)) {
arg1 = SUB(arg1, ONE);
goto f__1;
} else
if (arg1 ==a ZERO) {
arg1 = ASINT(99);
goto g__1;
} else {
ERROR(…);
}

A body call looks something like
t = allocate(frame overhead + save area needed);
t->FP = FP;
t->PC = &&ret;
t->save0 = …;
FP = t;
… pass arguments …
goto callee;
ret:
t = FP;
FP = t->FP;
… = t->save0;
…
make the frame t available for reuse

and a return looks like
RESULT = …;
goto FP->PC;

One interesting point is that the cost of a body call
depends on how many live variables there are. Other

things being equal, small simple functions will have
cheaper calls than big ones with lots of live variables.

1 Like