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

On 3/5/07 12:27 AM, "Michael Nedzelsky" <[email protected]> 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
> 
> 
>