Re: [stack] the concatenative wikipedia article

John Nowak <[email protected]> wrote:
> William Tanksley, Jr wrote:
>>> 1. 'f g' denotes the composition of 'f' and 'g'
>>> 2. 'f g h' denotes the composition of 'g' with the construction of
>>> 'f'
>>> and 'h' (construction is basically a cleave combinator)
>>> 3. Grouping is to the right such that 'f g h i j k == f g (h i (j
>>> k))'
>>> 4. Composition is associative such that '(f g) h == f (g h)'

>>> So, is this concatenative? It's just composition and cleave
>>> combinators.

>> As I see it, no. The problem is that grouping is semantically
>> significant (rule 3), but not syntactically significant (rules 1&2).
>> It violates my rule that a concatenative language must have
>> associative semantics and syntax -- that means no required implicit
>> grouping.

> So if I got rid of rules 2 and 3, would it be concatenative? It would
> have the same underlying semantics except concatenation is would
> always mean composition.

Yes -- if you provide syntax for cleave, the rest of the language is
clearly listlike and associative.

Unfortunately, the example you give doesn't appear to conform to the
rules I listed above; you seem to be using some alternative
non-concatenative syntax.

> This:
>    (sq b) - 4 * a * c
> Would be written like this instead:
>    - [sq b, * [4, * [a, c]]]

How is that concatenative? It appears totally applicative. I certainly
don't see any opportunity for associativity in that example... If this
is how things must be done, then I take it back: your language may
possibly technically use composition, but if it's not associative in
practice, it's not concatenative.

> If your answer is yes, my problem with that is that we don't impose
> the same syntactic restrictions on the definition of an applicative
> language.

We talk about applicative languages here, but the reality is that
there are many different syntaxes for applicative languages, united in
common by one syntactic feature: the need for a tree structure.
Calling a language "applicative" doesn't tell you what its syntax is
like (except that it must be tree-structured), while calling a
language concatenative does tell you what its syntax is like.

I think it's proper to define and classify languages in terms of their
syntax, as long as one remembers that syntax and semantics are tied
together by definition of "language". "Applicative" is not such a
classification; "concatenative" was intended to be. Remember the
now-obsolete term "flat", that was intended to be a subset of
"concatenative"? I decided there was little need for flatness once we
realized that associativity neatly explained concatenative ease of
use; but flatness is syntactic too. Other syntactic classifications
include tree-structured, LL, LALR, etc...

> Tons of syntaxes are employed (Lisp, Haskell, J, FP, etc),
> yet we still call them all applicative. Perhaps concatenative isn't
> the right term, but I'd very much like a term focused strictly on
> semantics like "applicative" is. Again, "compositional" or similar
> seems like the obvious choice with "concatenative" being a subset
> defined partially by its syntax.

Composition is a possible term for semantics... I suppose you could
use it. It doesn't seem very useful, since as Chris and I have been
hammering out, it's neither a subset nor a superset, but rather just
one feature a language can have. An applicative language can have
compositional semantics in some part of its syntax (your language
appears to be an example of that), and that part of its syntax will be
concatenative... but it's kind of hard to say that it's a
concatenative language, since actual use of associativity is very
rare.

> - John

-Wm