8

I have this teacher, he's quite smart (sometimes, haha) he said good programmers try to use while loops instead of for loops. the reason he gave for this is because while loops can be proven, as in, one can completely explain what happens in a while loop whereas you can't do that for a for loop. he also said something about NASA programmers only using while loops and not allowed to do for loops because of this.

I have quite a hard time understand this, for both loops one can explain how they work in detail right? for both you would always know what is going to happen?

can someone explain to me why while loops can be proven (And because of it, might be better than for loops, in some cases at least).

EDIT:
maybe he was reffering to:
2: All loops must have a fixed upper bound. It must be trivially possible for a checking tool to statically prove that a preset upper bound on the number of iterations of a loop cannot be exceeded. If the loop-bound cannot be proven statically, the rule is considered violated.

Though this still doesn't say anything about the difference between while and for loops.

  • 17
    Your teacher is either completely wrong, or you have misreported what he said somehow. This rationale for preferring for over while simply makes no sense. There may be one, but this isn't it. – Kilian Foth Apr 21 '15 at 6:52
  • 7
    I agree with Kilian. It makes no sense that there should be a difference, as for (init; test; step) { body } has a trivial desugaring to while: {init; while (test) { step; body }}. – user7043 Apr 21 '15 at 6:59
  • 1
    For(;;) { cout<<"they're really not that different" <<endl;} . The biggest difference is that for loops let you easily keep a variable (i) at the scope of the loop. – Nathan Cooper Apr 21 '15 at 7:00
  • 2
    @MikeNakis on the contrary. A cargo culter wouldn't ask the question, just perpetuating myths. Perhaps even punishing others for not "adhering to the rule". – sehe Apr 21 '15 at 8:55
  • 2
    @MikeNakis I don't know whether we have enough information to assess the mentaility of the teacher. – sehe Apr 21 '15 at 8:57
13

In a nutshell: What your teacher probably meant is that the semantics of while is pretty much the same in most languages, while the semantics of for may change considerably (see discussion below). Hence, abstract language independent proof are more reliable with a while, but one should be careful that a proof with a for loop may not match the semantics of the for loop in many languages.

Your question is not precise enough (though that may not be your fault).

The point is that, afaik, there is no official, ISO supported standard, or otherwise officially accepted reference definition of for and while loops. The definition depends on the programming language.

Hence you cannot make any general statement regarding their equivalence before you have defined precisely what each can do. I adress that more precisely, since it is one of the main argument used in other answers (and the discussion will be useful in what follows).

On intertranslatability of for and while loops

Summary: it depends on the programming language, but is always possible a long as you can have one infinite loop and a way to get out of it.

But you can make such a statement for a specific programming language, and the answer will depend on the features fo the language.

That also means that there is no general proof, but only one for each programming language.

One thing that is generally true is that a while loop can generally mimic a for loop, because the while loop can do the exit condition testing of the for loop, doing the initialisation of the control variable with an assignment before entering the loop, and doing the incrementation at the end of the loop body, so that

for i from 1 by 2 to 10 do { xxx }

becomes

i=1
while i≤11 do { xxx; i←i+2 }

This more or less works for most languages, but it is not as obvious as it seem, and there may be many "details" to worry about.

For example, in many languages, the for loop evaluates it 3 arguments (initial value, increment, and final value) as strict arguments, evaluated once before entering the loop, while others will take then as thunk arguments to be reevaluated at each turn, or possibly as lazy argument to be evaluated only when first needed.

Another point may be that the increment variable may be local to the for loop, or have to be a local variable of the function where the loop appears.

Depending on such issues, the translation of a for to a while may vary widely, though it is usually possible to achieve it.

The same holds for the converse, thranslating a while into a for loop.

Th first problem is that a while loop will always reevaluate the exit condition at each turn. But some for loops do not provide for a condition that is reevaluated at each turn, other than comparison of the control variable with some fixed value computed on loop entry. Then the translation is not possible unless there is some other mean to jump out of the loop on some arbitrary conditions.

That is achievable with various devices, usually starting with a conditional statement testing the condition, followed by an a jump out implemented, as available, by a loop exit statement, a return statement (after encapsulating the loop in a function), a goto statement or an exception raising.

In other words, it is again very dependent on languages, and possibly on subtle features of languages.

This say, as answered by @milleniumbug, the intertranslation is easy in the language C, because a for lopp is essentially a while loop plus some extra for an incremented control variable.

But this does not necessarily apply to other languages, and most likely not in the same way.

This being said, programming languages are usually supposed to have Turing power with only one of these loops, since all you need for it is one infinite loop. So, as long as you have some way of looping for ever, and possibly deciding to stop, you are pretty sure you can mimic any other construct ... but not necessarily easily.

Regarding proofs

Summary: There is no reason known to me to assert that proofs should be significantly harder with one or the other (unless some weird feature of the language).

