3 ms·
What is special about tail call optimisation is that it actually changes the semantics of your program: You now get a guarantee that certain recursive functions
by auggierose 4y ago
What is special about tail call optimisation is that it actually changes the semantics of your program: You now get a guarantee that certain recursive functions do not exhaust the stack space, but behave like a loop. There should really be a language level feature such that you can be sure your functions are not fully recursive, but tail-recursive.
- consilient 4y agoYou can do this with recursion schemes: Haskell: https://hackage.haskell.org/package/recursion-schemes https://hackage.haskell.org/package/recursion-schemes Scala: https://github.com/precog/matryoshka https://github.com/precog/matryoshka
- auggierose 4y agoYes, algebraising your control flow to become independent of implementation details like that is a possibility. Of course, you need a language that makes that a) easy, b) performant.
- atennapel 4y agoWhich recursion scheme guarantees tail-recursion?
- consilient 4y ago`cata` with a cps'd argument