2
$\begingroup$

I could guess why computers have arithmetic operations like add, sub, and mult instructions. It is to compute numbers, but I don't get why branch and jump instructions exist. I am asking what theory or purpose for implementing branch and jump instructions is there? I've tried to get rid of branch and jump instructions and what effect it will cause on the computation, but I could not get the result.

$\endgroup$
  • 5
    $\begingroup$ How much programming experience do you have? $\endgroup$ – Yuval Filmus Oct 16 '16 at 8:15
  • $\begingroup$ How else do you program if-else conditions? $\endgroup$ – shapiro yaacov Oct 16 '16 at 9:26
  • $\begingroup$ There was a recent question about calculating GCD. Try implenting this without branch and jump instructions. $\endgroup$ – gnasher729 Oct 16 '16 at 10:10
  • 1
    $\begingroup$ Because they are a way to obtain Turing-completeness. $\endgroup$ – Raphael Oct 16 '16 at 18:50
  • $\begingroup$ Actually, branch and jump are much more important than the arithmetic operators. Look at the definition of a turing machine. $\endgroup$ – gardenhead Oct 16 '16 at 22:22
9
$\begingroup$

Theoretically speaking you do not need any branch and jump instructions. This is so because you can encode them into artihmetic. For instance, instead of writing

if p:
   x = a
else:
   x = b

you can write (assuming that $0$ stands for "false" and $1$ for "true"):

x = p * a + (1 - p) * b

Gödel was the first to have realized that when he proved his incompleteness theorem, namely that arithmetic sufficies for all of programming, theoretically speaking. So in this sense you are correct.

Supplemental: we do need some sort of iteration or recursion, as was noted in the comments. By "arithmetic" here I mean general recursive functions which have recursion built in. There is a form of "conditional" in recursion, namely the distinction between zero and a successor.

However, it is impractical to insist that arithmetic is somehow the most important thing. There are many different ways to do computation. For instance, we do not even need any arithmetic or recursion, we could use just pure $\lambda$-calculus, which is a pure theory of functions, without any numbers, booleans, or any other form of data (they can all be built up). Which paticular form of computation should be used actually depends on many factors: What does the hardware support? What makes programming most maintainable? How do we make programs efficient? And so on. The actual programming languages and CPUs that we know today are the result of many years of experience. It's turned out that it's better to have conditional branching than not.

$\endgroup$
  • 2
    $\begingroup$ You also need to implement loops somehow, otherwise the output is always polynomially bounded in the input (assuming only $+,-,\times,\div$ are allowed). How do you implement a loop using arithmetic expressions? $\endgroup$ – Yuval Filmus Oct 16 '16 at 13:08
  • $\begingroup$ @YuvalFilmus Do the combinators have something to do with this? $\endgroup$ – CinchBlue Oct 16 '16 at 14:35
  • $\begingroup$ There are cases where you can use arithmetic tricks (and computers / compilers actually do that). But consider this: if p: print "p is true" else: print "p is false". $\endgroup$ – gnasher729 Oct 16 '16 at 15:38
  • $\begingroup$ Indeed, we need a form of recursion, such as primitive recursion or general recursion. I have updated the answer. $\endgroup$ – Andrej Bauer Oct 16 '16 at 21:14
2
$\begingroup$

There are many, many different ways to perform computations, but any general-purpose computer has some form of conditional execution, and some way to repeat a computation with different data.

We have invented many models of computation, and it turns out that all the ones we think of as sufficiently powerful are equivalent. A sufficiently powerful model of computation is said to be Turing complete. There are of course models of computation that aren't Turing complete, but they feel restricted: you can't do as much with them. Pretty much all programming languages are Turing complete if you ignore the fact that computers have finite memory (and reasoning about computers with large but finite memory is so hard that we normally approximate the memory as infinite).

A computer that doesn't have any way to compute conditionally or to repeat a computation can effectively perform only the particular sequence of instructions that it was programmed to do. That lets you define some simple operations, but not much. If there's conditional execution but no repetition, then the program can behave differently depending on the data, but there is effectively a finite number of different behaviors. If there's repetition but no conditional execution, then a program either always terminates or never terminates, there's no way for a program to terminate or not depending on the data. To write all possible programs, both conditional execution and repetition are necessary.

In practice, to write most interesting programs, both conditional execution and repetition are necessary. Exactly what programs you can write without them depends on what basic operations you allow, but it won't be much. For example, if you only have the basic four operations on integers (+, -, *, /) then something as simple as primality testing can't be done without repetition (e.g. to repeat trial division) and branching (to exit the program once the answer has been found).

Conditional execution and repetition aren't enough to be Turing complete: you also need some way to use an unbounded amount of memory. But that's a story for another time.

In low-level imperative programming, conditional jumps are the usual way to implement conditional execution and repetition (you repeat by jumping to an earlier point in the program). In a higher-level imperative program, repetition is expressed via looping.

In other models of computation, conditionals and repetition may be derived from other primitive functionality in a non-obvious way. For example, one of the most important models of computation, the lambda calculus, does not have a conditional feature or a repetition feature per se. Lambda calculus has just one computation rule, called beta reduction: “if you apply the function that maps $x$ to $M$ to the argument $N$, then the result is $M$ in which $x$ has been replaced by $N$”. It indirectly permits repetition because there can be many occurrences of $x$, and so $N$ is repeated. It indirectly permits conditional execution because the lambda calculus doesn't distinguish between data and code, and the argument of a function can be treated as a function and executed, resulting in behavior that depends on the argument. So conditionals, repetition and unbounded memory (like repetition, arising from the repetition of the argument in the substitution) are all present.

In fact, conditional branching and unbounded memory are all you need to make a Turing complete model of computation. A suitably-chosen one-instruction set machine is Turing complete. Many such instructions involve a subtraction in addition to the conditional branching, because it's convenient, but arithmetic is not actually necessary, it's just convenient to access memory. Turing machines, another very important model of computation, doesn't include anything like arithmetic, just conditional branching (inside the finite automaton, conditional because it depends on the value read from the tape) and the tape for memory. Likewise the lambda calculus doesn't have anything like arithmetic in its rule, but you can build arithmetic above the lambda calculus.

$\endgroup$
  • 1
    $\begingroup$ In theory looping can be provided with wrap-around addressing (having to execute through the entire instruction address space to get to the "jump" back to the beginning of the loop body is a little inconvenient). $\endgroup$ – Paul A. Clayton Oct 17 '16 at 0:06
  • 1
    $\begingroup$ @PaulA.Clayton That would be one way to provide repetition, indeed. $\endgroup$ – Gilles 'SO- stop being evil' Oct 17 '16 at 0:24
1
$\begingroup$

A very short example.

Let's say you need to write a program that get three variables:
a is an integer.
b is an integer.
op is an operand (can be only + or *).

Lets say you know how to calculate a+b and also a*b.
You also know how to process what op is (+ or *).
All that is left is to perform the relevant calculation.

How do you suggest doing this without a jump or branch?

$\endgroup$
  • $\begingroup$ You could implement it with conditional instructions. $\endgroup$ – David Richerby Oct 16 '16 at 11:12
  • $\begingroup$ This is a trivial case that can be and often is implemented without branches using conditional instructions, for example conditional assignment. The disadvantage is that both a+b and a*b would have to be evaluated. In more complicated cases this becomes inefficient. $\endgroup$ – gnasher729 Oct 16 '16 at 15:41

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.