There is probably a misunderstanding, or your teacher had his mind on something else.

Formals semantics can be defined for the various kinds of loops defined in programming languages, and then used for proving properties.

It may be, again depending on the language, that conducting formal proofs regarding programs may be more complex in some cases. But that depends on the language.

I cannot imagine a reason why proofs should be significantly harder with one construct more than with the other. The for loop may be more complex since it can offer, as in C, all that is done with a while plus other things. But if you did it with a while, you would have to add the extras in some other form.

I could use the formal general argument of intertranslatability, as long as there is the possibility for a single infinite loop. I will however refrain from doing that, as the constructions involved are nothing you want to deal with in a proof, and it would clearly be an unfair statement, at least in practice.

Following the above discussion, however, we have seen that the difficulties for intertranslatability come from the great variability of the for loop from language to language. Hence the following conclusion which is probably the right answer:

One possibility to understand your teacher's statement is that the semantics of the while loop is pretty much the same in all programming languages, while the syntax and semantics of the for loop can vary significantly from language to language. Hence, it is possible to make general "abstract" proofs with while loops that have language independent semantics to a good extent, while this is not possible for the for loop that has syntax and semantics changing too much from language to language. But this does not apply within a given language, when the semantics of both are precisely defined.

My best suggestion is that you should ask your teacher what he precisely meant, and whether he can give you an example. Misphrasing or misunderstanding is a common event.

  • 1
    @VincentAdvocaat Well, the site is for all users, no just the Original Poster of the question. That is why I did it. I also flagged my own answer for the moderator to stop it if improper. Actually it was an interesting question, and it took me some time to reach my conclusion ... hoping it is the right one. Let us know if you find out. – babou Apr 21 '15 at 13:01
  • I only just noticed the edit you made an hour ago adding what you state in your answer here, this is indeed the best possible answer to my question and I thank you for it. What moderator attention is concerned, it is more my fault for creating a duplicate amongst multiple SE sites. So for that I see no reason to delete this answer, if anything should be delted it would have to be the 2nd question I asked, but since your answer there is well formulated and explains the statement made here in depth i do not think it wise to remove either one. unless you add the information to this question. – Vincent Apr 21 '15 at 13:22
  • 1
    I have no idea, strange things happen, always fun when people don't explain any reasons for this. – Vincent Apr 22 '15 at 9:58
  • 3
    Happened again: 1 up + 1 down. What bothers me is that it is hurting the site more than myself. I try to write complete answers that help people. If it is at fault, it would be wiser to comment to give me an opportunity to correct. If it is some other reason, it just reduces attractiveness of an answer that might be useful, at the site expense. I am wondering whether replacing with the extended answer, or removing the disclaimer at the end, has anything to do with it. But the moderator seemed ok with the situation. – babou Apr 22 '15 at 14:40
  • 1
    As a moderator I like your answer and I learned something from reading it. It is a good answer – maple_shaft Apr 22 '15 at 22:51
12

In the C language you can rewrite every for loop to an equivalent while loop and vice versa.

while -> for transformation:

Rewrite

while(condition) { instructions; }

to

for(; condition; ) { instructions; }

for -> while transformation:

This is slightly more complicated, especially if you have continue statement in your loop.

Rewrite:

for(init; condition; next) { instructions; }

to:

{
    init;
    while(condition)
    {
        instructions;
    next_label:
        next;
    }
}

but replace every continue; statement with goto next_label; statement. If condition is a null instruction, replace it with true.

As you can see, in C language neither is more "provable" (whatever that means) than the other, since even if one of the loop was, you could rewrite it in terms of another loop.

Now, there exist other languages where this while <-> for equivalency doesn't exist. For example, in Pascal, you can assume more about the for loop. This means that you can't express every concept when writing a for loop, but you can prove more about the flow of the code:

for i:=1 to n do
    instructions;

