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.

Lives

+1 for taking extra effort to get more feedback on top of solving the Homework. – Erubescent

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

Lives

Yes, I think the key is a getOutOfJail variable to short circuit the while loop. My VB.NET, C#, Perl, PHP, Java, Javascript. ECMAScript samples would follow this pattern. – Joachima

This doesn't give you the "else" effect. What if 'd' had been set to a non-zero number in the first while-loop. If that had happened, then you would have had both the IF path and the ELSE path run. – Radiothermy

The else would be while(getOutOfJail) ... (no other condition) after the other while statements. – Joachima

@Radiothermy - That's the purpose of the continue variable. If d had been set to non-zero, then continue would be false and the second loop wouldn't run. – Lives

@Jason Baker, you got the explanation backwards I think, but the code is right... – Nest

There is no "True" or "False" in the language definition, unless cons allows it. You may need to use C-style booleans (1 and 0) with "and continue = 1". But otherwise a good solution. – Elderly

My professor wasn't exactly clear about that. Based on other lectures, I suppose I kind of cheated. :-) – Lives

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.

Fruge

This changes the values of d and a which may have bad side effects. You can fix this with: d1 := d; a1 := a; at the beginning and d :=d1; a := a1; at the end. – Nest

Answer 3

Would this work?

td := d
x := 1

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

Feminize

So this avoids another cycle by overwriting a default value and optimizes the predicate. It might be worth expressing only the overwriting idea: continue := True; x := 1; while d != 0 and continue do x := a/d; continue := False od – Eduard

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. :-)

Fissi

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

Tjirebon

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.

Aurist