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

[Sensei]

"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.

 

If() is used to exit loop abnormally f.e.

 

for( ; ; )

{

[...]

if( [condition] ) break;

[...]

}

 

If() is used to end loop cycle f.e.

 

for( i = 0; i < 100; i++ )

{

[...]

if( [condition] ) continue;

[...]

}

Edited October 27, 2014 by Sensei

[John Cuthber]

Are you deliberately missing the point?

Why would you need a loop if all the outputs are stored, and it's just a matter of referring to the one which corresponds to the inputs?

[SarK0Y]

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.

John, some IFs, indeed, can be avoided w/ func pointers. However, such method ain't clear for fractions. Sensei has been right upon memory penalty, but fractions make situation much worse. You have matrix 100 by 1000 & what do ye gonna do, if program calls matrix[10.4][94.2]????

[John Cuthber]

You too have missed the point.

I did say there were a finite number of possible entries. If those entries include 10.4 then you have to scale the input s so that 10.4 doesn't map to the same location as 10.3.

No computer really deals with decimals- the numbers all get represented as binary. Once you have that binary, you can use it as a memory address and look up the output from that memory without any further calculation- so there's no need for ant If statement.

That's easy enough to do.

 

The only thing Sensi seems to have been right about is the memory penalty and, since that was mentioned in the first post it's not an issue.

The question is can it be done in principle, and the answer seems to be yes.

[SarK0Y]

You too have missed the point.

I did say there were a finite number of possible entries. If those entries include 10.4 then you have to scale the input s so that 10.4 doesn't map to the same location as 10.3.

No computer really deals with decimals- the numbers all get represented as binary. Once you have that binary, you can use it as a memory address and look up the output from that memory without any further calculation- so there's no need for ant If statement.

That's easy enough to do.

 

The only thing Sensi seems to have been right about is the memory penalty and, since that was mentioned in the first post it's not an issue.

The question is can it be done in principle, and the answer seems to be yes.

John, i was playing w/ different approaches to avoid IFs as much as possible. precomputed table of func pointers ain't something new & 'tis really efficient thing for some cases. But situation of abnormal indices have been very curse for such approach. Yes, Jonh, we all are damn sure that computer deals w/ "0"s & "1"s. Meanwhile, "bad" indices can call wrong addresses. i consider you ain't gonna argue that situation is deeply bad for security & stability.

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

 

in fact, it's possible to avoid IFs entirely. Practically, mostly, it has zero or (very) negative effect upon performance. here i did do some hints on such techniques. meantime, it needs some remarks:

 

1. your if-free code at high level could become very if-stuffed in asm output thanks to compiler.

2. for the speed-up's sake, better off to use logical AND than multiplication.

============================================

significantly more efficient techniques are placed here.

 

Func pointers are good instrument to self-change algo on-fly, thereby it makes possible to minimize "dead" blocks. If to return precomputed matrices, i can add yet another moment: they're very bad in case of your example because you take short task & it turns into not just mindblowing waste of memory, but into waste of Time as well. E.g., deposit of $1k makes matrix 100x1000 to account each cent there. Data centers of banks shall be completely ruined by such method

[Strange]

 

in fact, it's possible to avoid IFs entirely.

 

But it is not possible to avoid conditional execution (if you want to create a general purpose computer / language).

[John Cuthber]

John, i was playing w/ different approaches to avoid IFs as much as possible.

You failed

I could use a laugh.

Can someone explain to me how, if we take a computer programme as a means to turn a finite set of input data into a finite set of output data, it can't be replaced by a look up table?

[SarK0Y]

You failed

I could use a laugh.

Can someone explain to me how, if we take a computer programme as a means to turn a finite set of input data into a finite set of output data, it can't be replaced by a look up table?

John, not sure of what you do mean & any reason of your laugh. expressions of logical & arithmetic operations w/ vars (& w/ pointers, in particurlar) definetely can substitute IFs. Another question has been, this way makes mostly a lot of "dead" runs, so performance suffers very much. Only for some cases, that substitution might pay off. much more efficiently to reduce number of cmp's op. for instance,

cmp %rdx, %rax
jXX
jYY
jZZ

'tis really significant speed-up in comparison w/

 

