Re: [stack] language hierarchy

Christopher Diggins <[email protected]> wrote:
> William Tanksley, Jr <[email protected]> wrote:
> > 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.

Okay.

> > 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".

Your change is accepted.

> You would have problems in Cat  because of the fact that you can't write:
> 1 2 [define f { 3 4 }]

Clearly, the 'define' part of Cat is not itself concatenative. That's
okay; Joy has a non-concatenative superset. So does every other
practical concatenative language. The only way around that is to use
dynamically scoped definitions.

> Allow me to paraphrase:
> "A concatenative programming language is a language in
> which the concatenation of any two valid expressions 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?

Right. This is why I threw away the "finite set of expressions" rule,
and instead used the term "Kleene closure".

> 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.

I'm very much not good at reading these things... But is this grammar
actually complete? That is, does it accept an expression if and only
if it denotes a valid SK expression? From just looking at it, it
appears that it will accept things which are not single SK
expressions. To the best of my knowledge, an SK parse tree must have a
single root. I'm not familiar with how to interpret a dual-rooted SK
parse tree.

And I can't seem to find any description of SK's grammar online. I
found Iota and Jot, which are similar...
http://barker.linguistics.fas.nyu.edu/Stuff/Iota/, in one of the first
paragraphs, says that the language includes 'i', but not 'ii', so they
fail my definition.

> > 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.

Because application isn't closed under concatenation -- you can
concatenate two valid terms together and not get a valid application
(if the first term isn't a function with at least one free variable).
If the programmer does this, the language has to choose some semantics
OTHER than application, which isn't permitted by either of our
definitions (that there be only one operation).

> > 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.

Concatenation is associative. Any operation which is bidirectionally
implied by it must also be associative.

> 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
> semanatics, not their syntax.

Not true. Regular expressions are a language that is syntactically
different from other languages; then you have LL languages, then LALR,
then LR. The classifications you're listing are not "language
classifications" in a language-theoretical sense; they're different
styles of programming, and any of them can be done in a single
language. Many computer scientists study them, and many programming
languages are specialized to use one exclusively; but most of those
languages are a subset of LALR, so a pure language researcher will
yawn and look elsewhere.

Another way of looking at things is to point out that those
programming styles cannot be languages, because there's no way to
distinguish between them using a terminating grammar. (Hmm, that
statement smells suspicious to me... But I think it's close enough to
true.)

My point: when studying languages, syntax is important. See
http://en.wikipedia.org/wiki/Formal_language: "In formal language
theory, a language is nothing more than its syntax; questions of
semantics are not addressed in this specialty."

So how would you tell a formal language theorist how to tell when he's
looking at a concatenative language? This guy's going to be looking
only at a grammar -- he won't look at the generated source code. I can
tell him to look for a language which is identical to its own Kleene
closure, and he'll know what to look for.

Now, if I tell that to a programmer, he'd be stumped. Even a language
implementer won't know what to do -- although he'd be able to write a
parser, he couldn't write an interpreter. So I like your definition,
as it provides additional clarity.

Keep in mind that your definition isn't any more precise, or at least
I hope not. If it's more precise, I'm ruling out languages which
should be considered concatenative, and that would be a pity. Nor is
your definition the easiest to implement; for example, if I weren't
curious about whether there were other interesting operations, I could
define concatenative languages to require composition; or to go even
further, I could define them to require a stack of lists, symbols, and
numbers plus a global dictionary as the parameter which is passed
between the functions.

Those definitions would be more clear, but in at least the latter
case, destructively more narrow, since the last definition would
exclude Forth and Factor (which use two stacks and the contents of
memory) -- and I suppose would make Joy programs that perform output
technically non-concatenative.

> 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.

Yes, but now you're trying to define a language in terms of its
semantics. Semantics rests on a foundation of syntax.



> - Christopher

-Wm