7 ms·

Particularly interesting to me: Embedded recursion is much harder than tail recursion. This reminds me of the difficulty of central embedding vs tail embedding

Particularly interesting to me: 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.

pierrebai 2y ago
... or simply that the LOGO language syntax and choice of commands is confusing? Without formal explanation, how surprising is it really that a child would assume that STOP mean stop? 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. [1] https://esolangs.org/wiki/Brainfuck https://esolangs.org/wiki/Brainfuck
- dmurray 2y ago
  But STOP does mean stop. Stop executing this subroutine. 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.
antonvs 2y ago
It’s not clear whether these results would generalize much beyond Logo. Reading the part which starts with “To understand how recursive procedures work in Logo one must know:” makes Logo recursive procedures sound pretty terrible - typical ad-hoc language design.
- hnlmorg 2y ago
  Logo is ostensibly a LISP, so the syntax might seem a bit alien to modern developers used to C-style braces or ALGOL-style declarations.
  - antonvs 2y ago
    The issue here seems to be specifically that it's a Lisp with dynamic scoping, which allows the statement I quoted in another comment to hold: > "[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.
- andybak 2y ago
  What part? It's confusingly explained but this sounds like how nearly every other language behaves.
  - antonvs 2y ago
    This: > 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.
    - Jensson 2y ago
unconed 2y ago
It seems the children's model is BASIC-like in that a function call is just equivalent to "GOTO <#LINE>", and that the program state is just the line number currently being executed. 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.
- aidenn0 2y ago
  > 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. 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.
  - Someone 2y ago
    Nitpick: the call stack is an implementation detail. It is a way to implement call frames. 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/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-21.html#%_idx_3040 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/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-31.html#%_idx_5560 https://mitp-content-server.mit.edu/books/content/sectbyfn/b...)
    - aidenn0 2y ago
taneq 2y ago
> Embedded recursion is much harder than tail recursion. 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.
- jrochkind1 2y ago
  I mean it's a non-obvious-to-me interesting finding though that people understood "loop expressed as tail-end recursion" as easily loop expressed as loop though! Like it's not obvious to me that their semantic equivalence would be obvious to a beginner! 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.
  - sitkack 2y ago
    I think recursion in the tail position makes sense because "you have to go somewhere", it is just another place to go. Recursion in the middle is like starting over, so they might think of it as a weird jump. 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). :)

pierrebai 2y ago

... or simply that the LOGO language syntax and choice of commands is confusing? Without formal explanation, how surprising is it really that a child would assume that STOP mean stop? 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. [1] https://esolangs.org/wiki/Brainfuck https://esolangs.org/wiki/Brainfuck

dmurray 2y ago
But STOP does mean stop. Stop executing this subroutine. 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.

antonvs 2y ago

It’s not clear whether these results would generalize much beyond Logo. Reading the part which starts with “To understand how recursive procedures work in Logo one must know:” makes Logo recursive procedures sound pretty terrible - typical ad-hoc language design.

hnlmorg 2y ago
Logo is ostensibly a LISP, so the syntax might seem a bit alien to modern developers used to C-style braces or ALGOL-style declarations.
- antonvs 2y ago
  The issue here seems to be specifically that it's a Lisp with dynamic scoping, which allows the statement I quoted in another comment to hold: > "[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.
andybak 2y ago
What part? It's confusingly explained but this sounds like how nearly every other language behaves.
- antonvs 2y ago
  This: > 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.
  - Jensson 2y ago

unconed 2y ago

It seems the children's model is BASIC-like in that a function call is just equivalent to "GOTO <#LINE>", and that the program state is just the line number currently being executed. 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.

aidenn0 2y ago
> 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. 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.
- Someone 2y ago
  Nitpick: the call stack is an implementation detail. It is a way to implement call frames. 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/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-21.html#%_idx_3040 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/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-31.html#%_idx_5560 https://mitp-content-server.mit.edu/books/content/sectbyfn/b...)
  - aidenn0 2y ago

taneq 2y ago

> Embedded recursion is much harder than tail recursion. 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.

jrochkind1 2y ago
I mean it's a non-obvious-to-me interesting finding though that people understood "loop expressed as tail-end recursion" as easily loop expressed as loop though! Like it's not obvious to me that their semantic equivalence would be obvious to a beginner! 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.
- sitkack 2y ago
  I think recursion in the tail position makes sense because "you have to go somewhere", it is just another place to go. Recursion in the middle is like starting over, so they might think of it as a weird jump. 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). :)