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

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

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

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

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

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

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

> 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

> but few people call Smalltalk object-oriented.

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

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

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

> 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

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

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

Concatenative versus Compositionality

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

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

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

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

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

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

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

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

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

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

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

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

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

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