Either a single expression of a recursive function;
Or a small piece of code of the form
f = .......g = .......:main = .......
where ....... are expression of M-recursive functions and the function to be compiled is main.
Recursive function syntax
0 is the null fonction. It takes as many arguments you want and returns 0.
S is the successor fonction. It takes one argument n and returns n+1.
pi(k) is the k-th projection fonction. It takes several arguments and returns the k-th argument.Example: When we apply pi(2) on (3, 4, 10), it returns 4.
o(f, g1, ... gk) is the composition of f and g1, ... gk where f : N^k ---> N and gi : N^l ---> N.
rec(b, r) is the recursive scheme build up from the basis case b and the recursive case f.
If b : N^l ---> N and r : N^{l+2} ---> N
rec(b, r) is defined as
rec(b, r)(vec n, 0) = b(vec n)
rec(b, r)(vec n, k+1) = r(rec(b, r)(vec n, k), vec n, k)
In the recursive case, arguments of r are:
1
2
3
...
l+1
l+2
rec(b, r)
n1
n2
...
nl
k
Example:
In rec( pi(1), o(S, pi(1)) ), the basis case function is pi(1). And o(S, pi(1)) is the recursive case function. We obtain the function +.