Re: [stack] Re: Jon Purdy: Why Concatenative Programming Matters

Robbert van Dalen <[email protected]> wrote:
>> iepos proved that although you can produce a parsed combinator
>> language with only one complete combinator (in the literature usually
>> called X), this is an illusion caused by the availability of arbitrary
>> nesting.

> can you give an example of a flat - two combinator - base?

Yes.

Given 'q' and 'k', both defined in iepos' webpage, we can define:

"0" = [] [q] [k]
and
"1" = k.

So, for example, "01" evaluates as follows:

"01" =
[] [q] [k] "1" =
[] [q] [k] k =
[] k.

But since 'k' evaluates its topmost argument and drops its next
argument, the net result is to always drop one argument. (This is the
base I normally use.)

Of course, I haven't given you an example that happens to use the
universal constructor 'q'; this example just dropped it. I can execute
'q' using the bit sequence "0011":

"0011" =
"0" "01" "1" =
"0" drop "1" =
[] [q] [k] drop "1" =
[] [q] "1" =
[] [q] k = q.

Notice that I used the previous result that "01" is a drop.

> does such flat base mean that you can cut an valid expression anywhere to produce two valid expressions?

Exactly -- at literally any bit boundary. This also means that every
bitstring is a valid program, which means that the natural numbers are
valid programs; to enumerate ALL the valid programs I use the natural
numbers (i.e. positive integers, not zero), converted to bitstrings,
stripped of their high bit (this easily includes the empty program,
encoded by "1", and programs with leading zeros).

>> > i believe the real challenge is to find two combinators that have the most 'impact'.
>> Sure, but what does that *mean*? It's a very tough question and may in
>> fact have no answer. I've built most of an evolutionary algorithm to
>> test bases against each other to try to find the "best" one. Figuring
>> how to measure bestness is TOUGH. I've come up with some measures, but
>> none of them are great. (My fitness function builds an array of
>> fitness metrics and randomly compares them.)

> what's the meaning of life?
> the only we can say for certain, is that we - humans - are more likely to reproduce in 'hostile' environment than any other species.

I feel inadequate -- compared to extremophilic archeobacteria -- for
having such a difficult time reproducing around hydrothermal vents,
then. :-)

> for zeroone to survive it must be a meme that easily sticks to a programming brain.

Naw. If that's what anyone wants, stay away from zeroone. It's a
purely computing-theoretic concept.

> zeroone certainly sticks as a name :).

Indeed. I really like "tworing".

> as a concept, zeroone is also interesting.

That's where it's at.

>> Yes, although either a base forms ALL functionality or it isn't
>> complete. (Well, iepos does explain some alternate definitions of
>> "complete" that have some interesting results.)
> yes, i also only consider complete combinator bases - but that they are also capable in generating short programs for small problems.
> or, even better - short programs for big problems.

Yes, you're right; but it's fairly easy to prove that you can always
make some programs shorter at the expense of others. It's very
unlikely that this kind of tradeoff would extend to the macroscopic
effect of making a complete program shorter. On the other hand, I do
suspect it could make describing a more useful base (that is, one with
more than two combinators) easier, and the resulting sublanguage would
be easier for humans to program in. If the elements of that
sublanguage were as short as possible, then it's likely that programs
carefully written using the sublanguage would be candidates for
maximally short programs, and thus decent estimates for the true
k-complexity of the programs produced.

>> But there might be some other measures of "functionality"; for
>> example, would a base be "better" if it provided short bitstrings with
>> known meanings (i.e. commonly used combinators)? The base I use now is
>> defined so that "drop" is "01".
> so
> 101    and   001
> reduce to empty?

No. First: 1 does not simply return an element. Second: 0 returns 3
elements, not just 1. The shortest nontrivial no-op is "0010101",
which runs "0" to place 3 items on the stack, then runs "01" three
times to pop each of them off.

>> What if "nip" or "swap" could be
>> provided as a short bitstring as well, thus allowing selection of a
>> single item out of stack junk?

> can this be done with only 2 combinators?
> can you give an example

Yes, it can be done -- but the bases I've chosen so far make it very
hard. No, I can't give a useful example; I don't remember right off
because there are too many bits.

>> And what about quotations -- how hard
>> or easy is it to express an enquoted version of "0" and "1", and might
>> a language be better if it provided a complete basis, plus a short way
>> to express quotations of its constituent combinators, plus concat to
>> build arbitrary quotations?

> again, can quotations be encoded with only 2 combinators, without nesting?

Yes. I have constructed this; what you do is use my searcher to find a
"short" program that has the same stack effect as "[0]", another
program that has the same effect as "[1]", and a program that performs
"concat". That proves that I can form all combinators.

>> The latter language would be easy to build
>> a Joylike language on, and the automatically produced zeroone code
>> would be decent (unlike a language where the enquoted combinators were
>> long and complex).

> i think you should stick to flat, otherwise all the nice properties of flatness are lost.
> and then you'll just end up with an alternative Joy (which happens to be encoded in bitstrings).

Well, building this other language is a secondary goal. I actually am
more interested in exploring flatness.

>> (Technically,
>> zeroone is more of an abstract machine language than it is a language;
>> there's no names or anything like that. Tworing might eventually
>> include at least an assembler, already includes a superoptimizer, and
>> might include a high level language based on zeroone.)

> how does the super optimizer, runtime and other components relate to each other?

The superoptimizer uses the runtime to test candidates against the
combinator goal. Note that the superoptimizer can only test true
combinators, but within that realm it's quite effective.

> does the super optimizer choose the set of combinators?

No; you have to give it to it.

> is the high level language independent of the choosen set of combinators?

That's tough to answer; I haven't produced it yet. In theory I suppose
you could write base-independent code in it, but that's not why I'm
considering writing it -- it's more intended to help me talk about the
low-level concepts. I'm also interested in what a high level flat
language might look like; nobody knows.

Even more esoteric, though, is the question of what else can happen to
a flat language. I vaguely suspect that a flat language might be able
to address control flow. Such a language would not be concatenative in
the same sense, although it would hold the same aspect in other ways.
I don't know what it would be.

> when and how do you fix the a sequence of combinators  (like 01 = drop)? is that encoded by the fitness functions.

The fitness functions currently test for how good of a base a given
pair of functions make. As always, the problem is that I don't really
know what makes a base better; I have some ideas that I've tossed into
an array, but I don't KNOW.

To make matters worse, I based this genetic algorithm on my old
superoptimizer; but the genetic algorithm produces things that aren't
pure combinators, so the comparison that worked well for the
superoptimizer is BAD for it. It's obvious to any student of computer
science that you can't ever hope to compare two functions, but since I
can already compare combinators correctly, I can make an extension to
compare some impure combinators in many cases. The evolutionary
algorithm won't be perfect, but it'll cover a lot more cases than it
does now, hopefully enough that the fitness landscape will be
adequate.

> R.

-Wm