The while language

Question

For my theory of computing languages class, we got a homework assignment to implement a piece of code in a language that only has while statements for flow control (no if statements). This is mainly to prove that you can write a Turing-complete language with only a while loop.

For those of you who can understand language grammars, here are the language rules:

S -> S;S | while C do S od | id := E

E -> E + T | T | E - T

T -> T * F | F | F / T

F -> id | cons | (E)

C -> E = E | E > E | E < E | E >= E | E <= E | E != E | C and C | C or C | not(C)

This is copied from my class notes, so don't blame me if something is missing or incorrect!

The piece of code to implement is this:

if d = 0 do
    x := 1
else
    x := a / d

At any rate, if you want to go ahead and write that using the language rules above, go ahead. Otherwise, go ahead and write it in whatever language you're most comfortable in. But there are a few caveats!

• No if statements or any other kind of flow control other than while loops.
• No cheating: the grammar above doesn't include any break statements, return statements, or exceptions. Don't use them.

I've got my piece of code written for this (which I'll post just to prove this isn't a show me teh codez post). I'm kinda curious what anyone else can come up with though.

Answer 1

Here's my code:

continue := True
while d = 0 and continue do
    x := 1
    continue := False
od
while d != 0 and continue do
    x := a/d
    continue := False
od

Answer 2

It can be done with a single while loop, but it is not that clear:

while d == 0 do
  d := 1;
  a := 1
od
x := a / d;

Explanation, if d = 0, then d will be 1, also a will be 1. This ends the loop.

Now x is set to a / d which is fine, because if d was 0, a / d evaluates to 1.

Answer 3

Would this work?

td := d
x := 1

while td != 0 do
    x := a / d
    td := 0
od

Answer 4

To be Turing Complete, you need to support both selection and iteration. While loops obviously iterate. Selection can be accomplished by making it go through the loop once if the condition is true, and not at all otherwise.

So worst case you can do everything you need to by applying those techniques. I'd imagine some complicated control flows would get ugly fast though. :-)

Answer 5

Without using details of the true or false branches, and without repeating the predicate:

statementIncomplete := True
while d = 0 and statementIncomplete do
    x := 1
    statementIncomplete := False
od
while statementIncomplete do
    x := a/d
    statementIncomplete := False
od

Answer 6

This is an expansion of Eamon's answer.

The semantics of if <condition> then <stmt> else <stmt> fi is the following:

• evaluate <condition>;
• if it was true, execute the statement between then and else;
• otherwise, execute the statement between else and fi.

The semantics of while <condition> do <stmt> od is the following:

• evaluate <condition>;
• if false, the while statement is done executing;
• otherwise, execute the statement between do and od, and execute the while statement again.

To express if A then B else C in terms of while, perform the following transformation:

Let gensymN be a name not used for any other variable; then emit the following code

gensymN := 0;
while gensymN = 0 and A do B; gensymN = 1; od;
while gensymN = 0 do C; gensymN = 1; od

The semantics of this program is:

• Assign 0 to gensymN.
• Evaluate gensymN = 0 and A (it's true iff A is true)
• If true, then:
  • execute B
  • execute gensymN = 1
  • evaluate gensymN = 0 and A (it's false)
  • evaluate gensymN = 0 (it's false)
• else (if gensymN = 0 and A was false):
  • evaluate gensymN = 0 (it's true)
  • execute C
  • execute gensymN := 1
  • evaluate gensymN = 0 (it's false)

Observe the following substructure of the above:

• It (effectively) evaluates A;
• If true, it executes B, otherwise C.
• Apart from A, B and C, the program (fragment) only fiddles with gensymN, which is not present in the input program.

Hence this program has the same semantics as

if A then B else C fi; gensymN := 1

One footnote: if A is true when evaluated, it will be evaluated once again (unless and is short-circuiting). If the language allows storing booleans in variables, one can introduce one more dummy variable and do dummy := A; <insert the above program here, with dummy instead of A>. Then the two evaluations of dummy are essentially just a load. If evaluating boolean expressions cannot have side effects, preventing the second evaluation is not necessary for correctness; it may (or may not) be an optimization.

Take the above as a "soft proof", with the provisos of the preceding paragraph, that this is a correct fully general translation of if to while. The full generality sets this (= Eamon's) answer apart from the others, in my view.