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

On Tue, 1 May 2007 06:48 pm, William Tanksley, Jr wrote:
>
> In the case of your language, the (S+S) form means that programs
> cannot be built solely by concatenating simple forms (flat
> concatenative) nor by passing programs to other programs (non-flat
> concatenative).

So the possibility of passing programs to other programs must be a part  of 
definition of non-flat concatenative language?

Let's consider the next example.

In [1] has been shown that the set of all primitive recursive functions of one 
variable can be generated by some two primitive recursive functions, say f_a 
and f_b, by composition and iteration.

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 ]

Let L denotes the language which generated by this grammar.

The semantics of this language as follows:
let M be mapping from L to the set of all primitive recursive functions, such 
that
1) M(a) = f_a
2) M(b) = f_b
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)

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

Is the language L a concatenative language?

[1] Robinson Julia, General Recursive functions, Proc. Amer. Math. Soc. 1 
(1950), 703-718.

Michael Nedzelsky



 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/concatenative/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:[email protected] 
    mailto:[email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/