Well, the c8 && f is definitely a tail call. However, that may not
be where the depth is.
The c1 && f isn't a tail call because the function continues
after it returns, and the conditions aren't mutually exlusive.
An example of this kind of function is an N-ary tree traversal.
Say a tree with up to 8-way branching:
function f (node) {
if (node.children > 0)
f(node.child[0])
if (node.children > 1)
f(node.child[0])
...
if (node.children > 7)
f(node.child[7])
}
E.g. in lisp we have binary nodes, conses with car and cdr.
Most lists grow in the cdr direction, so tail calling on the cdr
case keeps the stack shallow.
This is an issue for garbage collectors, which have to traverse whatever
is reachable, however the application has chosen to shape it.
The application can create cruft in the heap using non-recursive
techniques which then choke a recursive garbage collector.
There are stackless techniques for garbage collection via
"pointer reversal". When the garbage collector follows some link
into an object, it picks one of the pointers in *that* object
and stashes the incoming pointer. Before doing that, it removes
that child pointer, and recurses on that child, passing it
its own address as the next pointer.
Basically, the backwards pointers for returning are stored
into the object graph itself, the originals bein restored
when the reverse path is taken.
It goes something like this:
// stacklessly traverse "3-node": node with 3 child pointers
function visit_3_node(node, escape_pointer)
{
switch (node.traversal_state) {
case UNTRAVERSED:
{
traverse_next = node.child[0]
node.child[0] = escape_pointer
node.state = TRAVERSED_0
// tail call!!!
// child[0] is traversed next, and *its* escape_pointer
// is just node, so it will return here.
return top_level_visit_fn(traverse_next, node)
}
case TRAVERSED_0:
{
orig_escape_pointer = node.child[0]
traverse_next = node.child[1]
node.child[0] = escape_pointer // restore child[0]
node.child[1] = orig_escape_pointer // move to child[1]
node.state = TRAVERSED_1
// child[1] traversed next, again with pointer back to here
return top_level_visit_fn(traverse_next, node)
}
case TRAVERSED_1:
{
// One child left to traverse: different handling.
orig_escape_pointer = node.child[1] // recover orig ptr
node.child[1] = escape_pointer // restore child[1]
// We don't stash the orig_escape_pointer any more.
// Just go to child[2] and pass the original escape
// pointer as the next object to go to (i.e. our caller's).
node.state = TRAVERSED_2; // traversed 0, 1, 2: all done.
return top_level_visit_fn(node.child[2], orig_escape_pointer)
}
}
Basically it is just like continuation passing style (CPS), where the
continuation we are passing down isn't a function, but just pointer to
the object in the graph where to continue. Because the continuation
isn't a function, we simulate one with a state machine; the state
we switch on gives us a kidn of instruction pointer to move through
the traversal cases of the function.
> Frankly, I cannot say whether it could be transformed - I mean without
> explicitly organizing the call stack. I've done that with special cases
> of a (simple, 2-branch) cascading function (fib; see comp.lang,awk the
> post "Yet another obfuscated Awk code", Jan. 2022), but here I am lost.
Language expressiveness is an issue. E.g. how nicely/easily can we code
a pointer-reversal state machine (if such as thing is necessary) in
shell?
:)