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

[Steffen Schuldenzucker]

On 7/5/2010 8:33 PM, Andrew Coppin wrote:
> Tillmann Rendel wrote:
>> Hi Steffen,
>>
>> Steffen Schuldenzucker wrote:
>>> Given the definition of a recursive function f in, say, haskell, 
>>> determine if f can be implemented in O(1) memory.
>>
>> Constant functions are implementable in O(1) memory, but interpreters 
>> for turing-complete languages are not, so the property of being 
>> implementable in O(1) memory is non-trivial and therefore, by Rice's 
>> theorem, undecidable.
>
> Damn Rice's theorum, spoiling everybody's fun all the time... ;-)

Definitely! Thanks, Tillmann, for this quite clear answer.

> Of course, as I understand it, all the theorum says is that no single 
> algorithm can give you a yes/no answer for *every* possible case. So 
> the next question is "is it decidable in any 'interesting' cases?"
>
> Then of course you have to go define 'interesting'...

Yes, perhaps I should reformulate my original question to something like

"What is a good algorithm for transforming an algorithm written in a 
functional language to constant-memory imperative code? Which properties 
must the functional version satisfy?"

(one answer would be tail-call optimization, but, as I pointed out in my 
first post, I guess this isn't the whole story)

or even:

"Can you tell me an example of a set of functionally-defined algorithms 
maximal in the property that there exists a single algorithm which 
transforms them all into constant-memory imperative code?"

-- Steffen