6 ms·

The process of writing an optimized compiler involves utilizing hundreds of algorithms and strategies, one of which is tail call optimization. It seems that th

The process of writing an optimized compiler involves utilizing hundreds of algorithms and strategies, one of which is tail call optimization. It seems that this particular optimization technique is frequently discussed and written about, leading me to wonder if it holds a unique level of importance among the other strategies. Is my perception incorrect, or is there more to the significance of tail call optimization that I am unaware of?

mhh__ 4y ago
It doesn't require almost any advanced compiler techniques, and you can implement it without constructing the playpen typical of compilers (doing optimization on an AST directly is quite hard, tail calls are easy)
- toolslive 4y ago
  Tell that to the Rust Compiler people ;)
  - 3836293648 4y ago
    I thought the rustc people were against guaranteeing TCO, not having it at all
blagie 4y ago
Tail recursion isn't just an optimization technique. It enables a broad range of algorithms to work. Anything where the stack grows O(n) can't be done without tail recursion because of stack overflows. There are two camps of programmers: 1) Ones who are used to writing such algorithms (e.g. in Lisp) who cry bloody murder because they can't use them in Python. It's painful to lose that type of expressiveness. 2) Ones who have never used them, and don't realize what they're missing. These will usually complain about surface issues (like nicer stack traces for debugging). Camps like camp #2 comes up a lot in history. - In the eighties and nineties, most BASIC programmers had never used pointers, references, or real data structures, and saw them as abstract theoretical constructs without any real-world use. - C / C++ programmers would call Java programmers lazy for wanting garbage collection (ignorant of the broad set of algorithms enabled if you don't need to keep track of when memory is no longer needed manually). - Java / C / C++ programmers saw closures and a lot of other functional tools as pointless, complex, theoretical abstractions, until Python / JavaScript / etc. ate their lunch. - Many people who have never used relational databases before see them as pointless complexity for most systems, aside from very specific use-cases. ... and so on. The other argument always made hinges on the Turing Completeness of languages ("I'd like to do X!" "Well, here's how you do it without Y. If you were just more clever, you'd see why Y is useless complexity.") You can ALWAYS implement any use case in any Turing-complete language. BASIC programmers stuck things into arrays. Java/C++ programmers could use objects instead of a closure. And tail-recursive code can always be translated into iteration.
- jacquesm 4y ago
  Languages like LISP, Clojure and Erlang would be a whole lot less useful in practice without tail call optimization, it allows you to write the 'naive' version of an algorithm and magically it 'just works'. Otherwise you'd have to explicitly code a loop where you would much rather use recursion.
  - codetrotter 4y ago
    > Otherwise you'd have to explicitly code a loop where you would much rather use recursion. I find it much easier to reason about loops than to reason about recursion. Likewise I find it much easier to write loops than to write recursive functions. It probably comes down to experience mainly. I spent some time with functional languages, but I have spent far far far more time writing imperative procedural code.
    - jacquesm 4y ago
      Even a simple problem such as the 'Towers of Hanoi' looks to me like a pretty messy solution when done with loops and with recursion it all just falls into place.
      - Jensson 4y ago
        Recursion is great due to the implicit stack. The cases where you don't have an implicit stack, ie where tail call optimization works, are usually easier and much clearer to just do in a loop.
  - toast0 4y ago
    > Otherwise you'd have to explicitly code a loop where you would much rather use recursion. The language would have to change for you to be able to code a loop. And that would have all sorts of consequences: in Erlang, preemption happens at function calls and no loops means a bounded time until you make a function call or terminate, with loops, that changes and preemption gets more difficult.
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 ago
  You 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 ago
    Yes, 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 ago
    Which recursion scheme guarantees tail-recursion?
    - consilient 4y ago
      `cata` with a cps'd argument
