One simple question I've never been able to answer is, "why use 'for', 'while', and 'if' as control statements?"

Could someone please elucidate the rationale behind using the above mentioned control statements, that have been embraced by most, if not all, high-level languages. I believe this has something to do with automata theory, but I'm generally uncertain.

  • $\begingroup$ Because you often need to do things more than once, and only do things if some condition holds? That seems to be the completely obvious answer to the question I think you're asking. So have I misunderstood your question? $\endgroup$ Feb 10 '18 at 10:04
  • $\begingroup$ No, you seem to understand the question, but why am I using those control statements across different languages? Can computation be simplified to, doing "things more than once, and only do things if some condition holds"? $\endgroup$
    – XYZandMe
    Feb 10 '18 at 10:22
  • $\begingroup$ You use them across different langauges because they're useful for programming, regardless of what language you're using. To a large extent, yes, computation can be simplified in the way you suggest: essentially, you can simulate a Turing machine using only a repeat loop (repeat... until I reach the halting state), conditionals (if I see this character in this state, do that) and reading/writing memory. $\endgroup$ Feb 10 '18 at 10:27
  • $\begingroup$ @XYZandMe Where do you see the difference between "only do things if some condition holds" and "if / else"? Where do you see the difference between "things more than once" and for / while / repeat loops? $\endgroup$
    – gnasher729
    Feb 10 '18 at 13:57

From computability theory, we know that a programming language which only contains terminating programs (say, without loops and recursion) is strictly less powerful than a Turing machine (or any other Turing-complete programming languages).

So, if we want a programming language $P$ which is able to express, say, a Python interpreter, a JVM implementation, or even an interpreter for $P$ itself, we need a language having some sort of unbounded loop / recursion.

Technically, if we have a while loop, we no longer need if, since

if condition then cTrue else cFalse

is equivalent to

branchTaken = false
while condition and !branchTaken do
   branchTaken = true
while !condition and !branchTaken do
   branchTaken = true

where branchTaken is an otherwise unused boolean variable. But this is terribly inconvenient to use in practice! So, programming languages tend to include if, even if not strictly needed.

Now, about while (ans similar unbounded loops). We said that we need some construct for unbounded looping/recursion. Why while, then?

Well, recursion alone suffices, but it is not very convenient in imperative programming. Note that, by contrast, functional programming languages typically do not have any while loop, and only exploit recursion -- in functional programming, recursion is far more natural and convenient, especially if the language is pure (without side effects) and a WHILE loop would be pointless, since we can not mutate variables.

Most widespread imperative programming languages use while or similar loops. In principle, they could instead use if+goto, which have the same power. However, practice showed that goto often led to code which was very hard to read and modify. Dijkstra wrote his famous letter "GOTO considered harmful", advocating for using structured programming (while and friends) instead. One of the scientific motivations behind this, is that to properly reason about a while loop we need to think about a loop invariant. This is already quite hard, in general. In a goto-using program, we need an invariant for every label/line number which is being targeted by some goto. This is much harder, in general, since many gotos may point to the same label, so the invariant must take into account the multiple "incoming" points. A solution for this could be using goto in a more disciplined way, but if we do, we'll probably end up in using while (or another loop) under a different notation.

  • 1
    $\begingroup$ @DavidRicherby Thanks, I tried to rephrase. (If you think it's still misleading, please let me know.) $\endgroup$
    – chi
    Feb 10 '18 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.