> 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