automatic tail recursion transformation?

femu
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 12. Sep 2009 19:21

automatic tail recursion transformation?

Beitrag von femu »

I think once you get accustomed to functional programming languages, functional programs seem more similar to natural language. You are not describing what steps to do, to produce a result - you describe the result. This lets you program faster and less error prone for the price that you can't do certain manual optimizations.

(Of course this is not always true and functional programming has disadvantages too.)

But when you write a procedure in tail recursion style to make the memory usage more efficient, you lose some of that advantage again. I sometimes struggle to find a name for the "inner" function with the additional parameter. That is because it doesn't refer to a real concept but is instead a artificial hack.

Isn't there a way to translate a "intuitive" style procedure to a tail recursion style procedure automatically? Or is it purposely not applied?
Or do you just use higher-order functions so often that you don't need any kind of recursion, except to implement fold, map etc.?

Benutzeravatar
sewe
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

Re: automatic tail recursion transformation?

Beitrag von sewe »

femu hat geschrieben:Isn't there a way to translate a "intuitive" style procedure to a tail recursion style procedure automatically? Or is it purposely not applied?
Yes, there is indeed an automatic way to translate any program into a purely tail-recursive one. This is called CPS-transform (transformation into continuation-passing style) and will be discussed later in the lecture. The resulting programs, however, often don't look very "natural."
femu hat geschrieben:Or do you just use higher-order functions so often that you don't need any kind of recursion, except to implement fold, map etc.?
That's a good observation. The availability of a well-stocked library of higher-order functions alleviates the problem quite a bit. So maybe the library's definition of a higher-order function is not the most readable, but you don't have to care about that, as the unnatural-looking code is hidden behind a simple interface (in particular if you consider list comprehensions in Haskell).

DanielSchoepe
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 28. Sep 2009 11:39

Re: automatic tail recursion transformation?

Beitrag von DanielSchoepe »

femu hat geschrieben: Isn't there a way to translate a "intuitive" style procedure to a tail recursion style procedure automatically? Or is it purposely not applied?
Or do you just use higher-order functions so often that you don't need any kind of recursion, except to implement fold, map etc.?
Another point is that tail-recursion (with our definition) isn't even the critical thing for running in constant space in lazy functional languages like Haskell (of course, this doesn't answer the question for strict functional languages), where it's more important that a recursive call is in an argument to a data constructor (called "Guarded Recursion"). Here's a thread on the Haskell-cafe mailing list that discusses this point.

Antworten

Zurück zu „Archiv“