[stack] A small example of a (possibly concatenative) language for primitive recursive functions of one variable.

A small example of a (possibly concatenative) language for primitive recursive 
functions of one variable.

It is well known (see [1]) that the set of all primitive recursive functions 
of one variable can be generated by some two primitive recursive functions, 
say s and q, by composition, addition and iteration.

Iteration is defined as follows:
for f: Nat -> Nat the function g: Nat -> Nat is iteration of f if
g(0) = 0
g(n+1) = f (g(n)).

Let J(f) denotes the result of iteration of f.

We can define the following language:

Terminal symbols: a, b, [, ], +, (, )
Production rules:
S --> e | a | b | S S | [ S ] | (S + S)

Let L denotes the language which generated by this grammar.

Now we define the semantics for L:
let M be mapping from L to the set of all primitive recursive functions, such 
that
1) M(a) = s
2) M(b) = q
3) (\forall x,y \in L) M(xy) = M(x) M(y) # i.e. composition of the functions 
M(x) M(y)
4) (\forall x \in L) M( [x] ) = J(M(x)) # i.e. iteration of M(x)
5) (\forall x,y \in L) M( (x+y) ) = M(x) + M(y)

For example,
[(a+b)] q  maps to J(s+q)q

M maps L onto the set of all primitive recursive functions of one variable.

In the article www.latrobe.edu.au/philosophy/phimvt/joy/faq.html
we can read the following.
--------------------------------
A language in which the concatenation of programs denote the composition of 
functions has been called a concatenative language.
--------------------------------

It seems according to this sentence language L is a concatenative language.
Are you agree?

[1] Robinson R.M., Primitive recursive functions, Bull. Amer. Math. Soc. 53 
(1947), 925-942.

Michael Nedzelsky