6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So, you want an array of functions instead of condition statements? Why don't I like this? $\endgroup$ – John Dvorak Oct 26 '14 at 12:35
  • 2
    $\begingroup$ Why did you post this twice? You just completely wasted my time when I wrote an answer to your question and then found it had already been answered. $\endgroup$ – David Richerby Oct 26 '14 at 14:10
  • $\begingroup$ See also here. $\endgroup$ – Raphael Oct 29 '14 at 17:15
4
$\begingroup$

Literal if statements are not fundamental. As you've shown, it's possible to remove them by writing your program as a state machine, though at the gigantic cost of having to have a different version of the widthdraw() function for every possible starting balance and withdrawal amount. You can also avoid literal if statements by replacing

if (condition) {
    foo
} else {
    bar
}

with

b1 := condition
b2 := not(b1)
while (b1) {
    foo
    b1 := false
}
while (b2) {
    bar
    b2 := false
}

On the other hand, doing so has no clear advantages and many disadvantages. The gigantic-table-of-functions approach leads to huge redundancy, is very hard to maintain and is very hard for compilers and CPUs to optimize. If you're lucky, the while loop hack might compile to the same code as the simple code with if statements but it's much harder to read and much more prone to programmers mistakenly thinking they can optimize it.

At a fundamental level, some form of conditional execution is necessary. If you have no kind of conditional statement at all, then you can only perform a class of very limited programs called "straight-line programs". These are, perhaps surprisingly, useful as a model of computation because they have a fairly simple correspondence with circuits: they correspond to the simplest notion of algorithm, i.e., take your input data and perform a fixed sequence of operations on it. For example, when you compute the length of a 2D vector, you're using a straight-line program: square the $x$-coordinate, square the $y$-coordinate, add the two squares, take the square root (at least, assuming that all those arithmetic operations, including square root, are taken as being built in to your langauge).

$\endgroup$
  • $\begingroup$ Exercise to the reader: find the "conditional" in $\mu$-calculus. $\endgroup$ – Raphael Oct 29 '14 at 17:15
2
$\begingroup$

On a processor, the if-else statement is ultimately a conditional branching instruction, where the execution address is generated on the basis of some comparison to get to a decision.

On hardware (like on an FPGA) however, if-else is (for example) done using a multiplexer/demultiplexer where the 'condition' is done through the state of the 'select' inputs. In this case, the logic for which branching logic is burned onto hardware, where there's no need for a "next address" generator.

If I understand correctly, your question is whether branching on-the-fly is "fundamental" to computing, or whether it can be circumvented by other ways.

I would say that, yes it is fundamental to computing. On the FPGA, the branch states are usually finite at the level of one mux/demux, therefore, there's no physical analogue to branching. On a processor, however, given the practical limits on memory, condition branching is a fundamental operation.

$\endgroup$
  • $\begingroup$ Welcome to CS Stack Exchange! This answer explains why conditional instructions are necessary in practice on processor-based systems but note that there are models of computation such as automata that don't really have a processor (but which still have some kind of conditional). $\endgroup$ – David Richerby Oct 26 '14 at 13:21
2
$\begingroup$

Your construction seems a bit tautological. The if statement is itself a form or branching through an array of two addresses, depending on a value that is 0 or 1. Actually, the if statement generalizes to the case statement, which may be implemented as branching through an array. Whether the array is code or static data is immaterial and pretty much in the eyes of the beholder.

Another way to state this is that your program could be simulated by a Turing machine, which does not have any if statement, and could thus be a positive answer to your question.

Indeed, a Turing machine should be as good an answer as any other state machine. Compared to a FSA, the only difference is that it can read and write on an infinite tape.

So, if you do not accept the Turing machine as an answer, I wonder whether your problem is not more with eliminating this infinite memory tape, at the expense of replacing it with an infinite program (TM states and transitions).

Then, I am afraid you may just fall into something similar to a Turing Tar Pit, or much worse (a Turing hell?).

The main point is that the technique you are proposing will require your program to have an infinite size, if it is to be equivalent to the original program, using infinite matrices, i.e. really an infinite number of states.

