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

[Strange]

You can, of course, contrive any number of examples where conditional code is not needed (although, I am not convinced that is possible in this case because of the non-deterministic [from the point of view of the program] user input).

 

However, the original question was about the general principle; in which case, a general purpose computing device (or language - just to annoy winger) must include conditional execution in some form.

[Sensei]

However, the original question was about the general principle; in which case, a general purpose computing device (or language - just to annoy winger) must include conditional execution in some form.

Like I showed in post #20 we just need math/move operation performed on PC register, like any other register.

 

Imagine we have calculated new PC register value in temporary data register, and then MOVE.L D0,PC (equivalent to JMP (D0) or GOTO (D0))

Branch is taken when D0 is not equal to current PC, and branch is not taken when D0 is equal to current PC.

[Strange]

Like I showed in post #20 we just need math/move operation performed on PC register, like any other register.

 

Imagine we have calculated new PC register value in temporary data register, and then MOVE.L D0,PC (equivalent to JMP (D0) or GOTO (D0))

Branch is taken when D0 is not equal to current PC, and branch is not taken when D0 is equal to current PC.

 

That may be one way to implement the operation but says nothing about whether it is required or not.

[John Cuthber]

 

...

 

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

And, once more I will point out that nobody said it would be practical.

 

Ok, so here's how to design the computer that plays space invaders without an IF statement.

 

