# Are if statements avoidable is we define a program according to explicit state transitions?

1. Oct 26, 2014

### DarkFalz

This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation.
Consider a program that manages a single bank account (for the sake of simplicity). The bank account could be defined as something like
Account
{
int balance; // current amount of Money

boolean withdraw(int n)
{
if (balance >= n)
{
balance = balance -n;
return true;
}
else
return false;
}

void deposit(int n)
{
amount = amount + n;
}
}
Since the program has no way to known in which state it currently is unless it performs validations using if statements, as in the withdraw operation, if statements are unavoidable.
However, over the course of time, the program will pass through a finite set of states that can be known beforehand. In this particular case, a state is defined solely by the value of the balance variable, hence we would have states: {balance = 0 , balance = 1, balance = 2...}.
If we assign each state a number, say state {0,1,2,....} with a 1-1 correspondence to the above set of states, and assign to each operation a number identifier as well (say deposit = 0 and withdraw = 1), we could model the program as an explicit transition between states and therefore remove every if statement from the code.
Consider that state = 0 is the state where balance = 0 and we want to perform a deposit of 50 dollars, if we coded every single possible execution of the deposit function, we could just define the deposit function as
void deposit (int n)
{
deposit[state][n]; // index deposit instance for state = 0, amount = n;
}
deposit[][] would be a matrix of pointers for a set of functions that represent each possible execution of deposit, like
deposit[0][0] -> balance = balance + 0; state = 0;
deposit[0][1] -> balance = balance + 1; state = 1;
....
In the case of withdrawal, it would be like:
boolean withdraw (int n)
{
// index withdraw instance for the current state and amount=n
return withdraw[state][n];
}
withdraw[][] would be a matrix of pointers for a set of functions that represent each possible execution of withdraw, like:
deposit[0][100] -> return false; state = state;
...
deposit[200][100] -> balance = balance - 100; state = 100; return true;
In this situation, the program that manages the single bank account can be written without using a single if statement!
As a consequence however, we have to use A LOT more memory, which may make the solution unreasonable. Also one may put the question of how did we fill the deposit[][] and withdraw[][] matrices? By hand? It somehow implies that a previous computation that used ifs as necessary to determine and possible states and transitions.
All in all, are ifs fundamental or does my example prove that they aren't? If they are, can you provide me an example where this does not work? If they are not, why dont we use solutions like these more often?
Is there some law of computation which states that if statements are unavoidable?

2. Oct 26, 2014

### DrZoidberg

http://en.wikipedia.org/wiki/Turing_machine

It's basically the most simple computer possible that is still able to run any arbitrary algorithm. And it works only by explicit state transitions.

3. Oct 26, 2014

### 256bits

An "if" statement is just making a comparison.
You have seen the truth tables of boolean logic for AND, NAND, OR,.. gates.
The truth table, and the corresponding logic gates, are just basic "if" statements.
For an AND gate, when both inputs are "1", the output will be a "1". All other times the output will be a "0.
That is the same as IF A=1 an B=1 THEN C=1 ELSE C=0

In your program without the if statements, say for example in the deposit routine , the program still has to determine which and only which deposit[][] to execute. Does it?

4. Oct 26, 2014

### Staff: Mentor

The if statement makes a comparison, and then chooses one of two options based on that comparison.

5. Oct 26, 2014

### phinds

The point is that DECISIONS have to be made in programming and if statements are an extremely simple, and easy to understand, way to do that. If you get rid of them, you have to replace them with something that is likely to take as much computational time and without necessarily being as easy to understand when debugging.

6. Oct 26, 2014

### FactChecker

You would find that restricting all decisions to be done using array pointers with state indices to be impractical in many cases. I personally would prefer a statement like "if( x < y){" to "execute_procedure[183]->" as you describe it. Enumerated values might help, but what is the point?