6 ms·

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 g

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." https://tinyletter.com/programmingphilosophy/letters/i-don-t-like-to-crack-an-egg-with-a-sledgehammer https://tinyletter.com/programmingphilosophy/letters/i-don-t...

pjmlp 11y ago
> For example, they always terminate. How do you terminate? for(;;) { }
- meggar 11y ago
  break;
  - pjmlp 11y ago
    Not all programming languages have break; C syntax was just an example. Also break is no different from using return (to keep C syntax as example) when recursing. If you guard break with if then you also need to prove if the "if" condition does indeed provide a dataflow path to break.
    - AnimalMuppet 11y ago
      > If you guard break with if then you also need to prove if the "if" condition does indeed provide a dataflow path to break. In all cases, for all possible inputs. On the other hand, if that's what your for loop looks like, you probably have the same problem of proving that your recursion terminates (in all cases, for all possible inputs).
      - pjmlp 11y ago
        Of course, I was just arguing against the OP that all loops terminate.
nilved 11y ago
Loops aren't any safer than recursion. A loop is a special case of recursion and is just as susceptible to the halting problem.
mafribe 11y ago
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.
- mafribe 11y ago
  Why is this being down-voted? Could somebody please explain why they think what I wrote is wrong? I'd be happy to learn something new about loops and recursion.
  - conceit 11y ago
    Wasn't me, but it's probably because iterative loops are believed to be easier to reason about. OTOH the recursive definition for the Fibonacci or factorial numbers seem easier, for one because they map to the literal explanation.
    - mafribe 11y ago
      iterative loops are believed to be easier to reason about. This cannot be the case, because you can translate loops into recursion and vice versa, so every reasoning problem that one finds with loops is also a problem in reasoning about recursion and vice versa. If you look at the Hoare-logic rules this shows up clearly. In both case you need a suitably invariant, and you need a termination argument.
      - conceit 11y ago
        Does the translation come for free? If not, it's probably complicated to reason about.
- 11y ago
nbevans 11y ago
Dijkstra was from a different era from when mutable state wasn't frowned upon. Note to self: This may not go down well here but I'm willing to take the flack.
- rer0tsaz 11y ago
  He actually discusses it a bit in the previous paragraph, which does not seem to be online anywhere: > When programming languages emerged, the "dynamic" nature of the assignment statement did not seem to fit too well into the "static" nature of traditional mathematics. For lack of an adequate theory mathematicians did not feel to easy about it, and, because it is the repetitive construct that creates the need for assignment to variables, mathematicians did not feel to easy about repetition either. When programming languages without assignments and without repetition --such as pure LISP-- were developed many felt greatly relieved. They were back on familiar grounds and saw a glimmer of hope of making programming an activity with a firm and respectable mathematical basis. (Up to this very day there is among the more theoretically inclined computing scientists still a widespread feeling that recursive programs "come more naturally" than repetitive ones.) Continued https://tinyletter.com/programmingphilosophy/letters/i-don-t-like-to-crack-an-egg-with-a-sledgehammer https://tinyletter.com/programmingphilosophy/letters/i-don-t...
  - douche 11y ago
    I've always felt that imperative programming is more in line with the way the overwhelming majority of people are exposed to algorithmic instructions; cookbooks, furniture instructions, Lego construction, driving directions, pick-your-own-adventure books, etc. Especially given how piss-poor most mathematics instruction is, unless you happen to be a mathematician and have put in the effort to recast your brain along those lines, it's easier to come to grips with the imperative style vs more mathematically inspired paradigms.
  - nbevans 11y ago
    I wasn't slighting Dijkstra but merely commenting on the era of the time. You can for example see how primitive things were back then by describing "mutable state" as "dynamic" and "immutable" as "static". Dynamic and static these days have entirely different connotations typically more associated with type systems. Things have moved on and now in 2016 mutable state is increasingly being pushed out of codebases in favour of immutable practices. Recursion is (and always has been) one way of doing that. :)
