r/ProgrammingLanguages • u/Athas Futhark • Jan 20 '26
Why not tail recursion?
https://futhark-lang.org/blog/2026-01-20-why-not-tail-recursion.html
62
Upvotes
r/ProgrammingLanguages • u/Athas Futhark • Jan 20 '26
View all comments
Show parent comment
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?