3 ms·

I've been hearing experienced programmers opine for a long time that while is the more natural representation of repetitive tasks. Twelve years ago my oldest w

by brlewis 16y ago

I've been hearing experienced programmers opine for a long time that while is the more natural representation of repetitive tasks. Twelve years ago my oldest was learning to walk upstairs. I watched her say "up", go up one stair, then say "up" again, and go up the next stair. This concrete example of recursively calling the "up" function did more to convince me that recursion is natural than any explanation with abstract words like "keep doing the same thing". >As soon as they figure out that for and while loops are sufficient to express all the programming ideas they can come up with, they won't want to learn anything else. This is contrary to my firsthand experience. As a teenager, I did BASIC programming. I had a magazine (printed on paper; I'm dating myself) with a BASIC program listing that generated mazes. I could not wrap my head around what that program was doing. At some point my parents bought me FORTH, which does have recursion. That was sufficiently expressive for me to understand how to generate a maze, and even write the program myself without an example. Yes, it's possible to express any programming idea with loops, but many ideas are much more easily expressed with recursion.

Cushman 16y ago
As pointed out in your parent, that still seems like a loop— wouldn't recursion have been your daughter saying "climb the stairs" before each step?
- brlewis 16y ago
  She was too young for sentences. For her, "up" was not some standard library function she could call from a loop. It was the very procedure she was in the middle of defining. (define (up) (and (stair-in-front-of-me) (walk stair) (up)))
  - Cushman 16y ago
    That's certainly a way of representing it. But surely it's equivalent in practice (as long as the next step can't be a nested flight of stairs) to the iterative approach: while there are stairs in front of me climb one stair I guess it's just not as clear to me as it is to you that the "up" utterance is associated with the "climb the stairs" procedure rather than the "climb one stair" procedure.
    - brlewis 16y ago
      I agree that it's equivalent in practice; both programs could compile to the same machine code. Where it's different is the human thinking represented by the two programs. The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. It's a conceptually simpler program, up until the point we use that fancy mathematical r-word to describe it.
      - Cushman 16y ago
        You're still talking about state, yes? In either case you see a flight of stairs, you start executing "climb the stairs" and that continues until you are no longer climbing stairs. It seems to me that "climb one stair as long as there are stairs" is a conceptually simpler definition than "climb one stair and then climb the stairs if there are still stairs." I think my point still is I don't see how you're differentiating between these procedures in your daughter's mind— why you're assuming that "up" means "I need to climb all of these stairs" rather than "I need to climb this one stair in front of me." (If indeed it makes sense to model human behavior either way at all; it probably makes the most sense to think of it more as an event loop...)
      - dkarl 16y ago
        The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. I disagree. The word "while" does connote time, but it's just the word chosen by early programmers to describe a process of performing an action immediately depending on current conditions, with no knowledge of history. Recursion amounts to the same thing -- after you make the mental leap of a tail-recursive optimization. When you climb the next step, you're climbing it because it's part of the definition of climbing the rest of the steps, which was part of the definition of climbing the rest of the steps when you were on the previous step. As I pointed out in another comment, when you're climbing the last step of a twelve-step staircase, you're actually performing twelve "climb up the steps" operations that are nested like Russian dolls. Thinking recursively is only simple when you learn to mentally simplify all of that, basically to think in terms of the "same machine code" you mention in your comment. I don't think we arrive at that "machine code" starting from a recursive definition of climbing the stairs. It seems much more likely that we figure out the implementation (the while loop) long before we figure out (if we ever do) that we can derive that implementation from a recursive definition of the task.
dkarl 16y ago
Both iteration and recursion result in repeated operations. Either way you define the operation of going up a flight of stairs, it's going to involve going "up" a step over and over again, so there's no way to know which way your kid was thinking just from the fact that she said "up" over and over again. In the "while" scenario, the higher-level function "up the staircase" is done once and the lower-level function "up the next step" is performed many times to accomplish it. In the recursive scenario, "up the stairs" is defined in terms of "up the stairs." Climbing the last step is "up the stairs" and it is also part of the "up the stairs" operation of climbing the last two steps, which is part of the "up the stairs" operation of climbing the last three steps. So if your kid was thinking recursively, the last "up" operation would be part of the first "up" operation and also part of every intervening "up" operation. If you asked your kid on the last step of a twelve-step staircase how many "up" she was doing, she presumably wouldn't answer "twelve;" she would answer "one." Would that be because she performed the obvious optimization of a tail-recursive function, or because she wasn't actually thinking recursively?
- brlewis 16y ago
  Thinking recusively doesn't necessitate a mental model of the stack. See pg's comment.
  - dkarl 16y ago
    Obviously not -- recursion isn't limited to computing. However, nested meanings is inherent in recursive definitions because recursion means defining something in terms of itself. If you come up with a recursive idea that happens to be amenable to tail-call optimization, then you will be able to forget about the nesting, but that only happens through work or luck. Forgetting about the nesting is an implementation hack. Consider the classic example of the Von Neumann ordinals: 0 = {} n + 1 = n ∪ {n} 3 = 2 ∪ {2} = 1 ∪ {1} ∪ {1 ∪ {1}} etc. Or even consider the most natural definition of the factorial function, which is not tail-recursive either: f(1) = 1 f(n+1) = (n+1) * f(n) As the factorial function illustrates, the most natural recursive definition is often not tail-recursive. If you're trying to turn a recursive function into a form that can be efficiently executed as a computer program, you often have to transform the function into a form that is amenable to tail-call optimization. That's something that only programmers care about, though. Or, perhaps, programmers and babies. If you believe that people naturally conceive of recursive ideas, then what happens when their ideas aren't easily transformed to a tail-recursive form? Is that why babies cry all the time? Perhaps by the time we are small children we have learned to subconsciously discard all recursive ideas that we can't transform into a tail-recursive form? If there is a part of my brain that naturally generates tail-recursive solutions to problems but won't plague me with frustrating non-tail-recursive solutions, I would love to tap into it.

by brlewis 16y ago

Cushman 16y ago

As pointed out in your parent, that still seems like a loop— wouldn't recursion have been your daughter saying "climb the stairs" before each step?

brlewis 16y ago
She was too young for sentences. For her, "up" was not some standard library function she could call from a loop. It was the very procedure she was in the middle of defining. (define (up) (and (stair-in-front-of-me) (walk stair) (up)))
- Cushman 16y ago
  That's certainly a way of representing it. But surely it's equivalent in practice (as long as the next step can't be a nested flight of stairs) to the iterative approach: while there are stairs in front of me climb one stair I guess it's just not as clear to me as it is to you that the "up" utterance is associated with the "climb the stairs" procedure rather than the "climb one stair" procedure.
  - brlewis 16y ago
    I agree that it's equivalent in practice; both programs could compile to the same machine code. Where it's different is the human thinking represented by the two programs. The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. It's a conceptually simpler program, up until the point we use that fancy mathematical r-word to describe it.
    - Cushman 16y ago
      You're still talking about state, yes? In either case you see a flight of stairs, you start executing "climb the stairs" and that continues until you are no longer climbing stairs. It seems to me that "climb one stair as long as there are stairs" is a conceptually simpler definition than "climb one stair and then climb the stairs if there are still stairs." I think my point still is I don't see how you're differentiating between these procedures in your daughter's mind— why you're assuming that "up" means "I need to climb all of these stairs" rather than "I need to climb this one stair in front of me." (If indeed it makes sense to model human behavior either way at all; it probably makes the most sense to think of it more as an event loop...)
    - dkarl 16y ago
      The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. I disagree. The word "while" does connote time, but it's just the word chosen by early programmers to describe a process of performing an action immediately depending on current conditions, with no knowledge of history. Recursion amounts to the same thing -- after you make the mental leap of a tail-recursive optimization. When you climb the next step, you're climbing it because it's part of the definition of climbing the rest of the steps, which was part of the definition of climbing the rest of the steps when you were on the previous step. As I pointed out in another comment, when you're climbing the last step of a twelve-step staircase, you're actually performing twelve "climb up the steps" operations that are nested like Russian dolls. Thinking recursively is only simple when you learn to mentally simplify all of that, basically to think in terms of the "same machine code" you mention in your comment. I don't think we arrive at that "machine code" starting from a recursive definition of climbing the stairs. It seems much more likely that we figure out the implementation (the while loop) long before we figure out (if we ever do) that we can derive that implementation from a recursive definition of the task.

dkarl 16y ago

Both iteration and recursion result in repeated operations. Either way you define the operation of going up a flight of stairs, it's going to involve going "up" a step over and over again, so there's no way to know which way your kid was thinking just from the fact that she said "up" over and over again. In the "while" scenario, the higher-level function "up the staircase" is done once and the lower-level function "up the next step" is performed many times to accomplish it. In the recursive scenario, "up the stairs" is defined in terms of "up the stairs." Climbing the last step is "up the stairs" and it is also part of the "up the stairs" operation of climbing the last two steps, which is part of the "up the stairs" operation of climbing the last three steps. So if your kid was thinking recursively, the last "up" operation would be part of the first "up" operation and also part of every intervening "up" operation. If you asked your kid on the last step of a twelve-step staircase how many "up" she was doing, she presumably wouldn't answer "twelve;" she would answer "one." Would that be because she performed the obvious optimization of a tail-recursive function, or because she wasn't actually thinking recursively?

brlewis 16y ago
Thinking recusively doesn't necessitate a mental model of the stack. See pg's comment.
- dkarl 16y ago
  Obviously not -- recursion isn't limited to computing. However, nested meanings is inherent in recursive definitions because recursion means defining something in terms of itself. If you come up with a recursive idea that happens to be amenable to tail-call optimization, then you will be able to forget about the nesting, but that only happens through work or luck. Forgetting about the nesting is an implementation hack. Consider the classic example of the Von Neumann ordinals: 0 = {} n + 1 = n ∪ {n} 3 = 2 ∪ {2} = 1 ∪ {1} ∪ {1 ∪ {1}} etc. Or even consider the most natural definition of the factorial function, which is not tail-recursive either: f(1) = 1 f(n+1) = (n+1) * f(n) As the factorial function illustrates, the most natural recursive definition is often not tail-recursive. If you're trying to turn a recursive function into a form that can be efficiently executed as a computer program, you often have to transform the function into a form that is amenable to tail-call optimization. That's something that only programmers care about, though. Or, perhaps, programmers and babies. If you believe that people naturally conceive of recursive ideas, then what happens when their ideas aren't easily transformed to a tail-recursive form? Is that why babies cry all the time? Perhaps by the time we are small children we have learned to subconsciously discard all recursive ideas that we can't transform into a tail-recursive form? If there is a part of my brain that naturally generates tail-recursive solutions to problems but won't plague me with frustrating non-tail-recursive solutions, I would love to tap into it.