cmp %rdx, %rax
jXX
cmp %rdx, %rax
jYY
cmp %rdx, %rax
jZZ

[Sensei]

You failed

I could use a laugh.

Can someone explain to me how, if we take a computer programme as a means to turn a finite set of input data into a finite set of output data, it can't be replaced by a look up table?

You It seems to have very limited understanding of what is "computer program", which is sign of lack of experience in subject "writing real software". I have calculated that I have spend at least 81,000 hours writing software. People used to pay me for translating C/C++ code to assembler twenty years ago.

Typical computer program is waiting for external data to arrive at random order, at random moment of time, read from external source of data (such as i/o disk), downloaded from random source like Internet. Basically adopting to situation meet in environment and unknown in advance at compile time.

Your "computer program" has to have all data ready at run time... as you cannot have any loops, any conditional branches, abnormal exiting of loops...

 

Do you want to replace if( mouse_x == x ) with jump table? Then you have to do it at compile time.... You will make 640 entries jump table ready for 640 pixels wide screen, then new monitor manufacturer come by next year and make 800x600 monitor, and your code will simply fail with it...

You will make code ready for 800x600, the next year new manufacturer will come by with 1024.. Your code would have to be AI and self-modifying code to adapt to unknown situation spontaneously..

Repeat it several times over the last 20 years. I have personally 1920x1080 screens, but some my friends are now at 2560x1440. Conditional branch code will adopt automatically to different size of screen, while compile-time jump-table will be screwed.

Edited November 8, 2014 by Phi for All
author request

[SarK0Y]

Sensei, what is funny w/ lookup tables -- there is very need to test the indices for proper bounds. how to test them w/o IFs???

[Sensei]

I showed this thread to friend of mine, who was recently programming PIC microcontrollers.
He told me that his PIC doesn't have branch functions except one:

BTFSC z <skip the next instruction if Z flag is clear>
GOTO somewhere <branch taken if Z was set>
do stuff <branch not taken if Z was clear>

 

All instructions have fixed width, so BTFSC known in advance how many bits skip (12 bits per instruction!), without having offset parameter.

You have to jump by yourself to location you want.

Edited November 8, 2014 by Sensei

[John Cuthber]

Can you stop talking about efficiency and speed please?

It has nothing to do with the topic.

 

~The question in the initial post was "Is there some law of computation which states that `if` statements are unavoidable?"

Now, once again,

Can someone explain to me how, if we take a computer programme as a means to turn a finite set of input data into a finite set of output data, it can't be replaced by a look up table?

 

Sensei, what is funny w/ lookup tables -- there is very need to test the indices for proper bounds. how to test them w/o IFs???

If you have , for example, a pair of inputs that are each one byte wide and the table has an output for all the 65536 possible combinations of inputs, how can there be an index that's out of bounds?

 

 

 

Incidentally, Sensei, I realise that, if you have spent that much time doing things the conventional way, it might be difficult for you to explore alternatives.

At least read the question I asked and answer it, rather than citing bits of irrelevant code.

Edited November 8, 2014 by John Cuthber

[Strange]

Can someone explain to me how, if we take a computer programme as a means to turn a finite set of input data into a finite set of output data, it can't be replaced by a look up table?

 

There is a tiny subset of programmes which can be represented like that. They consist purely of combinatorial logic based on their inputs, have no loops and no stored state. There are few real-world programmes in this class apart from a few teaching examples like "get input from the user, convert it from miles to kilometers and display the result".

 

A general purpose computer (or language) must have stored state, the ability to jump to a destination address, and conditional operations (which does not necessarily mean "if" constructs). Or, more generally, it must be equivalent to a Turing machine or the lambda calculus.

[winger]

 

There is a tiny subset of programmes which can be represented like that. They consist purely of combinatorial logic based on their inputs, have no loops and no stored state. There are few real-world programmes in this class apart from a few teaching examples like "get input from the user, convert it from miles to kilometers and display the result".

 

A general purpose computer (or language) must have stored state, the ability to jump to a destination address, and conditional operations (which does not necessarily mean "if" constructs). Or, more generally, it must be equivalent to a Turing machine or the lambda calculus.

