Re: [stack] Concatenative Research

Justin <[email protected]> wrote:
> Hello. Is this forum still alive?

Well... it is not dead which can eternal lie.

I'm still actively working on some theory.

> I haven't shown my head here for a couple of years. I'm a MA/CS major with an ongoing interest in giving concatenative languages a firmer mathematical foundation. I have a few partial results: (i) an operational semantics, (ii) a concept of & application for homomorphisms, (iii) a type system. Is anyone else around here interested in this sort of research? Here's a link to my (ongoing) work,
> http://dl.dropbox.com/u/17328602/concat/index.html

Wow, that's pretty cool. Thank you!

Others have suggested using "compositional language", and there's
nothing wrong with that; but historically, it's already been used in a
number of fields to describe other languages. In cognitive science,
it's the ability for the brain to form languages out of multiple
parts; in software engineering, a compositional language is a language
designed to help components interoperate. I like "concatenative
language" not only because it's not previously used in this field, but
also because it nicely describes the syntax of the language, and
syntax is a crucial part of a language's description.

I'm currently working on exploring a useless nook of concatenative
languages that I called "completely flat languages". A completely flat
concatenative language is defined not only by being concatenative
(that is, any two valid programs can be concatenated to form a valid
program), but also by being completely flat -- there is no discernible
syntactic structure. This means that every bitstring is a valid
program, and a program can be cut at any location to produce two valid
programs the composition of whose semantics is the original program's
semantics.

Naturally, I reduced this to the single-bit case: a language with only
two words, "0" and "1". "0" pushes some quotations on the stack, and
"1" pops and executes things from the stack. I'm currently using the
"k" combinator for "1", and usually "0" is something like "[], [cake],
[k]". (See Kerby's definitions of common combinators on
http://tunes.org/~iepos/joy.html#cakek for explanations.)

I fairly easily built a brute force searcher for combinators in the 01
language (integers map to all possible programs, so brute force is a
simple search), then I added two interesting types of pruning (took me
years to track down the last bug I fixed), and just a few months ago
completed it. I just (this month) added a genetic algorithm to search
for "better" definitions for "0", after which I ran into problems with
my brute force searcher (I can compare combinators, but I don't
properly compare quoted combinators). We'll see what happens...

Your typechecker may well be useful, and your theory looks in line
with what little I know. What license is your code under?

My code's at https://bitbucket.org/wtanksleyjr/tworing, under GPL.
Python, just like yours.

-Wm