Re: [stack] language hierarchy

> John Nowak <[email protected]> wrote:
> 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?

This page might explain it a bit better:
http://en.wikipedia.org/wiki/Function-level_programming

This goes into more detail on functional forms (aka "functionals" on the
wikipedia article):
http://www.stanford.edu/class/cs242/readings/backus.pdf

As for J and K, I've seen them called function-level, but this may simply 
be confusion because they're point-free. I'm not really sure.

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

Is Forth really not functional? Can you not view every function as [stack,
world] -> [stack, world]? I realize this doesn't really capture the spirit
of the language, but I think it allows Forth to still be classified as
functional (or function-based). It is possible that Forth violates this in
ways I'm not aware of; for instance, a Forth with local variables (global
is fine)
might not apply. I'd be interested in hearing arguments as to why this
view of Forth as a functional language isn't valid.

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

It is necessary to exclude them if you're writing strictly in terms of
function composition. Dealing with variables implies you're doing
value-level programming, not function-level programming. If you don't
consider concatenative languages to be function-level, then you'd not need
to exclude them. Backus's paper goes into more detail on this.

However, if you do allow variables, you lose the factorability of
languages like Joy. I'm not sure I'd want to call anything with local
bindings (module systems are okay) concatenative, because you can't create
new functions simply by concatenating; you've got scopes, name clashes,
and so on getting in the way. Modules don't violate this, because you can
still compose functions easily within a module, modules exist to avoid
name clashes, etc.

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

He's a rogue and a drunkard anyway.

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

Perhaps the quick, precise definition is:
"A language is composable if programs are written only by composing
functions."

This implies a few things that we can avoid stating outright:
- There are no variables; if there are, you're not writing only in terms
of function composition, are you!
- All functions are unary (else they'd not be composable... assuming they
all return single values anyway, which seems to be a sane assumption)
- A concatenative syntax isn't required, but it is the most obvious choice

Joy would fit in this category. FL would not, as functions can be
manipulated in ways beyond composition. Forth should fit provided local
variables are eschewed. Haskell wouldn't.

> Is it possible to be concatenative but not combinatory?

Heh, it really depends on the definition of concatenative. If you just
mean a concatentive syntax, then yes. For example, look at unary messages
in Smalltalk. You're composing messages which select functions, not
functions themselves.

> It's definitely NOT possible to be concatenative but not composable
(both by my definitions).

Again, depends on the definition. I would think the Smalltalk example
above is concatenative and not composable, assuming you're talking about a
concatenative *syntax*. If you consider concatenative languages as a
subset of compositional/composable languages as I originally proposed (and
as I would still stick with), then you're correct (by definition).

- John