This is a prime example of the conflict between the "machine model" of programming (a computer is a large and elaborate state machine that advances instruction by instruction) and the "maths model" (by reasoning from a set of axioms and rules of production we can transform information or prove facts).
The former maps onto imperative programming, and the latter onto functional programming. It seems that different people find these models harder or easier to understand - and then get confused when not everyone sees it that way.
I think this POV is limiting. In my experience, many people who take the "maths model" respect and use the "machine model" quite often as well.
The formal term of note here is "denotation" in that "a language may be understood through its denotation" as an abstract machine or as a mathematical object. The best understanding comes from recognizing that many denotations may be valid for a language and that great richness comes from this. To work, the denotations must be in alignment in various ways and when they are it means that you can transport understanding from one denotation to another to the language itself.
So I don't think there's an honest conflict, though I imagine there are programmers and PL experts who either (a) honestly only ever use one denotation or (b) play favorites and this may lead to some clouding of things.
Yes, you can use both, but look at all the disputation of preference going on elsewhere in this thread - that's what I meant by a conflict.
I like your phrase "transport understanding"; an important part of programming is dealing with informal understandings of what the software does or is intended to do. Most programming has very little formal reasoning in.
I'm not sure I can agree. The original post makes the point that you can see recursion in multiple ways, including machine-oriented (e.g. using a stack and stack pointer) and abstract, e.g. using an axiomatisation of self-reference, for example using the Y combinator which satisfies YM = M(YM).
Incidentally, stacks can also be given an axiomatic treatment indepented of concrete machine models.
I think that the confuse comes from the fact that one wants to mix both views; after all, I don't remember see anyone being confused bu the classic recursive definitions (Fibonacci, factorial) in my school days. IIRC the factorial function is introduced in high school. It can literally be understood by a kid.
I believe the reason why people want to expose both views at the same time is that the math view doesn't really explains "how it works" as far as CS is concerned.
As far as I'm concerned, I can't imagine programming without the knowledge of how things work at assembly level. I think I would feel so crippled in my understanding that I would want to learn about assembly... again. I would probably not stand working with a machine that works on magic.
> I can't imagine programming without the knowledge of how things work at assembly level.
The author's point is that recursion is a pervasive concept that is essential to understand even how modern computer hardware works:
> the very concept of a digital computer is grounded in recursive self-reference (the cross-connection of gates to form a latch), which, needless to say, does not involve a stack. Not only do real programmers use recursion, there could not even be programmers were it not for that.
The author is not suggesting that we forget about "what's really going on". He's rightly pointing out that you actually cannot understand what's really going on at all without first understanding recursive self-reference.
Bingo. Recursion is easy in the func^H^H^H^H"application-oriented programming" model of computing where the whole program is a mathematical expression written out in tree form on a blackboard, and applying a function means erasing a node that says (fib 8) and replacing it with a node that says (+ (fib 7) (fib 6)), and eventually with one that says 21. But most programmers, most of the time, seem to use a different mental model, one of functions as little actors that send function-call messages to each other and themselves, including when they are doing "functional programming" (and ofc mutable state and performance considerations tend to push the language into this model anyway). The problem is that in an actors-ish model continuations are easy, while recursion and function-call behaviour in general are hard, derived concepts built on top of continuations.
So I've come to think that introductions to programming should usually look something like this:
Stage 1: Teach "application-oriented programming": functional programming that's explicitly, and exclusively, about substituting expressions in an expression tree.
Stage 2: Teach how to program using only simple "dataflow" models of stateless (or stateful) actors that reliably pass messages (ie. call continuations) to each other in parallel. (To prepare for stage 3 you'll need to cover "dynamic dataflow" with actors passing around the capabilities to call other actors, but it's also a good opportunity to probe what can reasonably be done with a static graph of calling capabilities.)
Stage 3: If the students are led to push the Stage 2 programming models hard enough they'll naturally see that a lot of the code they write for those models (but NOT all of it) really wants to be able to take advantage of an explicit function-call abstraction. Teach them how to implement the Stage 1 language as a DSL inside a Stage 2 language.
Almost as an incidental benefit the students will end up understanding call/cc, too. By contrast, it's the attempt to blur these two, very different, models of computing together and handwave the distinction that leaves students confused by recursion—and they should feel confused by recursion in this case! The feeling of confusion is their intellect warning them that something is wrong. The real damage is done when they either give up, or end up feeling that they understand it when they don't.
(Another side benefit is that it's an early introduction to the huge and indispensable diversity, and yet intense inter-relatedness, of models of computing. Among other things that should hopefully temper the zeal to smash square pegs through the One True, Round Hole, and hopefully even the polar opposite vice of unthinkingly picking up whatever "the tool for the job" is supposed to be. Similarly, the order of stage 1 and stage 2 could be reversed.)
TL:DR: "Continuations are easy: functions are hard."
PS: The really fun question is how lexical scope fits into the Stage 2 model. It's a restricted case of something else...
It's interesting to use languages that do not harshly penalize recursion by imposing stack size limits. The upcoming GNU Guile 2.2 release, a Scheme implementation, has a dynamically expandable stack so algorithms that are naturally recursive can be implemented that way rather than contorted into iterative form to please the stack limit god.
For example, in Guile 2.0, this natural definition of 'map' will cause the stack to overflow on large lists:
There's no real gain here in terms of performance or readability. You trade a large stack for a large reverse operation at the end. Guile 2.2 allows a whole class of recursive algorithms that were not practical before because of the fixed size stack (like most languages I know of), and they perform well, too!
Needless to say I agree with this article. Recursion is an integral part of computing, and more programming languages should provide better support for it. Embrace it, don't avoid it!
There is a performance gain. Two primary gains: reduced memory usage (your stack size is constant, with tail-call elimination); theoretically faster execution as you don't have a cons and a return pending at the end of each iteration.
You also eliminate the function call, potentially, on the recursive call. If TCE is present, instead of a function call, the recursive step is actually just a branch (and can be an unconditional branch in many cases). Reverse can also be made efficient, as the Erlang people have done.
I will agree that the first version is clearer in illustrating the intent of the program for many people. The second one is probably just familiar for me from my time playing with Erlang, where it's the idiomatic way to write something like this.
I was under the impression that Schemes generally compile down to continuation-passing-style, and hence in the case of something like Fibonacci one of the recursive calls would be performed as a tail call, whilst the other would become part of the continuation, e.g. something like:
function fib(n, k) {
if (n == 0) k(1);
if (n == 1) k(1);
fib(n-1, function(f_1) {
fib(n-2, function(f_2) {
k(f_1 + f_2);
});
});
}
The natural recursive definition of a Fibonacci function is a different beast. The big issue with the naive and simple Fibonacci implementation is that it duplicates work, a ton of it. The 'map' above doesn't have this issue. To make Fibonacci efficient, it can be implemented as an iterative algorithm which isn't too bad to read. But there's better news! The recursive algorithm can be kept as-is, provided that the function is memoized, so that already computed values are cached.
I was thinking about this the other day too. Recursion in CS101 is taught in such a bizarre way. At least it was back when I was in CS101. It was almost as though CS tries to discourage its usage simply because "most minds cannot understand it as easily as iterative loops".
No, "they" are not. Maybe you're thinking of Software Engineering? Computer Science is supposed to teach you about the branch of mathematics called Computer Science. Recursion is a very important part of that—important enough that the need to address it early was one of the things that made Scheme an obvious choice for a teaching language for decades.
It's more readable because other programmers have been taught the imperative style too, because their teachers find it more readable, because <tail call here>.
Not enough reason in my opinion. The thing is all the people in my CS101 that couldn't fluently grasp recursion generally didn't do very well and I don't think many of them ended up working in software jobs.
Recursion, good code and readable code are not related; I don't understand this point.
Iterative loops are much easier to analyze and reason about, by humans and by computers. For example, they always terminate. To paraphrase Dijkstra, "I regard general recursion as an order of magnitude more complicated than just repetition, and I don't like to crack an egg with a sledgehammer."
Iterative loops are much easier to analyze and reason about,
This is not the case. Loops and recursion can be translated into each other, hence are of equal complexity in terms of reasoning. And you see that when you write down the Hoare-logic axioms for either.
What Dijkstra had in mind was probably simple, syntactically constrained forms of loops, like for-loops where the loop variable is read-only in the loop body. They are simpler than general recursion, sure. But there are corresponding simpler forms of recursion, e.g. primitive recursion or tail recursion that are much simpler than general recursion.
> Iterative loops are much easier to analyze and reason about, by humans and by computers. For example, they always terminate.
It's a bit of an apples-to-oranges comparison to compare (proper, bounded) for-loops to general recursion. A more appropriate question would be whether humans and computers find, say, primitive recursion or structural recursion easier to analyse and reason about than for-loops.
The difference between general- and primitive-recursion becomes very apparent when working in Coq, for example!
I never got what the problem with recursion in CS101 might be.
In Portuguese universities, by time you get to this programming issues you already had enough maths to be able to relate recursion to how mathematical proofs work.
At least it was so for me and most of my friends back in the 90's.
In what scenario do you prefer recursion over a loop? Your comment made me think of code readability and maintainability. But I'm not judging. Really curious how you manage to prefer recursion over loops.
I suppose I had trouble with recursion until I understood that each call should strive to be stateless - meaning, you don't try and remember previous results. Each new call should be just the same as the initial. You only act on the current set and try to reduce the problem further. Trying to remember previous iterations results in a lot of headaches.
> Implementing recursion does not require a stack, nor does it require any special provisions for managing the stack.
When I wanted recursion in Atari BASIC it involved implementing stacks for all my local variables (because there's not such thing as local variable in Atari BASIC).
Thinking about the task in terms of bits of work that should be put on a stack or in the queue felt way more controllable than recursion.
Once I needed to reimplement recursion in mathlab because the stack was too small, it was an interesting experience, I had a matrix-repurposed-as-stack and did all the push/pop manually while the recursion ran as a loop - goes to show that recursion isn't that essential if one knows how to split state, data and code properly.
Readit News
The former maps onto imperative programming, and the latter onto functional programming. It seems that different people find these models harder or easier to understand - and then get confused when not everyone sees it that way.
The formal term of note here is "denotation" in that "a language may be understood through its denotation" as an abstract machine or as a mathematical object. The best understanding comes from recognizing that many denotations may be valid for a language and that great richness comes from this. To work, the denotations must be in alignment in various ways and when they are it means that you can transport understanding from one denotation to another to the language itself.
So I don't think there's an honest conflict, though I imagine there are programmers and PL experts who either (a) honestly only ever use one denotation or (b) play favorites and this may lead to some clouding of things.
I like your phrase "transport understanding"; an important part of programming is dealing with informal understandings of what the software does or is intended to do. Most programming has very little formal reasoning in.
Incidentally, stacks can also be given an axiomatic treatment indepented of concrete machine models.
I believe the reason why people want to expose both views at the same time is that the math view doesn't really explains "how it works" as far as CS is concerned.
As far as I'm concerned, I can't imagine programming without the knowledge of how things work at assembly level. I think I would feel so crippled in my understanding that I would want to learn about assembly... again. I would probably not stand working with a machine that works on magic.
The author's point is that recursion is a pervasive concept that is essential to understand even how modern computer hardware works:
> the very concept of a digital computer is grounded in recursive self-reference (the cross-connection of gates to form a latch), which, needless to say, does not involve a stack. Not only do real programmers use recursion, there could not even be programmers were it not for that.
The author is not suggesting that we forget about "what's really going on". He's rightly pointing out that you actually cannot understand what's really going on at all without first understanding recursive self-reference.
So I've come to think that introductions to programming should usually look something like this:
Stage 1: Teach "application-oriented programming": functional programming that's explicitly, and exclusively, about substituting expressions in an expression tree.
Stage 2: Teach how to program using only simple "dataflow" models of stateless (or stateful) actors that reliably pass messages (ie. call continuations) to each other in parallel. (To prepare for stage 3 you'll need to cover "dynamic dataflow" with actors passing around the capabilities to call other actors, but it's also a good opportunity to probe what can reasonably be done with a static graph of calling capabilities.)
Stage 3: If the students are led to push the Stage 2 programming models hard enough they'll naturally see that a lot of the code they write for those models (but NOT all of it) really wants to be able to take advantage of an explicit function-call abstraction. Teach them how to implement the Stage 1 language as a DSL inside a Stage 2 language.
Almost as an incidental benefit the students will end up understanding call/cc, too. By contrast, it's the attempt to blur these two, very different, models of computing together and handwave the distinction that leaves students confused by recursion—and they should feel confused by recursion in this case! The feeling of confusion is their intellect warning them that something is wrong. The real damage is done when they either give up, or end up feeling that they understand it when they don't.
(Another side benefit is that it's an early introduction to the huge and indispensable diversity, and yet intense inter-relatedness, of models of computing. Among other things that should hopefully temper the zeal to smash square pegs through the One True, Round Hole, and hopefully even the polar opposite vice of unthinkingly picking up whatever "the tool for the job" is supposed to be. Similarly, the order of stage 1 and stage 2 could be reversed.)
TL:DR: "Continuations are easy: functions are hard."
PS: The really fun question is how lexical scope fits into the Stage 2 model. It's a restricted case of something else...
For example, in Guile 2.0, this natural definition of 'map' will cause the stack to overflow on large lists:
The iterative solution is to construct the list backwards and reverse it as a final step: There's no real gain here in terms of performance or readability. You trade a large stack for a large reverse operation at the end. Guile 2.2 allows a whole class of recursive algorithms that were not practical before because of the fixed size stack (like most languages I know of), and they perform well, too!Needless to say I agree with this article. Recursion is an integral part of computing, and more programming languages should provide better support for it. Embrace it, don't avoid it!
You also eliminate the function call, potentially, on the recursive call. If TCE is present, instead of a function call, the recursive step is actually just a branch (and can be an unconditional branch in many cases). Reverse can also be made efficient, as the Erlang people have done.
I will agree that the first version is clearer in illustrating the intent of the program for many people. The second one is probably just familiar for me from my time playing with Erlang, where it's the idiomatic way to write something like this.
Wouldn't that be enough reason? They're supposed to teach you how to write good code, and that includes readable code.
Recursion, good code and readable code are not related; I don't understand this point.
https://tinyletter.com/programmingphilosophy/letters/i-don-t...
Note to self: This may not go down well here but I'm willing to take the flack.
How do you terminate?
What Dijkstra had in mind was probably simple, syntactically constrained forms of loops, like for-loops where the loop variable is read-only in the loop body. They are simpler than general recursion, sure. But there are corresponding simpler forms of recursion, e.g. primitive recursion or tail recursion that are much simpler than general recursion.
It's a bit of an apples-to-oranges comparison to compare (proper, bounded) for-loops to general recursion. A more appropriate question would be whether humans and computers find, say, primitive recursion or structural recursion easier to analyse and reason about than for-loops.
The difference between general- and primitive-recursion becomes very apparent when working in Coq, for example!
No. In fact, it's a huge problem in imperative code at all layers.
In Portuguese universities, by time you get to this programming issues you already had enough maths to be able to relate recursion to how mathematical proofs work.
At least it was so for me and most of my friends back in the 90's.
Often I find subtle bugs in my loops where as with recursion the compiler seems to pick them up for me.
Deleted Comment
Deleted Comment
When I wanted recursion in Atari BASIC it involved implementing stacks for all my local variables (because there's not such thing as local variable in Atari BASIC).
Thinking about the task in terms of bits of work that should be put on a stack or in the queue felt way more controllable than recursion.
But you need to know what a stack is - because it gives you the practical depth to which you can recurse. Ditto with tail recursion optimization.
And that is why C should be mandatory. You must be able to translate the mathematical concepts into something real and tangible.