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)