Fwd: [stack] language hierarchy

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

It does indeed! Thank you.

And now I'm enlightened. You weren't merely making up your own
hierarchy :-); you were citing well-established terms.

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

Wikipedia lists them as examples, and doesn't list APL. I think it's
right -- APL functions are not really manipulable.

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

I see what you mean. I agree.

And I guess one might say that concatenative languages would then be
function-level languages such that the functional form 'unary
composition' is denoted by the syntactic relationship of
concatenation. I'm not sure that it's right to say that composition is
the ONLY functional form; others may be permitted (for example, 'map'
is a functional form). Perhaps the rule is that those functional forms
not be expressed in syntax.

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

I agree. It's also not destructive to have local non-concatenative
syntax here and there, so long as there's some interesting subset of
the language that IS 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.

> 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

Okay, I'll agree with that.

What other syntax choices are available, aside from the trivial choice
of using a symbol to represent the composition operator? Is that the
only difference between this definition of 'composable' and
'concatenative'?

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

...yet well-defined and "interesting" subsets of all those languages
would be composable. Haskell, to the best of my knowledge, doesn't
have an interesting subset that's concatenative -- you have to use an
explicit operator to denote composition.

Correct?

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

> Again, depends on the definition.

Hence my caveat "by my definitions".

> - John

-Wm