Brent L Kerby <bkerby <at> byu.net> wrote:
> > I find it interesting that completeness is different between
> > applicative and concatenative languages (for example, {s,k} is a
> > complete applicative basis, but not is not complete when
> > concatenative).
> Right. When we map the applicative combinators to concatenative
> ones in the obvious way, the image of this map is not a complete
> (concatenative) set. But it's interesting to note that, in the other
> direction, things turn out differently. I.e., the image of the natural
> map (or at least, what I'm calling the natural map) from
> concatenative combinators to applicative ones _is_, remarkably
> enough, a complete applicative set.
This would seem to generally fit my theory -- that applicative syntax
is more powerful in its greater complexity, because an applicative
syntax allows a language to directly express the concept of
"siblings". Whenever a function takes two parameters, those parameters
are "siblings". The only way to connote the concept of siblings in a
concatenative language is to build the putative siblings into a list.
> So there we have it! The image of P is a complete applicative set!
> What is perhaps even more surprising is that we didn't need to
> use the image of "i" or "dip".
I noticed the lack of need for "i" much earlier. At first I thought
this was a problem with our notation (since the applicative notation
doesn't even have a concept of dequotation), but I believe now that
it's not a problem: it's a result of how concatenative notation can't
denote siblings, so a runtime concept (quotation) must take its place.
> In any case, note that I'm not claiming P is surjective
> (i.e., that it maps onto to every applicative combinator),
> only that it maps onto a complete subset of the applicative
> combinators.
I know many of those terms, but I don't know what "complete subset"
means. Does it mean "a subset of combinators which includes a complete
base"? If so, that makes sense.
> If P (or rather, the version of P which operates on equivalence
> classes of lambda-forms rather than the forms themselves --
> call it P^, "P-hat") is surjective, then it would be an isomorphism
> between the concatenative and applicative systems of
> combinators (the well-definedness and injectivity of P^ follow from
> the fact that P respects reduction). I doubt that such an isomorphism
> exists but don't know how to prove this. This is really the fundamental
> question about the relationship between concatenative and
> applicative combinators: are the two systems isomorphic?
This last question definitely nags at me in one way, which I can't
define. I have a nagging doubt that we're missing something.
In another way it seems evident (after much exploration) that the
systems are "equivalent" (in the sense that a program in one can
always be expressed in the other). But I don't know too much about
isomorphism, except that it's more complex than that... I've only had
a general undergrad intro to modern algebra (groups, fields, algebras,
etc).
> For this argument, I'm using a special case of the
> Church-Rosser property, that an (applicative) combinator
> has a unique normal form (i.e., a form with no redexes) if
> it has one at all. (The general case states that if A, B, and
> C are lambda-forms with A=>B and A=>C, then there is a
> form D such that B=>D and C=>D. This essentially says
> that if you can get a form to reduce to two different forms
> (by choosing different redexes to reduce), you can perform
> further reduction to converge again to a common form. This
> an intuitive idea which is nevertheless highly non-trivial to
> prove). Although I'm not relying on it here, it would also be
> nice to know if an analogous "Church-Rosser" property holds
> for concatenative combinators.
Is this something of what you mean by "isomorphism"? That would indeed
be an awesome property. There are a lot of very simple things that are
obvious about flat concatenative languages (for example, it makes
sense that once you understand the meaning of a bitstring without
context, you therefore know its meaning in any context), but there are
also a lot of things that seem to take more work to parse out (for
example, some "optimizations" seem to be very complex to express
formally).
(Sorry for the informal terminology. I'm very new at this.)
> > [B] [A] cake == [[B] A] [A [B]]
> > Clearly, A and B are not siblings here. Of course, constructing concat
> > is possible, which obviously makes siblings out of A and B, but is it
> > somehow less theoretically pure to have a basis in which the siblings
> > are not explicit in the provided basis combinators?
> Well, the construction of "cat" in terms of {cake,k} relies on transparent
> quotation; ultimately, it's the same construction as this one from i, dip,
> and cons:
Ah! And this helps me understand what "transparent quotation" means at
a semantic level. My implementation (01.py) clearly uses transparent
quotation, since it executes combinators at the earliest opportunity
(in fact, I think it actually might execute them too soon... I need to
work on that).
>Therefore, "cat" is inconstructible in {cake,k} under opaque
>quotation. So, {cake,k} is not complete in as strong a sense
>as, for example, {q,k} (from which all combinators are constructible,
>even assuming opaque quotation):
YES! I'm starting to "get it".
> In addition, I'd say "q" is a bit nicer than "cake" since, aside from
> being simpler, it has the pretty property that it produces a (unit)
> quotation and a concatenation, which correspond precisely to
> the two syntactic constructions of the language. This may not
> be particularly significant in the grand scheme of things, but we
> have to admit that it's a bit nifty.
Hmmm... I'm a ways from being knowledgable enough to be able to admit
that. I'll take your word for it, after I play around with your
joys.exe program a bit more. I'm not sure how I'm going to get any
different results; in particular, getting a concat seems to be
essential to completeness. I suspect that the only way to do anything
else would be to have a combinator which took more parameters (and
that just seems like it'd be less efficient).
Hmm again.
> So I'm perfectly fine with "condemning {cake,k} to contempt and
> contumely" 
It's one of the things I'm qualified to do, having studied ancient literature.
Would you like fries with that?
> - Brent
-Billy
RSS Feed