[Haskell-cafe] Criteria for determining if a recursive function can be implemented in constant memory

[Steffen Schuldenzucker]

Dear Cafe,

since a little discussion with my tutor I am wondering how the following 
problem can be solved and if it is decidable:

Given the definition of a recursive function f in, say, haskell, 
determine if f can be implemented in O(1) memory.

First I thought the solution would be "check if f is tail-recursive". 
However, consider the following definition:

 > -- for the sake of uniformity
 > if' c t e = if c then t else e
 >
 > f :: (Num a) => a -> a -> a
 > f x y = if' (x <= 0) y $
 >    if' (x >= 2) (f (x-2) (y+1)) (f (x-1) y)

(I don't really care what this function computes as long as it 
terminates, which is obvious)

Although ghc will probably not perform this optimization, f can be 
realized in O(1) mem:

// trying to duplicate f's structure as closely as possible
double f( double x, double y )
{
START:
     if ( x <= 0 )
         return y;
     else
     {
         if ( x >= 2 )
         {
             x = x - 2;
             y = y + 1;
             goto START;
         }
         else
         {
             x = x - 1;
             y = y;
             goto START;
         }
     }
}

It is crucial that (the second) if' does not use both of its last two 
arguments, but only one. If we replace the second if' by, say

 > g :: (Num a) => c -> a -> a -> a
 > g c t e = if' c (t + e) (t - e)

, then we have to compute *both* (f (x-2) (y+1)) and (f (x-1) y), and x 
and y have to be kept in memory during the call to (f (x-2) (y+1)), 
therefore f cannot be implemented in constant memory. (read: I haven't 
found a way which does not radically alter f's structure).

So, does someone know how to solve this or can prove that it can't be 
solved?

Best regards,

Steffen