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

Robbert van Dalen <[email protected]> wrote:
>> I've got a few more things to do today, so I can't post much more; but
>> anyone who doesn't know what I'm talking about when I say "new bases"
>> should start reading http://tunes.org/~iepos/joy.html. What you should
>> try to understand is his sentence: "The eight combinators presented
>> above are by no means all of the combinators; there are infinitely
>> many combinators. However, eventually we'll show that from the above
>> combinators, it is possible to construct all other combinators. In
>> fact, it will turn out that there is a base consisting of just two
>> combinators, from which all other combinators can be constructed."

> Does zeroone have exactly two combinators and are they different from iota or jot?
> http://semarch.linguistics.fas.nyu.edu/barker/Iota/

Yes, exactly two; and yes, the languages are different. Iota and Jot
are not concatenative. One simple consequence of this is that in Iota
or Jot, knowing what a particular sequence of zeros and ones means in
one part of a program doesn't tell you what that same sequence means
at a different part of the program. Those two languages have a tree
sequence, so by copying and pasting a string into a new place you
produce a string with a different meaning; the one string may actually
be parsed into two or more strings that get passed to completely
different combinators.

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. If you remove parentheses from the language, you need at
least two combinators. In a completely concatenative combinator
language, one of the combinators in the base MUST accept no input and
produce some output, while the other combinator will execute at least
one of its inputs.

>> Once that sentence makes some sense to you we're ready to go. You
>> won't have to understand how to construct combinators; you'll only
>> need to understand the basic ideas behind that sentence: combinators,
>> a base consisting of a number of combinators, and the concept that
>> combinators can be used to construct other combinators.

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

> i.e. their combinations must spawn maximal useful 'functionality'.

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

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

That probably made little sense to most people here, but it does
explain the questions I'm wrestling with.

> is that what zeroone is about? to find the best two combinators?

Sort of, yes. Zeroone is just a name for the set of languages.
"Tworing" is the project's name; it includes a brute force
superoptimizer, an evolutionary algorithm to find the best two
combinators, and a language constructor for zeroone(s). (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.)

>> Seriously, though, I read up on CAMs; sounds right up your alley (from
>> your work with the Enchilada language), as it would fit nicely on
>> highly parallel machines. I'd like to hear more.
> the idea is that OER will always produce all possible results (postfix expressions that can't be rewritten anymore), lazily.
> in that sense, OER is non-deterministic, just like prolog, but i'm not sure if i should pursuit this direction.

Sounds like there's a lot of work to be done there. Cool! It also
reminds me of DNA computing.

> R.

-Wm