Re: [stack] language hierarchy

On Dec 9, 2007 3:21 PM, William Tanksley, Jr <[email protected]> wrote:
> Christopher Diggins <[email protected]> wrote:
> > > > So concatenation of terms in Haskell denotes application, but it isn't
> > > > considered a concatenative language according to your definition. Try
> > > > explaining that to a random group of programmer or computer scientists
> > > > and see what their reaction is.
>
> > > But it doesn't, I think. Concatenation of terms in Haskell perhaps
> > > offers those terms for partial application; but the application only
> > > happens if the first term denotes a function with a free variable.
>
> > That statement is simply false.
> > See: http://www.haskell.org/onlinereport/exps.html
> > "Function application is written e1 e2."
>
> I can't read that page, unfortunately (a lack of experience with the
> grammar); but from the look of it, the grammar is a LOT more complex
> than you're implying. It's true that function application is written
> e1 e2; but that doesn't mean that everything written as e1 e2 is a
> function application. Does it?

Yes: where e1 and e2 are expressions. Haskell gets confusing because
it has infix and prefix operations, but this is negotiated by the
syntax parsing rules. Haskell is concatenative (by your *current*
definition), interesting (e.g. turing complete and expressive), and
based on application instead of composition.

However, you may find it telling that while "f 5 2" might be valid (if
f is a binary function). The terms "5 2" by themselves are not a valid
expression, because "5" is not a function and can't be applied to 2.
In Haskell you have to build left-associative parse-trees. This is
very unpleasant from my point of view: I like concatenative languages
precisely because I can generate a left-parse tree or right-parse
tree, evaluate both of them and get the same result.

You may then want to restrict the definition of concatenation to
reject this anomaly. So perhaps in a concatenative language
concatenation should have meaning and be associative. Application is
not associative. So given that new reformation of concatenation, I
would come right back to the fold, and embrace concatenative as a good
description of Cat. See below for a new definition proposal.

>  And in fact, right above the informal
> discussion of e1 e2, there's a grammatical and precise note about
> "[fval] aval", which seems to imply a distinction between functions
> and things which can be applied to functions.

There isn't any distinction. Application (a.k.a. "function
application") is a higher-order operation that takes a function and a
value (which can also be a function). Only functions can ever be
"applied" to values.

> > > I don't think the path you're trying to walk will be fruitful. The
> > > problem is that any language written in plain text MUST do something
> > > when terms are concatenated (because that's the only thing you can DO
> > > with plain text);
>
> > False. The following is not simply invalid C:
> > "12 13"
> > Notice the concatenation of terms!
>
> I don't get it. That looks to me like invalid C. Why do you say it's
> not invalid?

Sorry, typo, I meant "simply not valid". It contradicts your claim
that "any language written in plain text must do something when terms
are concatenated".

> Anyhow, my point was that there must be SOME use of concatenation for
> every text based language;

But there isn't a [semantic] use for concatenation in C: it is simply
a token delimiter. I am overlooking that.

> but calling a language "concatenative" has
> to mean that concatenation _always_ means something.

Which it does in Haskell. It always means application.

> > > trying to call a language "concatenative" merely
> > > because it "does something" *in some cases* when terms are
> > > concatenated is so vague it describes ALL languages.
>
> > That is not true. See: C, Java, C++, Pascal, Algol, etc. etc. etc.
>
> Those are further examples of my point: languages in which
> concatenation does something some times.

What does concatenation do in these langauges other than as token delimiters?

> The simple *presence* of
> concatenation in the grammar isn't enough, any more than the simple
> presence of functions is enough to make a language "functional".

I agree concatenation of expressions has to have a specific semantic
meaning: this implies a presence in the abstract syntax grammar (as
opposed to the concrete or surface syntax grammar).

> > > A language that deserves the name "concatenative" should respond to
> > > concatenation in the same way every time.
>
> > Whatever response you require in your definition, be it application,
> > composition, or some other operation, will be arbitrary: hence
> > confusing.
>
> But my point is that I don't require anything in my definition.

Yes, sorry that was aimed at other people intent on deciding that
concatenation should imply composition.

> There's nothing arbitrary there. You can propose any operation you
> want; but so far, the only one that's proven to work consistently and
> "interestingly" is function composition.

Application has also been proven to be interesting. See: Combinatory
Logic, ML, Haskell.

> Now, I admit that my definition lacks boundaries; nobody knows for
> sure whether composition is the only possible operation.

I have already shown you several examples of langauges where
concatenation implies application.

> But in the
> same sense my definition also lacks arbitrariness.

Yes. I disagree that as it stands the definition rejects applicative
languages. Here is a new suggestion for the definition of
concatenative language:

"A concatenative language is a programming language where the
concatenation (i.e. the sequencing or juxtaposition) of terms
corresponds to an associative operation on functions."

The implication of this is that any sequence of terms will have both
left-associative and right-associative abstract syntax trees that are
equivalent in meaning.

I know that this is a bit of an about-face from my earlier stance, but
having been forced to think about things more deeply by William's
comments it seems somehow intuitive that in a concatenative language
(f * g) * h and f * (g * h) are equivalent, where * is the operation
denoted by concatenation. It makes me very happy to be able to express
this with some degree of formalism.

> > - Christopher
>
> -Wm

Thanks for hammering out these issues William,
Christopher