6 ms·

Kinda off topic. And a kinda crazy hypothetical: I would really like to see a production language, where program-stack based recursion was a compile time error

Kinda off topic. And a kinda crazy hypothetical: I would really like to see a production language, where program-stack based recursion was a compile time error. Instead, only recursion as syntax sugar is allowed. i.e. Only recursion (or any cyclic function call graph) that the compiler can translate to "imperative code", should be allowed to compile. For two reasons: 1. I honestly dream of a world where we can no longer think about infinitely propagating program-stacks. 2. It would force us to invent better optimization algorithms (like tail-call optimization) but for more general recursive patterns.

buzzybee 10y ago
Oh, I do believe this was attempted with Algol 60. And there's an article on what happened. It turns out to be (possibly mathematically) unfeasible as there are many ways to sneak it in. [0] https://news.ycombinator.com/item?id=10131664 https://news.ycombinator.com/item?id=10131664
crimsonalucard 10y ago
I'm sure it can be done. The compiler just needs to manually create a stack as a variable rather than use the call stack.
- colorint 10y ago
  You also need the iterative structure to support continuations. Of course, if you do all that---you've just reimplemented function calls.
dreamcompiler 10y ago
You're talking about continuation-passing style, which makes stacks superfluous. It's a mind-blowing idea. But it's also a royal pain to write code directly this way, so some compilers convert to continuations under the sheets.
- yazaddaruvala 10y ago
  Its crazy that this idea was invented in 1975[0], and I haven't heard of it, even after: - 4 years of self learned programming - 4 years of university for computer engineering - 5 years in the industry, as a software engineer [0] https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style
  - dreamcompiler 10y ago
    There are two very different (yet of course functionally equivalent) paradigms for general computation: Turing Machines and Lambda Calculus (Turing vs. Church). All schools teach TMs but not all teach LC. Which is a shame, because some wonderful insights like Functional Programming and Lisp and CPS come mostly from the LC paradigm.

buzzybee 10y ago

Oh, I do believe this was attempted with Algol 60. And there's an article on what happened. It turns out to be (possibly mathematically) unfeasible as there are many ways to sneak it in. [0] https://news.ycombinator.com/item?id=10131664 https://news.ycombinator.com/item?id=10131664

crimsonalucard 10y ago

I'm sure it can be done. The compiler just needs to manually create a stack as a variable rather than use the call stack.

colorint 10y ago
You also need the iterative structure to support continuations. Of course, if you do all that---you've just reimplemented function calls.

dreamcompiler 10y ago

You're talking about continuation-passing style, which makes stacks superfluous. It's a mind-blowing idea. But it's also a royal pain to write code directly this way, so some compilers convert to continuations under the sheets.

yazaddaruvala 10y ago
Its crazy that this idea was invented in 1975[0], and I haven't heard of it, even after: - 4 years of self learned programming - 4 years of university for computer engineering - 5 years in the industry, as a software engineer [0] https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style
- dreamcompiler 10y ago
  There are two very different (yet of course functionally equivalent) paradigms for general computation: Turing Machines and Lambda Calculus (Turing vs. Church). All schools teach TMs but not all teach LC. Which is a shame, because some wonderful insights like Functional Programming and Lisp and CPS come mostly from the LC paradigm.