8 ms·

yeah but how do i know for sure that the compiler is going to optimize the memory or not ? Some compilers are smarter than other to rewrite recursion in a tail

by bsaul 5y ago

yeah but how do i know for sure that the compiler is going to optimize the memory or not ? Some compilers are smarter than other to rewrite recursion in a tail recursive way, and others aren't, and it's probably not possible all the time anyway.. It seems like a very convoluted way to do a simple thing ( sometimes).

emodendroket 5y ago
In Scala, as I recall, you could annotate a method as tail recursive so it wouldn't build if it weren't. A serious functional language pretty much has to have an answer for this since you're supposed to use recursion instead of iteration.
- yawaramin 5y ago
  Scala has the '@tailrec' annotation for this, and OCaml has the '[@@tailcall]' attribute for the same reason.
carnitine 5y ago
A tail recursive function can always be optimised into code which does not consume memory on recursion, and it’s a pretty basic fact to learn about a given language/implementation.
- bsaul 5y ago
  my question was more about cases where the tail recursive version isn't possible, or even worst when the code isn't written in a tail recursive way but you expect the compiler to rewrite it to the tail recursive version. the fact that FP works over a model of computation (aka an abstraction over the underlying hardware limits) makes it a bit harder to visualize its behavior in the bounded real-world environment ( imho ). The more i progress the more i want to develop with "visible wires", and reduce the amount of abstraction to its most basic components..
Twisol 5y ago
I suspect you think about recursion in terms of a call stack, yes? So when you have tail recursion, you're still pushing a frame onto the stack by default, unless the compiler recognizes that it can optimize that way. Yes? The traditional FP model of computation doesn't have a call stack. It proceeds by reduction: replace one subexpression with another, in the program text itself, and repeat until you can't do it anymore. So if I've got a fibonacci function in two clauses, `fib 0 a b = b` and `fib n a b = fib (n - 1) b (a + b)`, then a reduction may look like this: fib 3 0 1 -- initial program = fib 2 1 (0 + 1) -- substitute second clause of `fib` = fib 2 1 1 -- evaluate `+` = fib 1 1 (1 + 1) = fib 1 1 2 = fib 0 2 (1 + 2) = fib 0 2 3 = 3 -- substitute first clause of `fib` Notice how the tail-recursion naturally falls out of the substitution steps performed by the interpreter. There are no stack frames; the whole "rest of the program" (which is what a call stack is) is just the program itself. This isn't just an analogy; this is the way computation works in an FP. To an FP system, the call stack is the invisible, behind-the-scenes optimization.
c-cube 5y ago
Functional languages will typically guarantee you that tail recursion is constant space. The exception is languages running on a FP adverse runtime such as the jvm, and they tend to provide a special keyword and rewrite into a loop. Also, mutual recursion is a bit more general than loops :)
- Twisol 5y ago
  Mutual single recursion is still a loop; you just pick where you want to cut the cyclic dependencies to return to the top. In the worst case, you can put a `switch` in the loop and track what state you're in, although that's gross (you have to keep the union of all variables that might be used in each state). Multiple recursion, like in `fib n = fib (n - 1) + fib (n - 2)`, is more general than loops... in a world without higher-order functions. You can make such a function tail-recursive by doing the continuation-passing transform, which basically just makes the stack explicit. (You'd then want to "defunctionalize the continuation" [0] to clean up.) (I've actually done this in Java! Writing the multiply-recursive solution is sometimes a lot easier to do (and verify); transforming it into an iterative solution mechanically exposes a lot more hidden details, but you still have your recursive solution you can test and compare against.) [0] http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html http://www.pathsensitive.com/2019/07/the-best-refactoring-yo...

by bsaul 5y ago

emodendroket 5y ago

In Scala, as I recall, you could annotate a method as tail recursive so it wouldn't build if it weren't. A serious functional language pretty much has to have an answer for this since you're supposed to use recursion instead of iteration.

yawaramin 5y ago
Scala has the '@tailrec' annotation for this, and OCaml has the '[@@tailcall]' attribute for the same reason.

carnitine 5y ago

A tail recursive function can always be optimised into code which does not consume memory on recursion, and it’s a pretty basic fact to learn about a given language/implementation.

bsaul 5y ago
my question was more about cases where the tail recursive version isn't possible, or even worst when the code isn't written in a tail recursive way but you expect the compiler to rewrite it to the tail recursive version. the fact that FP works over a model of computation (aka an abstraction over the underlying hardware limits) makes it a bit harder to visualize its behavior in the bounded real-world environment ( imho ). The more i progress the more i want to develop with "visible wires", and reduce the amount of abstraction to its most basic components..

Twisol 5y ago

I suspect you think about recursion in terms of a call stack, yes? So when you have tail recursion, you're still pushing a frame onto the stack by default, unless the compiler recognizes that it can optimize that way. Yes? The traditional FP model of computation doesn't have a call stack. It proceeds by reduction: replace one subexpression with another, in the program text itself, and repeat until you can't do it anymore. So if I've got a fibonacci function in two clauses, `fib 0 a b = b` and `fib n a b = fib (n - 1) b (a + b)`, then a reduction may look like this: fib 3 0 1 -- initial program = fib 2 1 (0 + 1) -- substitute second clause of `fib` = fib 2 1 1 -- evaluate `+` = fib 1 1 (1 + 1) = fib 1 1 2 = fib 0 2 (1 + 2) = fib 0 2 3 = 3 -- substitute first clause of `fib` Notice how the tail-recursion naturally falls out of the substitution steps performed by the interpreter. There are no stack frames; the whole "rest of the program" (which is what a call stack is) is just the program itself. This isn't just an analogy; this is the way computation works in an FP. To an FP system, the call stack is the invisible, behind-the-scenes optimization.

c-cube 5y ago

Functional languages will typically guarantee you that tail recursion is constant space. The exception is languages running on a FP adverse runtime such as the jvm, and they tend to provide a special keyword and rewrite into a loop. Also, mutual recursion is a bit more general than loops :)

Twisol 5y ago
Mutual single recursion is still a loop; you just pick where you want to cut the cyclic dependencies to return to the top. In the worst case, you can put a `switch` in the loop and track what state you're in, although that's gross (you have to keep the union of all variables that might be used in each state). Multiple recursion, like in `fib n = fib (n - 1) + fib (n - 2)`, is more general than loops... in a world without higher-order functions. You can make such a function tail-recursive by doing the continuation-passing transform, which basically just makes the stack explicit. (You'd then want to "defunctionalize the continuation" [0] to clean up.) (I've actually done this in Java! Writing the multiply-recursive solution is sometimes a lot easier to do (and verify); transforming it into an iterative solution mechanically exposes a lot more hidden details, but you still have your recursive solution you can test and compare against.) [0] http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html http://www.pathsensitive.com/2019/07/the-best-refactoring-yo...