Re: [stack] Concatenative versus Compositionality

Hi William,

I hope my heavy editing of the post to reduce the size is okay.

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

Sorry, lets say the sequencing of terms

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

Yes you are correct. The operation denoted by the sequencing of terms
is sometimes called the whitespace operator, but as you point out it
is not completely accurate. Lets call it the sequencing operator for
now.

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

Sure but that is not so much my quibble.

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

But we most definitely are discussing semantics if the definition
requires a special meaning to the sequence of terms. If we are only
discussing syntax (which is a completely valid discussion) then we can
not be prescriptive about what the sequencing of terms actually means.
In other words: if you are saying that concatenative is a statement
about syntax, then we must include languages for which concatenation
means things other than composition.

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

Functional purity really has to do with semantics than implementation.
I am not convinced that this property is exclusive to concatenative
compositional languages. Either way, this line of discussion could
lead off of topic.

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

I believe so.

>  If it's possible to define an interesting language which is
>  concatenative, but not "compositional concatenative", then the
>  distinction is important.

It is definitely possible: just look at the SK calculus (or combinatory logic).

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

There is nothing wrong with the group keeping the name concatenative. :-)

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

You could definitely make a convincing philosophical argument along
these lines, however most of the academic literature related to the
study of programming languages is concerned more with the semantics of
languages rather than the syntax.

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

I think that is valid.

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

You can implement the SK calculus in Haskell.

> 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?)

I believe it is. Why would it not?

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

Not Iota but rather Jot.

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

He claims all sequences of 1's and 0's are valid Jot programs.

>  What (if any)
>  restrictions are on the resulting program -- I know that not all
>  bitstrings are valid Iota programs,

Why not?

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

Agreed.

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

Yes that is fine.

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

Sure, but I would say that distinguishing between "programs" and
"terms" (i.e. "expressions") is important. In C, if you define an
entry point other than main, you can have two valid programs
concatenated to create a new valid program. Okay, technically I may be
wrong (I don't know the C spec), but the point is still valid for some
C-like language. Point is: concatenation of programs is less
interesting than concatenation of terms.

>  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 wouldn't like that restriction for reasons stated in my earlier
post. There are languages which have structures at the program level,
but are for the most part in the same category of language as Joy.

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

I am pretty sure Iota is not concatenative.

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

Here's my counter: "A concatenative language is a language such
that the concatenation of any two valid terms is another valid term."

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

I find the second half overly restrictive.

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

I appreciate your open-mindedness on the subject.

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

I think we are on the right track.

Christopher