### About the input: recursive functions

You may refer to the M-recursive function article on wikipedia.

#### Global structure of the input

The input is:
• 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 +.

• The mu-minimisation operator is not implemented!