Re: [stack] So what is a concatenative language?

Christopher Diggins <[email protected]> wrote:
> I've made an attempt at creating a more formal definition of
> concatenative languages which I posted on my blog (
> http://cdiggins.com/2007/04/27/what-is-a-concatenative-language/)

A noble ambition! Thank you.

> "A concatenative language is a context-free language that can be
> expressed using a concatenative grammar. The defining characteristic
> of phrases in a concatenative language, is that if A and B are valid
> phrases in a concatenative language L then the concatenation of A and
> B is also a valid phrase in L."

The second sentance is not part of the defintion; it's purely
informational. (Right?)

> "A concatenative grammar is any context free grammar G, where S = S S
> is a valid production rule."

Hmmmmm... This seems far too expansive. It seems possible that S could
be defined with arbitrary parsing complexity, and S itself would be
embedded in a language of more complexity. For example, it almost
seems like C could include a production like that, perhaps named
'ClusterOfStatements' instead of 'S' (a ClusterOfStatements would go
inside a Block).

But C isn't concatenative, nor is the sublanguage that you can use
inside a block concatenative. Is it? (Perhaps our definitions truly
are too vague, and it accidentally is!)

I'm definitely including some implicit restriction that your
definition doesn't. Perhaps I'm just being too parochial, limiting my
personal definition to tightly fit only the languages I already know.
I'm definitely doing a bad thing by leaving the restriction unstated,
but I can't think of a formal way to say it. I did say something about
"arbitrary parsing complexity", but I recognise mere handwaving even
when I'm the one doing it.

> "Flat concatenative languages are simply the set of all strings over a
> given alphabet".

Gut feeling: I think you're right (of course, ignoring semantics such
as typechecking).

> Christopher Diggins

-Billy