_pmf_ 11y ago
> For example, they always terminate. No. In fact, it's a huge problem in imperative code at all layers.
chriswarbo 11y ago
> 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!

pjmlp 11y ago

> For example, they always terminate. How do you terminate? for(;;) { }

meggar 11y ago
break;
- pjmlp 11y ago
  Not all programming languages have break; C syntax was just an example. Also break is no different from using return (to keep C syntax as example) when recursing. If you guard break with if then you also need to prove if the "if" condition does indeed provide a dataflow path to break.
  - AnimalMuppet 11y ago
    > If you guard break with if then you also need to prove if the "if" condition does indeed provide a dataflow path to break. In all cases, for all possible inputs. On the other hand, if that's what your for loop looks like, you probably have the same problem of proving that your recursion terminates (in all cases, for all possible inputs).
    - pjmlp 11y ago
      Of course, I was just arguing against the OP that all loops terminate.

nilved 11y ago

Loops aren't any safer than recursion. A loop is a special case of recursion and is just as susceptible to the halting problem.

mafribe 11y ago

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.

mafribe 11y ago
Why is this being down-voted? Could somebody please explain why they think what I wrote is wrong? I'd be happy to learn something new about loops and recursion.
- conceit 11y ago
  Wasn't me, but it's probably because iterative loops are believed to be easier to reason about. OTOH the recursive definition for the Fibonacci or factorial numbers seem easier, for one because they map to the literal explanation.
  - mafribe 11y ago
    iterative loops are believed to be easier to reason about. This cannot be the case, because you can translate loops into recursion and vice versa, so every reasoning problem that one finds with loops is also a problem in reasoning about recursion and vice versa. If you look at the Hoare-logic rules this shows up clearly. In both case you need a suitably invariant, and you need a termination argument.
    - conceit 11y ago
      Does the translation come for free? If not, it's probably complicated to reason about.
11y ago

nbevans 11y ago

Dijkstra was from a different era from when mutable state wasn't frowned upon. Note to self: This may not go down well here but I'm willing to take the flack.

rer0tsaz 11y ago
He actually discusses it a bit in the previous paragraph, which does not seem to be online anywhere: > When programming languages emerged, the "dynamic" nature of the assignment statement did not seem to fit too well into the "static" nature of traditional mathematics. For lack of an adequate theory mathematicians did not feel to easy about it, and, because it is the repetitive construct that creates the need for assignment to variables, mathematicians did not feel to easy about repetition either. When programming languages without assignments and without repetition --such as pure LISP-- were developed many felt greatly relieved. They were back on familiar grounds and saw a glimmer of hope of making programming an activity with a firm and respectable mathematical basis. (Up to this very day there is among the more theoretically inclined computing scientists still a widespread feeling that recursive programs "come more naturally" than repetitive ones.) Continued https://tinyletter.com/programmingphilosophy/letters/i-don-t-like-to-crack-an-egg-with-a-sledgehammer https://tinyletter.com/programmingphilosophy/letters/i-don-t...
- douche 11y ago
  I've always felt that imperative programming is more in line with the way the overwhelming majority of people are exposed to algorithmic instructions; cookbooks, furniture instructions, Lego construction, driving directions, pick-your-own-adventure books, etc. Especially given how piss-poor most mathematics instruction is, unless you happen to be a mathematician and have put in the effort to recast your brain along those lines, it's easier to come to grips with the imperative style vs more mathematically inspired paradigms.
- nbevans 11y ago
  I wasn't slighting Dijkstra but merely commenting on the era of the time. You can for example see how primitive things were back then by describing "mutable state" as "dynamic" and "immutable" as "static". Dynamic and static these days have entirely different connotations typically more associated with type systems. Things have moved on and now in 2016 mutable state is increasingly being pushed out of codebases in favour of immutable practices. Recursion is (and always has been) one way of doing that. :)

_pmf_ 11y ago

> For example, they always terminate. No. In fact, it's a huge problem in imperative code at all layers.

chriswarbo 11y ago

> 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!