Children's mental models of recursive LOGO programs (1985)
telearn.hal.science
telearn.hal.science
Embedded recursion is much harder than tail recursion. This reminds me of the difficulty of central embedding vs tail embedding in linguistics.
Level 3: tail recursion program (:SIDE = 80) TO SHAPEB :SIDE IF :SIDE = 20 STOP REPEAT 4 [FORWARD :SIDE RIGHT 90] RIGHT 90 FORWARD :SIDE LEFT 90 SHAPEB :SIDE/2 END Level 4: embedded recursion program (:SIDE = 80) TO SHAPEC :SIDE IF :SIDE = 10 STOP SHAPEC :SIDE/2 REPEAT 4 [FORWARD :SIDE RIGHT 90] RIGHT 90 FORWARD :SIDE LEFT 90 END
> Mental model of embedded recursion as looping - The children were fundamentally misled by thinking of recursion as looping. While this mental model is adequate for active tail recursion, it will not do for embedded recursion.
> programming constructs often do not allow mapping between meanings of natural language terms and programming language uses of those terms. Neither STOP or END stop or end, but pass control back. The reason that this is important for the Logo novice is that when their mental model of recursion as looping fails, they have no way of inferring from the syntax of recursion in Logo how flow of control does work. So they keep their inadequate looping theory, based on their successful experience with it for tail recursion, or blame discrepancies between their predictions and the program's outcomes on mysterious entities such as numbers, or the "demon" inside the language itself.
> Beyond mistaken mental models about recursion, we have found these to involve atomistic thinking about how programs work, assigning intentionality and negotiability of meaning as in the case of human conversations to lines of programming code, and application of natural language semantics to programming commands.
The part that is missing is the stack. So I wonder what would happen if you let them step through while showing the stack state at every point. This would clue them in immediately that there is nested control flow.
The part about alternative explanations is funny but just reflects the fact that there is an element of the language not reflected in the code, that they can't just reify visually (unlike the instruction counter).
That is, the kid who inferred that there was an invisible "demon"... was right.
>The part that is missing is the stack.
Bingo. Function-call-as-GOTO and not knowing about the stack are the root cause of so many confused questions on beginner programming forums. You can spot it a mile away because they tend to write functions without any parameters or return values. Instead, they pass information around by mutating global state everywhere. It's difficult to fit the idea of parameters and return values into a mental world that doesn't include a call stack, so their absence in novice code isn't surprising.
A friend in college (Aerospace major) took an intro to programming course in C, and was calling main() to get back to the menu at the start of his program instead of using any sort of loop. Was so confused why he had to choose "quit" from the menu a whole bunch of times before it would actually exit.
>Why is this important? As I read the book (and if you read my notes, you know where this is going) I started to notice something in the wording and tone. The further I progressed the more I became convinced of it, and I think it explains how he managed to mangle the explanation of C pointers so badly.
>I don’t think he understands the call stack.
[...]
>Suppose you’re used to writing BASIC for small memory electronic devices and you learn about C. You read about pointers and realize something: it’s possible to write a subroutine that can change variables without knowing their names. It’s manna from heaven! You don’t have to devote global variables to being the “parameters” of your subroutines anymore. Life is great.
>This is the mindset I think Traister had and never got past.
I saw so many of my peers needlessly confused by a pedagogy that insists that the call stack is an implementation detail and thus does not belong in a CS class.
Because that implementation doesn’t handle functions returning closures that depend on the call frame, something that is very common in modern languages, I think we should teach call frames first.
Starting with a call stack makes understanding how closures work later unnecessarily hard.
That also is what SICP does. It starts with call frames in chapter 3 (https://mitp-content-server.mit.edu/books/content/sectbyfn/b...) and only in chapter 5 introduces stack frames when discussing how to implement recursion on register machines (https://mitp-content-server.mit.edu/books/content/sectbyfn/b...)
Sorry, I was unclear that it was the second half of the implication I disagreed with. I never had the pleasure of a SICP based class, but I did eventually learn the concept of closures (though never in a CS class). Many of my peers were flummoxed by recursion and I personally believe that intentionally avoiding discussion of a call stack was poor pedagogy (possibly because I leaned on my understanding of it when I first learned recursion) that unnecessarily caused people to drop out long before they would ever encounter closures.
> Because that implementation doesn’t handle functions returning closures that depend on the call frame, something that is very common in modern languages, I think we should teach call frames first.
I guess I'm showing my age. Pascal, C, C++ and Java (which at the time lacked not only closures, but also generics) were the only languages I encountered in my CS classes (there was an optional upper-level survey of languages class that I didn't take). I will, however, stand by my general sentiment that there are a large class of people that learn better by learning a concrete example and then generalize to the abstract, and those students were poorly served by the pedagogy I encountered.
I try not to introduce them too early because lots of concepts at once gets frustrating - but eventually you get to a point where it clearly would save stress to be able to step and inspect state.
> Seven children (two girls and five boys, eleven- to twelve-years-old) in their second year of Logo programming participated in the study. The children were highly motivated to learn Logo programming, and had averaged over fifty hours of classroom programming time under the supervision of experienced classroom teachers knowledgeable in the Logo language, who followed the "discovery" logo pedagogy set out by Papert [3]. All seven children had received instruction in iteration and recursion, and had demonstrated in their classroom programming that they could use iteration and recursion in some contexts
To those who don't get what "discovery" method implies, it is proposed by Seymour Papert, a pioneer of computer pedagogy, based on the constructionist theory of learning. It posits that students learn best when they are actively engaged in constructing their own knowledge and understanding through the creation of personally meaningful artifacts or projects. They would be on their own, writing programs with minimal guidance, developing their own intuitive understanding of how programs operate.
I don't know what was Papert's intention, as I never read his book Mindstorms in full, but from what I read, I think 20% probability he believed that the "stack" concept would be discovered by children, and 80% probability he believed that children should be allowed to discover concepts on their own, even if they "misunderstand" the nature of computer programming, because there is no nature, except what we construct of them, and so there is nothing to "misunderstand". He is a radical constructivist in pedagogy.
Notably, in the study, the children were receiving instructions (though what kind of instruction, the authors didn't say). It was discovered that pure discovery learning is extremely inefficient, and so most actual discovery learning programs were not "pure", but included extensive instruction, or guidance. See for example Mayer, R. E. (2004). Should There Be a Three-Strikes Rule Against Pure Discovery Learning? American Psychologist, 59(1), 14–19.
I actually was thinking of adding this study somewhere in my post on the Perceptron Controversy, but don't have a good place to place it.
https://yuxi-liu-wired.github.io/essays/posts/perceptron-con...
Tail-end recursion is just a way to express a loop. Yes, true recursion is much harder to get your head around than a loop. The fact that the loop is expressed as tail-end recursion doesn't change the basic fact that loops=easy, recursion=headache.
I don't remember finding tail-recursion easier to learn than embedded recursion -- I do recall it being very confusing for me to learn at first either way, but I can't recall exactly what was in my head then, or how it was taught to me! It was a long time ago. But I remember finding it tough to understand.
I'd love to teach kids to program, so many minds to run (ethical) metacognitive experiments on! Once you understand recursion, you never go back (and with tail recursion you don't have to). :)
> "[calling a procedure] acts to insert all lines of the named procedure into the executing program at the point where the call occurred"
But that notoriously has its own issues - the various variants of the funarg problem, which were essentially solved by switching to lexical scope.
> this acts to insert all lines of the named procedure into the executing program at the point where the call occurred
...is quite dubious, perhaps it works in Logo, but in many languages it would raise scoping issues at the very least. Procedures calls are not in general the equivalent of textually cutting and pasting the procedure's code. Given that Logo has dynamic scoping, perhaps it works - but that's an issue in itself, dynamic scoping is hard to reason about in general.
print_x() {
print(x);
}
foo(msg) {
let x = msg;
print_x();
}
main() {
let x = "Hello!";
print_x();
foo("Goodbye!");
print_x();
}
Hello!
Goodbye!
Hello!
I'd bet that if LOGO had used RETURN, like many other languages, then the children's reasoning would be likely be more accurate. Or go the other way and make them tell you what this or that brainfuck[1] program does. So, to me, this research says more about LOGO choices than anything.
If the program were instead (as a set of commands for a person, not a turtle) START WALKING; STOP; START CLAPPING; STOP; ... any child would understand what was intended. It would be more confusing if the first STOP here meant "stop all program execution, never proceed to the next step".
So the problem isn't STOP, it's the fact that there's more program to execute, hidden in the call stack.