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

[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:

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?

[Strange]

You are replacing an explicit "if" statement with a function call which is determined by the program state; i.e. the function that is called is conditional.

 

So, yes, conditional execution is required for a turing-complete language.

[Sensei]

You must have a lot of free time, to waste it asking such questions..

 

In Motorola assembler we had:

 

BRA - branch (jump) to relative address, without checking conditional flags

BEQ - branch if equal

BNE - branch if not equal

BPL - branch if plus

BMI - branch if minus

 

In your case:

 

if( balance >= n )

 

CPU has to subtract in memory (not stored result, just flags changed) balance = balance - n

and set flags

if flag is negative after subtraction, jump to omit part of code.

It's built-in very deeply, inside of processor.. Branch and status flags are essential instructions for CPUs. You can have no multiplication function (it's often missing in cheap 8 bit cpus used in electronics, have to be simulated by hand (shifts and adding)), but must have branches/flags.

 

 

Some if() could be avoided and changed to single line f.e.

 

if( x > y ) x = y;

 

could be replaced by:

 

x = ( x > y ) ? y : x;

 

or

 

x = min( x, y );

Edited October 26, 2014 by Sensei

[Strange]

You must have a lot of free time, to waste it asking such questions..

 

I thought it was a very intelligent question. Working out that you can code a jump table like that, instead of using explicit conditional code, is pretty smart.

 

