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 - Instruction Set

FunCPU will operate with 7-bit numerals (to understand why see the next couple of posts) and will directly support the following built-in functions:

inc(x) is used for incrementing a value, that is for any x: x+1=inc(x).

dec(x) is used for decrementing a value in the similar fashion.

if-then-else is used for conditional evaluation. if cond then exp1 else exp2 will yield exp1 if and only if cond is true, otherwise it will yield exp2 (assuming that evaluation of the condition terminates).

In addition to the above built-in functions, user definable functions may be entered arbitrary in the available 32 slots. These functions may use the built-in functions as well as any other user-defined functions. Functions can be embedded one into other at arbitrary depth. Functions can be created with arity 1, 2, 3 and 4. Constant functions still can be constructed, but they must have at least one argument. Thus, for example, if F(x) is a one-argument constant function, then F(x)=c for any x, where c is a constant.

Functions will only accept numeral constants as arguments (no higher order functions are supported), and will return also numerical value. Note: „0” represents True, any other value is considered to be False by convention.

By design, no advanced data structures (i.e. list, record, object, etc. ) will be supported natively. 

At first it may seem suprising that with this very limited instruction set (and of course with the poweful construct of function embedding), any computable function can be defined and thus computed within this model, provided that its encoded algorithm (and also all expressions as a result of the function evaluation) fits in the memory. 

FunCPU - Goals

It has been a long time since my last CPU project, which focused on a very simple 8 bit CPU. Nothing groundbreaking, just a very simple variation of an accumulator machine. 

This time I have set out a different, more ambitious goal. I have wanted to create still something simple, but original unconventional architecture, which is still useful. 

I had considered to target a CPU optimized for logical programming, but finally I have decided on a CPU with an instruction set and architecture, which natively supports functional programming.

A tagged architecture is selected. Basically, this means that each unit of information carries its own type information. A special instruction set will be carefully selected, which would be most useful to support creation of functional programs in assembly or even in machine code. The whole design will be very simple, yet powerful enough to perform arbitrary complex computations (in theory) to be Turing-complete.

It will have 

• no PC;
• no SP or stack;
• no conventional user readable flags;
• no user readable registers (not even an accumulator in the conventional sense);
• no branching/jumping instructions;
• no I/O operations

So, what is what we have?

• 7 bit literals (yep, not mispelt!);
• 3 built-in,
• 32 user-definable functions;
• ROM – to store functions (256 bytes);
• RAM – to evaluate expressions (256 bytes);
• 8 bit data bus;
• 8/9 bit address bus.