# Pseudo-combinators and Church numbers

## Brent Kerby — 2002-10-09 18:04:19

    > Could you clarify why you say that your Cpow is not a true combinator?

     Well, it's pretty simple, really. When we try to write a "reduction rule"

    for Cpow, the best we can get is this:

      [p] [m] [n] Cpow  ==  [p] [[m] cons] n i

    Note the appearances of "cons" and "i" on the right hand side. This is in

    essence what makes it a pseudo-combinator. A true combinator has a reduction

    rule without such things on its right hand side, for example:

            [a] dup   == [a] [a]

        [b] [a] swap  == [a] [b]

        [p] [n] Csucc == p [p] n

    [p] [m] [n] Cadd  == [p] m [p] n

    [p] [m] [n] Cmul  == [[p] m] n

    See how in all of these the right hand side consists solely of variables,

    mixed up through concatenation and quotation. That is why they are called

    true combinators, because they possess a reduction rule of this kind.

    For the curious, there is some interest in a system that contains only true

    combinators, no pseudo-combinators. Such a system would have to get rid of

    quotation, since the quotation of any combinator is a pseudo-combinator

    (e.g., "[dup]" or "[swap]" is a pseudo-combinator, since it possesses no

    reduction rule). This idea hasn't been fully explored, but you might like to

    look back on the post

    http://groups.yahoo.com/group/concatenative/message/1051 and other posts

    thereabouts. The idea is that a workable base is {nil, zap, dup, i, unit,

    take, cat}:

             nil  == []

         [a] zap  ==

         [a] dup  == [a] [a]

         [a] i    == a

         [a] unit == [[a]]

     [b] [a] take == [a [b]]

     [b] [a] cat  == [b a]

    I suspect that all true combinators can be constructed form these, using

    concatenation alone (no quotations allowed), and there is very probably a

    smaller base that will work. Here's a few examples of some constructions in

    this system (a searcher reveals that these are the minimal constructions):

      dip  == take i

      swap == unit take i

      flip == unit take take i  (i.e., a combinator that reverses the top 3

    items)

      dupd == unit take i unit dup cat take i

           == unit take i dup unit take take i

      sip  == unit take i unit dup cat take i take i

           == unit take i dup unit take take i take i

    More simply, we could have

      dupd == swap dup flip

      sip  == dupd dip

     > I do remember that in one reference (I cannot remember which, alas)

    > it was pointed out that exponentiation could be implemented

    > as applying the exponent n to the base m, but that was

    > considered "cheating" [sic]. I did not understand that

    > either, but maybe you are talking about the same thing.

     Yes, in the classical combinatory logic you can exponentiate Church numbers

    simply by applying them (although it is the base that is applied to the

    exponent, not the other way around). We can do the same thing in Joy if we

    reform the Church numbers once more (I'll call them Zn, as that is what the

    Church numbers are standardly called):

      [x] [p] Zn  ==  [[[[[x] p] p] ...] p

    For example,

      [x] [p] Z0  == x

      [x] [p] Z1  == [x] p

      [x] [p] Z2  == [[x] p] p

    Note these Church numbers take two parameters as opposed to the one

    parametered Cn and Rn. Anyhow, we can define the operators then in this way:

         [x] [p] [n] Zsucc ==  [[x] [p] n] p

     [x] [p] [n] [m] Zadd  ==  [[x] [p] n] [p] m

     [x] [p] [n] [m] Zmul  ==  [x] [[p] n] m

     [x] [p] [n] [m] Zpow  ==  [x] [p] [n] m

    Or by construction,

      Zsucc  == [B] S

      Zadd   == [B] N

      Zmul   == B

      Zpow   == i

    where B, S, and N are the classical combinators

        [c] [b] [a] B == [[c] b] a

        [c] [b] [a] S == [[c] b] [c] a

    [d] [c] [b] [a] N == [[d] c] [[d] b] a

    See how neat that works, with Zpow being simply "i".

    Anyhow, these Zn seem to be the true analogue of the classical Church

    numbers, although that's not to say that they are necessarily the most

    appropriate in a concatenative system. But, Zn do have use; for example,

      dip2 == [dip] Z2

      dip3 == [dip] Z3

      dip4 == [dip] Z4

      ...

    See,

       [p] dip3

    == [p] [dip] Z3

    == [[[p] dip] dip] dip

    That seems pretty handy.

     > > - Brent

    > - Manfred

     - Brent