4 ms·

Clojure also doesn't support TCO, and from what I can tell the explicit loop/recur is sufficient, which also has the advantage that it is very clear (i.e., the

by dewitt 13y ago

Clojure also doesn't support TCO, and from what I can tell the explicit loop/recur is sufficient, which also has the advantage that it is very clear (i.e., the compiler will tell you) when TCO is not being invoked. With implicit TCO you might think you're getting the benefit, only to have a stack blow up unexpectedly at runtime with an edge-case input.

pcwalton 13y ago
Especially with destructors. Whenever you have a destructor in the frame, you're not in tail-call position. This means that tail-call positions in Rust are going to be few anyway.
- cpeterso 13y ago
  Does this mean Rust's `be` keyword can be retired? :)
  - pcwalton 13y ago
    Yes.
- qznc 13y ago
  That calls for an interesting optimization: Using escape+liveness analysis you could probably call some of those destructors earlier.
  - kragen 13y ago
    The problem is that TCO in the sense we're talking about isn't really an "optimization". It's a language feature that removes the need for explicit looping constructs by allowing you to write them as higher-order functions instead. This only works if the guy writing the higher-order function can prove that the compiler will successfully "optimize away" the tail call, or if he doesn't care whether the program dies with a stack overflow. If the success of TCO is dependent on which conservative approximation the compiler is using for escape and liveness analysis, then people who care about their programs continuing to run will demand explicit looping constructs anyway. There are three separate inventions in Scheme that work this way. Closures give you objects without an object construct, tail-call optimization gives you loops without looping constructs, and call/cc gives you threads, exceptions, and backtracking without thread, exception, or backtracking constructs. (I mention Scheme because all three of these were, as far as I can tell, introduced in Scheme, and only later adopted by other functional languages like ML, although to be fair, TCO at least falls out naturally from combinator-graph reduction.) In a sense, Scheme is sort of like a functional assembly language: there are lots of object systems, looping constructs, threads, and exception systems in Scheme, and they aren't compatible with each other. It's sort of like the situation with linked lists in C, where every library has its own linked-list type. It's exactly the opposite of assembly language in another way, though. By making object instantiation and population implicit, both the compiler and the maintenance programmer have to do extra work to figure out what's an object and what's not, and what the object's fields are. The same is true of loops, threads, and exceptions. In assembly, instead, you have the problem of things being too explicit, thus losing the signal in the noise. That's my take, anyway. I haven't spent that much time programming in either Scheme or assembly, although I did write an almost-Scheme compiler targeting assembly called Ur-Scheme.
    - solinent 13y ago
      The "assembly language" for ML would actually be the lambda calculus. Scheme isn't really defined unless you're talking about some standard, and the semantics of the language are probably just defined in English.
      - kragen 13y ago
        Hmm, it sounds like you're trying to argue with me, but I'm not clear on what you're saying — some quick responses — hope this helps: ① I did not claim Scheme was an "assembly language" for ML. I said that programming in, reading programs in, and compiling programs in Scheme was like programming in, reading programs in, and compiling programs in assembly language in some specific ways, and very unlike it in others. The relationship between Scheme and ML is that some of the central insights of Scheme were adopted by ML. ② ML defines evaluation order. The lambda calculus does not. Typical ML implementations compile to the assembly languages of actual processors. Can you clarify? ③ I think Scheme is sufficiently well defined for this discussion — it's a family of languages originating in some papers by Sussman and Steele in the 1970s, and continuing through the current R7RS work, including a number of compilers. Several of the standards define the semantics of the language symbolically, not just in English.
kvb 13y ago
Doesn't loop/recur only help in directly self-recursive calls, as opposed to mutual recursion or tail calls to function arguments?
- anonymoushn 13y ago
  That's correct. It should be possible to have an explicit guarantee of TCO while maintaining the ability to write things that aren't trivially reducible to loops...
  - nicolast 13y ago
    Which is +- what Scala allows with an annotation.
    - fhars 13y ago
      No, scala's @tailrec annotation only guarantees that calls that can trivially be compiled to loops in fact are. You can't do better on a standard JVM without jumping through hoops (or, rather, trampolines).
- dewitt 13y ago
  Right. In Clojure you'd use an explicit trampoline for stack-free mutual recursion.
  - andrewvc 13y ago
    Mutual TCO is really uncommon for what it's worth. Of you need it that bad a trampoline should suffice
    - kvb 13y ago
      Direct mutual recursion is somewhat rare (but useful for encoding state machines, for instance). However, using continuation passing style (and tail calls to a continuation argument) to prevent stack overflow is a common idiom in some functional languages (e.g. when mapping over a binary tree).

