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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
