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

FD - if-then-else

FE - decrement function

FF - end of expression

Identity function

I(x):= x

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

FC 7B FF

That is, essentially, incrementing the value 7B to get the 7C.

Or analogously,

FE 00 FF

represent the constant function 7F.

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

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

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.

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)))

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

## No comments:

## Post a Comment