Re: [stack] language hierarchy

On Dec 10, 2007 1:17 PM, William Tanksley, Jr <[email protected]> wrote:
> I'm going to do something that's VERY unusual for me. I'm going to
> say, "let's skip the arguments and cut straight to the agreement."
>
> We've got a LOT of misunderstandings going in this thread... But
> you've come up with a refinement of the "standard" definition which is
> IMO beautiful.

Thank you. This definition is only due to your help.

> So, let's skip the arguments and cut straight to the agreement. THEN
> we can start arguing again more efficiently.
>
>
> Christopher Diggins <[email protected]> wrote:
> > 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."
>
> I like it. It actually reveals something to me that our original
> standard definition failed to do; specifically, it explains how my
> idea of "flatness" is related to the standard idea of concatenativity.
> I think you've discovered something very important.
>
> Let me paste in my phrasing of the "standard definition": "A
>
> concatenative programming language is a language in which the
> concatenation of any two valid programs is a valid program."

By saying program instead of expression or term, you are introducing a
new restriction which IMO unneccesarily restricts the class of
languages excluding a Cat language with namespaces. Program structure
is generally not considered as interesting as term or expression
structure.

> Your definition is superior in that it expressly requires
> associativity, which (come to think of it) was part of what I was
> assuming all along. Therefore, I like it and second your vote to make
> it the new standard definition.

> I do have a question, though. Does the old standard definition
> covertly imply associativity? It does rule out application (contrary
> to your earlier statement), since application doesn't work between
> "any two programs". I think there's a clear implication that the
> properties of concatenation should apply, but I think the old
> definition is incomplete and erroneous because it does NOT clearly
> state that all programs in a concatenative language can be built using
> only composition.
>
> I did, earlier in this thread, post a definition which included that
> requirement: "A concatenative programming language is a language in
>
> which the concatenation of any two valid programs is a valid program,
> and the entire language can be generated by the concatenation of a
> finite set of primitive programs."

Again, I disagree with the usage of "programs".

You would have problems in Cat  because of the fact that you can't write:

1 2 [define f { 3 4 }]

Allow me to paraphrase:

"A concatenative programming language is a language in
which the concatenation of any two valid expression is a valid expression,
and the entire language of expressions can be generated by the
concatenation of a
finite set of expressions."

This rejects Joy:

expr = primitive | expr expr | [expr]

How do you construct [expr] from concatenation alone?

And if you allow it somehow is still seems no different than the
generative grammar for the abstract syntax of the S K calculus:

expr = S | K | expr expr | (expr)

Looks pretty much the same to me.

> In other words, the language must
> be closed under concatenation (which rules out application as the
> meaning of concatenation)

I don't see how you arose at that conclusion.

> and must consist only of primitives and the
> concatenation of valid programs. This requirement in turn implies that
> the semantics of the language must follow the properties of
> concatenation, including associativity.
>
> I believe that this is exactly equivalent to your definition: HOWEVER,
> I believe that your definition is useful when discussing semantics,
> since it makes a direct semantic requirement which my definition
> leaves implied.

Again, I don't see the semantic requirement implied.

> Hmm. My definition still has a flaw: it demands a finite set of
> primitives, which ignores the fact that literals (such as quotations)
> may be infinite. How about this: "A concatenative programming language
> is a programming language which is identical to its own Kleene
> closure."  I found that term on Wikipedia while trying to sort out the
> idea of closure. A Kleene closure of a language is the set containing
> all concatenations of all terms in the language. It's the meaning of
> the Regexp symbol "*".
>
> In other words, although Haskell isn't concatenative, Haskell* would
> be (by my definition). :-) This suggests (jokingly) that C* would be
> the new concatenative version of C, just as C++ is the object-oriented
> version. (No, I don't want to see C++*. I suspect C*++ would be less
> complex than C++ alone.)
>
> My definition, however, is now *very* specific to syntax. Perhaps I'd
> better phrase it as: "A language's syntax is concatenative if the
> language it accepts is its own Kleene closure." Then, your definition
> rephrased to be parallel to mine would be: "A language's semantics is
> concatenative if every term denotes a function, and every
> concatenation of terms denotes an associative operation on those
> functions." (Hmm, is the word "semantics" plural?)
>
> Now I *really* like your definition!!! This rephrase makes it VERY
> clear to me that even my new version is inadequate -- it was PURELY
> syntactic. I'm not sure whether your definition is sufficient by
> itself -- but it's clearly *necessary*.
>
> What do you think?

Well I don't think you need to say "semantics", it is implied. All
common programming language classifications are based on semantics
(functional, imperative, stack-based, declarative, logical,
higher-order, first-order, array-oriented, concurrent, etc.). Computer
scientists are concerned about classifying languages based on their
semenatics, not their syntax. I would make a couple of other minor
changes:

"A language is concatenative if every term denotes a function, and the
concatenation of terms denotes an associative operation on those
functions."

Though I think this is precisely my previously submitted definition.

- Christopher