# Concatenative versus Compositionality

## Christopher Diggins — 2007-12-03 17:35:58

    On Dec 3, 2007 10:17 AM, William Tanksley, Jr <wtanksleyjr@...> wrote:

     >

    > Christopher Diggins <cdiggins@...> wrote:

    > > FWIW I like your definition.

    >

    > In your blog you mention,

     For those who haven't seen it:

    http://cdiggins.com/2007/12/01/compositional-programming-languages-not-concatenative/

    And some reddit discussion is at:

    http://programming.reddit.com/info/61win/comments/

     > 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. What unifies the langauges

    so far labelled as concatenative is that they are compositional

    (whitespace denotes function composition).

     > I disagree. Our uncertainty about the precise meaning of the term

    > mirrors the fact that these languages are very little studied; the

    > fact that we're a bit murky on the precise boundaries of our field

    > therefore only makes sense.

     Yes of course.

     > At the same time, your suggested term, 'compositional', is good; the

    > obvious problem is that it's already been used. A compositional

    > computer language is a language used only to bring together code

    > written in other languages;

    >

    > the language Piccola

    > http://www.iam.unibe.ch/~scg/Research/Piccola/ is a 'pure' example,

     From the Piccola paper "a composition language — a language for

    building applications from

    software components implemented in another, host programming language."

    IMO Piccola would be much better described as a "component oriented language".

    Howerver, that said: there is an overloading of the term "composition"

    in Computer science to mean either object/component composition and

    function composition.

    We could offer the distinction of "function composition language" for

    Joy et. al. whereas Piccola would be an "object composition language".

     > and I suppose the various shell scripts are impure examples.  But

    > that's not broad use, and I don't see a severe problem with using it

    > anyhow.

    >

    > 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 think however, the concatenation of programs is of less relevance

    than what it means to concatenate terms (i.e. expressions) in the

    language. 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? This an indicator that

    concatenation defined at strictly the program level is too narrow to

    merit a categorization.

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

    Nonetheless Jot (http://barker.linguistics.fas.nyu.edu/Stuff/Iota/) is

    an example of the a language where concatenation denotes application.

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

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

    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 intutiviely descriptive as possible with our

    terminology.

    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.

     > > - Christopher

    >

    > -Wm

     Cheers,

    Christopher

## John Cowan — 2007-12-03 18:52:56

    Christopher Diggins scripsit:

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

     Yes, though "programs" must be interpreted strictly.  "1 [ 2" is not a

    Joy program.

    --

    But you, Wormtongue, you have done what you could for your true master.  Some

    reward you have earned at least.  Yet Saruman is apt to overlook his bargains.

    I should advise you to go quickly and remind him, lest he forget your faithful

    service.  --Gandalf             John Cowan <cowan@...>

## John Nowak — 2007-12-03 21:11:08

    On Dec 3, 2007, at 12:35 PM, Christopher Diggins wrote:

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

    > ...

    >  What unifies the langauges

    > so far labelled as concatenative is that they are compositional

    > (whitespace denotes function composition).

     Just a quick point: I think those are overly narrow definitions of

    concatenativity and compositionality if you include anything about

    "whitespace". Imagine a language where functions aren't entered as

    individual characters and concatenated via whitespace, but rather

    dragged off a palette of predefined functions and connected together

    like a jigsaw puzzle.  MIT's Scratch is works somewhat along these

    lines -- in fact, I've seen it described at least once as a

    "concatenative language for children":

    http://llk.media.mit.edu/projects/scratch/help/images/variableSet.gif

    It is easy to imagine Joy with a similar sort of graphical syntax;

    Quotation would work as the "forever" does in that example (albeit

    with the addition of an output like the other functions have).

    - John

## John Nowak — 2007-12-03 21:14:18

    On Dec 3, 2007, at 1:52 PM, John Cowan wrote:

     > Christopher Diggins scripsit:

    >

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

    >

    > Yes, though "programs" must be interpreted strictly.  "1 [ 2" is not a

    > Joy program.

     There may also be type system restrictions involved. For example, I

    believe this is a valid program in Cat:

    foo == [10] dup apply

    However, the due to the current lack of equirecursive types, this isn't:

    foo == [10] bar

    bar == dup apply

    Does that mean Cat isn't concatenative (or at least not fully

    concatenative)?

    - John

