Moving recursive calls in "almost tail position" to true tail position

Question

While reading Guido's reasoning for not adding tail recursion elimination to Python, I concocted this example of almost tail recursion in Haskell:

triangle :: Int -> Int
triangle 0 = 0
triangle x = x + triangle (x - 1)

This is of course not a tail call because although the recursive call is in the "return" per se, the x + prevents the current stack from being reused for the recursive call.

However, one can transform this into code that is tail recursive (albeit rather ugly and verbose):

triangle' :: Int -> Int
triangle' = innerTriangle 0
    where innerTriangle acc 0 = acc
          innerTriangle acc x = innerTriangle (acc + x) (x - 1)

Here innerTriangle is tail recursive and is kickstarted by triangle'. Although trivial, it seems like such a transformation would also work for other tasks such as building a list (here acc could just be the list being built).

Of course, if a recursive call isn't in the function return, this doesn't seem possible:

someRecusiveAction :: Int -> Bool
someRecursiveAction x = case (someRecursiveAction (x * 2)) of
    True -> someAction x
    False -> someOtherAction x

But I am only referring to "almost tail" calls, ones where the recursive call is part of the return value but isn't in tail position due to another function application wrapping it (such as the x + in the triangle example above).

Is this generalizable in a functional context? What about an imperative one? Can all functions with recursive calls in their returns be transformed into functions with returns in tail position (i.e. ones that can be tail call optimized)?

Never mind the fact that none of these are the "best" way to calculate a triangle number in Haskell, which AFAIK is triangle x = sum [0..n]. The code is purely a contrived example for this question.

Note: I've read Are there problems that cannot be written using tail recursion?, so I'm fairly confident that the answer to my question is yes. However, the answers mention continuation passing style. Unless I'm misunderstanding CPS, it seems like my transformed triangle' is still in direct style. In which case, I'm curious about making this transformation generalizable in direct style.

Answer 1

There are an interesting space of tail-recursion-modulo-operator optimizations that can transform some functions such that they run in constant space. Probably the most well-known is tail-recursion-modulo-cons, in which the not quite tail call is an argument of a constructor application. (This is an ancient optimisation which dates back to the early days of Prolog compilers - I think David Warren of Warren Abstract Machine fame was the first to discover it).

However, be aware that such optimisations are less suited to lazy languages. Languages like Haskell have very different evaluation models in which tail calls are not as crucial. In Haskell a constructor application enclosing a recursive call can be desirable, as it will prevent immediate evaluation of the recursive call and allow the computation to be consumed lazily. See the discussion at this HaskellWiki page.

Here's an example of a candidate for modulo-cons optimisation in a strict language:

let rec map f = function
  | [] -> []
  | x::xs -> f x::map f xs

In this OCaml function the recursive call to map is an argument to a constructor application in tail position, so a modulo-cons optimization could apply. (OCaml does not yet do this optimization, although there are some experimental patches floating around.)

The transformed function might look like the following psuedo-OCaml. Note that the inner loop is tail recursive and works by mutating the previous cons:

let rec map f = function
  | [] ->
  | x::xs ->
    let rec loop cons = function
      | [] -> cons.[1] <- []
      | y::ys ->
        let new_cons = f y::NULL in
        cons.[1] <- new_cons;
        loop new_cons ys in
    loop (f x::NULL) xs

(Where NULL is some internal value that the GC won't choke on.)

Tail consing is also common in Lisp via a different mechanism: there the mutation tends to be programmed explicitly and the messy details hidden within a macro such as loop.

How these approaches can be generalised is an interesting question.