Re: [stack] Concatenative versus Compositionality

Christopher Diggins <[email protected]> wrote:
> William Tanksley, Jr <[email protected]> wrote:
> > reasonably, that because we're uncertain
> > about the precise results of the term 'concatenative', we should use
> > another term; you suggest 'compositional'.

> That doesn't quite characterize my reasoning. The fact that there is
> uncertainty is not of concern to me. I am suggesting that the nature
> of these languages is not the concatenativeness (lets define this as
> meaning a language where whitespace corresponds to an operation) but
> rather the compositionality. Haskell is a language where concatenation
> denotes function application, and Joy is a language where
> concatenation denotes function composition.

Okay, good. This is really clearing my mind!

(But I don't agree that "concatenative" means anything about
"whitespace". More later.)

> What unifies the languages
> so far labeled as concatenative is that they are compositional
> (whitespace denotes function composition).

I didn't want to talk about whitespace... Ah! An example. In Joy:
"1[3][+]map" is concatenative in spite of not having whitespace. (Er,
I hope I got that right... you know what I mean.) Yes, I think you're
right that I intended the definition to refer to function composition;
but I didn't want to simply say that the language *allowed* function
composition, but rather that the language had function composition as
the default function when terms appeared adjacent to each other.

You're forcing me to think now.

I think you're right to point out that there are TWO terms,
"concatenative" and "compositional" that well-describe the languages
we're interested in on this group. I don't think that "compositional"
has any pride of place, though; either term would be appropriate, and
"concatenative" has the minor advantage of describing syntax, which
makes it clear that we're discussing syntax rather than pure
semantics. Indeed, one of the interesting things about "concatenative
compositional" languages is that their implementation semantics are so
flexible -- you don't _have_ to implement them in a functionally pure
manner (i.e. disassembling and reassembling the stack at each function
call).

...but, later, I discuss why "concatenative" may be sufficient after all.

> > I also don't agree with your claim that Haskell qualifies as a
> > concatenative language. Am I wrong? Do any two valid Haskell programs
> > concatenated together form a valid Haskell program?

> No it is not true in the general case. But does the general case hold
> for Forth or Postscript? Does it also hold for all Joy programs
> without exception?

I don't mean to make an impossible criticism. Of course, any real
programming language needs a superstructure, if for no reason other
than to allow quotation. Haskell also has OTHER purposes than "being
concatenative" (no matter what that means), so we must allow it to
exclude features.

So here's a rephrase of my "valid subset" question: Does Haskell have
an interesting subset which is "concatenative" without also being
"compositional concatenative"? One possible definition of
"interesting" is "Turing complete".

If it's possible to define an interesting language which is
concatenative, but not "compositional concatenative", then the
distinction is important. If it's not possible, the term
"concatenative" alone is sufficient. OTOH, if it's possible but simply
unlikely, the discussion group can keep the name "concatenative" until
someone actually manages to build that language.

> I think however, the concatenation of programs is of less relevance
> than what it means to concatenate terms (i.e. expressions) in the
> language.

Now we have a real difference. I see things the other way around: the
semantics of a language are secondary to the syntax, _when designing
or studying a language_. A language _is_ syntax; it merely connotes
semantics.

> Only looking at whether whole programs can be concatenated
> is too restrictive. Consider if we were to add some features to Joy
> (e.g. some kind of modularization constructs or scoping constructs)
> which meant that arbitary programs could no longer be concatenated,
> but the core semantics of the language were preserved: would that make
> the language an entirely new category?

I mentioned the concept of "interesting subset" above. I tried to
leave the definition of "interesting" loose... What do you think of
that?

> This an indicator that
> concatenation defined at strictly the program level is too narrow to
> merit a categorization.

The ability to construct a hypothetical doesn't show that the
hypothetical is possible. :-)

> > My knowledge here
> > is limited, but I don't _think_ currying is that powerful -- _some_
> > Haskell programs are 'concatenative' in that sense, but it's not a
> > general feature of the language, to the best of my knowledge.
> > Furthermore, if Haskell were concatenative, would that be bad?