## Christopher Diggins — 2007-12-03 21:22:42

    On Dec 3, 2007 4:14 PM, John Nowak <john@...> wrote:

     >  On Dec 3, 2007, at 1:52 PM, John Cowan wrote:

    >

    >  > Christopher Diggins scripsit:

    >  >

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

    >  >

    >  > Yes, though "programs" must be interpreted strictly. "1 [ 2" is not a

    >  > Joy program.

    >

    >  There may also be type system restrictions involved. For example, I

    >  believe this is a valid program in Cat:

    >

    >  foo == [10] dup apply

    >

    >  However, the due to the current lack of equirecursive types, this isn't:

    >

    >  foo == [10] bar

    >  bar == dup apply

     Cat 0.18.2 handles recursion by generating a new type ('A -> 'B) and

    unifying that. So "dup apply" is now valid again.

     >  Does that mean Cat isn't concatenative (or at least not fully

    >  concatenative)?

     The answer depends on whether an ill-typed program is valid or not.

    - Christopher

## William Tanksley, Jr — 2007-12-03 22:18:10

    Christopher Diggins <cdiggins@...> wrote:

     > William Tanksley, Jr <wtanksleyjr@...> 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

## Don Groves — 2007-12-03 22:56:49

    On Dec 3, 2007, at 19:11 , John Nowak wrote:

     >

    > On Dec 3, 2007, at 12:35 PM, Christopher Diggins wrote:

    >

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

    >> ...

    >>  What unifies the langauges

    >> so far labelled as concatenative is that they are compositional

    >> (whitespace denotes function composition).

    >

    > Just a quick point: I think those are overly narrow definitions of

    > concatenativity and compositionality if you include anything about

    > "whitespace". Imagine a language where functions aren't entered as

    > individual characters and concatenated via whitespace, but rather

    > dragged off a palette of predefined functions and connected together

    > like a jigsaw puzzle.  MIT's Scratch is works somewhat along these

    > lines -- in fact, I've seen it described at least once as a

    > "concatenative language for children":

    >

    > http://llk.media.mit.edu/projects/scratch/help/images/variableSet.gif

    >

    > It is easy to imagine Joy with a similar sort of graphical syntax;

    > Quotation would work as the "forever" does in that example (albeit

    > with the addition of an output like the other functions have).

    >

    > - John

     We could also define a language with single character names wherein

    xfg would mean g(f(x)) with no whitespace involved. Being a big fan of

    conciseness, this is on my list of ideas for experimentation ;-)

    --

    Don

     >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Daniel Ehrenberg — 2007-12-03 23:15:27

    > 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. What unifies the langauges

    > so far labelled as concatenative is that they are compositional

    > (whitespace denotes function composition).

     Hi Chris,

    Yeah, this is true, but I don't see why we need to change the words.

    The use of the term "concatenative" is fairly well-established within

    our community, and it's not unprecedented to have a term which does

    not specify all of what the constituent words mean. To take an example

    from the world of programming languages (though the rest of English is

    full of them), consider the term 'object-oriented'. Admittedly, this

    is not the most unambiguous term, but few people call Smalltalk

    object-oriented. Yet Smalltalk programs do use objects: they

    manipulate functions, lists, tuples and other types of stuff, or

    objects. "Concatenative" itself doesn't explain what it means to be

    concatenative, but the definition is now basically accepted that a

    concatenative language is one in which concatenation of two

    independent programs. OK, so this isn't strictly true: we have to

    define a program such that "1 [ 2" is not a program (since [ isn't a

    program without a matching ]) and we have to account for side effects.

    But the essence, in my mind, has been that a concatenative language is

    one where programs are built from function composition, which is

    probably indicated through some extremely light-weight syntax like

    whitespace.

    Maybe "compositional" is a good way to explain concatenative

    languages, but the switch of terms would leave "concatenative" without

    a useful meaning. Referring only to syntax, it doesn't really define a

    class of semantically-related programming languages. The end effect

    would be retiring the word "concatenative" in place of an equivalent

    term, "compositional".

    I hate to get myself into these definitional debates. If the consensus

    name is compositional, I will use that name to reduce ambiguity, but I

    fail to see the purpose in the switch. On the other hand,

    compositional is a word in my spell checker, unlike concatenative...

    Daniel Ehrenberg

## Daniel Ehrenberg — 2007-12-04 01:16:33

    > but few people call Smalltalk object-oriented.

     Of course, I meant few people *wouldn't* call Smalltalk object-oriented!

## Daniel Ehrenberg — 2007-12-04 01:18:59

    Oops, actually I really meant Haskell instead of Smalltalk. I feel

    really stupid.

     On Dec 3, 2007 8:16 PM, Daniel Ehrenberg <microdan@...> wrote:

    > > but few people call Smalltalk object-oriented.

    >

    > Of course, I meant few people *wouldn't* call Smalltalk object-oriented!

    >

## Christopher Diggins — 2007-12-04 03:51:49

    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

