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

Learning
1

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)

2

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
3

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
4

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.

5

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.