FunCPU - Evaluating 1+1

It is high time we turned our attention to a complex mathematical problem. Namely, how FunCPU computes:
1+1=?

Please recall that the definition of "add" is stored at 00 (referenced by 82) is as follows:

add(x,y):=   FD 7F 7E FC 82 7E FE 7F FF

The following is an extract from the FunCPU expression memory, which clearly indicates how a simple expression is stored, evaluated and reduced to a final result.

  : 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
00: 82 01 01 FF FD 01 01 FC 82 01 FE 01 FF FC 82 01 
10: 00 FF FC FD 01 00 FC 82 00 FE 01 FF FC FC 82 00
20: 00 FF FC FC FD 00 00 FC 82 00 FE 00 FF FC FC 00 
30: FF FC 01 FF 02 FF .............................

Where different colors denote different expressions as illustrated below:
- Initial expression 1+1
- the result
- first instance of unfolded, bounded function definition
- third cyle, after "if" condition is evaluated

As the above extract reveals, in the first cycle, the function definition is unfolded with the arguments bounded simultaneously. Then the "if" expression is evaluated. Since second argument is not zero, the else part is copied to the third cycle. Note, that the second argument now is reduced, thus add(1,0) is called. The result of this call is incremented, thus effectively expression became 1+add(1,0).

The following extract depicts the state of the expression memory at the final stage, when fac(5) is calculated. Result is shown in green. One can see, that evaluating fac(5) has required quite a many cycles (this is basically due to the low level of efficiency of the built-in functions inc and dec), and the original expression calling fac(5) is overwritten.

    00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
00: FF FC FC FC 75 FF FC FC 76 FF FC 77 FF 78 FF FC
10: FC FD 03 71 FC 82 71 FE 03 FF FC FC FC FC FC 82
20: 71 02 FF FC FC FC FC FC FD 71 02 FC 82 02 FE 71
30: FF FC FC FC FC FC FC 82 02 70 FF FC FC FC FC FC
40: FC FD 02 70 FC 82 70 FE 02 FF FC FC FC FC FC FC
50: FC 82 70 01 FF FC FC FC FC FC FC FC FD 70 01 FC
60: 82 01 FE 70 FF FC FC FC FC FC FC FC FC 82 01 6F
70: FF FC FC FC FC FC FC FC FC FD 01 6F FC 82 6F FE
80: 01 FF FC FC FC FC FC FC FC FC FC 82 6F 00 FF FC
90: FC FC FC FC FC FC FC FC FD 6F 00 FC 82 00 FE 6F
A0: FF FC FC FC FC FC FC FC FC FC FC 82 00 6E FF FC
B0: FC FC FC FC FC FC FC FC FC FD 00 6E FC 82 6E FE
C0: 00 FF FC FC FC FC FC FC FC FC FC FC 6E FF FC FC
D0: FC FC FC FC FC FC FC 6F FF FC FC FC FC FC FC FC
E0: FC 70 FF FC FC FC FC FC FC FC 71 FF FC FC FC FC
F0: FC FC 72 FF FC FC FC FC FC 73 FF FC FC FC FC 74

On (in)Efficiency of FunCPU

On Data and Program Representation

The computation (expression reduction) process is based on string manipulations (copy, insert, replace, etc.). The input string is scanned symbol by symbol until the string is reduced to an integer. This may happen in some cases, but may not in others. In the course of this scanning/copying operations built-in functions as well user-functions are evaluated. We will refer to a series of such scan/copy activities as cycle, until the expression end tag is reached. Please note that there is some optimization at work, so that, for instance, when copying the string

FC FE FC 00 (representing inc dec inc 00)

it is immediately reduced (that is to say in the very same cycle during scan/copy loop) to

FC 00 (representing inc 00), and then to 01

In this way some cycles can be saved. Otherwise the chain of reduction would be like this:

FC FE FC 00 => FC FE 01 => FC 00 => 01

Note each reduction happens in a separate cycle.

Still the clear disadvantage of this evaluation process lies in the facts that:

• high number of cycles (this is further detailed in the section below) are required;
• a relatively big number of symbols are copied/moved in each cycle.

On CPU Cycles

The FunCPU is quite inefficient, that is to say, each calculation requires quite many cycles. Actually too many. This is basically due to the very low level built-in functions, i.e. inc and dec. To illustrate this, just imagine how two integers are added. For example, x+y requires just y cycles to increment x (using the definition of “add” function as outlined below), that is, to add y to x, not to mention the additional cycles required for unfolding the “add” function, evaluating the if-then-else expression, etc.

add(x,y):=  if  y=0  then  x  else  inc(add(x,dec(y)))

It is worth noting that although addition is commutative, the computation of x+y and y+x requires different number of cycles (and thus execution time) provided that x and y are different integers. Of course, to eliminate this undesired property, one can define a more clever addition function, which swaps its arguments initially in order to minimize the number of cycles required.

It is quite straightforward to think of introducing higher level functions, such as addition, subtraction, multiplication, division, etc. Needless to say, that with such richer set of built-in function the efficiency of computation process is highly increased at the price of a more complex architecture.