Repository navigation
tail call elimination #4964
Description
Activity
I'm a schemehead and appreciate TCO as much as anybody, but we're not actually planning to implement this so I'm just going to close this. Apologies.
Reacted by Abdurrahman Ayyıldız || n x 10⁻⁹ × 3.34 s/mThere's a volcano of conversation coming from julia-dev. I'll definitely
search it as well is Issues in the future before bringing something up.
Clearly this topic has been discussed. I think the final word is:Jeff Bezanson
Nov 24
No, no update. It's not a high priority, but eventually we will
probably do some of the optimizations, but not the semantic guarantee.On Wed, Nov 27, 2013 at 6:24 PM, Isaiah notifications@github.com wrote:
See
https://groups.google.com/forum/#!searchin/julia-dev/tail-call/julia-dev/POP6YXCnP-k/qjEw2OiFVd8J—
Reply to this email directly or view it on GitHubhttps://github.com//issues/4964#issuecomment-29435198
.Michael
Oh hey Jeff. I just quoted you from julia-dev but you had already responded
to me. How are you doing that?!? You actually showed up in person before I
finished reading the thread where you rejected the idea last year.I want to figure out how this community is so engaged. A few hours before
thanksgiving and people are online. This is like the Reddit of ... I'm out
of metaphors. I need to go soak my head. What? Wow.On Wed, Nov 27, 2013 at 7:14 PM, Jeff Bezanson notifications@github.comwrote:
I'm a schemehead and appreciate TCO as much as anybody, but we're not
actually planning to implement this so I'm just going to close this.
Apologies.—
Reply to this email directly or view it on GitHubhttps://github.com//issues/4964#issuecomment-29436759
.Michael
Reacted by Páll HaraldssonI refuse to believe you're out of metaphors. We're all enjoying them :)
Yes, we are enjoying all the metaphors. Please keep them coming. :-)
I must admit, I'm not sure why or even how I've gotten so involved with Julia. I think it has something to do with the other contributors, but the experiments proving this are still running.
I refuse to believe you're out of metaphors. We're all enjoying them :)
+1. I'm confident and hopeful that you can come up with something. I haven't yet seen one that involves both bicycle grease and wildebeests :-).
I must admit, I'm not sure why or even how I've gotten so involved with Julia. I think it has something to do with the other contributors, but the experiments proving this are still running.
I can't figure it out either, but it's extraordinarily addictive. Perhaps because it's so rewarding.
I can't figure it out either, but it's extraordinarily addictive. Perhaps because it's so rewarding.
Julia specializes in having a very high result-to-effort ratio :-)
Reacted by Taine Zhao, Ron Wolf, Felipe S. S. Schneider and Jerry LingMentioning TCO and "tail call optimization" here so that we can avoid future duplicates of this issue.
If someone wants to go ahead and implement tail call elimination, then feel free to go for it. I'll leave this open for that eventuality.
Reacted by Felipe S. S. Schneider, Lilith Orion Hafner and The Potato ChroniclerReacted by Ron Wolf and The Potato Chronicler+1
Also, language support for lazy evaluation is the other side of that coin.
LazySequences.jl demonstrates the power but not the performance that you
could have.On Thu, Jan 9, 2014 at 5:51 AM, Stefan Karpinski
notifications@github.comwrote:—
Reply to this email directly or view it on GitHubhttps://github.com//issues/4964
.Michael
Look, we don't really need this and it is just a huge pain. It also conflicts with exposing C-callable entry points.
Reacted by Ron Wolf38 remaining items
Why? If you're writing code that needs TCE then you need it and being able to run Julia with/without just means your code might be broken by something you don't control. What is the use case for optional TCE? Explicitly required TCE is the only thing that makes sense to me, which then shouldn't be controlled by a flag, it should be a semantic guarantee.
Reacted by Gabriele Bellomia and FrankHB@StefanKarpinski I don’t know about the compiler/interpreter flag, but having some kind of globalish switch (e.g., on the module/package level) is very helpful on brevity. I suggest having the @tailcall macro support modules as well, where all the tail calls in that module get optimized. Perhaps we can add a disabler macro as well, @notailcall.
If you call it with anything besides a function invocation, it should error at macro expansion time. It would also allow invoking any function, not just the one that's currently running, since one of the use cases for tail calls is implementing state machines by transferring between a set of functions without pushing the stack.
A problem with this is that since basically everything is a method call in Julia, what would you even error on? For example, suppose someone is tweaking the definition of a tail recursive function
fand changes@tailcall f(...)into@tailcall 2*f(...). Well, that can still be turned into a tail call, but the call tofwill use stack space because it's not in tail position—the call to*is.Reacted by Feraidoon Mehri, Páll Haraldsson, Lilith Orion Hafner and Jerry LingThis isn't an issue for the pattern where you explicitly indicate that you want tail recursion since then it's clear that if the tail call isn't to the same function, then it should be an error.
I don't really get the brevity thing.
@return f(...)is only on character longer thanreturn f(...)and@tailcall f(...)is only three characters longer. I guess you want implicit return by havingf(...)be the last expression in the function body also get tail call elimination treatment? This is kind of a niche feature that the language has lived without for a decade, so worrying about brevity seems a bit unnecessary. But if the feature exists in the language, then writing a block macro that turns every implicit return into a tail call is easy, so I think we can dispense what that concern here.it's also not necessarily faster to reuse the current stack frame than to start a new one.
Do you have a counterexample? It seems it always should be faster or could be at least as fast, at runtime.
What I have in mind is only the local case (we could give a guarantee for it, postpone deciding for other cases) that Jeff wrote about:
Local recursion is the easy case. Full tail-call semantics mean that every call in tail position must use no stack space, no matter how many functions are involved or what the structure of the call graph is.
If TCE is sometimes slower then we do need both options. I'm not pushing for any change, because I know of the
@tailrecmacro. Most users, or beginners will not, so it's important to know how much slower the non-TCE case could be, at runtime. My worry is that even if it were faster at then, how much slower is it at compile time? Is that, only, what you had in mind with potentially slower?In at least one Julia style-guide:
https://github.com/invenia/BlueStyleWhen using long-form functions always use the return keyword
Since there are two ways to return (a called function result), without the keyword or not, would it be on the table to only have the TCE guarantee only one way, e.g. without
return, and only as then as simple function call (e.g. not for the2*f(...)case)?As soon as we provide a TCE guarantee, we can't really go back, as it would be a breaking change. And doing it as an optimization is worse, if you have it sometimes, you don't know when and why it went away.
From your link:
Scala sort of has this with the @tailrec annotation. The compiler will always attempt TCO, but the annotation makes failure to do so a compilation error. (Its not a perfect situation though, since there can still be functions assumed to be tail recursive without @tailrec, and whose behavior can change without warning)
I don't think we need a global option, to opt-in to TCE, but we do need one, to opt-out, likely as part of a debug/dev mode (there's a lot more we could have as part of such a mode, a separate discussion). We also need some way to opt out of TCE locally (if it were the default, and assuming sometimes slower), but I'm undecided on if it should be with skipping an explicit
@tailrec.LLVM does not at the moment provide a way to enforce this. I would expect it to happen in simple cases though.
Is that for sure? I noticed new in Clang (then implies LLVM supports?):
https://releases.llvm.org/13.0.0/tools/clang/docs/ReleaseNotes.html
Guaranteed tail calls are now supported with statement attributes [[clang::musttail]] in C++ and attribute((musttail)) in C.
Julia can already provide tailrec, as done with
@tailrec(I'm, not up to speed on all limitations). If LLVM provides support, is that a good enough reason to include support in Julia? [No (other) C/C++ compiler needs to support, only LLVM?]The following might be an interesting toy example if anyone would be interested in doing this. It was inspired by this question https://discourse.julialang.org/t/iterator-over-upper-triangular-part-of-cartesian-product/63118, where it appeared that
combinationsfromCombinatorics.jlwas apparently very inefficient. So I tried to generalize the "pairs" algorithm proposed in that thread and ended up using recursion:function combinations(x,n) if n <= 0 return ( () ) end if n== 1 return x end if n==2 # this case is unneccessary return ( (a,b) for (k,a) in enumerate(x) for b in Iterators.drop(x, k) ) end return ( (a, b...) for (k,a) in enumerate(x) for b in combinations(Iterators.drop(x,k), n-1) ) end
With the
n==2case you get@btime all(x-> gcd(x...) ==1, comb( (1,2,3,4,5,6 ), 2 )) 53.330 ns (0 allocations: 0 bytes)
If you leave out the
n==2case you get@btime all(x-> gcd(x...) ==1, comb( (1,2,3,4,5,6 ), 2 )) 742.421 ns (37 allocations: 3.08 KiB)
Since
combinations(x, 1)just returnsx, this could be optimized into then==2case with tail end optimization I think. But writing this algorithm without recursion is harder than I thought. So I think this might be an interesting toy exampleThere is no tail recursion in that example.
To make that more explicit: tail recursion requires a statement
return combinations(...)somewhere in your function. You don't have that.Julia can already provide tailrec, as done with @tailrec (I'm, not up to speed on all limitations). If LLVM provides support, is that a good enough reason to include support in Julia? [No (other) C/C++ compiler needs to support, only LLVM?]
out of my element here, but i believe it depends on the calling convention being used: https://internals.rust-lang.org/t/all-tail-calls-are-sibling-calls/1696/4
Ah right, I think I misunderstood tail recursion.
@TANRIninResulu, please stop posting off-topic and religious content.
It's interesting that this is valid syntax in Julia and Lua:
The difference is that in Lua, when you call
rec()it will stare at you and engage your motherboard's built-in space heater until you ctrl-C out. In Julia:So the stack 80000 things deep. That's interesting.
Why does this matter? I'm not sure. But some people care a lot:
http://www.lua.org/pil/6.3.html