You might not worrry about it, considering that we already work as if we could use unbounded integer in memory. That is true, but we use integer in a very precise way, that is finitely described. As a consequence, it is perfectly possible to mimic computation with arbitrary long integer, and it is actually done in some systems.

One fundamental principle of computer science (and I would add mathematics, but that has to be made precise) is that everything must be finitely definable.

To make any sense, your infinite program would similarly have to follow a finite specification, where your if statement would be back, or the TM with its infinite tape.

If you forget this constraint, then you drastically change the domain of discourse, as you get a continuous (rather than denumerable) infinity of different programs. You are no longer talking of computability with its accepted meaning, and its physical realizability. Actually, I suspect that you can then no longer consider a concept that would ressemble computability (but that is a somewhat fuzzy statement).

$\endgroup$
0
$\begingroup$

In a way, if statements are unavoidable at some stage, unless you write things "by hand", but in that case, it is not at all clear that you don't preform branching operations in your brain, so let's leave that aside.

Consider a program P in assembler (to have a low common ground). In assembler, the only branching operation is "if x>0 goto l1, else goto l2"

So assume you have a program without those. Then, you can define for every line $l$ in the code, a unique line $l'$ that always follows $l$ in the execution. Thus, the program either gets to exit and terminates within $n$ commands ($n$ being the number of lines) or it runs forever.

From this, we learn that if you want to describe a big system, but you want to describe it without branching, then you will need to write it more or less explicitly. If you use branching, you can get things exponentially more efficient.

Also, your question is related to the concept of symbolic representation and symbolic algorithms which can affect the succinctness of representation.

$\endgroup$
0
$\begingroup$

This is really answering Devian Dover's last question on this theme: Where does the need for conditionals (if, switch, jump tables, etc…) truly arise? Since that last question was closed as duplicate to the one I am answering here, I guess it is OK to answer it here. This answer is thus quite different from my previous one here, since the two questions are related rather than duplicates.

Hoopje's answer shows that Lambda Calculus can create conditionals out of its elementary constructs. Whether they are actually more elementary than conditional is a subjective matter. If you Had a while loop plus exit statement, that would also let you do conditionals, though a while loop may be seen as more complex than a conditional.

Another example is the Post Correspondence Problem (PCP). It can simulate a Turing machine, though it does not even have a concept of execution or evaluation to start with, let alone a conditional.

To take a more amusing example, you can build Turing Machines with Lego bricks, but there is no Lego brick that identifies as an if statement.

What you are really asking is an ontological question, and such questions often have only subjective answers. What organization there is to the world is largely made up by your own individual or collective subjective reconstruction of world order. The fact that the universe is organized and structured is not to be denied, but the expression of this structure by laws, the concepts we may put forward as fundamental, may vary without actually changing the structures described.

To formulate it in a more formal way, different systems of axioms could characterize a given unique set of possible interpretations.

You are asking:

My point is, where do conditionals come from? Where do they stop? Can we avoid them somehow? Can you prove me we need them? If we do, why do we put them at the hardware level? Why does the input of a program have to be compared against values to determine the branch to execute?

So my answer to your quest, rather than your question, is that conditional are one convenient way to express some algorithm is some formalization of what a computation may be. They stop where you choose to make them stop. We can avoid them, and many other concepts, since computation and algorithms can be expressed by totally different means. We do not need them: they happen to be, when we want to look at them, but we can proceed by other means when we do not (want to) see them. We do not have to put them at the hardware level since we do not have to have them at all. We do not have to compare input to anything since computation can be express by other means.

A very negative answer. The point is that the use of conditionals corresponds to a specific model of computation, essentially the von Neumann machine, that has been considered convenient as a fundamental set of concepts to represent computation in physical devices. In a sense, it is pure expediency. It is just one way, among many others, to see the structure and order of the computational world, one that we find easy enough to deal with, and for which we can produce physical simulators (called computers) that are not too expensive to produce or to use.

Conditionals are just one of many way we have to apprehend and express assessment of change or diversity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.