stevan apter — 2006-11-19 11:24:30

----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
>
> I'm trying to use Kerby's http://tunes.org/~iepos/joy.html brief
> exploration of concatenative combinators to design a combinator set
> which does not _also_ require the reams of quotations that his
> combinators require. Such a language would be purely concatenative and
> purely flat, both by the strictest definitions I could give -- after
> all, in a sense the quotation syntax [] is an applicative function
> q(x), which returns x quoted into a list.
>
> I started with his {cake,k} base, and tried to express some things in
> it -- but I found that even the simple result [] was unattainable. I
> realized that I'd need quoted forms of cake and k, so I tried the base
> {cake,k,[cake],[k]}. Again, [] wasn't evidently attainable, and it's
> needed for many fundamental expressions. I could try
> {cake,k,[cake],[k],[]}, but now it's getting clear that something's
> missing... The applicative quotation operator q() is secretly very
> important to the so-called concatenative combinator theory.
>
> My ingenuity and knowledge is hitting its limits... I don't know
> enough about combinator theory to work anything out here.
>
> I'm getting some ideas about combinators that, in addition to having a
> pattern effect as we're used to, also return a constant value which
> happens to be some other quoted combinator. In that way all the
> combinators can be generated onto the stack, where they can be
> captured into a pattern by a later combinator. But I don't know how to
> determine whether such a combinator "base" is actually complete, so
> I'm not eager to go to the work to construct one that merely looks
> complete to me.
>
> Does anyone have any ideas?

consider the following core:

some set of atoms (e.g. 12)
the empty quotation .
the quotation particle '
the disquotation combinator !
the cons operator ,
:

if x is a token, then 'x is a token (the quotation of x)

unlike joy, but like false, operators push themselves
onto the stack. so

2 3 + => 2 3 +

! is defined this way:

if x is a quotation, then x ! is joy's i
if x is an atom, then x ! is x
if o is an operator, then ... o ! is joy's ... o

the core is powerful enough to construct any quotation, and
all expressions using the core are flat.

>
> My ultimate goal is to build a flat bitstring encoding for a friend of
> mine who's researching genetic algorithms. Flatness, as you can
> imagine, would be a huge benefit to a genetic algorithm encoding -- it
> really would be nice to be able to cut a gene at any site.
>
> -Billy
>

William Tanksley, Jr — 2006-11-21 16:28:39

stevan apter <sa@...> wrote:

> consider the following core:
> some set of atoms (e.g. 12)

I'm not going to use any of those -- you have to build numbers (I'm
thinking of a tally system, like Enchilada's). Since we're dealing
with evolutionary algorithms, that only matters for input and output,
of course.

> the empty quotation .
> the quotation particle '
> the disquotation combinator !
> the cons operator ,
> :

So you suggest two operators, "!" and ",". That gives a total of four
symbols: 00="!", 01=",", 10="'!", and 11="',".

Oops, I missed the need for the empty quotation -- that gets a symbol
as well, so we need three bits to encode each symbol.

> if x is a token, then 'x is a token (the quotation of x)

Right.

> unlike joy, but like false, operators push themselves
> onto the stack. so
> 2 3 + => 2 3 +

+ isn't an operator, of course -- I guess cons is the only operator,
since you can't do anything without !.

> the core is powerful enough to construct any quotation, and
> all expressions using the core are flat.

Okay. I think I get it. Of course [cons], [], and i are sufficient to
construct any list; I should have STARTED with that.

I will also need a minimal set of execution primitives, as discussed
in the "Theory" paper -- cons and i will serve as two of them, of
course, and there are 3 more unused spaces for any other needed
combinators.

Okay, this is good.

-Billy

William Tanksley, Jr — 2006-11-21 18:27:22

stevan apter <sa@...> wrote:

> > I started with his {cake,k} base, and tried to express some things in
> > it -- but I found that even the simple result [] was unattainable. I
> unlike joy, but like false, operators push themselves
> onto the stack. so

Ah! That's what I needed.

My current language is therefore based on the {cake,k} combinators of
Kerby's paper:

00=k
01=[k]
10=[cake]
11=[]

I was able to easily duplicate all the expressions in that paper, so I
think it's good.

Not *pretty*; not at all. But complete, concatenative, flat, and with
a minimal alphabet. Oh, and with no "extra" symbols needed.

I'd be overjoyed -- or perhaps underJoyed -- to see a smaller
language. I don't see why something smaller shouldn't exist... I can't
read the notation in the Jot/Iota paper.Might it be possible to have a
single combinator that serves the purpose both of k and of cake? Such
a 3-symbol language (I'm assuming that [] can't also be eliminated?)
wouldn't meet my needs, but it would be fun to see :-).

I can imagine a language that eliminates the need for the [] operator
by replacing k with something like 'step'. The step operator doesn't
completely unquote its top-of-stack; instead, it unquotes the head,
and leaves the tail on the stack. (I haven't bothered working out the
details; probably something else needs to be done as well.) This
language, even if possible, wouldn't meet my needs, because it makes
quotations opaque (see Kerby's discussion of opaque versus transparent
quotation), and obviously the step operator as I've described it
doesn't work on an empty list.

-Billy

[] [was: Re: [stack] Parallel computing is concatenative]

stevan apter — 2006-11-19 11:24:30

William Tanksley, Jr — 2006-11-21 16:28:39

William Tanksley, Jr — 2006-11-21 18:27:22