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

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