8 ms·

A tail calling interpreter for Python (already landed in CPython)

• thunkingdeep 2y ago
  This does NOT mean Python will get Tail Call Optimization, as Guido cannot be shown The Light, and has decided.
  • rpcope1 2y ago
    That's probably one of the more frustrating things about Python. Each release it gets all sorts of questionable new syntax (including the very strange pattern matching "feature" that kind of sucks compared to something like Erlang or Scala), but we never get real useful quality of life improvements for basic functional programming like TCO or multi line lambdas
    • jgalt212 2y ago
      The utility value of multi-line lambdas is real, but the readability of these is terrible. And Python prizes readability. So you know where this initiative will end up.
      • saagarjha 2y ago
        Nothing more readable than a triply-nested list comprehension on an object that exists only to vend its __getattr__ for some unholy DSL
        • pinoy420 2y ago
          Annoying. Because it “compiles” to less optimal code than writing it explicitly.
      • vrighter 2y ago
        I personally find python to be highly UNreadable, especially with all of its syntax and braindead scoping rules
    • throwaway81523 2y ago
      Python has always been unashamedly imperative, with some functional features entering by slipping through the cracks. The pattern matching thing seemed ok to me when I tried it, but I haven't used it except briefly, since I'm still mostly on Python 3.9. Interestingly, Python has been losing users to Rust. I don't entirely understand that, other than everyone saying how Rust's tooling is so much better.
      • flakes 2y ago
        > Python has been losing users to Rust. I don't entirely understand that, other than everyone saying how Rust's tooling is so much better. Not to rust, but to Go and C++ for myself. The biggest motivating factor is deployment ease. It is so difficult to offer a nice client install process when large virtual environments are involved. Static executables solve so many painpoints for me in this arena. Rust would probably shine here as well. If its for some internal bespoke process, I do enjoy using Python. For tooling shipped to client environments, I now tend to steer clear of it.
        • sieve 2y ago
          > For tooling shipped to client environments, I now tend to steer clear of it. A guy on r/WritingWithAI is building a new writing assistant tool using python and pyQt. He is not a SE by trade. Even so, the installation instructions are: - Install Python from the Windows app store - Windows + R -> cmd -> pip install ... - Then run python main.py This is fine for technical people. Not regular folks. For most people, these incantations to be typed as-is in a black window mean nothing and it is a terrible way of delivering a piece of software to the end-user.
        • pjmlp 2y ago
          As someone that always kept a foot on C++ land, dispite mostly working on managed languages, I would that by C++17 (moreso now in C++23), dispite all its quirks and warts, C++ has become good enough that I can write Python like code with it. Maybe it is only a thing to those of us already damaged with C++, and with enough years experience using it, but there are still plenty of such folks around to matter, specially to GPU vendors, and compiler writers.
    • dragonwriter 2y ago
      > we never get real useful quality of life improvements for basic functional programming like TCO or multi line lambdas A lambda can be as big of an expression as you want, including spanning multiple lines; it can't (because it is an expression) include statements, which is only different than lambdas in most functional languages in that Python actually has statements.
      • kqr 2y ago
        > most functional languages Most popular functional languages I can think of except maybe Haskell has statements!
    • pinoy420 2y ago
      The choice of “unique” verbs is weird too. Case match. Try except?
      • maleldil 2y ago
        `match/case` looks absolutely fine to me. What's the problem? `try/except` is definitely weird, though.
  • ehsankia 2y ago
    Guido is no longer BDFL though, it's the steering committee that decides.
    • thunkingdeep 2y ago
      Ah, you’re correct. My comment was mainly meant as a tongue in cheek remark to point out that this definition of tailcall is wholly separate from Python function objects and merely an implementation detail.
    • riffraff 2y ago
      the steering committee seems way less conservative than Guido, right? Looking at python from the outside a lot of changes since GvR stepped down seem like stuff he'd not have been fond of.
      • pansa2 2y ago
        Any examples? The biggest change since Guido stepped down has been the addition of pattern matching, which he was strongly in favour of. Moreover, Guido is in favour of ongoing addition of major new features (like pattern matching), worrying that without them Python would become a “legacy language”: https://discuss.python.org/t/pep-8012-frequently-asked-questions/487/2 https://discuss.python.org/t/pep-8012-frequently-asked-quest...
        • pinoy420 2y ago
          Pattern matching seems like a cool feature that was added just because it was cool. I think the syntax is really odd too - apparently to “be pythonic”. I really see no use for it other than to “look smart”. The fact that case match (switch case is a much better description) is expanded to practically a huge if else is disturbing. Similarly the walrus operator. Other than an answer to “what is a new feature of python that you like” interview trivia question, really, who has actually used it?
          • pansa2 2y ago
  • beagle3 2y ago
    It is not an optimization ; it changes program semantics - converts programs that will run out of stack eventually regardless of the amount of available memory (and raise exceptions an the process, for example, which a program might rely on. Either way, semantics are changed) It should only be called Tail Call Elimination.
    • flakes 2y ago
      > converts programs that will run out of stack eventually regardless of the amount of available memory (and raise exceptions an the process, for example, which a program might rely on https://xkcd.com/1172/ https://xkcd.com/1172/
    • dragonwriter 2y ago
      By that standard, any optimization that changes scaling in any dimension changes semantics, which, well, I’m not saying its wrong, but I would say it is exactly what people looking for optimization want.
      • dataflow 2y ago
        > By that standard, any optimization that changes scaling in any dimension changes semantics That doesn't follow. This isn't like going from driving a car to flying an airplane. It's like going from driving a car to just teleporting instantly. (Except it's about space rather than time.) It's a difference in degree (optimization), yes, but by a factor of infinity (O(n) overhead to 0 overhead). At that point it's not unreasonable to consider it a difference in kind (semantics).
        • tomsmeding 2y ago
          Modern C compilers are able to transform something like this: for (int i = 0; i < n; i++) a += i; To: a += n * (n+1) / 2; Is this an optimisation or a change in program semantics? I've never heard anyone call it anything slse than an optimisation.
          • 2y ago
  • coldtea 2y ago
    Hasn't Guido step down from BD anyway?
