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.

FunCPU - Evaluation Strategy

It is not trivial how expressions should be reduced, i.e. evaluated. I have already mentioned that while some strategy could be fruitful in reducing an expression in a given interpretation, others may be not.

Let us have a look at the following simple example of evaluation of the factorial function is defined under the alias fac.
fac(n):= if n=0 then 1 else n*fac(n-1)

The reduction of fac(1) may lead to

if 1=0 then 0 else 1*fac(0)
If 1=0 then 0 else 1*(if 0=0 then 1 else 0*fac(-1))
If 1=0 then 0 else 1*(if 0=0 then 1 else 0*(if -1=0 then 0 else -1*fac(-1))) .......

We can easily see that the reduction goes on forever, it never terminates.

The goals of the evaluation strategy are as follows:

• Must terminate (simple applicative rules may result in infinite loop)
• Must be efficient (as possible).
• Must be simple (suitable to be represented in hardware directly).

The following strategy will be applied:

A user-defined function is reduced if and only if all of its arguments are constants. Similarly, inc and dec are reduced only, if their arguments are literals. As far as if-then-else is concerned: if its condition part is constant 0 (i.e. true), then it is reduced to exp1. If the condition part is a constant other than 0, then it is reduced to exp2. Othewise the reduction is postponed.

Corollary: all parameters passed to functions are constants.

The reduction algorithm is as follows:

1. Scan input expression symbol by symbol.
2. Copy symbol from source to output if symbol is not a function, or its a function but cannot be reduced in its current form (i.e. contains at least one argument, which is not a constant).
3. Evaluate functions (if, inc, dec, and user-defined) if possible. That is, rewrite the function call by replacing the call with the function definition with bounded arguments.
4. If EOX symbol is found, then the whole cycle restarts. Note: in the next cycle: the current output becomes the input and vice versa.
5. Stop, if the first symbol is a constant. This literal is the result of the reduction.

It is clear that inc, dec terminates immediately, thus reduces the length of expression. The expression size also shrinks when in the expression „if cond exp1 exp2” cond is a constant. Eventually everything is based on/can be reduced to the three built-in functions. Therefore sooner or later, all „if”, „inc”, „dec” are evaluated/reduced, thus the evaluation terminates (if this is possible). 

FunCPU - Memory Models

Needless to say that not only initial and final expression, but also temporary expressions should be stored in memory somehow. The way of how expressions are represented has impact on hardware design.

During reduction the cycles, expression symbols are being copied one by one. When a function symbol is found, then the symbol itself along with possible other consecutive symbols are rewritten in accordance with the function definition (this is used in a broader sense, and includes definition of built-in functions).

Please note that the following discussion is related only to expression evaluation, as user-defined functions are stored in a separate memory, possible in ROM.

Separate source and destination memory

Separate fragment of memory is used for source and destination expressions. Upon each reduction cycle the role of the memories are swapped. Source memory will become destination and vice versa. This is illustrated in the figure below. 

If l is the longest possible size (in memory cells including EOX) of the expression during the evaluation, then the minimum memory requirement is 2xl cells.

Shared memory, with index increasing and decreasing

A shared memory can also be used. In this case source index is increasing, whereas destination is decreasing while copying symbols. After each evaluation cycle, the role of the indexes will be swapped again. This memory model may be more econimic, since in some cases it will be suitable to reduce expressions over half of the memory size, provided that the reduced expression becomes smaller, satisfying the following equation, which in fact should hold in every cycle: e+r≤m, where e, r and m denote expression size (excluding EOX), reduced expression size and memory size respectively.

Shared memory with index following

The last model is also comparable to the previous one in econimical terms, as the same equation among expression lengths and memory size must hold. However, it has the additional benefit, namely that index roles do not need to be changed. This simplifies hardware design, as multiplexers (swapping the source and destination registers) and its relevant control signal and logic can be avoided.  As source index reaches the end of input expression marked by the EOX symbol, it should just copy and step over that symbol and the continue with the next reduction cycle. If memory end is reached, then indexes will wrap around starting from a lower location.