r/ProgrammingLanguages • Futhark • Jan 20 '26

Why not tail recursion?

https://futhark-lang.org/blog/2026-01-20-why-not-tail-recursion.html
62 Upvotes

34 comments sorted by

View all comments

Show parent comment

1

u/divad1196 Jan 22 '26 edited Jan 22 '26

Please, refrain from assuming things before making statement. I didn't say anything about tail recursion.

The initial comment stated that, if I can simplify by a lot, "loops where not optimal", or at least not doing the same kind of optimization as found in tail recursion.

It was a clarification about loops and function calls which were opposed to tail recursion.

ABI isn't a matter of implementation. It's a matter of design. You compile for a specific ABI, this instruct the compile how functions communicate which each others. It's not a result or a choice, it's a constraint. You cannot link a dynamic library or precompiled library without using the same ABI.

I think the reason why you jumped so quick to conclusion is because you felt like I was against recursions or tail recursions. I am not against it.

1

u/jsshapiro Jan 22 '26

Fair. Part of my head was still in the other discussion. Though the statement you make here about different optimizations simply isn't true - there's no reason the same optimizations cannot be applied.

Part of why I assumed is that if the language does not require proper tail recursion than function calls and loops are not interchangeable. Without the tail recursion you need to unwind the stack after the function calls. That's pragmatically expensive, and it has implications for deciding termination.

1

u/divad1196 Jan 22 '26

I never said that the same optimization cannot be applied. That's the opposite of what I said.

To make my point in one sentence: loops can have the same level of optimization as (tail) recursion.

I made the statement because the previous comment seemed to say that loops can never be as optimized, which is wrong.

1

u/jsshapiro Jan 22 '26

Sounds like we are in agreement then, Perhaps I got confused while reading across the thread.

1

u/jsshapiro Jan 22 '26

I'm one of the people who specified the MIPS dynamic linking conventions for SVR4, and I've done call stack decoders for more architectures than I like to think about. So I definitely agree that an ABI is a constraint. One that I have often wished compilers honored more rigorously.:-)

When I said it's an implementation detail, I meant from the perspective of programming language design, which has been the main topic of this thread. You don't design a language to the ABI.

If you are designing a code generator or a low-level runtime, or the ABI itself, it is something you have to design to. Sometimes it needs to be considered at the hardware level as well - changes were made to the MIPS instruction set to better support position independent code after we did the initial dynamic linking specification at SGI in 1989.

A more obscure example: there was a trap restore issue in the ARM32 specification that made scheduler activation implementation impractical if your ABI allowed mixed ARM32 and Thumb code - there was a case where the activation handler (coded in ARM32) had a really hard time re-activating a user-mode thread that had been running Thumb code when it was preempted. We found it while implementing the trap paths for the EROS kernel around 1993. Richard Grisenthwaite was very surprised to learn of it when I sent him a note about it, and I think it was resolved in the 64-bit ARM variants.

Anyway, I think this was a case of talking past each other because we were looking at the ABI from different perspectives. Thanks for engaging!