Re: [stack] language hierarchy

John Nowak <[email protected]> wrote:
> Going along with the discussion trying to pin down a definition of
> concatenative and/or develop a new term, I propose this hierarchy with
> the hope that it might be partially correct and/or useful:

Be careful about hierarchies that extend outside of this group's
direct interest -- if we were to develop one, we really should try to
develop it on a general-interest programming language group rather
than one limited to our narrow interests.

But I never could resist an argument over nit-picking semantics :-).

> A functional programming language is one that treats computation as
> the evaluation of mathematical functions and avoids state and mutable
> data.
> Examples: Scheme, ML, Haskell

Hey, that works. It's a direct quote of Wikipedia, so I can't argue with it.

> A function-level programming language is a variable-free functional
> programming language in which all functions are unary and new
> functions are created in terms of existing functions through the use
> of functional forms.
> Examples: FP, FL, APL (?), J (?)

I don't know about FP and FL, but APL, J, and K are binary; and I'm
not sure it's good to leave them out. How about we call this the
"combinatory programming language", and rather than talking about
"functional forms" (what are those? Google won't tell me), we refer to
"combinators"? Or is that totally not what you meant?

Another naming choice would be "dataflow language".

> A compositional programming language is a function-level programming
> language in which composition is the only functional form.
> Examples: Joy, Cat, etc

I don't know what a "functional form" is, so I can't reply.

> A concatenative programming language is a compositional programming
> language in which the concatenation of functions denotes composition.
> Examples: Joy, Cat, etc

I don't want to narrow us down enough to exclude Forth, Postscript,
and possibly Factor. Forth has never attempted to be functional.

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

> Side note: Given that the term compositional programming is taken,
> what about calling them composable programming languages? You'd have
> the following definition (roughly):

I don't mind using either word. Neither one is heavily used.

> "A programming language is composable if it is a variable-free, all
> functions are unary, and new functions are created only by composing
> existing functions."

I'd just skip the first two requirements. Why exclude a language which
includes variables?

> In addition to it not yet having a meaning, I find the term
> "composable programming language" somewhat more playful and to-the-
> point. It also highlights the composable/factorable nature of such
> programs nicely.

It does look like it's available for our use. I see one random person
on the web using it to mean "a language in which every statement
returns a value." I'd translate that to mean "a language in which
every statement is an expression," (and thus can optionally be
textually included inside another, appropriately typed, statement). I
think this definition has an advantage over your earlier one in that
it's phrased in a positive way. It also happens to be a broader
definition than "concatenative"; every concatenative language is
my-definition-composable, but Scheme is my-definition-composable but
not concatenative or combinatorial. FP is my-definition-composable and
combinatorial, but not concatenative.

Is it possible to be concatenative but not combinatory? It's
definitely NOT possible to be concatenative but not composable (both
by my definitions).

> - John

-Wm