• asicsp 2y ago
  See also this little bit of discussion about a week back: https://news.ycombinator.com/item?id=42999672 https://news.ycombinator.com/item?id=42999672
• VWWHFSfQ 2y ago
  Will Python ever get fast? Or even _reasonably_ fast? The answer is no, it will not. Instead they'll just keep adding more and more syntax. And more and more ways to do the same old things. And they'll say that if you want "fast" then write a native module that we can import and use. So then what's the point? Is Python really just a glue language like all the rest?
  • IgorPartola 2y ago
    Python is fast enough for a whole set of problems AND it is a pretty, easy to read and write language. I do think it can probably hit pause on adding more syntax but at least everything it adds is backwards compatible. You won’t be writing a 3D FPS game engine in Python but you definitely can do a whole lot of real time data processing, batch processing, scientific computing, web and native applications, etc. before you need to start considering a faster interpreter. If your only metric for a language is speed then nothing really beats hand crafted assembly. All this memory safety at runtime is just overhead. If you also consider language ergonomics, Python suddenly is not a bad choice at all.
    • VWWHFSfQ 2y ago
      I guess I'm wondering what is the point of tail-call optimizations, or even async/await when it's all super slow and bounded by the runtime itself? There are basically no improvements whatsoever to the core cpython runtime. So really what is all this for? Some theoretical future version of Python that can actually use these features in an optimal way?
      • throwaway81523 2y ago
        This TCO is in how the CPython interpreter works, not in making Python itself tail recursive. Some of the C code in the interpreter has been reorganized to put some calls into tail position where the C compiler turns them into jumps. That avoids some call/return overhead and makes the interpreter run a little faster. It's still interpreting the same language with the same semantics.
    • 2y ago
• saidinesh5 2y ago
  Recent discussion: https://news.ycombinator.com/item?id=42999672 https://news.ycombinator.com/item?id=42999672 Do check out the articles in the top most comment.. about how tail call optimization gets you faster interpreters. It completely eliminates the overhead of function calls in the generated machine code while you still your code modularly using functions.
  • haberman 2y ago
    Yes, that is the same article linked in the first sentence of this "update" article. :) I published this technique four years ago, and it's very exciting to see that others have taken up the cause and done the work to land it in CPython.
  • nine_k 2y ago
    I think this technique is known since 1970s as "direct threaded code".
• riffraff 2y ago
  How does this differ from direct threading interpreters? It seems like it solves the same problem (saving the function call overhead) and has the same downsides (requires non-standard compiler extensions) EDIT: it seems the answer is that compilers do not play well with direct-threaded interpreters and they are able to perform more/better optimizations when looking at normal-sized functions rather than massive blocks http://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html
  • noelwelsh 2y ago
    Unfortunately, most discussion of direct threaded interpreters confuses the implementation techniques (e.g. computed gotos) with the concepts (tail calls, or duality between calls and returns and data and codata, depending on your point of view). What is presented here is conceptually a direct threaded interpreter. It's just implemented in a way that is more amenable to optimization by the compiler technology in use. (More here: https://noelwelsh.com/posts/understanding-vm-dispatch/ https://noelwelsh.com/posts/understanding-vm-dispatch/)
  • coldtea 2y ago
    >and has the same downsides (requires non-standard compiler extensions) It's not a downside if: (a) you have those non-standard compiler extensions in the platforms you target (c) for the rest, you can ifdef an alternative that doesn't require them
  • haberman 2y ago
    This is a great summary. When Mike wrote the message you linked, his conclusion was that you have to drop to assembly to get reasonable code for VM interpreters. Later we developed the "musttail" technique which was able to match his assembly language sequences using C. This makes C a viable option for VM interpreters, even if you want best performance, as long as your compiler supports musttail. > they are able to perform more/better optimizations when looking at normal-sized functions rather than massive blocks It's not the size of the function that is the primary problem, it is the fully connected control flow that gums everything up. The register allocator is trying to dynamically allocate registers through each opcode's implementation, but it also has to connect the end of every opcode with the beginning of every opcode, from a register allocation perspective. The compiler doesn't understand that every opcode has basically the same set of "hot" variables, which means we benefit from keeping those hot variables in a fixed set of registers basically all of the time. With tail calls, we can communicate a fixed register allocation to the compiler through the use of function arguments, which are always passed in registers. When we pass this hot data in function arguments, we force the compiler to respect this fixed register allocation, at least at the beginning and the end of each opcode. Given that constraint, the compiler will usually do a pretty good job of maintaining that register allocation through the entire function.
• dammaj 2y ago
  To read about the basics of tail calls optimization: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
• __s 2y ago
  `return goto f()` syntax in C seems interesting I had a similiar idea that Python could have `return from f()` to support tail calls without the issues raised about implicit tail calls