Can someone give some real world examples for TCO? Every time I see this I only see fibonacci and gcd and I really want to encounter this one in the wild on something real and applicable
State machines come to mind: a transition is just a function call. Unfortunately that's a general tail call, not always a recursive one, so no love from this library, and that's where "proper" TCO wins (or trampolines if $your_language lacks TCO)
Also it wouldn't help with Fibonacci, since while it's recursive, it's not tail-recursive (yes, it can be written that way, but I'm talking about the idiomatic naive definition).
I don't know about real world "examples", but the beauty of tail-call recursion specifically is the theoretical insight that they have a one-to-one mapping with an loop-based equivalent formulation, and vice versa (which is generally not necessarily true of all recursion).
But, for languages that don't have loop constructs and you need to rely on recursion, all you need to do is write your recipe in standard loop form, and then map back to a tail-call syntax. This is often a LOT easier than trying to think of the problem in a recursive mindset from scratch. (though occasionally, the reverse is also true.)
So the only constraint for re-implementing such looped logic onto tailcalls is that this relies on the stack, which may overflow. By providing TCO you are effectively removing that restriction, so it's a very useful thing for a language to support (especially if they don't provide low-level loops).
The title "tail call optimisation" in the package above is a bit of a misnomer, since this is more of a "transformation" than an "optimisation", but effectively the whole loop-tailcall equivalence is exactly what the package mentioned above relies on to work; it uses decorators to transform tail-call recursive functions to their equivalent loop-based formulations, and thus passing the need to create multiple stacks for the recursion (and risk stack overflow), since the translated loop will now take place in a single stack frame.
but i suspect you're talking about tail-recursion rather than TCO specifically. Otherwise the only sensible answer is, why on earth wouldn't you want that if you could have it for free?
so as for tail recursion examples, one nice example i had in the past which made thinking about the problem a lot easier than loops, was when I was designing a 3D maze-like game. The recuraion allowed me to draw each subsequent "step" visible on the screen without having to kniw in advance hiw many steps should be visible. you just draw the "next" room at increasing vanishing distance, until you hit a "wall" (the base case). It was a very simple, elegant result for minimal code; where the equivalent loop would have been long and horrible.
There isn't a killer use case, because tail calls (to yourself or to siblings) can always be easily converted to a loop, and the loop is more idiomatic in most mainstream languages.
For tco to be really useful you need to think in a non procedural way. Imagine that you don't have loops in your language so you need recursion to do stuff multiple times.
Also even in procedural languages there are some problems that are easier to understand and model if you use recursion, for example tree or graph like structures.
traversing graph or a tree is not a TCO case because it would involve a stack/queue for DFS/BFS, whatever.
I dont want to think in non procedural way, I reserve this nonsense to haskellers, please provide me a valid python use case for TCO :)
Traversing a graph and inspecting each node can definitely make good use of tail call optimization.
For instance: you have a large graph and you are traversing a particular path through it — say a R/B tree seeking a node. You can write it iteratively or recursively. Neither needs to hold more than 1 node reference at a time, the choice is which you prefer to read and write.
I prefer to write that recursively. Sounds like you may not. Observing “well I can write it iteratively so why do I need TCO” is obvious and uninteresting; that’s the point.
It gives you arbitrarily complex control flow even in presence of modularity. A tail call is a state transition. Without them, you'd have to resort to a big loop (which breaks modularity), or some sort of trampoline (which works but it's a bit clumsy).
huh? what is the disadvantage? i am very tired of people parroting some non-arguments. goto is awesome. solves TCO, multiloop breaks, switches and whole lot more
A really simple one is traversing a linked list (or any naturally recursive data structure, such as a dictionary or tree). It is very natural to traverse a recursive data structure recursively.
Very cool. I've been sketching out a relay computer myself. Mostly unbuilt but I have tested a variety of circuits implementing gates, latches, oscillators, flip flops, counters, registers all using only SPST reed relays.
I'm fixated on speed. I connected some reed relays in a 3 stage ring oscillator and it ran at 1.8 kHz. That has me thinking that with a pipeline 100 instructions a second might be attainable. Reed relay logic seems to be fast enough for a UART at 50 baud. Teletype interactivity is a stretch goal.
My program counter is also 12 bits! And I've also been using Digital to simulate parts of it. Great tool for that.
The current design is RISC-like with a 12 bit word requiring 4 cycles for most instructions. I have an old version of the design specified in gate level Verilog. I should publish that. Though I'm forever tinkering with the control such that it'll probably never be done. Karnaugh maps are like Sudoku.
Oscillator can go high, but real logic is complex and requires realiability. and the fact that cheap relays are absolute crap with a ton toff spread between 3ms to 18ms! The actual clock frequency you can hope for is around 10-15 hz :(
Yes! Subroutine call is a) allocation of activation record b) switching context c) returning that combines de-alloc and switch.
while coroutines have all of these concepts separated. Why not start with a powerful and general concept and optimize for that one?
> Why not start with a powerful and general concept and optimize for that one?
As with basically everything, there are tradeoffs involved. Sometimes restrictions can be helpful for keeping things understandable, which can in turn make optimizations easier to implement. As a rather hamfisted example: completely unrestricted goto. Very general, debatably powerful, but relatively easy to use in a way that makes comprehension difficult. That same generality can also make it difficult to verify that optimizations don't change observable program semantics compared to something more restricted.
Because you can allocate the activation record on the heap, provide a way to reify continuations, and presto! now you have call/cc (and trivially implemented, no less)!
Price paid: a) you need a GC (ok, whatever, sure, you have one), b) well, the performance hit of having to GC activation records (you don't care; others do), c) whoops, thread-safety got much harder and maybe you can't even have threads (imagine two threads executing in the same activation record at the same time!).
leadership problem, as everywhere. old grampas that used to manually draw gears on paper now have to "strategically align" a huge corporation that has to deal with new shiny and complicated things like software and they all have zero fucking clue. at least with cars you can always try to safely stop, with planes - not so possible. this will also soon creep up there.
please add "super hard mode in germany" - you want to build new station? fill out 120423423 forms, 10 years of waiting, 35 lawsuits from NIMBY retirees, 312 lawsuits from environment protection agency, and after thats passed you run out of money or baloon your initial budget 10x.
Pft. Dublin's first underground metro (you could maybe vaguely argue that the surface-level/elevated DART is a metro-alike; it fits into the same not-quite-commuter-rail category as an S-Bahn) just finally got its railway order (planning permission), 24 years after it was first proposed and 17 years after the first application (though the south surface portion will not be built, as it would have required the closure of like three level crossings of the existing tram line that it would have used, and enough people complained that they gave up). All going well, it will be done around 2035, but realistically there will probably be a judicial review or two which will knock it back to 2040. All this is assuming that there isn't another recession; if there is funding will of course immediately be withdrawn.
Laughs in American. You can do all of that and one Karen who lives 300 miles from the project site and who has time to attend a 10am meeting on a random Tuesday gets the whole thing shut down.
Sorry for absolute tangential rant, but what the fuck is happening to our world. What is there actually to do besides quietly observe the insanity that is happening around? Prepare for things to get worse? Is there any other action that a normal citizen can take to actively make things better, besides the usual „go vote for X every Y years“?
Don't know; have been working through this myself. I'm not proposing ignoring reality; I'm proposing deliberately avoiding propaganda hoses. It's a tough problem.
I know this: Reading the 690th article on Charlie Kirk or whatever other emotion and violence-driven content they are all pumping isn't the way.
I struggle with this because its not just propaganda what the president says or lies about matters and to ignore seems to be at our peril. I agree its a tough problem. Wasn't even thinking about the Charlie Kirk tbh tragedy he was murder, but also shame his funeral was weaponized for political gain. I think it reaffirms that this idea though all propaganda even if ignore becomes a constituent member of the fabric of reality because it has an effect. Every time an Anti-vax idea is espoused by the president is another chip at some future childs life. If they actually revoke the ability to vaccinate its not just the children and grandchild of the people cheering Trump who will suffer its just children in general.
Honestly, log off the internet and touch grass. Things have always been like this, and most things that happen are inconsequential to your average person.
Like, who cares if he says Tylenol is bad for pregnant women? Just do whatever you want to do anyways.
The point of the article addresses this. A directive on Tylenol like this then gives pretext to dramatically reduce vaccine access, which affects everyone.
Blaming Tylenol is actually a surprisingly harmless and almost a relief. Remember it used to be vaccines until a few days ago. Antivax sentiment is not inconsequential to the average person. Gun rights are not inconsequential to the average person. Women rights are not inconsequential to the average person.
I get that some progressive arguments seem to be only relevant to particular audiences - "why should I care about trans rights if I'm not trans?" - but reality is these are a small portion of the actual discussions which take a disproportionate amount of atention from issues that do affect everyone.
I get my blood pressure to dangerous levels each time I stumble upon some high quality video lectures on youtube that explain some topics that were totally fucked in university, like PID control. 30 Minute video made by some amateur with cool animations explains basically 95% of everything you need to know vs old lifeless dork professor at "elite" university mumbling some nonsense and throwing walls of formulas with zero context, explanation or examples to help you understand. And in the end, your uni knowledge is at most 5% applicable in your work, you are still totally unprepared to enter the workforce and your first employer carries the burden to teach you.
> throwing walls of formulas with zero context, explanation or examples
This rings so true for me. Lot of teachers has this ass backwards style of teaching where they will come up with final formula like deus-ex machina. Why? To buy his text book where it is explained the way he wants it.
You can summarize years or even centuries of research into a some digestible steps with length of less than a average lesson. Months of research does not mean that I need to read your whole research journal from start to finish to understand what research was about and what it reached.
But that often expects that the person explaining a thing knows what they are talking about. I.e. people on high school does not like logarithms because they don't understand what it is for. I would bet that's because teachers themselves have absolutely 0 clue what in essence is a logarithm and why did it came to be. It was centuries of research, which you can summarize with one sentence - to make multiplication as simple as addition with lookup tables, because at 15th century they did not have calculators so multiplication was a hard laborious process. 135+265 is simple. 135*265 is difficult.
My experience is the opposite. The 30 Minute videos often give a very hollow outline of a subject, but fail to integrate it into any context. Almost always the formulas are more useful than the false intuitions you get from fancy animations.
> old lifeless dork professor at "elite" university mumbling some nonsense and throwing walls of formulas with zero context
"Oh, you have a PhD in Chemistry? I hated orgo in college..." I heard it often enough to suspect some kind of a collusion. But no, there is no collusion, just old crummy dudes gatekeeping knowledge to preserve their status, and the departments allowing them to do so.
reply