Re:Thinking About Recursion
by dreamcompiler on Thursday March 09, 2017 @12:57AM
(#13827319)
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.
Re:Thinking About Recursion
by yazaddaruvala on Thursday March 09, 2017 @09:23PM
(#13835818)
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
Re:Thinking About Recursion
by dreamcompiler on Tuesday March 14, 2017 @08:40PM
(#13872906)
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.
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.
Re:Thinking About Recursion
by crimsonalucard on Wednesday March 08, 2017 @06:25PM
(#13824988)
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.
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.