Whaaaaa? That doesn't even make any sense. You're not even spelling it right. It's programs not programmes.

 

There is a tiny subset of programmes which can be represented like that. They consist purely of combinatorial logic based on their inputs, have no loops and no stored state. There are few real-world programmes in this class apart from a few teaching examples like "get input from the user, convert it from miles to kilometers and display the result".

 

A general purpose computer (or language) must have stored state, the ability to jump to a destination address, and conditional operations (which does not necessarily mean "if" constructs). Or, more generally, it must be equivalent to a Turing machine or the lambda calculus.

computer (or language)? A computer is not a language and a language is not a computer. A programming language runs on a computer. The computer is the computer, the programming language is the programming language. What in heck are you talking about?

[Strange]

Whaaaaa? That doesn't even make any sense. You're not even spelling it right. It's programs not programmes.

 

Not where I come from. Although the foreign form has pretty much taken over now, so I am a little surprised to see I wrote that.

 

 

computer (or language)? A computer is not a language and a language is not a computer. A programming language runs on a computer. The computer is the computer, the programming language is the programming language. What in heck are you talking about?

 

It is an abstraction. The question is about what features are required to compute a general function. This can be considered from the point of view of a programming language (as the original question asked) or from the point of view of the hardware required (as someone else brought up). These are equivalent: a "thing" which implements either a Turing machine or lambda calculus can compute any [computable] function.

 

And I think it can also be shown that there is no extra functionality which would make the compute able to solve problems that the Turing-equivalent machine could not solve. (Apart from magic: knowing what the answer is. Such a machine is known as an oracle.)

 

But thanks for your useful contribution to the discussion.

 

