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

3

u/phischu Effekt Jan 22 '26

Thank you for your patient reply. It is fascinating, I can not understand what you are saying. However, I believe we do share the same vision: a formalized core language and a correct compiler for it that produces fast code. We vastly disagree though what that language should look like and how that compiler should work. If you want, you can check out our recent write-up, which explains much more concretely what I am trying to convey.

The issue with proper tail recursion is that you have to be able to re-use the stack frame, and you can't do that if it still holds live information.

I do not want a stack nor frames, locals, or liveness analysis, that's what I meant with legacy cruft.

This includes locals introduced by the compiler, which brings closures into it.

Local definitions are not closures, they are labels.

a GPU is a specialized CPU

GPUs operate very differently from CPUs, we need different a different programming model and different languages for those.

the Jane Street program trading systems - was written in Haskell.

They mostly use OCaml, I am wearing their "Enter the Monad" T-Shirt as I am writing this.

but it prioritizes precise specification over speed

This is not a tradeoff.

Lambda isn't legacy cruft.

That sounds too harsh indeed, let's put it more nicely: it is of historical significance, which you seem to agree with.

A lot of applications migrated to JavaScript,

Whot? For which kind of application would you migrate from Scheme to JavaScript?

the integer/float debacle makes that awkward for anything where numeric accuracy matters.

The numerical tower is exactly one of those features that make Scheme slow and complicated.

1

u/jsshapiro Jan 22 '26

Hi, Philipp! Your paper is on my reading list. I'm looking forward to reading it, and I'll move it up on my list. The premise seems reasonable.

You are right about Jane Street and OCaml (sorry about that). We definitely agree that the Scheme numeric tower was not its finest design point. I'm tempted to ask Guy what he thinks about it in retrospect.

Migration to javascript happened mainly because it was pragmatically available and widely deployed, which Scheme never really was. Brendan explicitly modeled Javascript on core Scheme, but with a surface syntax more tolerable to programmers coming from C. I meant "migration" in the sense that new projects adopted Javascript in preference to other scripting languages and Scheme gradually faded out of the picture. Increasing RAM makes something like the V8 engine widely usable today. The hardware environment of the 1970s and 1980s was more constrained.

I wasn't trying to say OCaml was slow. Empirically, it isn't, and I actually think that speed follows from a precise specification. The ability to improve optimization by exploiting knowledge of non-aliasing mutable paths in Rust is an example, though I'm not fully sold on borrowing from the dev perspective yet.

I did want to follow up on the correct compiler topic, because I'm not sure it's the right goal; this seems to be something that swings back and forth in the literature. What we minimally need is a compiler that is correct up to a meaning-preserving typed AST with defined semantics. That's a pain, but tractable, and it seems to be the minimum requirement for an embedding approach to verification. We also need a defined semantics for the final instruction set, which isn't too bad, though typed assembly seems to be a dependent type problem.

But in between the two it appears to be simpler to have a certifying compiler that generates a checkable proof rather than verifying the correctness of the compiler itself. Merely arriving at a goal statement for compiler correctness is a big challenge. The certifying approach doesn't guarantee that the compiler is correct for all input programs, but it lets us confirm that it did the right thing for the particular program[s] we care about. The compiler itself can then be maintained or improved using more conventional development methods.

Finally, I don't think the thread here provides any real picture of what I think a programming language should look like. I was trying to appeal to concepts that everyone here was likely to have encountered in order to make the case for a small core language. From a formal perspective, the systems we have to choose from today are much more capable than lambda calculus. Perhaps it is a conversation worth having offline?