FunCPU - Entering Expressions

FunCPU - Clock Generator

Construction of FunCPU has begun with the clock generator. The module is already fully functional on its own, but space is left for incorporating more components for the EPROM chips storing the micro-program and for some control logic.

An 555 is used to generate the base for the clock signals. There are two options to manipulate the clock frequency. A trimmer potentiometer is used to fine tune the frequency within two ranges selected by the right switch. In one position the base clock frequency ranges roughly from 1.4 Hz to 64 Hz, which can be used for debugging, in the other position this covers the interval from 14.5 Khz to 47 Khz, which is suitable for normal operations.

A 74HC74 is used to ensure the following:
whenever the two-phase clock starts:- it starts with phase 1
- it starts with full cycle
- signals when two-phase clock starts
furthermore the duty cycle is guaranteed to be roughly 50%.

A 74HC161 fed by the two-phase clock is applied to generate micro-sequence (from 0 to 3).
A 74HC02 is used as an RS flip-flop to debounce the Edit/Run toggle switch.and also to enable/disable clock signals.

The LED-bar is used for debugging and can be turned on/off by the left switch.

not used
not used
US0	least significant bit of the micro-sequencer
US1	most significant bit of the micro-sequencer
CLK2	phase 2 of the master clock
CLK1	phase 1 of the master clock
RUN	bright, if in Run mode
EDIT	bright, if in Edit mode
CLK RUN	to indicate whether clock is enabled
CLK	Master clock with half of the frequency of the base clock

 The following BUS  ("B6") is impelemted on the board:

RUN_OUT (15)	EDIT_OUT	CLK2	not used	CLK1	not used	CLK_RUN (3)	VCC (1)
GND (16)	US0	US1	not used	not used	RUN_IN	EDIT_IN (4)	not used (2)

RUN_IN and EDIT_IN are the incoming signals (with prell) representing Run or Edit respectively. Whereas RUN_OUT and EDIT_OUT are the debounced signals. The rest of the signals are described above along with LED indicators.

Finally, we can see the clock generator in action. Before the clicking noise, FunCPU is in "Edit" mode, therefore clock is basically idling. When Run/Edit toggle is switched to "Run" position, then at the next clock cycle the clock generator starts to operate as indicated by the the blinking LEDs.

FunCPU - Control Panel

Ok, here is a photo of the real control panel. It is a little bit different from the original design. It does not look that  spectacular, but has decent functionality. 

The upper section includes 8 LEDs and 8 toggle switches. These are used for data entry as indicated by the label in between. In addition to showing the full 8-bit value in the memory, this value is decoded and its type (remember, we are dealing with a tagged architecture) is indicated below by the type indicator LEDs. 

If the data is an argument, then the blue “arg” LED will be active, if a constant is found, then the “cons” LED is bright and so on. So by looking at these LEDs one immediately will know the function of the data being observed. 

Also six function shortcut buttons are introduced to facilitate the data-entry. One may have a choice of selecting the data with the 8 toggle switches or using one of the function buttons, or alternatively having a combination of them.

“0” is used to store zero value (also interpreted as True). This comes handy, since one does not have to bother about turning the toggle switches to zero position to be able to enter 0. “eox” (indicating end of expression) does the opposite, it gives a $FF value. “arg” button can be used along with the two least significant toggle switches to enter argument number. The use of “inc”, “dec” and “if” should be self-explanatory.

I expect that the majority of functions and expressions can be simply entered using the functional buttons, and toggle switches will be rarely used.  On one hand this would speed up data-entry significantly, on the other hand function indicator LEDs will be major help in debugging.

Once the actual data is selected, the “Store” button must be pressed to store the data into the memory.

To where and from where this 8-bit is actually coming, is determined by the address control gizmos. The toggle switch “Exp/Func” switches between expression and function memory. Whereas the two silver knobs enables us to select a full 8-bit value (four bit each).

All the above buttons, switches, knobs work only in “Edit” mode, but do not have any effect in “Run” mode. To choose between the two modes, one has to toggle the “Edit/Run” switch.

Please note that the LEDs are working in the same fashion regardless of the operating mode, except, that in running mode the address is determined by the processor internal state, therefore the data being shown (both by the data and address LEDs) reflects the actual computational state. The actual 4-bit state is indeed displayed by the state LEDS.
0000 is the initial, starting state. 1111 is the final state for successful computation.

Finally, the big red button on the right bottom is used to turn the computer on or off.

FunCPU - Boxing Day...

It is high time I had gone to look for a suitable box to be the case of the FunCPU. I have decided on the one below. It is quite ugly and girlish actually, but it was the cheapest option.

At least this will be the choice for CPU-case of my first attempt to build the CPU. 

I expect to implement all functionality using 5 or 6 modules. Each module will be implemented as a single board. These boards should fit into this box.

FunCPU - Overcoming Some Limitations

The FunCPU (in its current version) supports only numerical computation, more precisely, operations with integers. Functional languages, such as Lisp, Clean, etc. come with a richer set of data types and also have some kind of type construct capability. For example, Lisp as its name suggests mainly operates with lists.

Moreover, the maximum number of arguments is limited to four. Four arguments are usually enough to demonstrate some simple, yet interesting mathematical functions, but more complex scenarios require usually more arguments.

Hereunder I will be sketching some workarounds to overcome the aforementioned limitations, but please beware that these will bear mainly theoretical relevance.

More Arguments

To increase the number of arguments supported, one can use any pairing function, which is a bijective function mapping two natural numbers to another. For instance, the Cantor pairing function is defined as follows:

P(x,y):=0.5 * (x+y) * (x+y+1) + y

Even more arguments can be encoded, if we use nested pairing functions, that is essentially use the Cantor tuple function. For more information please refer to:

http://en.wikipedia.org/wiki/Pairing_function

Lists, Records

Similarly, lists (or record-like structures) can be encoded using the so-called Gödel’s encoding, so that, a list or string of n consecutive characters is encoded as follows:

enc(x1, x2, …, xn) := 2^x1 * 3^x2 * … * Pn^xn, where Pn denotes the nth prime.

Obviously, due to the 7-bit architecture such encodings are rather limited, but still theoretically feasible.

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.