markh@csd4.milw.wisc.edu (Mark William Hopkins) (02/04/89)
In article <6224@paris.ics.uci.edu> Doug Schmidt <schmidt@blanche.ics.uci.edu> writes: > ... can't both a while loop and a for loop be replaced by an if statement > and a goto? Yes. But a more appropriate means to define the while loop is via an equational specification: The while loop WHILE B DO S END is the fixed point solution, x, to the equation: x = IF B THEN S; x END Therefore, the loop is a special form of recursion, known as tail-recursion. It can be simulated by a parameterless recursively-called procedure (with equal efficiency when compiled by a self-respecting compiler). The same goes for C's for loop (in terms of which its while loop can be reduced): while (B) S; = for (; B; ) S; = for (; B; S) ; with suitable optimizations for initializations and increments. Incidentally, nearly every while loop I've ever seen in a C program can be more suitably represented as a for loop with at least one of the optimizations taking effect, so it's actually the while loop (and do-while loop) that should be regarded as superfluous. For the for-loop: for (Init; Cond; Incr) Body; = Init; x where x is the fixed point solution to the equation: x = if (Cond) {Body; Incr; x} Note that all of these equivalences remains so, even taking into account the effects of evaluating expressions (Cond) with side-effects. Just as an added note, C's for loop is formally defined in terms of its while loop. > >In fact, aren't all high-level control constructs superfluous? They're supposed to be. In fact, a well designed language should have most of its constructs defined in terms of its more basic "core" entities. The goto is also superfluous once you realise that every goto is a parameterless procedure call whose return address is the end of the block from which the goto issued (or some variant of that depending on which language one is talking about).