## Christopher Diggins — 2007-12-04 04:13:48

    > Hi Chris,

    >

    > Yeah, this is true, but I don't see why we need to change the words.

    > The use of the term "concatenative" is fairly well-established within

    > our community,

     The problem is that the computer science community is much larger than our own.

     > and it's not unprecedented to have a term which does

    > not specify all of what the constituent words mean.

     Precedence does not make right.

     > To take an example

    > from the world of programming languages

     Which is the only kind of language I am concerned with :-)

     > (though the rest of English is

    > full of them), consider the term 'object-oriented'.

     A perfect example of what I am talking about. A term that was never

    well-defined, and because it was too broad (it means literally "about

    things") it got corrupted. Even members of the Scheme community have

    been known to call Scheme object-oriented. Very few languages don't

    consider themselves object-oriented.

     > Admittedly, this  is not the most unambiguous term,

    > but few people *wouldn't* call Smalltalk

    > object-oriented.

     Edited as per your later email.

     > Yet Smalltalk programs do use objects: they

    > manipulate functions, lists, tuples and other types of stuff, or

    > objects.

     Except it is nearly impossible to define object precisely.

     > "Concatenative" itself doesn't explain what it means to be

    > concatenative,

     Yes.

     > but the definition is now basically accepted that a

    > concatenative language is one in which concatenation of two

    > independent programs.

     Within a very small community, and virtuallly no recognition from the

    academic community.

     > OK, so this isn't strictly true: we have to

    > define a program such that "1 [ 2" is not a program (since [ isn't a

    > program without a matching ]) and we have to account for side effects.

    > But the essence, in my mind, has been that a concatenative language is

    > one where programs are built from function composition, which is

    > probably indicated through some extremely light-weight syntax like

    > whitespace.

    >

    > Maybe "compositional" is a good way to explain concatenative

    > languages, but the switch of terms would leave "concatenative" without

    > a useful meaning. Referring only to syntax, it doesn't really define a

    > class of semantically-related programming languages.

     You are correct, it doesn't. Concatenative is a statement about

    syntax, not semantics. A syntactic classification of languages could

    still have use though.

     > The end effect

    > would be retiring the word "concatenative" in place of an equivalent

    > term, "compositional".

     I wouldn't jump to that conclusion yet.

     > I hate to get myself into these definitional debates. If the consensus

    > name is compositional, I will use that name to reduce ambiguity, but I

    > fail to see the purpose in the switch. On the other hand,

    > compositional is a word in my spell checker, unlike concatenative...

    >

    > Daniel Ehrenberg

     Cheers,

    Christopher

## Robbert van Dalen — 2007-12-04 20:45:00

    But what about postfix notation, i.e. the operator always comes after

    the operands?

    The reason that I like Joy (or any postfix language) is that

    evaluation follows naturally from syntax, and that evaluation is non-

    ambiguous.

    Contrast this with infix notation: sometimes this gives you

    evaluation headaches, such as operator precedence or excessive 'lisp'

    parentheses.

    I find it easy to 'run' or 'reduce' Joy programs on paper. Just

    follow some basic rules and you can do it too :)

    1) scan for any operator in an expression/program/continuation

    2) determine the valence (unary, binary, ternary, ....)

    3) are there enough elements before the operator to match the valence?

    4) and are the elements no operators?

    5) if yes to 4) and 5) execute with the preceding elements

    6) otherwise, scan for another operator and continue with 2)

    What's your preference?:

    1 2 + 3 4 + +

    or

    (+ (+ 1 2) (+ 3 4))

    I'd rather drop the parenthesis .... thank you very much!

    - Robbert

## Don Groves — 2007-12-07 00:44:40

    --- In concatenative@yahoogroups.com, Robbert van Dalen

    <robbert.van.dalen@...> wrote:

     >

    >

    > But what about postfix notation, i.e. the operator always comes after

    > the operands?

     Hi all,

    In an effort to discover exactly what's meant by the term

    "concatenative," I offer the following description of a language I

    think all of us would call concatenative:

    A program (or function) is a mapping from stacks to stacks such that,

    (S)[P] -> (S') where P is a program and S, S' are stack contents.

    A program is represented as an ordered sequence of terms which is

    evaluated from left to right according to these two rules:

    1 - Literal terms are pushed onto the stack. For example:

        ()[8] -> (8)

        ()[[1 2]] -> ([1 2])

        ()['name] -> (name)

    2 - Named terms are executed according to their definitions:

        (8)[dup *] -> (8 8)[*] -> (64)

        ()["Hello!" put] -> ("Hello!")[put] ->  () with Hello! output.

    Now, exactly why is this language concatenative?

    Is it because of the stacks?

    Is it because of the "ordered sequence of terms?"

    Is it because of right-associative notation?

    Is it something else?

    Is it all of the above?

    Is this example insufficient?

    IMHO, answering this question is required for the definition to be useful.

    --

    Don