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

Hi William,

I have responded inline below, but as a result of your suggestions I
have revised the definition:
http://cdiggins.com/2007/04/28/a-definition-of-concatenative-languages-refined/

On 4/28/07, William Tanksley, Jr <[email protected]> wrote:
> 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?)

Yes.

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

I'm using S in its common use as the initial (Starting) production.
However you bring to mind a good point.

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

You bring up an excellent point!

> 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 don't think you are.

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

After your post, and my thoughts I have realized that my definition is
overly general. I have a new idea.

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

Thanks for your feedback!

- Christopher