DarkFalz
-
Posts
2 -
Joined
-
Last visited
Content Type
Profiles
Forums
Events
Posts posted by 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 likeAccount{int balance; // current amount of Moneyboolean withdraw(int n){if (balance >= n){balance = balance -n;return true;}elsereturn 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 asvoid 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, likedeposit[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=nreturn withdraw[state][n];}`withdraw[][]` would be a matrix of pointers for a set of functions that represent each possible execution of withdraw, like:withdraw[0][100] -> return false; state = state;...withdraw[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 `if`s as necessary to determine and possible states and transitions.All in all, are `if`s 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?
0
Are if statements unnecessary if a program is represented as an explicit state machine with precomputed states?
in Computer Science
Posted
Thanks for the compliment! Still it is troubling my mind that given that this approach is feasible, why not use it more often? Is memory more important than execution time?