You need a really big stack of ROM memories (don't bother trying to do this at home, Sensei's arithmetic has already shown it won't fit into the universe).

Each one needs some address data- specifically, it needs the inputs from the joystick and so on, and also it needs a wide enough address bus to map the whole of the display memory as an input (That memory is an out put too but I will get back to it)

So, the address bus is something like 49766400 bits wide (Plus a few more for the joystick etc)

And, you need a memory of that size for each time point

So you need something like 3E11 of those memory chips.

Each memory address must point to some stored data- a wide enough word to include the screen and the sound generators.

And, of course it needs a wide enough data bus to spit that data out.

We then take that data and put it into a temporary store (that component is one of the few that's perfectly reasonable.

 

We also need a clock. We can have that tick at 200 Hz.

It needs a bit more hardware to do the synchronisation but the simplified version is that on every odd numbered clock cycle, it transfers the output from the huge memory to the output memory (and copied it to the screen- that's a massive parallel transfer but it's also roughly the throughput of the optic nerve)

On the even numbered clock cycles it increments a timer by 1 and feeds that to a 1 of 3E11 selector which selects the memory we are looking at.

It copies the output memory to the input address bus and it also copies the inputs from the joystick etc to the relevant bits of the address bus.

 

The tricky part is programming the ROM.

It needs to know what to send to the screen in any given circumstances of

how long the game has been in play,

what buttons the player is pressing and

(here's the bit that makes it deterministic)

the current state of the output- i.e. what's on the screen (and the sound generator).

 

The screen acts not just as an output, but also as the "working memory"

So, for example, the score isn't remembered explicitly as a score and incremented when he hits something, it is remembered as a pattern of dots on the screen.

 

 

OK, it's fair to say that Atari are not going to be adopting this any time soon but there are two important things to note.

The first is that it is , in principle, possible to write a Space Invaders game without using a single IF statement.

(That's what the thread was about)

 

There's another point.

 

How else can you write a Space Invaders game with a 200Hz clock rate?

 

There are circumstances where that increase in effective speed outweighs the impracticality of calculating all the answers in advance.

 

That's also why, if I ask you what five times nine is, you remember the answer, rather than counting it out on your fingers.

 

 

 

 

It also enables the memory chip so it outputs the data stored in the relevant address of the rom to the output memory

[Sensei]

It also enables the memory chip so it outputs the data stored in the relevant address of the rom to the output memory

Only when size of memory that is copied is fixed.

 

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

{

dst[ i ] = src[ i ];

}

 

can be unrolled to:

 

dst[ 0 ] = src[ 0 ];

dst[ 1 ] = src[ 1 ];

dst[ 2 ] = src[ 2 ];

dst[ 3 ] = src[ 3 ];

(to not use if() and loop)

 

But if code is:

 

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

{

dst[ i ] = src[ i ];

}

 

You can't unroll loop that has unknown size..

 

You can argue that int has fixed size 4 bytes = 32 bits = 2^32 possible states = 4294967296

So you would prepare 4294967296 different sets for different 'size'.

Ok. But then I can make dynamic integer C++ class that's dynamically changing its size, once x++ is reaching 4294967296 new buffer is allocated and now has 8 bytes = 64 bits = 2^64 possible states. Then after a while when x++ will reach 18446744073709551616 new 4 bytes space is allocated and counter is still going. And it'll be going forever (in practice to out of memory situation in real computer).

 

How are you going to prepare in advance infinite quantity set for infinite large number?

Edited November 9, 2014 by Sensei

[John Cuthber]

I seem to have screwed op the typing a bit there

the line you have quoted is out of place. It should be just before

"The tricky part is programming the ROM."

 

So that might affect your reply but I don't see how it can be relevant.

There is no loop.

and

All the memories, though huge, are finite (and almost all of them are fixed ROMs).

 

(except the "accidental" one where if you keep incrementing the "time" for long enough it will roll over to all zeroes again which is fine- the last two hundred or so instructions put a message on the screen saying it concedes. A second after the 100 years is up, the game starts over from scratch)

 

"How are you going to prepare in advance infinite quantity set for infinite large number? "

What infinitely large number?

[SarK0Y]

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?

John, it's unfair if you use all available virtual space, YeZzzzzzzz -- the're no ways to go beyond. But-but-but… for 8-bit machine, it's 2^8 addresses, 64-bit -- 2^64 ones. Not juicy to init that much for each time

 

 

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

Yes, you can avoid jXX ops in code entirely, but you need to use "call" op as alternative to jXX's. In short, you have no ways to abandon IFs as class.

[Strange]

The tricky part is programming the ROM.

 

Indeed. You are basically storing every possible game. But there are couple of problems with this (with respect to the original question).

 

Firstly, you can't just play back a particular game; you need to respond to input. This means that the system is a giant finite state machine (FSM) where the frame buffer is used to store the current state; the next state is determined by user input. This is implicit conditional execution.

 

But, apart from that, how do you know what to put in the ROM? The only way of working out the ROM content is to write a program and play (or simulate) every possible game!

 

This comes back to the example I was going to use before you went totally bonkers: generating digits of pi. You could, of course, have a big ROM and a bit of logic to output the first N digits if you knew what they were. But to calculate the digits, you need a general purpose computer.

[John Cuthber]

As I said "The tricky part is programming the ROM."

Fortunately for me, having pre-calculated the states of play is part of the original design brief:

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

 

I grant you that calculating them would need a conventional programme (and a long one at that).

 

But, once I have the table I can look up the outputs for any programme as long as it has finite possible inputs and finite possible outputs.

If, on the other hand, we look at programmes that have infinitely wide ranges of inputs and outputs, they might never finish.

So, OK I can't calculate all the digits of pi without using an If statement.

 

But you can't write a programme that tells me all the digits of pi with if statements.

.... In short, you have no ways to abandon IFs as class.

I just did.

[SarK0Y]

 

But you can't write a programme that tells me all the digits of pi with if statements.

all programs use mostly precomputed consts w/ needful precision. frankly, John, i don't understand what you stand for. we use precomputed vars to boost code -- 'tis rather routine practice. we use if-reducing approches as well for. But fully IF-less codes are extremely limited things & mostly they're Just things for fun

[Strange]

But you can't write a programme that tells me all the digits of pi with if statements.

 

I didn't say "all".

 

 

I just did.

 

No you didn't. The "next state" decision (based on user input) is a conditional decision. The main thing you are getting rid of in your approach is loops.

[SarK0Y]

 

No you didn't. The "next state" decision (based on user input) is a conditional decision. The main thing you are getting rid of in your approach is loops.

at asm level, loops are using jXX's, so they're just variation of IFs only situation to avoid loops is, when we get const number to run a loop.

[Endy0816]

Pure css/html games probably come the closest to what is being described here. No if statements though do utilize check/radio boxes(typically) to keep track of the program state.

[Sensei]

Pure css/html games probably come the closest to what is being described here. No if statements though do utilize check/radio boxes(typically) to keep track of the program state.

 

AFAIK css/html games use JavaScript a lot. F.e. if you have implemented ONCLICK="itemname.style='xxx'" it's exactly inline JavaScript. all ONxxxx="code" are execution of JavaScript code.

 

Save this to index.htm and open in browser (checked Firefox 33,Chrome 38,IE6 only):

 

<html>

<body>

<div id="xxx" onclick="xxx.style.color='#FF0000';">

Click me!

</div>

</body>

</html>

Edited November 10, 2014 by Sensei

[Endy0816]

Pure, not one of those hybrids. A couple of representative examples, though there are a number out there.

 

onSpaceStart

Pure CSS Game Pad(demo)

Edited November 10, 2014 by Endy0816

[John Cuthber]

 

No you didn't. The "next state" decision (based on user input) is a conditional decision. The main thing you are getting rid of in your approach is loops.

 

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.

Edited November 10, 2014 by John Cuthber

[Strange]

 

No you didn't. The "next state" decision (based on user input) is a conditional decision. The main thing you are getting rid of in your approach is loops.

 

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.

 

 

If there were no choices being made, then the game would continue in exactly the same way independently of the user's input (which wouldn't be much fun).

 

You have created an FSM with the next state determined by user input:

 

On the even numbered clock cycles it increments a timer by 1 and feeds that to a 1 of 3E11 selector which selects the memory we are looking at.

It copies the output memory to the input address bus and it also copies the inputs from the joystick etc to the relevant bits of the address bus.

 

That input then changes the state (i.e. what is stored in your frame-buffer) which determines how the FSM will respond to the next set of inputs. You may have eliminated "if" statements (because you have hardwired it) but you have not eliminated conditional behaviour. The state transitions are, by definition conditional (except for the trivial case where there is only one exit from a state).

 

This is a standard way of translating software (or a specification) to a hardware implementation - either manually or using automated tools.

 

An FSM is not quite equivalent to a Turing machine, but this is because it doesn't have working memory not because it doesn't have conditional execution. Therefore, not all programs can be turned in state machines, which means that your solution does not always apply.

[John Cuthber]

Fundamentally there's an implicit conditional branch of sorts in the logic

In the memory there's some sort of circuitry that chooses the right flip-flop (or capacitor or whatever) to store data in.

Something like the tiny scarp of circuitry shown.

Well, the gates in that are conditional.

the output of an AND gate is conditional on its inputs.

 

 

At that level, since it's not possible to make a digital computer without gates, it's not possible to make a programme that runs without conditional branching.

 

I might have to think a bit to see it f it can be done with an analogue computer (without comparators).

[Strange]

Fundamentally there's an implicit conditional branch of sorts in the logic

 

It is not (just) in the logic. IT IS A STATE MACHINE. Therefore, it is conditional. That is what "state machine" means. Sheesh.

[John Cuthber]

True, but if the answer to the original question is tautologically "no" then there's no fun to be had debating it.

[Strange]

Fun? Fun?? Bah. Humbug!

[SarK0Y]

I might have to think a bit to see it f it can be done with an analogue computer (without comparators).

Analogue computation summarize continuous functions as output. meantime, you need to infiltrate any noises. Thereby filters are comparators of AC's

[John Cuthber]

If I wanted a comparator in an analogue computer I would, with no great originality, use a comparator.

 

It's been a while since anyone said anything to do with the topic.

I wonder if Dark Falz is happy with the way the thread went.

[SarK0Y]

If I wanted a comparator in an analogue computer I would, with no great originality, use a comparator.

comporators/filters can be of the different kind

 

It's been a while since anyone said anything to do with the topic.

I wonder if Dark Falz is happy with the way the thread went.

He's got his answer