Incidentally, for those without a degree in computer science (which didn't even exist as a subject when I went to university) one of the best non-technical explanations of the theory of computability is in Gödel, Escher and Bach by Douglas Hofstadter.

Edited November 9, 2014 by Strange

[John Cuthber]

 

There is a tiny subset of programmes which can be represented like that. They consist purely of combinatorial logic based on their inputs, have no loops and no stored state. There are few real-world programmes in this class apart from a few teaching examples like "get input from the user, convert it from miles to kilometers and display the result".

 

A general purpose computer (or language) must have stored state, the ability to jump to a destination address, and conditional operations (which does not necessarily mean "if" constructs). Or, more generally, it must be equivalent to a Turing machine or the lambda calculus.

Would you consider, as an example, a Space Invaders type game as being to complex to write without conditional branching?

[Strange]

Would you consider, as an example, a Space Invaders type game as being to complex to write without conditional branching?

 

Yes. There are an unlimited number of possible outcomes. As far as I know a theoretical "perfect player" could keep the game going for ever. (Although that may be impossible to prove, per the 'halting problem'.)

[John Cuthber]

I did already specify a finite system...

But a real player would eventually die.

Also, the usual game speeds up as time goes on so it's impossible for a real human to play it.

If nothing else, eventually the machine won't have enough memory to remember the score.

 

So, what about a computer game that goes on for no more than 100 years, because at that point it concedes defeat and announces that the player won?

 

Do you think that would that be complex enough to need conditional branching?

[Strange]

I could not begin to say what class of algorithms require conditional statements (of some form). As I say, I never studied computer science, what little I know comes from learning to program in functional languages, some general reading and talking to people doing research in formal methods. However, something like determining if a missile hits a target or not is essentially conditional.

 

However, if you are asking specifically about "conditional branching" as implemented in hardware, then that is a more difficult question. There are ways of implementing a general purpose (Turing equivalent) machine without conditional branching.

[John Cuthber]

A conditional branch is what an "If" statement lets you do.

It transfers program control to one of two (or more) places depending on some parameter or other.

I said conditional branching because it's possible to et the same effect as an "if" statement by using other functions or operations.

In VBA you can use Select Case to achieve the same sort of thing.

 

 

Do you think it is possible to write a 100 year space invaders game without using an If statement (or its logical equivalent)?

[Strange]

Do you think it is possible to write a 100 year space invaders game without using an If statement (or its logical equivalent)?

 

No. But I wouldn't know how to go about proving it.

[Sensei]

Would you consider, as an example, a Space Invaders type game as being to complex to write without conditional branching?

 

Let's split such Space Invaders to parts:

 

It has main loop which does:

- clear screen, redraw background, redraw current state of all displayable objects. Redraw score on top. Swap buffers (without double buffering, display would be flashing)

- there are two dynamic arrays with unknown length: array of missiles, array of UFO objects attacking.

- missiles fired by player has simply y=y-1 performed each frame to move them in time. UFOs missiles have reverse.

- UFO object movement. For loop for every UFO object in array and perform change in direction.

- collision checking requires comparing every existing missile with every existing UFO object (this is the simplest algorithm and the slowest, begs for sorting objects in different axes and comparison only those who are close, otherwise with ufo_count=100, and missile_count=100 we will end up with 10,000 comparison every frame * 30 FPS = 300,000 per second):

- when if( ( missile->left_x > ufo->left_x ) && ( missile->right_x < ufo->right_x ) && ( missile->top_y > ufo->top_y ) && ( missile->bottom_y < ufo->bottom_y ) ) missile hit UFO object, and such object is deleted from array. Missile is also removed from its own array. It might be delayed - to show object is exploding. Score is increased.

- when missile->bottom_y is less than 0, or missile->top_y > height, missile passed screen and is removed from array.

(left_x,top_y,right_x,bottom_y are in range of screen resolution of currently picked by user in options, or default desktop resolution (unknown at compile-time))

- check whether user pressed left, or right key and move player's object accordingly increasing or decreasing it's position.

- check whether user pressed fire, make new missile object and add it to the array.

- check whether player has been hit by some UFO missile.

- check whether player has been hit by other UFO object.

- wait for vertical blank synchronization (to have f.e. 30/50 frames per second). (some old game missed it, or was implementing it as counting down for() loop, and are now unplayable on emulators, runs hundred times faster than on original machine)

 

Now John, please provide code without conditional branches which is responsible f.e. collision detection..

And other mentioned parts.

Edited November 9, 2014 by Sensei

[John Cuthber]

Odd as it may seem, I didn't say I'd provide code.

 

Lets make a few assumptions.

The person playing doesn't have infinitely fast reflexes.

For the sake of having a number, let's say he doesn't react to a change on the screen, or press a button in less than 0.01 seconds

He won't live forever. For the sake of discussion, can we keep the condition that if he's still playing after 100 years, the computer concedes defeat?

The input to the machine is a few switches - a joystick , fire button and perhaps a couple of other controls. (It doesn't really matter how many inputs there are as long as it's finite so you can have a trackball or some such if you want. . If you do that I will say we can connect it to a couple of A to D converters and just have a dozen or so inputs for x and y)

 

The outputs are a screen- we can easily model that as being memory mapped more or less directly to an LCD device- and a sound generator.

That sound generator has a handful of inputs which turn it on or off an d decide the pitch (there might be a few "voices" if it needs to be polyphonic or to do speech synthesis or whatever)

 

 

Happy so far?

[Sensei]

Yes. There are an unlimited number of possible outcomes. As far as I know a theoretical "perfect player" could keep the game going for ever. (Although that may be impossible to prove, per the 'halting problem'.)

LCD screen 1920x1080 24 bit color has

1920*1080*24=49766400 bits

so there is [math]2^{49766400}[/math] possible states.

 

CD sound has 44100 Hz, 16 bits, 2 channels has:

44100*16*2=1411200 bits

so there is [math]2^{1411200}[/math] possible states.

(my calculators refuse showing how much it's in decimal, error out of precision)

 

Interesting question appeared: how many (billions) years we could play without seeing the same setup of pixels twice.

30 FPS * 60 * 60 * 24*365,25 = 946728000 (approximately 2^30=1073741824)

Nearly billion unique frames per year..

 

But there is theoretically possible [math]2^{49766400}[/math]

 

Odd as it may seem, I didn't say I'd provide code.

Because you wouldn't been able, to your own example..

Edited November 9, 2014 by Sensei

[John Cuthber]

OK, big numbers.

So?

Incidentally, you forgot the potential need to refresh them 100 times a second for a century.

That's roughly 3E11 time points you need.

 

However,nobody said this would be sensible or practical.