# So what is a concatenative language?

## Christopher Diggins — 2007-04-27 21:13:20

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

    "A concatenative grammar is any context free grammar G, where S = S S

    is a valid production rule."

    "Flat concatenative languages are simply the set of all strings over a

    given alphabet".

    Any thoughts or comments?

    Cheers,

    Christopher Diggins

## William Tanksley, Jr — 2007-04-28 16:57:43

    Christopher Diggins <cdiggins@...> 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

## Christopher Diggins — 2007-04-28 18:22:16

    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 <wtanksleyjr@...> wrote:

    > Christopher Diggins <cdiggins@...> 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

## William Tanksley, Jr — 2007-04-28 19:42:50

    Christopher Diggins <cdiggins@...> wrote:

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

     Ah! That seems plausible. It seems intuitively right (not an indicator

    of truth, but certainly a good thing for a definition). It's

    definitely simple and complete, and clearly distinguishes flat from

    non-flat.

    There's a pernacious typo in your definition, though. You say that "x

    represents one or more non-terminals". Of course, you mean that it

    represents one or more _terminals_. :-)

    Also, rather than "no other production rules are allowed", I would

    suspect that "no other forms of production rules are allowed."

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

     Clearly, your new definition is better for flat concatenative

    languages, since it implies that they are clearly a subset of all

    concatenative languages.

     > Thanks for your feedback!

     You're quite welcome -- thank you for the formal definition.

    I would like to explore the formal semantics a little, though. I don't

    know what exactly a "state function" is, for example.

    Out of curiosity, and as a first attempt at applying this definition,

    is a regular expression specification language concatenative?

     > - Christopher

     -Billy

## Tom Duff — 2007-04-29 15:51:20

    The real definition of "concatenative" is semantic: If P and Q are

    sentences in a concatenative language, then so is P Q, and the meaning of

    P Q is the composition of P and Q.  Isn't that the definition that Manfred

    uses?

    The definition of "flat" is syntactic, and trickier: a flat concatenative

    language is a concatenative language whose sentencess are all either

    atomic or concatenations of (zero or more) other terms.

    This leaves "atomic" undefined.  I can't see offhand what a concise

    definition might be.

    --

    Tom Duff.  The bomb will never go off, and I speak as an expert in

    explosives.

## Christopher Diggins — 2007-04-29 16:40:00

    On 4/29/07, Tom Duff <td@...> wrote:

     >

    > The real definition of "concatenative" is semantic: If P and Q are

    > sentences in a concatenative language, then so is P Q,

     That however is a statement about the syntax. It's hard to not say

    something about the syntax.

     > and the meaning of

    > P Q is the composition of P and Q. Isn't that the definition that Manfred

    > uses?

     This might be slightly more general, but I don't know what a sentence

    is (any sequence of terminals?)

     > The definition of "flat" is syntactic, and trickier: a flat concatenative

    > language is a concatenative language whose sentencess are all either

    > atomic or concatenations of (zero or more) other terms.

    >

    > This leaves "atomic" undefined. I can't see offhand what a concise

    > definition might be.

    >

    > --

    > Tom Duff. The bomb will never go off, and I speak as an expert in

    > explosives.

     - Christopher

## Tom Duff — 2007-05-01 03:35:48

    "Christopher Diggins" cdiggins@... wrote:

     > On 4/29/07, Tom Duff <td@...> wrote:

    > > The real definition of "concatenative" is semantic: If P and Q are

    > > sentences in a concatenative language, then so is P Q,

    > That however is a statement about the syntax. It's hard to not say

    > something about the syntax.

     Any programming language definition is a mapping from syntax to

    semantics.  It's impossible to discuss semantics without mentioning

    syntax.

     > > and the meaning of

    > > P Q is the composition of P and Q.

    > This might be slightly more general,

     The question isn't how general it is, but how correct.  No purely

    syntactic definition can capture a useful, non-trivial notion of

    concatenativity.

     > but I don't know what a sentence is (any sequence of terminals?)

     Me either.  But it's not a problem -- anything that satisfies the

    definition will do.

    --

    Tom Duff.  (^x.xx)(^x.xx)