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:

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.

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.

FunCPU - Functional Encoding Scheme

In the previous post we have seen how 8 bit symbols represent literals, arguments, functions, etc. Similarly, it was vital to have a good and efficient function encoding. Basically in the context of function encoding we need to be able to answer the following question:

• Where does the function definition begin?
• Where does it end?
• How many arguments does a function have?

First, I have planned to use function identifiers as references to physical memory locations. So, for instance, functions will be indexed by starting from 0. But this indirection could cost a lot in terms of hardware.

Instead, I am using the actual symbol to determine the function address directly. The most significant bit itself signals whether the symbol in question is a function (it is a function, if it is on, except for EOX). The consecutive 5 bits multiplied by 8 will actually give the function physical address. For example, %1aaa.aaxx - function definition will start at physical binary address %aaaa.a000.

The observant reader may be wondering what the two least significant bits are used for. They represent the argument count encoded in two-complenent form as follows:

• - 4 arguments
• %01 - 3 arguments
• %10 - 2 arguments
• %11 - 1 argument.

Again, this rather strange encoding is selected to facilitate the processing in hardware.

 In the light of the aforementioned, a full function encoding works as follows:

• %10000000 - is a user-defined function with 4 arguments, of which definition starts at address $00.
• %10000111 - is a user-defined function with one argument with definition beginning at address $08.
• %11111010 - is a user-defined function with 2 arguments definition at address $F0.

Please also note that built-in function "if" is encoded in accordance with the above arity encoding, i.e $FD (symbol encoding "if") represents a 3 argument function. I should mention that the encoding of inc/dec does not conform to this, but they are being treated differently as we will see. 

FunCPU - Architecture Concept

The picture below depicts the overall architecture of the FunCPU. It employs a 8 bit wide databus and a 9 bit wide address bus. Please recall, that although the databus is 8 bits wide, due to the nature of the tagged architecture only 7 out of 8 bits can be used externally (i.e. by the program), and one bit is reserved by the processor to interpret the data. So, from the programmer's point of view the CPU can be considered as a 7-bit CPU, which admittedly is a little odd.

More surprisingly, none of the familiar registers such as PC, SP (stack pointer), accumulator is available. Not even conventional status bits, such as Zero, Overflow flags, etc. can be located (note: although carry bit is present, but it cannot be referenced explicitly or even implicitly by the programmer. More on this later.). This is, because FunCPU employs a rather unconventional, delicate concept for program evaluation. 

FunCPU supports 256 bytes of expression memory, in which expressions can be entered and reduced, and also has 256 bytes of function memory, which is dedicated solely to storing user-function definitions. The following internal registers are present:
- RI - reduction index register, is a 8 bit register used for function evaluation.
- DI - is the destination index register. This is a 8 bit register used to access and write destination symbols.
- FI - is the function index register. This is also a 8 bit register, which content is fetched upon entering a function. This register is being incremented as the function definition is being unfolded.
- SI - is the source index register. This is also a 8 bit register pointing to the current symbol of the expression to be reduced.
- ac - is the argument counter. This is a 4 bit register used to support function embedding.
- V - is the value register. This 8 bit register is somewhat analogous to the accumulator utilized in conventional processors, but again its value cannot be read or written by the programmer. V register is used as a termporal storage or a gateway between source and destination expressions.

Please notice that all registers are internal, none of them is exposed to the programmer. The programmer and the user program cannot read, refer to or manipulate these registers explicitly. 

 The address multiplexer selects among four possible address sources as follows:
- DI is selected (usually) when destination expression is extended/written.
- FI is selected when function definition is accessed.
- SI is selected when source expression is read.
- finally, the ALU output is selected (in a combination when SI and V' are added) to perform argument binding.

The right ALU MUX generates either V or V'. The left ALU MUX either generates a constant of the range from -2 to 1 (also depending on carry bit) or selects SI or ac as one of its inputs. 

Please refer to ALU physical implementation for more details.

FunCPU - Tagged Architecture

In the memory, different type of symbols are stored together. It is essential for the CPU to be able to differentiate among them. Therefore type information is required to be assigned to each unit of information. This piece of information is tagged to each symbol. A lot of effort has been dedicated to come up with an optimal encoding. I wanted to have an encoding/tagging scheme, which was very economical and yet efficient. 

I have decided to use a single 8 bit RAM/ROM for memory, so everything (including the actual data and its type information) must fit there. With 8 bits of data I could encode the following information:

• 7 bit literals
• built-in functions
• user-defined functions
• expression terminator.

The latter is used to mark the end of an expression (essentially the core of the functional program) or a function.

I have further classified the 8 bit symbols with respect to the above categories as follows:

• zero constant, which also represents True;
• other constants
• arguments;
• inc function
• dec function
• if function
• user-dedinable function
• expression terminatior (EOX).

This classification, as we will see, will heavily facilitate the processing of the expressions.