Here, the n is saved at the beginning of the loop, so changes to n don't make any influence on iteration count, and you can't modify i in the body of the loop. This means you can trivially prove this loop will eventually end (as n is finite, and you can't modify i).

  • Rewriting some "for" loops as "while" loops would require code duplication, adding flags, or adding goto. If one adds flags, all other loops can be emulated using a single "while(1)..." around a function which runs until a "return"; if one adds "goto", all other loops can be emulated using that. – supercat Jul 25 '16 at 16:14
  • Thanks for proving my point. Copy-pasting the code fragment A doesn't change my ability to reason about it. – milleniumbug Jul 25 '16 at 16:43
  • Indeed, copy/paste doesn't change one's ability to reason about code, but it is IMHO an important reason not to regard "for" as a superfluous language construct, since one of the design goals of a good programming language should be to minimize the need for copy/paste. – supercat Jul 25 '16 at 17:13
7

In Floyd-Hoare logic, the most common formal system for reasoning about the correctness of computer programs, there is the while rule.

In words, if you have a guard clause (the expression in brackets in the while()), a variant function (an expression with discrete values that can be shown to decrease monotonically each time the loop runs, and always be positive), and a loop invariant (a logic statement that is always true before and after every time the loop runs), you can prove that the while loop will finish (because the variant function can't keep decreasing) and that eventually the guard clause will be false and the loop invariant be true.

Floyd-Hoare logic doesn't have rules for for loops or whatever constructs actual languages may have.

However, as other answers explain, for loops can always be written in terms of while loops. That means that they can be reasoned about, it just takes a little more work.

If your teacher had courses at university where he had to provide correctness proofs of his programs, he probably wrote programs using only while loops. I know I did. And once you are used to thinking in terms of guards and variant functions and loop invariants, they seem very natural. Overusing while loops is a habit you see with CS graduates, I had to learn to stop doing that in my first months as a professional developer.

Somewhere down the line, your teacher misremembered all this as "good programmers use while loops", whereas what really happens is more like "some CS graduates turn their correctness proof habits into practical programming habits".

  • This seems to be quite consistent with my own assessment, though based on a different view. Floyd-Hoare logic had no reason to consider the for loop, which has no fixed definition and is more complex, without being formally necessary. – babou Apr 22 '15 at 14:48
3

Actually, in some sense, the exact opposite is true.

A language with only for-loops is not Turing-complete, it can only compute the primitive-recursive functions, not all Turing-computable functions. Since all computation in a language with only for-loops always terminates, the Halting Problem and all the other Decidability Problems based upon it, simply don't arise, so it is possible to mechanically decide many more static properties of programs than in a language with while-loops.

OTOH, a language with only natural numbers, a single variable, and while-loops is Turing-complete, and so it is not possible to decide even the simplest of properties: will this program return a result?

  • 1
    A for-only language can produce while-equivalent behavior by decrementing the loop variable (assuming the language allows it) during iterations which aren't supposed to result in a termination. (E.g., for n in 1 to 2 { if condition then n := n-1 }) – Blrfl Apr 22 '15 at 11:11
  • There are many ways in which a for loop can be made to loop for ever, depending of course on its definition in the language at hand. And one infinite loop is enough for Turing completeness. – babou Apr 22 '15 at 14:53
  • @babou: The most common interpretation of a for loop is a loop that iterates over a finite range or collection. Of course, in many languages you can hack a for loop to behave like a while loop, but I think that's not what Jörg had in mind. – Giorgio Apr 25 '15 at 9:03
0

I would like to say that in reality, there is no difference .Your question is irrelevant. May be your teacher might have meant to use while-loop when no. of iterations is not known beforehand.In many cases we need to use a while loop to extract digits of a no. when the user enters the no. which can be of any length. Technically speaking, the similarity between for & while loop is that both are entry-controlled loops wherein the (test-expression/condition) is evaluted before entering into the loop body.This is the distinction between while & do-while loops.

-1

It likely comes from early C programming where, by todays norms, loops were widely abused and misused, especially the conditional being modified. As programmers started to understand the effect certain programming styles had, the abuse and misuse of loop conditionals fell out of favor, and the statement, while (arguably) once valid, no longer holds any truth.

The statement holds absolutely no truth if you look solely at the language definition and syntax and ignore how it was being used.

The statement itself does however offer a valuable lesson to anyone who wants to understand it, its history and why its no longer considered true. - Whats the expression about learning, mistakes and repeating them.....

-10

Your teacher is correct!

The reason is the following is valid C

for (int x = 1 ; x < 20 ; x++ ) {
   x = x + 9;
}

You cannot guarantee the condition variables have not been tampered with!

  • 2
    How does that make while loops fare better here? – milleniumbug Apr 21 '15 at 9:25
  • 7
    Oh yeah? Whereas, with while loops you can actually guarantee that the condition variable has not been tampered with? In fact, tampering with the condition variable is the only way to break out of a while loop! I usually refrain from downvoting stuff, but for this answer, I shall make an exception. – Mike Nakis Apr 21 '15 at 9:25
  • James could you perhaps elaborate why this is less of an issue for while loops, you might be on to something however people seem to disagree for a lac of counter evidence in the case of while loops – Vincent Apr 21 '15 at 9:31
  • 1
    @VincentAdvocaat I'd say that with a while loop you expect the condition variable to be tampered with in some way, whereas a for loop you expect it to be changed only in the step part of the for loop construct itself. This principle of least astonishment is more important than many realise in programming. – gbjbaanb Apr 21 '15 at 9:42
  • 3
    @gbjbaanb true, but as far as the question is concerned, it is a far cry from principle of least astonishment to provability. – Mike Nakis Apr 21 '15 at 10:19

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.