2014-04-19

FunCPU - Computational Model

As the computational model will be purely functional without any imperative elements (which could introduce side effects), a simple expression rewriting system will be adequate.
User-defined functions will make up a library, which will in turn, also define the rewriting rules. Functions from library may refer to each other (i.e. one function can be used in another).
The expressions to be evaluated can be made of:
  • built-in functions;
  • user-defined functions (as stored in the library);
  • literals. 
EOX symbol will mark the end of such exrpession. Program execution will be not other, than evaluation of a closed expression (it is called such, because it may not contain any variables or quantifier) following the rewriting rules (as defined in the library) transforming an expression into a chain of expressions, and finally into a constant.
If it is possible to reduce the initial expression into constant in finite steps, then the evaluation stops succesfully, and we say that the expression is defined. Otherwise we say that the expression is undefined. The latter may happen
  • if expression or function deifinitions are not well formed, that is, they do not obey syntactical rules (e.g. a function is called with less or more arguments, than as its definition states,etc.);
  • if an infinite loop is encountered (via recursion);
  • if the particular evaluation strategy causes non-termination. This implies that there may co-exist other evaluation strategies, such as that provided that they are followed, the same expression with the same library (also called interpretation) can be reduced succesfully.
 For example:
Library:
f(x,y) :=x+y
g(x,y,z) :=f(x,y)-f(y,z)
Closed expression
g(3,2,1)+f(2,2)

Execution:
g(3,2,1)+f(2,2) =  ( f(3,2) – f(2,1) ) + (2+2) = ( (3+2) – (2+1) )+ (2+2) = 6
Please note that as a function may refer to itself, it enables recursive function definition, and hence recursion. Along with function composition and atomic functions (inc, dec, if) it gives a real computation power to this simple model.

2014-04-05

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.