> Nope, in fact it would be very good. Bridging the gap between
> compositional concatenative languages, and applicative concatenative
> languages would be an excellent thing for the community. There is a
> lot for members of Haskell and ML community to bring to the table.

Again, I'm not sure that Haskell does have any "interesting" subset
that's concatenative but not also compositional. Specifically, I don't
believe it's possible to apply arbitrary expressions to each other in
any interesting way. Yes, you can apply expressions to functions with
free variables, but I don't think it's interesting/meaningful to apply
expressions to completely applied functions. (Is it?)

> Nonetheless Jot (http://barker.linguistics.fas.nyu.edu/Stuff/Iota/) is
> an example of the a language where concatenation denotes application.

Interesting point (and one I've pondered before). I don't understand
the notation used to discuss Iota, but I admit that it does seem
plausible to me that it's concatenative, and it's definitely not
concatenative-compositional. The problem is that I can't tell whether
it's concatenative. Can someone assure me that any two valid programs
in Iota can be concatenated to form a valid program? What (if any)
restrictions are on the resulting program -- I know that not all
bitstrings are valid Iota programs, so it seems likely that the
universe of concatenated programs is smaller than the universe of Iota
programs (i.e. there are Iota programs that cannot be formed by
concatenation of nonempty programs).

Does my last point there matter? I'm going to discuss that later on.

Now, let me mention that in my opinion, if Iota is even partially
"concatenative" (i.e. if it fails my last test above, but still meets
the general definition), it's an interesting thing for this group to
talk about.

> This naturally leads to interesting ideas: what else could whitespace
> denote? Pick a combinator, and you have a very interesting esoteric
> language to study. (Hmmm: a language where whitespace could be changed
> dynamically ...).

We'd call it C-space-space.

Seriously, though, I'd prefer to refer to concatenation rather than whitespace.

> >  I admit
> > that I did invent 'concatenative' with some vague idea of being
> > 'opposite' to applicative languages,  but I don't think the category is
> > useless even if it's orthogonal rather than opposite.

> Yes, perhaps I overstated the case. If we broadened the term
> "concatenative" to mean something like a "language where the
> concatenation of terms is valid, and has semantic meaning (e.g.
> function application or function composition)". It would be a useful
> and interesting categorization, and one which I think is much more
> intuitively correct. I could see it as being a nice way to classify
> languages where whitespace has semantic meaning.

The definition we gave is more restrictive than that, though (even
though it's informal and vague). We require that not only
concatenation denote _something_, but that the concatenation of two
valid programs denotes another valid program. That clearly means more
than what you're proposing.

Here's an idea... if I were to modify "my" definition to end with
"...and the entire language can be formed by concatenation of valid
programs," would the resulting definition be more interesting? I'm not
doing this simply to exclude Iota (actually, I suspect that the
resulting definition includes Jot, although again I'm not sure), but
the idea is given by the fact that programs in Iota have a special
form.

Here's the full text: "A concatenative language is a language such
that the concatenation of any two valid programs is another valid
program, and the entire language can be formed by concatenation of
valid programs."

(There may be a precise mathematical term for this. I thought "the
language is closed under concatenation," but it turns out that's just
another way of stating the first half of the definition, and doesn't
help with the second half.)

> It may be late in the game, where there is already a fair amount of
> momentum behind the usage of the term concatenation (and this
> wonderful community), but I still think it is worthwhile to try and be
> as accurate and intuitiviely descriptive as possible with our
> terminology.

I think there's a great reason to do this... Everyone here agrees that
the definition is imperfect in some way. Nobody knows how to fix it.
So discussion will certainly help... Whether it leads us to fix it, or
to discard it.

> Perhaps you are wondering why I am pushing back now. I am currently
> writing and submitting numerous articles for computer science
> conferences. I would like to write a paper introducing the
> "concatenative" category of languages, as something worth studying,
> but in fact I am only interested in compositional concatenative
> languages. I fear that the referees in the academic computer science
> community will bring up the same concerns that I am pointing out here.

I'm sure you're right. Perhaps my definition will be narrower?

> Christopher

-Wm