In interviewing candidates, I have found recursion a consistent source of issue. One of the interview questions involves a piece of code that is broken because it does not have a proper termination check, and, while, it does not stump all candidates, it does give most of them a hard time. Many can understand that the code is wrong but struggle in explaining why it is wrong. And many have trouble fixing it without trying to rewrite it in terms of a loop (which makes the solution, IMO, significantly complicated). On top of that, many people I have met seem to view identifying and solving the problem as impressive, something that they would not actually expect anyone to be able to do.
I don’t think it’s the education system broken, or something like that. I think the tools most developers are exposed to simply don’t value recursion as a way to solve problems. They make it expensive and thus non-idiomatic, so many people are simply not exposed to it.
Good read, but the message about the stack being a distracting detail seems a bit off to me.
Perhaps this is just my background showing a bias–I cut my teeth on C and C++–but I’m rather convinced that the existence of a stack isn’t something to be glossed over: it is a fundamental law of computing in languages that allow direct access to memory and that run on architectures similar to what we have today.
In languages that don’t have those things, I think it is reasonable to omit discussion of a stack. Javascript, Java, and the delightful Lisps either don’t expose that memory directly or don’t execute as one would expect, so the existence of a stack is immaterial. In a systems language like C (and everyone should be at least passingly conversant in C) the stack is something to be aware of if you ever want to write safe or clever code (hint: how do varargs work in C?).
What harms people is when they are thrown stacks without explanation. Like, doing basic assembly in a contrived language with a register machine, both with and without stacks, is enough to convince one both of the benefits and the drawbacks of using stacks (why did I just lose like half my registers? ah, okay, worth it.).
Otherwise, a good if somewhat theoretical article.
While it’s valuable to learn about a stack in the context of a language like C, I do not believe C requires a stack in any way. In fact, last time I read it, the C standard never used to word stack. So transforming a C program to CPS would be completely valid, unless someone knows better. But from a “understanding the system” perspective, a stack is useful to be aware of. In defense of the article, I think if you consider the more general concept of recursion, such as a recursive data structure (linked list, for example), recursion clearly does not require a stack at all to explain.
I believe that the semantic machine model C targets pretty much requires a stack, though I may well be wrong.
I agree that the general concept of recursion is useful and does not require a stack–that said, there is a nontrivial conceptual leap between knowing about recursion and implementing recursion, and that should be covered by folks seriously trying to treat it.
Remember, it was a near thing that we even ended up with recursion in mainstream languages.
I believe that the semantic machine model C targets pretty much requires a stack, though I may well be wrong.
I’m nearly 100% certain they don’t. A CPS compiler for C would be perfectly valid. The only funny case I can think of is setjmp and longjmp, but even those have a pretty clear meaning in CPS.
Why would varargs require a stack? Aren’t they just packing some data into a sequence of bytes and unpacking it? The API itself makes no reference to a stack (assuming you mean stdarg).
To expand on my claim a bit more, since I’ve had time to think a bit more: stdarg requires a calling convention in order to work, but I don’t believe that calling convention requires something like a stack.
Well, strictly speaking (and why I brought up varargs in the first place), is that any calling convention talks about what order things are pushed onto the stack and whether the caller or callee is responsible for cleaning things up. Then again, there are example of args being passed solely in registers, which are obviously not stacks.
In interviewing candidates, I have found recursion a consistent source of issue. One of the interview questions involves a piece of code that is broken because it does not have a proper termination check, and, while, it does not stump all candidates, it does give most of them a hard time. Many can understand that the code is wrong but struggle in explaining why it is wrong. And many have trouble fixing it without trying to rewrite it in terms of a loop (which makes the solution, IMO, significantly complicated). On top of that, many people I have met seem to view identifying and solving the problem as impressive, something that they would not actually expect anyone to be able to do.
I don’t think it’s the education system broken, or something like that. I think the tools most developers are exposed to simply don’t value recursion as a way to solve problems. They make it expensive and thus non-idiomatic, so many people are simply not exposed to it.
Good read, but the message about the stack being a distracting detail seems a bit off to me.
Perhaps this is just my background showing a bias–I cut my teeth on C and C++–but I’m rather convinced that the existence of a stack isn’t something to be glossed over: it is a fundamental law of computing in languages that allow direct access to memory and that run on architectures similar to what we have today.
In languages that don’t have those things, I think it is reasonable to omit discussion of a stack. Javascript, Java, and the delightful Lisps either don’t expose that memory directly or don’t execute as one would expect, so the existence of a stack is immaterial. In a systems language like C (and everyone should be at least passingly conversant in C) the stack is something to be aware of if you ever want to write safe or clever code (hint: how do varargs work in C?).
What harms people is when they are thrown stacks without explanation. Like, doing basic assembly in a contrived language with a register machine, both with and without stacks, is enough to convince one both of the benefits and the drawbacks of using stacks (why did I just lose like half my registers? ah, okay, worth it.).
Otherwise, a good if somewhat theoretical article.
While it’s valuable to learn about a stack in the context of a language like C, I do not believe C requires a stack in any way. In fact, last time I read it, the C standard never used to word stack. So transforming a C program to CPS would be completely valid, unless someone knows better. But from a “understanding the system” perspective, a stack is useful to be aware of. In defense of the article, I think if you consider the more general concept of recursion, such as a recursive data structure (linked list, for example), recursion clearly does not require a stack at all to explain.
I believe that the semantic machine model C targets pretty much requires a stack, though I may well be wrong.
I agree that the general concept of recursion is useful and does not require a stack–that said, there is a nontrivial conceptual leap between knowing about recursion and implementing recursion, and that should be covered by folks seriously trying to treat it.
Remember, it was a near thing that we even ended up with recursion in mainstream languages.
I’m nearly 100% certain they don’t. A CPS compiler for C would be perfectly valid. The only funny case I can think of is
setjmpandlongjmp, but even those have a pretty clear meaning in CPS.Varargs?
Why would varargs require a stack? Aren’t they just packing some data into a sequence of bytes and unpacking it? The API itself makes no reference to a stack (assuming you mean
stdarg).Hm, interesting point.
To expand on my claim a bit more, since I’ve had time to think a bit more:
stdargrequires a calling convention in order to work, but I don’t believe that calling convention requires something like a stack.Well, strictly speaking (and why I brought up varargs in the first place), is that any calling convention talks about what order things are pushed onto the stack and whether the caller or callee is responsible for cleaning things up. Then again, there are example of args being passed solely in registers, which are obviously not stacks.