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

## Michael Nedzelsky — 2007-05-01 10:38:45

    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

## Michael Nedzelsky — 2007-05-01 11:33:10

    > For example,

    > [(a+b)] q  maps to J(s+q)q

     Of course,  the correct version is

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

     Michael Nedzelsky

## William Tanksley, Jr — 2007-05-01 14:48:29

    Michael Nedzelsky <MichaelNedzelsky@...> wrote:

     > A small example of a (possibly concatenative) language for primitive recursive

    > functions of one variable.

    > We can define the following language:

    > Terminal symbols: a, b, [, ], +, (, )

    > Production rules:

    > S --> e | a | b | S S | [ S ] | (S + S)

     By the basic syntactic definition we looked at before, this wouldn't

    be concatenative -- its (S+S) form fails.

    (By the way, this suggests a different wording of the definition that

    might pass the test. We originally stated that there may be no other

    grammatical rules; we could instead state that "S may not appear in

    the RHS of any other rules," and of course we would have to allow some

    other nonterminals. I'm going to stop here, but we need to figure more

    out.)

     > Let L denotes the language which generated by this grammar.

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

     Okay, makes sense.

     > 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?

     Yes. But I don't think this sentence stands alone. It's like saying "A

    language in which the lambda form is used to define functions, which

    can be passed to other functions, is called a functional language."

    That may be true, but there are other requirements on a functional

    language, such as referential transparency.

    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).

     > Michael Nedzelsky

     -Billy

## Michael Nedzelsky — 2007-05-01 15:53:42

    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

## William Tanksley, Jr — 2007-05-02 02:34:24

    Michael Nedzelsky <MichaelNedzelsky@...> wrote:

     > 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?

     I'd have to say no... That's semantic, not syntactic, so it can't be

    part of a syntactic definition. I was incorrect to suggest that.

    However, we still have the problem that expressions of the form (S+S)

    cannot be built by concatenating valid programs. Your definition

    allows them simply because it doesn't "look inside" the parentheses.

    Of course, it also doesn't look inside square brackets, even though if

    you were to look inside those you'd see another valid program (in Joy

    and in your grammar).

     > Let's consider the next example.

     I'm glad you're here. This is providing some definitional rigor I

    certainly needed. Thank you for putting the thought into this.

     > Terminal symbols: a, b, [, ]

    > Production rules:

    > S --> e | a | b | S S | [ S ]

    > Let L denote 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?

     I would need to understand more about "iteration". Right now I really

    don't know what it means. If my hunch is right, though, this is a

    concatenative language. If so, this is rather interesting... It's very

    different from the other concatenative languages I've looked at.

     > Michael Nedzelsky

     -Billy

## Michael Nedzelsky — 2007-05-02 14:27:30

    On Wed, 2 May 2007 06:34 am, William Tanksley, Jr wrote:

     > I'm glad you're here. This is providing some definitional rigor I

    > certainly needed. Thank you for putting the thought into this.

     You are welcome. :)

    I also find this discussion very useful for me.

     > I would need to understand more about "iteration".

     I hope the following explanation will be useful:

    let f ba a function from natural numbers into natural numbers. Define the

    function g as follows:

    g (0 ) = 0

    g( 1 )   = f(0)          # one f

    g( 2 )   =f (f(0))      # two f

    g (3 )   = f (f f(0)))  # three f

    ...

    g (n)    = f ( ....f(0)...)   # n times f

    ...

    That g is the iteration of f.

    Examples (here % means \lambda):

    1) if f = %x. 0 then g = %x. 0

    2) if f = %x. 1 then g = %x. sgn(x), i.e. g(x)=(if x=0 then 0 else 1)

    3) if f = %x. (x+1) then g  = %x. x

        g(0) =0, g(1) = f(0)=0+1=1, g(2)=f(f(0))=1+1=2 ...

    Michael Nedzelsky

## Manfred Von Thun — 2007-05-07 05:34:08

    On 3/5/07 12:27 AM, "Michael Nedzelsky" <MichaelNedzelsky@...> wrote:

     > I hope the following explanation will be useful:

    > let f ba a function from natural numbers into natural numbers. Define the

    > function g as follows:

    > g (0 ) = 0

    > g( 1 )   = f(0)          # one f

    > g( 2 )   =f (f(0))      # two f

    > g (3 )   = f (f f(0)))  # three f

    > ...

    > g (n)    = f ( ....f(0)...)   # n times f

    > ...

    > That g is the iteration of f.

     I had always assumed that in Joy the quotation parameters for a

    combinator should always be on top of the stack. But in my current

    experimental implementation of Joy in Prolog I also allow myself

    a lot more freedom. One was to relax the assumption, and allow a

    numerical parameter above the quotation parameter. This looks

    promising for generalisations of three combinators which take

    one quotation: i, dip and infra. The generalisations are called

    reps, dips and infras. They expect a single quotation and above that

    a natural number.

    [Q] 0 reps == id

    [Q] 1 reps == [Q] i == Q

    [Q] 2 reps == [Q] 1 reps Q == Q Q

    [Q] n reps == Q Q Q Q...  # n times

    The reps combinator is your iteration combinator, I think.

    For example, 1 [2 *] 10 reps == 1024, and in general,

    [m *] n reps computes the n-th power of m.

    (The reps combinator is similar to the times combinator in

    current Joy, with just the two parameters reversed.)

    [Q] 0 dips == id

    [Q] 1 dips == [Q] dip

    [Q] 2 dips == [[Q] dip] dip

    [Q] 3 dips == [[[Q] dip] dip] dip

    [Q] n dips == [[[..[Q] dip..]]] dip  # n [[[s, n Qs, n]]]s

    For example:

    1 2 3 4 5 6 7 8 [dup *] 3 dips == 1 2 3 4 25 6 7 8

    1 2 3 4 5 6 7 8 [pop] 6 dips == 1 2 4 5 6 7 8

    1 2 3 4 5 6 7 8 [999] 4 dips == 1 2 3 4 999 5 6 7 8

    1 2 3 4 5 6 7 8 [[pop] 6 dips] nullary == 1 2 3 4 5 6 7 8 2

    The last two examples show that dips is useful for

    burying something deep in the stack or digging it up.

    [Q] 0 infras == id

    [Q] 1 infras == [Q] infra

    [Q] 2 infras == [[Q] infra] infra

    [Q] 3 infras == [[[Q] infra] infra] infra

    [Q] n infras == [[[..[Q] infra...]]] infra  # n times

    Note that [Q] 3 infras expects a stack whose top element is

    a list whose first element is a list whose first element is

    a list. This last list is being used as the stack for [Q]

    to use. Possibly infras is less useful than reps or dips.

      - Manfred

     >

    > Examples (here % means \lambda):

    > 1) if f = %x. 0 then g = %x. 0

    > 2) if f = %x. 1 then g = %x. sgn(x), i.e. g(x)=(if x=0 then 0 else 1)

    > 3) if f = %x. (x+1) then g  = %x. x

    >     g(0) =0, g(1) = f(0)=0+1=1, g(2)=f(f(0))=1+1=2 ...

    >

    > Michael Nedzelsky

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >