Sorry; I said in my last post that I had one more question, and then I
forgot to ask it.

My question is: how does Okasaki's and Barker's work apply to this?
Okay, actually, what I want to know is how to design a flat,
two-combinator, concatenative language that's implemented using stacks
and lists (like Joy).

I've wanted to figure this out for a while, but my friend wants it in
order to design a genetic algorithm system that allows maximum
flexibility in cutting genomes.

iepos <bkerby@...> wrote:
> So what about a one-combinator basis? This is an interesting
> question. It will not work to simply take the concatenative version
> of the Fokker X combinator (or the Rosser, or any other applicative
> one-combinator complete basis). This would be equivalent to the
> basis {s, k}, which is _not_ complete in a concatenative system.

Okasaki, in the postscript file linked to at
http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03, builds a
concatenative system using different rules, under which the classical
combinators form the classical structures (and so {s,k} is complete,
hence the classical X combinators are complete). The difference
between his notation and yours is that his notation uses combinators
to build a list-structure which is then treated as a grammatical
structure in itself; your notation has its own grammatical structure.

His notation has two strengths: first, it harnesses directly the
classic combinators; and second, it is syntactically completely flat
(lists and quotation play no part in the grammar). I'm concerned that
it has weaknesses that I don't understand, however, because I can't
figure out how it actually works well enough to design an
implementation.

I also found Barker's work on Zot at
http://ling.ucsd.edu/~barker/Iota/zot.html to be compelling -- I
speculate that Zot (and probably Jot as well) qualify as
concatenative, although they don't explicitly specify a stack (that
could be another example of a non-stack-based concatenative language,
or it could just be that the stack is hidden by the way in which the
semantics of the language is described). Again, though, the notation
used is foreign to me, so further examination is hindered. The reason
I qualify Zot as probably concatenative is that the author describes
several properties of it in ways that make me think it might meet my
definitions as well. Interestingly, it's probably also applicative, if
I read its notation right (although it doesn't provide
variables/lambdas, so it's pure dataflow -- that certainly reduces the
differences between the concepts).

> But after some fiddling, I was able to find a one-combinator base
> that does work. The idea is to make a combinator with 'cake' and 'k'
> somehow embedded in it, built in such a way that, with a little
> manipulation, we can extract them back out. Let
> z == [zap [cake] [k]] dip i

Interesting. I came up with a similar combinator (i.e. one which
contained both cake and k) when I was attempting to build a system
that didn't use a list structure as part of its grammar back a while
ago. Unfortunately, my notes are lost, and since I wasn't trying for
completeness (indeed, I didn't understand it at all) I doubt I
achieved it.

Your combinator, unlike Barker's and Okasaki's, makes sense to me :-).
The problem is that I don't see whether it's possible to transform it
to a flat system.

My problem with non-flat systems isn't merely syntactic; my concern is
that they hide infinite semantic complexity in the ability to create
layers of quotations. It's hard to unambiguously measure the
K-complexity of a non-flat syntax; do you count the depth of nesting,
or do you count opening brackets, or ...? A flat syntax makes the
K-complexity of things implemented in it obvious.

> - Brent

-Billy