It is not trivial how to handle argument passing in the lack of stack, or any dedicated storage for parameters. Consider the following examples:
fac (n):= n*fac(n-1)
fac(add(2,3))?
ack(add(fac(fac(2)+fac(1)),fac(1)),1)?
I wanted a simple solution, which still works without posing serious restrictions. I wanted arbitrary function calls with arbitrary depths.
I have come up with a very simple solution. The evaluation of a function is deferred up to the point when all of its parameters become constant. Referring the the term fac(add(2,3)), first add(2,3) is reduced to 5. Only after that is the fac function reduced by applying the previous result as an argument, that is, fac(5), which in turn is reduced to 120.
In similar fashion the evaluation of the second example happens.
First, fac(2), fac(1) (this appears twice) are reduced. Please note that there is a lot of potential to exploit parallelism and for optimization. These expressions can be reduced in paralllel, furthermore fac(1) should be calculated only once.
In the second step fac(fac(2)+fac(1)) is evaluated. Note: this time we have the constant value both for fac(2) and fac(1). In the third step add is performed, finally ack is executed.
