2014-09-21

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:
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.

2014-09-13

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