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.