soegaard 4y ago
> ... is there more to the significance of tail call optimization that I am unaware of? Looking at TCO in isolation is missing the big picture. You need to consider other language features that uses TCO. In Scheme/Racket the specification says that implementations must support an "unbounded number of active tail calls" (for implementations that use stack frames to implement function calls, this means that TCO must be supported). This requirement is a global requirement. The other feature of Scheme/Racket that compelled the authors of the Scheme standard to require an "unbounded number of active tail calls" are macros. Macros in Scheme allow users of the language to add new bindings constructs (e.g. pattern matching), new control constructs etc to the language using syntax rewrite rules. In Scheme these rewrite rules work locally. [Racket allows for global program rewrites too]. There is a range of constructs that are possible to specify locally - if tail calls don't allocate that is. As an example: There are embeddings of Prolog in Scheme. If Scheme didn't support TCO then a global transformation of the program is needed. So instead of writing local macros - a full compiler is needed. These days it is common to see JavaScript as a compilation target. Babel compiles JavaScript+NewFeatures to GoodOldJavaScript. The features that allow local rewriting are much easier to implement than the ones that require a global transformation. If JavaScript had TCO it would be much easier to use JavaScript as a compilation target.
- neilv 4y ago
  One thing to add: It's idiomatic for Scheme (or Racket) code to use tail calls in places that would be unnecessary and inappropriate in many languages. This can combine with other language features and idioms, to get effects such as (in addition to what soegaard mentioned) reducing mutations, and avoiding `return` exits. Which can increase the readability/maintainability -- and therefore correctness -- of the code. So some suggest that Tail Call Optimization for Scheme should instead be called Proper Implementation of Tail Calls.
kybernetyk 4y ago
>leading me to wonder if it holds a unique level of importance among the other strategies. Nah, it's just very easy to understand while being of technical nature. People tend to feel smart when they grasp it and then they can't shut up about it. They even write musicals...
- douglee650 4y ago
  It's ok to wonder at new (to you) knowledge and relay it with passion, even as grizzled vets look on, some scoffing, some with hope. This is the exact type of reaction that makes people turn off the YT comments ... came here to see how deep in the comments this would be; it's the 4th one
  - kybernetyk 4y ago
    https://imgflip.com/i/76qp89 https://imgflip.com/i/76qp89
- jacquesm 4y ago
  You're doing the same thing only from one level higher up. Insert recursion joke here.
fckgnad 4y ago
Yes. For functional programming it is a required optimization for performant programs. This is because loops don't exist in functional programming. The base way of imitating looping in functional programming is recursion then building abstractions on top of the recursion like map and reduce.
hendrikrassmann 4y ago
I think the true goal is to bully Guido van Rossum into putting it into python. (See his reasons to not include it here: http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...)

mhh__ 4y ago

It doesn't require almost any advanced compiler techniques, and you can implement it without constructing the playpen typical of compilers (doing optimization on an AST directly is quite hard, tail calls are easy)

toolslive 4y ago
Tell that to the Rust Compiler people ;)
- 3836293648 4y ago
  I thought the rustc people were against guaranteeing TCO, not having it at all

blagie 4y ago

Tail recursion isn't just an optimization technique. It enables a broad range of algorithms to work. Anything where the stack grows O(n) can't be done without tail recursion because of stack overflows. There are two camps of programmers: 1) Ones who are used to writing such algorithms (e.g. in Lisp) who cry bloody murder because they can't use them in Python. It's painful to lose that type of expressiveness. 2) Ones who have never used them, and don't realize what they're missing. These will usually complain about surface issues (like nicer stack traces for debugging). Camps like camp #2 comes up a lot in history. - In the eighties and nineties, most BASIC programmers had never used pointers, references, or real data structures, and saw them as abstract theoretical constructs without any real-world use. - C / C++ programmers would call Java programmers lazy for wanting garbage collection (ignorant of the broad set of algorithms enabled if you don't need to keep track of when memory is no longer needed manually). - Java / C / C++ programmers saw closures and a lot of other functional tools as pointless, complex, theoretical abstractions, until Python / JavaScript / etc. ate their lunch. - Many people who have never used relational databases before see them as pointless complexity for most systems, aside from very specific use-cases. ... and so on. The other argument always made hinges on the Turing Completeness of languages ("I'd like to do X!" "Well, here's how you do it without Y. If you were just more clever, you'd see why Y is useless complexity.") You can ALWAYS implement any use case in any Turing-complete language. BASIC programmers stuck things into arrays. Java/C++ programmers could use objects instead of a closure. And tail-recursive code can always be translated into iteration.

