A Definition of Concatenative Languages (refined)
My previous attempt at a formal defintion of the syntax a concatenative language was overly broad. Thanks to William Tanksley for helping me understand the problem with the earlier definition. For an informal description of a concatenative languages see the Wikipedia entry.
A concatenative language is any language that can be described using a concatenative grammar. A concatenative grammar has no non-terminals other than the initial one (S) and always has the following production rules:
- S = SS
- S = x
-
S = empty
Where x represents one or more terminals. A non-flat concatenative grammar contains at least one production rule of the form:
-
S = aSb
No other production rules are allowed.
The semantics of a concatenative language are that each term is a state function (e.g. from a set of stacks to a set of stacks), and the concatenation of two terms implies the composition of those functions.
[…] The following definition was far too broad. A refined definition is now available at: http://cdiggins.com/2007/04/28/a-definition-of-concatenative-languages-refined/ […]
Pingback by cdiggins.com » Blog Archive » What is a Concatenative Language? — April 28, 2007 @ 6:19 pm
Well, I don’t exactly get that, but I suppose it now means I can then write
S = x
S = Sx
Because the strings in the language are identical to the ones you gave, only not ambiguous.
Now, one could form such a string by gluing two strings that are each S’s together to get another S, of course, but the grammar above is sufficient and unambiguous: It applies to the concatenation as much as it does the two separate strings.
(One of the interesting features of generative grammars is that many grammars may produce the same languages and the question then, is, what is the simplest type of grammar that the language has. In the case above, it would appear that we are talking about regular languages, not context-free ones. I think multi-adic operators and types will require a context free version, whether prefix- or postfix-style.)
I get the semantics now. Thanks for that separation.
Comment by orcmid — April 28, 2007 @ 11:02 pm
Oh, if you are going to allow the empty string [overlooked it] then we have
S = emtpy
S = Sx
And we are in the same boat. These are still all of the strings of the language with only the one terminal, x. I assume adding more terminals is simply to add productions like
S = Sy
S = Sz
and so on.
There’s something way too simple about this. What am I still missing?
Comment by orcmid — April 29, 2007 @ 4:04 am
There is now a counter-example against my definition at http://tech.groups.yahoo.com/group/concatenative/message/3320 .
We are in the process of hammering out a better definition.
Comment by cdiggins — April 29, 2007 @ 4:41 pm
It would seem that S = SS is the giveaway. Anything with that production is going to be concatenative. You’ll notice that I didn’t use it. I made concatenative a consequence of the grammar, not a feature of the grammar.
It will be interesting to see how this plays out, although I’m not sure this is going to be critical to your work on Cat (since typing takes you outside of even context-free grammars and has to be dealt with as a semantic constraint, it seems to me).
Comment by orcmid — April 29, 2007 @ 5:38 pm
You are correct. A syntactic definition of concatenative is really just me procrastinating, since working on the type checker is much harder ;-)
Comment by cdiggins — April 29, 2007 @ 5:43 pm