Is this implementation tail-recursive

Question

I read in an algorithmic book that Ackerman's function cannot be made tail-recursive (what they say is "it cannot be converted to iteration"). I am very puzzled by this, so I tried to come up with this:

let Ackb mn = let rec rAck cont mn = match (m, n) with | 0, n -> cont (n+1) | m, 0 -> rAck cont (m-1) 1 | m, n -> rAck (fun x -> rAck cont (m-1) x) m (n-1) in rAck (fun x -> x) mn ;; 

(this is OCaml / F # code).

My problem is that I'm not sure if this is actually a tail recursive. Could you confirm that this is so? If not, why? And in the end, what does it mean when people say that the Ackerman function is not primitive recursive?

Thanks!

Answer 1

Yes, it is recursive. Each function can be made tail-rec by explicit conversion to Continue Passing Style .

This does not mean that the function will be executed in read-only memory: you create stacks of continuations that should be allocated. Perhaps it is more efficient to defunctionalize continuations to represent this data as a simple algebraic data type.

Being primitive recursive is a completely different concept related to the expressiveness of a certain form of recursive definition, which is used in mathematical theory, but is probably not very important for computer science, as you know it: they have very low expressiveness, and systems with functional composition ( starting with Gödel System T), such as all current programming languages, are much more efficient.

In terms of computer languages, primitive recursive functions roughly correspond to programs without general recursion, where all loops / iterations are statically limited (the number of possible repetitions is known).

Answer 2

Yes.

By definition, any recursive function can be converted to an iteration if it has access to an unbounded construct like a stack. An interesting question is whether this can be done without a stack or any other unlimited data store.

A tail-recursive function can be turned into such an iteration only if the size of its arguments is limited. In your example (and almost any recursive function that uses continuations), the cont parameter is for all means and purposes for the stack, which can grow to any size. In fact, the whole point of the continuation transfer style is to store the data usually present on the call stack ("what should I do after I return?") Instead of the continuation parameter.