replace if/else with while/if statement

Question

is it possible to replace a if/else statement with while and if statement(s) (say, we're working in C)? If it's possible, can you please share an example. So, say I have

if (cond1)
    exec1
else 
    exec2

And I really want to get rid of the if/else and just use if/while constructs.

Is it enough for a Turing Complete language to have while/if statements (for the control flow)?

How would I do it with if/else constructs?

(this is not a homework, this is out of curiosity)

Answer 1

The if, else can be replaced with: using If :

if (condition cond1 is true) {

execute exec1;

}

if (!(condition cond1 is true)) //condition is false

{ execute exec2;

}

using While loop :

while (condition cond1 is true) {

execute exec1;

}

while (!(condition cond1 is true)) //condition is false

{ execute exec2;

}

Answer 2

For a general replacement of the if() ... else ... construct, you can cache the result of the condition:

int condition = cond1;
if(condition) exec1;
if(!condition) exec2;

That way you avoid issues with sideeffects in cond1 and exec1.

Concerning your question about turing completeness:
As Paul Griffiths notes, if() and goto are sufficient. However, so are if() and recursion. You can replace any while(cond1) exec1; loop with a self recursive function:

void loopy(/*whatever state the loop touches*/) {
    if(cond1) {
        exec1;
        loopy(/*pass on the current state*/);
    }
}

This fact is heavily abused in functional languages like lisp and scheme. When you learn programming in these languages, you are taught to write your recursions in such a way (tail recursion) that the compiler can figure out that you intended to write a loop and optimize accordingly...

Answer 3

You don't even need while, you just need to be able to compare and to be able to branch, in other words, if and goto. In the following program, the functions test_normally() and test_subnormally() are equivalent:

#include <stdio.h>

void exec1(void)
{
    puts("exec1() called");
}

void exec2(void)
{
    puts("exec2() called");
}

void exec3(void)
{
    puts("exec3() called");
}

void test_normally(void)
{
    int cond1 = 0;
    int cond2 = 1;
    int i = 5;

    /*  First if test  */

    if ( cond1 )
        exec1();
    else
        exec2();

    puts("First if test over.");

    /*  Second if test  */

    if ( cond2 )
        exec1();
    else
        exec2();

    puts("Second if test over.");

    /*  While test  */

    while ( i > 0 ) {
        exec3();
        --i;
    }

    puts("Loop test over.");
}

void test_subnormally(void)
{
    int cond1 = 0;
    int cond2 = 1;
    int i = 5;

    /*  First if test  */

    if ( !cond1 )
        goto cond1_false;

    exec1();
    goto cond1_end;

cond1_false:
    exec2();

cond1_end:
    puts("First if test over.");

    /*  Second if test  */

    if ( !cond2 )
        goto cond2_false;

    exec1();
    goto cond2_end;

cond2_false:
    exec2();

cond2_end:
    puts("Second if test over.");

    /*  While test  */

loop_start:
    if ( !(i > 0) )
        goto loop_end;

    exec3();
    --i;
    goto loop_start;

loop_end:
    puts("Loop test over.");
}

int main(void)
{
    test_normally();
    putchar('\n');
    test_subnormally();
    return 0;
}

and output:

paul@local:~/src/sandbox$ ./goto
exec2() called
First if test over.
exec1() called
Second if test over.
exec3() called
exec3() called
exec3() called
exec3() called
exec3() called
Loop test over.

exec2() called
First if test over.
exec1() called
Second if test over.
exec3() called
exec3() called
exec3() called
exec3() called
exec3() called
Loop test over.
paul@local:~/src/sandbox$ 

By comparing the two functions, hopefully you can see why if and while and all their friends are better than the alternatives.

test_subnormally() is actually very close to what the processor is actually doing, after your C source gets compiled into machine code. Here's the assembly output of test_normally() from gcc on a 64 bit Intel processor - you can see that there's almost a one-to-one mapping between the assembly instructions and the C source for the other function, test_subnormally():

.LC3:
    .string "First if test over."
.LC4:
    .string "Second if test over."
.LC5:
    .string "Loop test over."
    .text
    .globl  test_normally
    .type   test_normally, @function
test_normally:
.LFB3:
    .cfi_startproc          # // Function entry
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $16, %rsp
    movl    $0, -8(%rbp)    # // -8(%rbp) is cond1
    movl    $1, -12(%rbp)   # // -12(%rbp) is cond2
    movl    $5, -4(%rbp)    # // -4(%rbp) is i
    cmpl    $0, -8(%rbp)    # if ( !cond1 )    
    je  .L5                 # goto cond1_false;
    call    exec1           # exec1();
    jmp .L6                 # goto cond1_end;
.L5:                        # cond1_false:
    call    exec2           # exec2();
.L6:                        # cond1_end:
    movl    $.LC3, %edi     # // move "First if test over" to %edi
    call    puts            # puts("First if test over");
    cmpl    $0, -12(%rbp)   # if ( !cond2 )
    je  .L7                 # goto cond2_false;
    call    exec1           # exec1();
    jmp .L8                 # goto cond2_end;
.L7:                        # cond2_false:
    call    exec2           # exec2();
.L8:                        # cond2_end:
    movl    $.LC4, %edi     # // move "Second if test over" to %edi
    call    puts            # puts("Second if test over");
    jmp .L9                 # goto loop_start;
.L10:                       # loop_body:
    call    exec3           # exec3();
    subl    $1, -4(%rbp)    # --i;
.L9:                        # loop_start:
    cmpl    $0, -4(%rbp)    # if ( !(i > 0) ) ...
    jg  .L10                # ...goto loop_body;
    movl    $.LC5, %edi     # // move "Loop test over" to %edi
    call    puts            # puts("Loop test over");
    leave                   # // Function exit
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc

The compiler has here chosen to put the loop pieces in a slightly different order, but other than that it reads almost exactly like the C source for test_subnormally(). The underlying reason we have if, and while, and their friends in C is precisely so that we don't have to write code that looks like this, but that level of simplicity and spaghetti-like code is what processors ultimately end up executing (and is all you need to be Turing-complete), so we have a compiler to turn something that looks more understandable and maintainable to human beings into the kind of messiness that processors are perfectly happy with.

Answer 4

These are equivalent, if cond1 is not changed in exec1.

if (cond1) exec1 else exec2

if (cond1) exec1
if (!cond1) exec2

No while needed.

Answer 5

It's somewhat clunky, but assuming that the execution of either branch doesn't change the condition, you could replace an if-else construct with a couple of whiles: Assume the original is:

if (cond) {
   exec1();
else {
   exec2();
}

It could be replaced with only ifs:

if (cond) {
    exec1();
}
if (!cond) {
    exec2();
}

Or with whiles:

while (cond) {
    exec1();
    break;
}
while (!cond) {
    exec2();
    break;
}