Re: [stack] S-K Construction of Dip?

Brent L Kerby <[email protected]> wrote:
> Does that clear things up?

Thank you!

Let me first say that recasting combinatorial operations in terms of a
flat concatenative language has made it MUCH easier for me to reason
about them. I definitely don't understand them completely, but somehow
the reasoning seems more in line with my brain's workings. One of my
friends felt the same way. Am I just mentally disturbed from years of
Forth use and abuse, or is there actually something simpler here?

Anyhow:

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

Thinking about this, I'm guessing that this is because application
forms a syntactic tree, so that it's possible to talk about a
combinator's "siblings". Concatenation forms a syntactic list (not
nested), so although elements can have a child, there are no syntactic
siblings.

My theory: Therefore, because the syntax doesn't provide that
operation, the semantics have to provide it. And indeed, every
complete basis we've produced has combinators that can provide access
at the same level to either of two elements. In other words, the
combinators must include some way of making two different elements
into (equal) siblings.

The problem with this theory is that the cake combinator in {cake,k}
is an obvious counterexample:

[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? My theory suggests
something like that, but I (intuitively) find it difficult to believe.

Is there a better theory? Or should I reform my intuitions instead,
and accept the theory (thereby condemning {cake,k} to contempt and
contumely)?

> - Brent

-William (Billy)