3 ms·

That calls for an interesting optimization: Using escape+liveness analysis you could probably call some of those destructors earlier.

• kragen 14y 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 14y 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 14y 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.