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

_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to