The rest of your answer appears to be irrelevant to the question asked. (It wasn't me who gave you a negative vote ... but it was tempting!)

Edited October 26, 2014 by Strange

[DarkFalz]

 

I thought it was a very intelligent question. Working out that you can code a jump table like that, instead of using explicit conditional code, is pretty smart.

 

The rest of your answer appears to be irrelevant to the question asked. (It wasn't me who gave you a negative vote ... but it was tempting!)

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?

[Strange]

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?

 

It is used in quite a few cases. It may be referred to as a vector table or a jump table. It is just a bit less "obvious" than an if-else type structure so you don't often see it in source code. It can be more efficient though (but the overheads of setting it up may not always be worth it) so you do come across it occasionally, especially where size or performance are critical (e.g. operating system code).

 

It is one of the ways a case statement can be compiled. Depending on the number and types of the cases, the compiler might turn it into the equivalent if-else-if-else statements or the sort of structure you describe. It is also used a lot by C++ compilers to handle the fact that there can be multiple functions with the same name and which one gets called depends on the types of the arguments, for example.

 

It is often used in hardware as well, for example for interrupt vectors.

[Sensei]

I thought it was a very intelligent question. Working out that you can code a jump table like that, instead of using explicit conditional code, is pretty smart.

Are you programming on daily basis? I don't think so, if you're considering jump-table as viable alternative option for if() for presented case..

Below code is simply jumping to sub-routine! While if() is jumping to relative address omitting what if contains in { }.

 

200 states * 200 deposit amount = 40000 sub-routines needed.

For 1 mln states and 1 mln deposits = 10^12 sub-routines needed.

 

Jump to subroutine is *slow*. Requires putting all registers on stack. Return address is put on stack. Then subroutine also does initializations at beginning and cleaning up on ending. Then stored registers are restored from CPU stack.

It's much more expensive than simple comparison of values..

 

The rest of your answer appears to be irrelevant to the question asked. (It wasn't me who gave you a negative vote ... but it was tempting!)

It's very relevant. I'm showing that if() handling is at CPU machine code level implemented..

 

Is memory more important than execution time?

You should make example code and run it f.e. 1 mln/bln execution times and compare times, to check your statement whether it's faster or slower..

 

Typically we can do it by f.e.:

 

clock_t t0 = clock();

 

[..code...]

 

clock_t t = clock() - t0;

printf( "Clock %d seconds\n", t / CLOCKS_PER_SEC );

 

or use time() instead of clock()

Edited October 27, 2014 by Sensei

[John Cuthber]

Sensei.

Yes, I do programme on a daily basis, and I have programmed stuff for decades.

In some circumstances - for example when the problem is specified as a table of inputs and outcomes, it's easier and clearer to code the problem as a look-up table rather than a set of conditions.

 

However the question wasn't asked as a day to day issue, but as a matter of principle and, the answer is that you can do without if statements.

 

And showing that the If function is implemented at a machine code level is not that same as showing that it is needed.

[Strange]

Are you programming on daily basis?

 

Yes, for well over 30 years. And I have worked on compilers and the design of microprocessors.

[Sensei]

In some circumstances - for example when the problem is specified as a table of inputs and outcomes, it's easier and clearer to code the problem as a look-up table rather than a set of conditions.

But there must be very few conditions and/or functions must be repeatable and table filled automatically at initialization.

In presented by OP example there is needed 40 thousands unique sub-routines! With bank accounts up to 1 mln, 10^12 entries.

 

Example place where there could be used jump-table is interpreter of language with up to 8 bit commands, emulator of 8 bit cpu.

They would have array of size 256 entries to sub-routines called to process single instruction.

For 16 bit wide instructions it would stop making sense (65536 entries), and for 32 bit wide instructions (4 bln) even not possible. Out of memory for table (16 GB on 32 bit machine, and 32 GB on 64 bit machine).

 

However the question wasn't asked as a day to day issue, but as a matter of principle and, the answer is that you can do without if statements.

Reminds me what Maria Antonia said...

 

And showing that the If function is implemented at a machine code level is not that same as showing that it is needed.

 

I showed it's implemented by the most basic CPUs.

JSR/BSR - Jump Sub-Routine - can be not implemented.

Early graphics card GPUs often didn't have it. And they couldn't have recursion, nor didn't have cpu stack.

However even the simplest CPUs/GPUs have conditional jumps Bxx (xx - condition).

 

Conditional/absolute branch instruction in CPU are superior to jumping to sub-routine.

 

Every action must have purpose, sense. OP said "Is memory more important than execution time?" But his code won't be faster, it will be actually slower, than code with if()..

That's why I told him to benchmark both codes, to compare and see it on eyes.

Edited October 27, 2014 by Sensei

[Strange]

But there must be very few conditions and/or functions must be repeatable and table filled automatically at initialization.

 

Actually, if there are very few conditions then the if-else structure is likely to be more efficient.

 

In presented by OP example there is needed 40 thousands unique sub-routines!

 

I am fairly sure the OP was interested in the principle, rather than this specific example. (If there are a very large number of conditions, then it may be better to do a computed jump.)

 

For 16 bit wide instructions it would stop making sense (65536 entries), and for 32 bit wide instructions (4 bln) even not possible.

 

Many 16 and 32 bit microprocessors use a microcoded instruction set where there is typically a jump table to go from opcode to microcode entry point. (And, of course, a 16 bit processor doesn't have 64K instructions.)

 

I showed it's implemented by the most basic CPUs.

 

Which is utterly irrelevant. It doesn't matter how it is implemented.

 

JSR/BSR - Jump Sub-Routine - can be not implemented.

 

I have programmed dozens of different processors. I can only think of one that didn't support subroutine calls. However, there were several that support conditional subroutine calls. But you can still implement any of these techniques on any of them.

 

Early graphics card GPUs often didn't have it

What! What on earth do GPUs have to do with it? The question was about programming models and computability.

 

I think you should stop digging that hole.

[Sensei]

Many 16 and 32 bit microprocessors use a microcoded instruction set where there is typically a jump table to go from opcode to microcode entry point.

Now you're talking about CPUs internals implemented in transistors. Even more nothing to do with programming side of them..

 

(And, of course, a 16 bit processor doesn't have 64K instructions.)

Of course 8 bit CPU have 8 bit wide instructions. 1 byte per instruction (plus additional optional 1-2 bytes parameters). Take f.e. Motorola 6502,6510 as example.

Of course 16 bit CPU can have 16 bit wide instruction. 2 bytes per instruction (plus additional optional 2,4,6,8 bytes parameters). Take f.e. Motorola 680x0 as example. Each instruction has at least 2 bytes. It doesn't mean there is 64 k instructions. But emulator has to read whole word and use as index to jump-table. Some fields will be causing exception.

If 16 bit CPU would have 8 bit wide instruction-1 byte, it would be often reading from not word aligned address! Which would cause problem with CPU cache, if one half of instruction is in cache, and other byte outside in physical memory.

 

Intel is different as its instruction set grew up with time?

 

See

http://www.eventhelix.com/realtimemantra/ByteAlignmentAndOrdering.htm#.VE4UWle198E

"Most 16-bit and 32-bit processors do not allow words and long words to be stored at any offset. For example, the Motorola 68000 does not allow a 16 bit word to be stored at an odd address. Attempting to write a 16 bit number at an odd address results in an exception."

 

Which is utterly irrelevant. It doesn't matter how it is implemented.

Nonsense. Purpose is to have faster working program. Why to bother so much to have slower working code?

Jumping to sub-routine is time expensive!

 

I have programmed dozens of different processors. I can only think of one that didn't support subroutine calls. However, there were several that support conditional subroutine calls. But you can still implement any of these techniques on any of them.

Add to list cheap GPUs..

 

What! What on earth do GPUs have to do with it? The question was about programming models and computability.

 

I think you should stop digging that hole.

Are you up to date with modern GPUs?

You can program pixel and vertex shaders.

They're programs, developed by programmers, compiled for their GPUs..

Executed by GPUs at demand of programmer.

[Strange]

Now you're talking about CPUs internals implemented in transistors. Even more nothing to do with programming side of them...

 

Then why did you bring it up? I was simply correcting your misinformation.

 

But emulator has to read whole word and use as index to jump-table.

 

You either need to try writing an emulator OR learn how to do it better.

 

Nonsense. Purpose is to have faster working program.

 

Is it? Did the OP ask about performance?

 

Why to bother so much to have slower working code?

 

Perhaps becaise it is smaller. perhaps because it is more maintainable or portable.

 

Jumping to sub-routine is time expensive!

 

Are you up to date with modern GPUs?

 

Yes. I have worked for companies that make them and been involved in the development of programming models and compilers for them. But that is, of course, utterly irrelevant to the topic of the thread.

 

If you want to start a thread on processor architecture, assembler programming and GPUs, then do it. Otherwise stop taking this one off topic.

[Sensei]

Then why did you bring it up? I was simply correcting your misinformation.

You misunderstood.

I gave writing EMULATOR of CPU as example of where jumping-table can be useful (instead of handling banking account).

 

You either need to try writing an emulator OR learn how to do it better.

Using JIT would be even worser off topic. JIT is not portable. So it's better to have first make interpreter code. And then add JIT for specific target CPU. And user will pick up whether he wants JIT or normal emulation in options.

 

Is it? Did the OP ask about performance?

Post #5.

Edited October 27, 2014 by Sensei

[Strange]

Post #5.

 

"Is memory more important than execution time?"

 

Good question, which I didn't really notice before. There is no simple answer. It depends on the application. In some applications (embedded, typically) memory use is much more important than performance. In some cases, large amounts of memory can be used to improve performance (e.g. unrolling loops, inlining functions, etc.)

 

Also, it is not always obvious which approach (if-else vs jump tables) will be best for a given requirement.

[Sensei]

"Is memory more important than execution time?"

 

Good question, which I didn't really notice before. There is no simple answer.

That's why in post #7 I suggested benchmarking it, instead of guessing..

Edited October 27, 2014 by Sensei

[John Cuthber]

The OP didn't ask about speed or efficiency, but it did accept that this uses a lot of memory.

So any discussion on those points is pretty well beside the point.

On the other hand, it did ask an interesting question.

 

"Is there some law of computation which states that `if` statements are unavoidable?"

Now, I'm going to stick my neck out here and say that I think the answer is no. It might be impractical, or even bloody mindedly stupid, but that's not the question here.

Can anyone actually show that I'm wrong?

 

Not that it matters, whether or not a look up table is faster depends on how it's organised and how much memory you can squander.

Imagine that I want to produce a 1 byte output that is some arbitrary combination of 2 single byte inputs.

I can write the look-up table into a single 64K rom and use the two inputs as the high and low bytes of the address.

The poutput of the rom can be programmed to be the output of the look-up table.

The delay in calculation is equal to the clocking time of the memory.

That's roughly 1 clock cycle.

How fast can you write that with "if" statements?

Edited October 27, 2014 by John Cuthber

[Strange]

 

For example, an imperative language is Turing complete if it has conditional branching

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

 

Other styles of programming language may not have explicit conditional branches, but must still have some mechanism to choose what operations to perform (such as the branhc table the OP suggests).

[John Cuthber]

With a look up table stored in memory there is no explicit choice to make. the operation is "retrieve the data at the address specified by the inputs".

It will work with any finite set of inputs as long as the output is determined solely by those inputs.

 

There is a deeper question, does an OR gate or AND gate count as a conditional branch?

I'd say no, because there's no clear branching- but I think it's a matter of semantics.

[Sensei]

There is a deeper question, does an OR gate or AND gate count as a conditional branch?

I'd say no, because there's no clear branching

Wrong.

 

BEQ for instance is Branch if EQual. When Z flag status register is set to 1, there is jump, otherwise no jump. That's what programmer see from outside.

But it's doing AND operation between Z flag status register and parameter (relative offset).

Then result of this AND operation is added to PC (Program Counter) register. Simple math operation on one of CPU registers!

 

So actually BEQ instruction is equivalent to:

PC += relative offset & Z flag; // (extend in mind single Z bit to whole word/long word)

 

Z flag is 0 -> to PC there will be added 0, and nothing will happen. Because it was cleared by AND operation.

Z flag is 1 -> to PC there will be added relative offset.

 

In BNE (Branch if Not Equal), Z flag will be passed through NOT gate, prior AND (or simply NAND).

PC += relative offset & ~Z flag;

And that's it. Bitwise AND operation, then adding operation, one by one..

 

Do you want me to also explain you how ADD operation looks like from point of view of logic gates?

The OP didn't ask about speed or efficiency, but it did accept that this uses a lot of memory.

So any discussion on those points is pretty well beside the point.

 

Have you bother reading thread you're replying? In post #5 he clearly thinks his solution is speeding up program..

Edited October 27, 2014 by Sensei

[John Cuthber]

 

Wrong.

 

BEQ for instance is Branch if EQual. When Z flag status register is set to 1, there is jump, otherwise no jump. That's what programmer see from outside.

But it's doing AND operation between Z flag status register and parameter (relative offset).

Then result of this AND operation is added to PC (Program Counter) register. Simple math operation on one of CPU registers!

 

So actually BEQ instruction is equivalent to:

PC += relative offset & Z flag; // (extend in mind single Z bit to whole word/long word)

 

Z flag is 0 -> to PC there will be added 0, and nothing will happen. Because it was cleared by AND operation.

Z flag is 1 -> to PC there will be added relative offset.

 

In BNE (Branch if Not Equal), Z flag will be passed through NOT gate, prior AND (or simply NAND).

PC += relative offset & ~Z flag;

And that's it. Bitwise AND operation, then adding operation, one by one..

 

Do you want me to also explain you how ADD operation looks like from point of view of logic gates?

 

Have you bother reading thread you're replying? In post #5 he clearly thinks his solution is speeding up program..

You are quite correct in your first line there- all the stuff that follows is, indeed, wrong.

OK, so, you don't know that an Or gate is different from a CPU and you don't know what OP stands for in this context.

Have a look at the question I actually asked

" does an OR gate or AND gate count as a conditional branch?"

That's a question about logic gates not a CPU (or even an ALU if we want to get into a bit more detail).

It hasn't got anything to do with BEQ because BEQ isn't an option available to an AND gate is it?

Re "Do you want me to also explain you how ADD operation looks like from point of view of logic gates?"

No thanks I learned that some time in the late 70s and it hasn't changed.

The even better reason for not bothering is that it doesn't have anything to do with the question.

As I said, you can create a look up table in a ROM.

So anything to do with the PC is irrelevant- a ROM hasn't got one.

You seem to have become fixated with the idea that you have to use a CPU.

I'm pointing out that there are other ways to do it- and they don't need an if statement because an if statement relates to control flow and you can sidestep that with a table.

There's only 1 operation which is "retrieve the data from the cell that's being addressed".

That's it.

No control flow so no need for an if statement.

Since OP stands to Original Post, anything that was stated in any subsequent post hasn't got anything to do with it.

Post #5 isn't post #1

Edited October 27, 2014 by John Cuthber

[Sensei]

 

Since OP stands to Original Post, anything that was stated in any subsequent post hasn't got anything to do with it.

Post #5 isn't post #1

 

Again, wrong. OP means Original Poster in the first place.

http://acronyms.thefreedictionary.com/OP

In this context = author of this thread. So all of his replies are equally valid, to understand his intentions.

 

Yet another websites will explain you what OP means:

http://www.urbandictionary.com/define.php?term=op

 

http://www.webopedia.com/TERM/O/op_original_poster.html

Edited October 27, 2014 by Sensei

[John Cuthber]

Or not...

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

But lets not bother to throw dictionaries at each other.

It's clear from what I wrote that I meant a post not a person

I wrote

"The OP didn't ask about speed or efficiency, but it did accept that this uses a lot of memory."

Not

"The OP didn't ask about speed or efficiency, but it he did accept that this uses a lot of memory."

 

In any event the question in the first post here was about whether or not something is possible, not about speed or practicality

 

"Is there some law of computation which states that `if` statements are unavoidable?"

Why not try answering it?

try and come up with a program that can't be replaced by a huge look-up table.

Edited October 27, 2014 by John Cuthber

[Endy0816]

Can do something similar using straight algebra as well.

 

example of '!='

 

x = a-b;

x = x/x; // note: 0/0 needs to result in 0 for this line to work...

balance = balance - n*x;

 

As for the And/Or question I'm really not sure. Am aware of the necessity of essentially the Not gate along with either And/Or for functional completeness, but had not considered this in relation to conditional branching.

Edited October 27, 2014 by Endy0816

[John Cuthber]

It's OK, you can do everything with just NAND gates

Edited October 27, 2014 by John Cuthber