# Do I break tco if I use a partially applied function at the tail?

I would like to know if `loop_v2` is still tail recursive here?

``````let rec loop_v1 keep_me number =
if number <= 0 then
print_endline "finished v1"
else begin
print_int number;
print_newline ();
loop_v1 keep_me (number - 1)
end

let rec loop_v2 keep_me number =
let helper = loop_v2 keep_me in
if number <= 0 then
print_endline "finished v2"
else begin
print_int number;
print_newline ();
helper (number - 1)
end

let () =
print_endline "Starting loop_v1..";
loop_v1 "something to keep around" 5;
print_endline "Starting loop_v2..";
loop_v2 "something to keep around" 5;
()
``````

So far, Iâ€™ve learnt that recursive functions should have â€śthe same shapeâ€ť at the tail to behave nicely.

My understanding is a bit abstract though. Introducing a partially applied function should be equivalent but I have a slight doubt.

How can I observe myself that tail call optimization is (or isnâ€™t) in effect? (apart from running the programming and monitoring memory usage)

So far, Iâ€™ve learnt that recursive functions should have â€śthe same shapeâ€ť at the tail to behave nicely.

To understand this, it helps to forget about recursion altogether and focus on tail calls. A tail call is a function call in tail position, meaning that the call is the last operation the caller performs. A sequence of tail calls can be executed in constant stack space, which is what tail call optimization does. (Notice that the name â€śtail call optimizationâ€ť does not mention recursion.)

A tail call can be recursive (your function calls itself) or it can be a call to another function. That does not really matter. We simply happen to use recursive functions quite a lot and a nice property of tail-recursive functions is that they run in constant stack space (or, more rigorously, the stack space does not depend on the number of recursive calls). A tail-recursive function is a recursive functions whose all recursive calls are tail calls.

With that in mind, is `loop_v2` tail-recursive? Well, yes. It is a bit obfuscated by the partial application, but at worst `helper` will be a closure (which is just a function with some extra values attached to it) which is tail-called, and it tail-calls `loop_v2`. In other words, the call to `loop_v2` is the last executed instruction: it is a tail call.

You can annotate a function application with `[@tailcall]` and the compiler will issue a warning if the call is not actually in tail position:

``````let rec loop_v2 keep_me number =
let helper = loop_v2 keep_me in
if number <= 0 then
print_endline "finished v2"
else begin
print_int number;
print_newline ();
(helper [@tailcall]) (number - 1)
end
``````

One way is to look at the bytecode instructions, by passing `-dinstr` to `ocaml`. For your `loop_v2` youâ€™ll see the following bytecode:

``````       	closurerec 1, 0
acc 0
push
const "loop_v2"
push
getglobal Toploop!
getfield 1
appterm 2, 4
restart
L1:	grab 1
event "//toplevel//" 36-208
acc 0
push
offsetclosure 0
apply 1
event "//toplevel//" 49-64
push
event "//toplevel//" 70-208
acc 2
push
const 0
geint
branchifnot L2
event "//toplevel//" 94-121
const "finished v2"
push
getglobal Stdlib!
getfield 45
appterm 1, 4
L2:	event "//toplevel//" 129-208
acc 2
push
getglobal Stdlib!
getfield 43
apply 1
event "//toplevel//" 139-155
const 0
push
getglobal Stdlib!
getfield 46
apply 1
event "//toplevel//" 161-177
acc 2
offsetint -1
push
acc 1
appterm 1, 4
``````

In the code for `L2` youâ€™ll see the three applications corresponding to `print_int number`:

``````	push
getglobal Stdlib!
getfield 43
apply 1
``````

to `print_newline ()`:

``````	const 0
push
getglobal Stdlib!
getfield 46
apply 1
``````

and to `helper (number - 1)`

``````	push
acc 1
appterm 1, 4
``````

in the `else` branch of `loop_v2`. The first two use the standard call instruction `apply`, but the call to `helper` uses the tail-call instruction `appterm`, confirming that the application of the partially-applied function is a tail call.

2 Likes

A relevant article is It Is What It Is (And Nothing Else). Stacks are used to implement compound expressions and have become conflated with recursion. A tail call, which may or may not be recursive, is simply a call that has the same continuation as its caller, therefore not pushing more â€śwork to doâ€ť on the stack.

Thanks for clarifying. I did mistakenly think tco was related to calling functions recursively.

Interesting tool!

I like this. Iâ€™d like to learn more about those bytecodes. Are there any GUI tools that could help visualizing the effect of interpreting bytecodes on the memory of the virtual machine as we step through the program?

I found this article a little hard to follow. Fundamentally, I understand recursion is a different topic. For instance defining a tree type in OCaml, which is self-referential, was quite mind blowing for me.

But with regards to calling functions recursively, Iâ€™m not sure I understand why one shouldnâ€™t think about whatâ€™s really going under the hood (at the stack level).

I first encountered this topic when learning Elixir, then I saw it again in the book â€śOCaml from the very beginningâ€ť. My mental model is still pretty vague though, as you can see from the opening of my post.