Post Merged (destination) from cs.stackexchange.com/questions/32327/…
3 Tags
| link
2 grammar, formatting
source | link

Are if statements unnecessary if a program is representrepresented as an explicit state machine?

This question occurred to me some time ago when iI was thinking about whether or not ifif 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; } }

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 ifif statements, as in the withdraw operation, ifif 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 balancebalance variable, hence we would have states: {balance = 0 , balance = 1, balance = 2...}{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 osof states, and assign to each operation a number identifier as well (say deposit = 0 and withdraw = 1deposit = 0 and withdraw = 1), we could model the program as an explicit transition between states and therefore remove every ifif statement from the code.

Consider that state = 0state = 0 is the state where balance = 0balance = 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]; // índex deposit instance for state = 0, amount = n; }

void deposit (int n)
{
   deposit[state][n]; // índex deposit instance for state = 0, amount = n;
}

deposit[][]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; ....

deposit[0][0] -> balance = balance + 0; state = 0;
deposit[0][1] -> balance = balance + 1; state = 1;

....

inIn the case of withdrawal, it would be like:

boolean withdraw (int n) { return withdraw[state][n]; // índex withdraw instance for the current state and amount = n; }

boolean withdraw (int n)
{
    // índex withdraw instance for the current state and amount=n
    return withdraw[state][n]; 
}

withdraw[][]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; return true; state = 100;

deposit[0][100] -> return false; state = state;
...
deposit[200][100] -> balance = balance - 100; return true; state = 100;

In this situation, the program the managers the single bank account can be written without using a single ifif 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[][]deposit[][] and withdraw[][]withdraw[][] matrices? By hand? It somehow implies that a previous computation that used ifsifs as necessary to determine and possible states and transitions.

All in all, are ifsifs fundamental or does my exempleexample prove that they aren't? If they are, can uyou provide me an exempleexample 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 ifif statements are unavoidable?

Thanks in advance

Are if statements unnecessary if a program is represent as an explicit state machine?

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 os 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]; // índex 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) { return withdraw[state][n]; // índex withdraw instance for the current state and amount = 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; return true; state = 100;

In this situation, the program the managers 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 exemple prove that they aren't? If they are, can u provide me an exemple 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?

Thanks in advance

Are if statements unnecessary if a program is represented as an explicit state machine?

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]; // índex 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)
{
    // índex 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; return true; state = 100;

In this situation, the program the managers 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?

    Tweeted twitter.com/#!/StackCompSci/status/526238690486411264
1
source | link

Are if statements unnecessary if a program is represent as an explicit state machine?

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 os 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]; // índex 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) { return withdraw[state][n]; // índex withdraw instance for the current state and amount = 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; return true; state = 100;

In this situation, the program the managers 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 exemple prove that they aren't? If they are, can u provide me an exemple 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?

Thanks in advance