jacquesm 4y ago
Languages like LISP, Clojure and Erlang would be a whole lot less useful in practice without tail call optimization, it allows you to write the 'naive' version of an algorithm and magically it 'just works'. Otherwise you'd have to explicitly code a loop where you would much rather use recursion.
- codetrotter 4y ago
  > Otherwise you'd have to explicitly code a loop where you would much rather use recursion. I find it much easier to reason about loops than to reason about recursion. Likewise I find it much easier to write loops than to write recursive functions. It probably comes down to experience mainly. I spent some time with functional languages, but I have spent far far far more time writing imperative procedural code.
  - jacquesm 4y ago
    Even a simple problem such as the 'Towers of Hanoi' looks to me like a pretty messy solution when done with loops and with recursion it all just falls into place.
    - Jensson 4y ago
      Recursion is great due to the implicit stack. The cases where you don't have an implicit stack, ie where tail call optimization works, are usually easier and much clearer to just do in a loop.
- toast0 4y ago
  > Otherwise you'd have to explicitly code a loop where you would much rather use recursion. The language would have to change for you to be able to code a loop. And that would have all sorts of consequences: in Erlang, preemption happens at function calls and no loops means a bounded time until you make a function call or terminate, with loops, that changes and preemption gets more difficult.

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 ago
You 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 ago
  Yes, 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 ago
  Which recursion scheme guarantees tail-recursion?
  - consilient 4y ago
    `cata` with a cps'd argument

soegaard 4y ago

> ... is there more to the significance of tail call optimization that I am unaware of? Looking at TCO in isolation is missing the big picture. You need to consider other language features that uses TCO. In Scheme/Racket the specification says that implementations must support an "unbounded number of active tail calls" (for implementations that use stack frames to implement function calls, this means that TCO must be supported). This requirement is a global requirement. The other feature of Scheme/Racket that compelled the authors of the Scheme standard to require an "unbounded number of active tail calls" are macros. Macros in Scheme allow users of the language to add new bindings constructs (e.g. pattern matching), new control constructs etc to the language using syntax rewrite rules. In Scheme these rewrite rules work locally. [Racket allows for global program rewrites too]. There is a range of constructs that are possible to specify locally - if tail calls don't allocate that is. As an example: There are embeddings of Prolog in Scheme. If Scheme didn't support TCO then a global transformation of the program is needed. So instead of writing local macros - a full compiler is needed. These days it is common to see JavaScript as a compilation target. Babel compiles JavaScript+NewFeatures to GoodOldJavaScript. The features that allow local rewriting are much easier to implement than the ones that require a global transformation. If JavaScript had TCO it would be much easier to use JavaScript as a compilation target.

neilv 4y ago
One thing to add: It's idiomatic for Scheme (or Racket) code to use tail calls in places that would be unnecessary and inappropriate in many languages. This can combine with other language features and idioms, to get effects such as (in addition to what soegaard mentioned) reducing mutations, and avoiding `return` exits. Which can increase the readability/maintainability -- and therefore correctness -- of the code. So some suggest that Tail Call Optimization for Scheme should instead be called Proper Implementation of Tail Calls.

kybernetyk 4y ago

>leading me to wonder if it holds a unique level of importance among the other strategies. Nah, it's just very easy to understand while being of technical nature. People tend to feel smart when they grasp it and then they can't shut up about it. They even write musicals...

douglee650 4y ago
It's ok to wonder at new (to you) knowledge and relay it with passion, even as grizzled vets look on, some scoffing, some with hope. This is the exact type of reaction that makes people turn off the YT comments ... came here to see how deep in the comments this would be; it's the 4th one
- kybernetyk 4y ago
  https://imgflip.com/i/76qp89 https://imgflip.com/i/76qp89
jacquesm 4y ago
You're doing the same thing only from one level higher up. Insert recursion joke here.

fckgnad 4y ago

Yes. For functional programming it is a required optimization for performant programs. This is because loops don't exist in functional programming. The base way of imitating looping in functional programming is recursion then building abstractions on top of the recursion like map and reduce.

hendrikrassmann 4y ago

I think the true goal is to bully Guido van Rossum into putting it into python. (See his reasons to not include it here: http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...)