2014-08-30

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.

2014-08-23

FunCPU - Some Functions and Predicates

Let us have a look at some elementary functions and predicates to have a better look and feel how FunCPU works. The definitions of these objects will be suppmented with their assembly code counterparts written directly in FunCPU machine code.
In the subsequent section, the following encoding is used:
FC - increment function
FD - if-then-else
FE - decrement function
FF - end of expression
Identity function

I(x):= x 
7F FF
Constant function
C(x):= c
„c” FF, where c=00..7B
Please note that as 7C and above, up to 7F denote arguments, therefore it is impossible to write a constant function directly, which returns these values. For example, as we have seen 7F FF denotes the one-argument identity function.
Fortunately we can overcome this limitation by defining the function "7C FF" as follows:
FC 7B FF
That is, essentially, incrementing the value 7B to get the 7C.
Or analogously,
FE 00 FF

represent the constant function 7F.
Please note this will work, as functions will be evaluated by unfolding the function definition and inserting into the expression memory. In the expression memory no distinction is made between constants and arguments, they are all being treated in the same way.
Few Predicates

not(x):=  if  x  then  1    else  0
FD 7F 01 00 FF

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

FD 7F 7E 82 FE 7E FE 7F FF

Assuming that "=" definition is stored at address 00.
>(x,y):=  if  x=0  then  not(y) else  >(dec(x),dec(y))

FD 7E 8A 7E 92 FE 7E FE 7F FF
Assuming further, that "not" and ">" definitions are stored at 10 and 20 respectively.
Some functions
add(x,y):=  if  y=0  then  x  else  inc(add(x,dec(y)))
FD 7F 7E FC 82 7E FE 7F FF
Assuming that "add" is stored at 00.
 mul(x,y):=  if  y=0  then  0   else add(x,mul(x,dec(y)))
 FD 7F 00 82 7E 92 7E FE 7F FF
Assuming that "mul" is stored at 20.
fac(n):=    if  n=0  then  1  else  mul(n,fac(dec(n)))

FD 7F 01 82 7F 9B FE 7F

Assuming that "fac" is stored at 30.
As one can see, a whole set of interesting and useful functions and predicates can be built, one based on another. So the three atomic functions along with the potential of user defined functions and (recursive) function calls make it possible to define arbitrary complex functions (in theory, in reality memory constraints put limitation on the set of definable functions).
A more complex function is the Ackermann function, which is recursive, but not primitive recursive.
ack(m,n):=
if m=0 then inc(n)
elsif n=0 then ack(dec(m),1)
else ack(dec(m),ack(m,dec(n)))
FD 7E FC 7F FD 7F 82 FE 7E 01 82 FE 7E 82 7E FE 7F FF 
where "ack" is defined at location 00.
We can already "feel" that the FunCPU is Turing-complete... 

Here is a short video on evaluation of mathematichal functions:


2014-08-02

Intefacing with the Functional CPU

Now let us take a look at how the functional CPU (FunCPU for short) can be programmed in reality, from the programmer’s point of view.


This will be covered by looking at each gizmo  (i.e. button, switch, LED, etc.) on the front/control panel.
On the bottom right side, the purpose of the power switch is self explanatory.
On the  bottom left side,  the switch is used to select between run and edit mode. In edit mode, the functions and/or expressions can be entered/modified/displayed. The computation can be initiated by pressing start button, only when the edit-run switch is turned to run mode.
The third switch is provided to switch between editing functions and expressions.
The two rotary switches next to it, are used to enter the 8-bit physical address in hexadecimal mode. The current physical address (both in edit or run modes) are indicated by the 9  address indicator LEDs. The most significant, the 9th bit LED is on, when expressions are edited in edit mode, or when in run mode the expression symbol is selected by the CPU.
Similarly, the current data byte stored at the actual address is displayed by the LEDs labelled Data.  Under these LEDs the eight switches are provided to enter or modify data in binary mode.
Store button (only working in edit mode) is actually used to enter the 8 bit value in either to function memory or expression memory depending on the position of the Func/Exp switch. When the store button is released, the previous data byte displayed by the 8 data LEDs, is overwritten, and the new value is displayed.
The most significant bit (8) denotes whether the value is a function (LED is on) or a constant (or possibly an argument) (LED is off). The following 5 LEDs as suggested by their corresponding label give the physical address of the user-function. The actual address can be obtained by multiplying this 5 bit value by 8 (or simply shifting it left three times). The last two LEDs encode the arity of a user-defined function: 00 , 01, 10, 11 represent arity 4, 3, 2 and 1 respectively.
Finally, some important values in binary form:
  • 0000 0000 – zero
  • 0111 11xx – argument 1, 2, 3  or 4 (in function mode)
  • 1111 1100 – dec function
  • 1111 1101 – if function
  • 1111 1110 – inc function
  • 1xxx xxaa – user-defined function at address %xxxx x000 with arity aa, provided that it is different from the code of the 3 built-in functions described above
  • 1111 1111 – end of expression / function
Current machine state is indicated by the four LEDs labelled as State. The initial, starting state is 0000, whereas 1111 denotes the succesfull termination of the computation. In the latter case, the result of the computation is displayed by the data LEDs in binary model.