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

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 4

Would this work?

td := d
x := 1

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