by dewitt 13y ago

pcwalton 13y ago

Especially with destructors. Whenever you have a destructor in the frame, you're not in tail-call position. This means that tail-call positions in Rust are going to be few anyway.

cpeterso 13y ago
Does this mean Rust's `be` keyword can be retired? :)
- pcwalton 13y ago
  Yes.
qznc 13y ago
That calls for an interesting optimization: Using escape+liveness analysis you could probably call some of those destructors earlier.
- kragen 13y ago
  The problem is that TCO in the sense we're talking about isn't really an "optimization". It's a language feature that removes the need for explicit looping constructs by allowing you to write them as higher-order functions instead. This only works if the guy writing the higher-order function can prove that the compiler will successfully "optimize away" the tail call, or if he doesn't care whether the program dies with a stack overflow. If the success of TCO is dependent on which conservative approximation the compiler is using for escape and liveness analysis, then people who care about their programs continuing to run will demand explicit looping constructs anyway. There are three separate inventions in Scheme that work this way. Closures give you objects without an object construct, tail-call optimization gives you loops without looping constructs, and call/cc gives you threads, exceptions, and backtracking without thread, exception, or backtracking constructs. (I mention Scheme because all three of these were, as far as I can tell, introduced in Scheme, and only later adopted by other functional languages like ML, although to be fair, TCO at least falls out naturally from combinator-graph reduction.) In a sense, Scheme is sort of like a functional assembly language: there are lots of object systems, looping constructs, threads, and exception systems in Scheme, and they aren't compatible with each other. It's sort of like the situation with linked lists in C, where every library has its own linked-list type. It's exactly the opposite of assembly language in another way, though. By making object instantiation and population implicit, both the compiler and the maintenance programmer have to do extra work to figure out what's an object and what's not, and what the object's fields are. The same is true of loops, threads, and exceptions. In assembly, instead, you have the problem of things being too explicit, thus losing the signal in the noise. That's my take, anyway. I haven't spent that much time programming in either Scheme or assembly, although I did write an almost-Scheme compiler targeting assembly called Ur-Scheme.
  - solinent 13y ago
    The "assembly language" for ML would actually be the lambda calculus. Scheme isn't really defined unless you're talking about some standard, and the semantics of the language are probably just defined in English.
    - kragen 13y ago
      Hmm, it sounds like you're trying to argue with me, but I'm not clear on what you're saying — some quick responses — hope this helps: ① I did not claim Scheme was an "assembly language" for ML. I said that programming in, reading programs in, and compiling programs in Scheme was like programming in, reading programs in, and compiling programs in assembly language in some specific ways, and very unlike it in others. The relationship between Scheme and ML is that some of the central insights of Scheme were adopted by ML. ② ML defines evaluation order. The lambda calculus does not. Typical ML implementations compile to the assembly languages of actual processors. Can you clarify? ③ I think Scheme is sufficiently well defined for this discussion — it's a family of languages originating in some papers by Sussman and Steele in the 1970s, and continuing through the current R7RS work, including a number of compilers. Several of the standards define the semantics of the language symbolically, not just in English.

kvb 13y ago

Doesn't loop/recur only help in directly self-recursive calls, as opposed to mutual recursion or tail calls to function arguments?

anonymoushn 13y ago
That's correct. It should be possible to have an explicit guarantee of TCO while maintaining the ability to write things that aren't trivially reducible to loops...
- nicolast 13y ago
  Which is +- what Scala allows with an annotation.
  - fhars 13y ago
    No, scala's @tailrec annotation only guarantees that calls that can trivially be compiled to loops in fact are. You can't do better on a standard JVM without jumping through hoops (or, rather, trampolines).
dewitt 13y ago
Right. In Clojure you'd use an explicit trampoline for stack-free mutual recursion.
- andrewvc 13y ago
  Mutual TCO is really uncommon for what it's worth. Of you need it that bad a trampoline should suffice
  - kvb 13y ago
    Direct mutual recursion is somewhat rare (but useful for encoding state machines, for instance). However, using continuation passing style (and tail calls to a continuation argument) to prevent stack overflow is a common idiom in some functional languages (e.g. when mapping over a binary tree).