the concatenative wikipedia article

[John Nowak]

The Wikipedia article on concatenative languages has a number of  
issues that I think should be addressed. I'm willing to make the  
changes, but I'd like to make sure I'm not off-base first.

I realize many of these concerns are rather tired at this point. I  
apologize. However, that doesn't change the fact that they've gone  
unresolved. Indeed, there seems to be almost a resistance to resolving  
them. I personally think that the non-applicative style of programming  
has important properties and that it would be great to have a term for  
them so I could stop redefining "concatenative" every time I talk to  
someone (including those knowledgeable about concatenative languages).

Here are my issues with the article:

1. Concatenative should not be conflated with "stack-based". I have  
already shown that the counter-examples are beyond mere curiosities.

2. It should be more clearly stressed that concatenative languages are  
not applicative. The reduction of a concatenative expression is the  
simplification of one function to another function (e.g. '1 2 + + ==>  
3 +'). Never is it necessary to deal with objects or application, and  
much is gained by not doing so (as is mentioned at http://www.latrobe.edu.au/philosophy/phimvt/joy/j08cnt.htm)
.

3. There is no reason concatenative languages must use a postfix  
syntax. A prefix syntax is also a valid approach. Other syntaxes are  
useful (as I've shown recently with my infix construction syntax  
similar to that of in FL and J) but ruled out by the need for  
concatenation to always denote composition (which I think is probably  
unfortunate).

4. Not all concatenative languages have parsing words or an equivalent  
to macros. Talking about them here makes as much sense as talking  
about macros on a page about applicative programming.

5. It should be stressed that concatenative languages are function-
level and pointfree. They also go beyond languages like Backus's FP in  
that objects are entirely removed from the language; The expression  
'3' represents a *function*, not an object.

6. I dislike the sentence "The term 'concatenative' is not universally  
accepted as a particularly useful term". It's an objectively useful  
term if some care is given to its definition; What's "universally  
accepted" is unimportant. Hell, even Slava (who says it's unimportant)  
has started concatenative.org (which lists C++ and Java as  
"interesting languages"... ugh).

So, should I make the changes or should I just define a new term so I  
that can communicate with people without boring myself? I did like  
Diggins's "compositional" suggestion which is more to the point; The  
fact that it is already used in various vague ways doesn't disturb me  
too much.

Sorry for bringing this up *again*, but I'm trying to write a paper  
and keep stumbling over how to describe what it is that I'm talking  
about.

- John

[William Tanksley, Jr]

John Nowak <john@...> wrote:
> The Wikipedia article on concatenative languages has a number of
> issues that I think should be addressed. I'm willing to make the
> changes, but I'd like to make sure I'm not off-base first.

I'd like to see that. For some reason I've never felt adequate to
munge the page...

> Here are my issues with the article:

The number one problem is the motivation for the definition. As given,
it sounds like a mathematical or historical curiosity.

> 1. Concatenative should not be conflated with "stack-based". I have
> already shown that the counter-examples are beyond mere curiosities.

Agreed entirely.

I'd like to see your examples, specifically emphasizing how you know
it's concatenative. I didn't notice them.

> 2. It should be more clearly stressed that concatenative languages are
> not applicative. The reduction of a concatenative expression is the

This is a very big point, and should be strongly emphasized.

> 3. There is no reason concatenative languages must use a postfix
> syntax. A prefix syntax is also a valid approach. Other syntaxes are
> useful (as I've shown recently with my infix construction syntax
> similar to that of in FL and J) but ruled out by the need for
> concatenation to always denote composition (which I think is probably
> unfortunate).

Technically it's not prefix or postfix; it's beginning-to-end or
end-to-beginning. I really don't see any utility in the latter.

It can also be ruled out by the use of other definitions for
concatenativity -- I really like the one we arrived at a year ago.
Here are a couple of (hopefully) alternative phrasings (that is,
they're intended to imply the same things):

1. For the mathematically oriented: "A concatenative language consists
of a mapping from a syntactic monoid over program concatenation to a
semantic monoid over an associative operation on functions." This
language is motivated by von Thun's "Mathematical Foundations of Joy",
http://www.latrobe.edu.au/philosophy/phimvt/joy/j02maf.html (but I'm
to blame for applying it here, so don't shoot at Manfred if I've got
it wrong).
2. A simple definition: "A concatenative language is a programming
language where the syntactic concatenation of terms expresses an
associative operation on the functions that the terms represent." This
was built by Christopher Diggins.
3. Purely language-theoretical: "A language's syntax is concatenative
if it is its own Kleene closure."

My favorite is #2. I'd really want to call out the advantages granted
by associativity; I think that's the single biggest thing experienced
concatenative programmers enjoy, even if they never know to name it.
It's the property that allows one to refactor merely using cut and
paste.

> 4. Not all concatenative languages have parsing words or an equivalent
> to macros. Talking about them here makes as much sense as talking
> about macros on a page about applicative programming.

Granted. I'd be okay with removing this... Although Forth (for
example) has a very simple and powerful macro system, it's interesting
that its creator recommends that it be entirely avoided. The theory of
macros on top of a concatenative language is simple and clear, but is
really a different issue.

> 5. It should be stressed that concatenative languages are function-
> level and pointfree. They also go beyond languages like Backus's FP in
> that objects are entirely removed from the language; The expression
> '3' represents a *function*, not an object.

Okay, that's good. I'd worry a little about the expression "objects
are entirely removed"... There's an obvious way to entirely
misunderstand that. The terminology in the Wikipedia definition of
"function-level" suggests that perhaps you should say something along
the lines of "the distinction between data and functions is entirely
removed from the language, and all functions are built up from other
functions, with constant functions standing in for data."

> 6. I dislike the sentence "The term 'concatenative' is not universally
> accepted as a particularly useful term". It's an objectively useful
> term if some care is given to its definition;

I agree... I suspect this is one of Wikipedia's famous controversy
edits. It doesn't fit well with the rest of the page, and it serves no
purpose.

> So, should I make the changes or should I just define a new term so I
> that can communicate with people without boring myself? I did like
> Diggins's "compositional" suggestion which is more to the point; The
> fact that it is already used in various vague ways doesn't disturb me
> too much.

I'd like the changes made -- it would be nice to have an encyclopedic
reference for this list's discussions. I'd rather not branch to
another term; I think "concatenative" is well-established and
fruitful, even if it is a bit vague. (But what isn't vague?)

> - John

-Wm

[Christopher Diggins]

>> 1. Concatenative should not be conflated with "stack-based". I have
>> already shown that the counter-examples are beyond mere curiosities.
>
> Agreed entirely.
>
> I'd like to see your examples, specifically emphasizing how you know
> it's concatenative. I didn't notice them.

Allow me to present the deque language that I just made up.

1! - Pushes a one to the right of the deque
!1 - Pushes a one to the leftt of the deque
...
add! - Adds the right two numbers of the deque
!add - Adds the left two numbers of the deque
...

3! !5 !2 sub! !add

If applied to an empty deque this will leave the value 4 on the deque.

So is this a concatenative language? It satisfies many of the
criteria, but I am not sure. If we could agree that this is or is not
concatenative, it may prove useful.

>> So, should I make the changes or should I just define a new term so I
>> that can communicate with people without boring myself? I did like
>> Diggins's "compositional" suggestion which is more to the point; The
>> fact that it is already used in various vague ways doesn't disturb me
>> too much.
>
> I'd like the changes made -- it would be nice to have an encyclopedic
> reference for this list's discussions. I'd rather not branch to
> another term; I think "concatenative" is well-established and
> fruitful, even if it is a bit vague. (But what isn't vague?)

Agreed, I think there is value in refining the term concatenative.
However, I think it is more important to define it here than somewhere
else like a wiki where people with no knowledge of the subject can
make arbitrary uninformed edits. Besides whatever is agreed upon in
the list can serve as a source of citation for the Wikipedia article.

- Christopher

[William Tanksley, Jr]

Christopher Diggins <cdiggins@...> wrote:
>>> 1. Concatenative should not be conflated with "stack-based". I have
>>> already shown that the counter-examples are beyond mere curiosities.
>> I'd like to see your examples, specifically emphasizing how you know
>> it's concatenative. I didn't notice them.

> Allow me to present the deque language that I just made up.
> 1! - Pushes a one to the right of the deque
> !1 - Pushes a one to the leftt of the deque
> add! - Adds the right two numbers of the deque
> !add - Adds the left two numbers of the deque
> ...

> 3! !5 !2 sub! !add
> If applied to an empty deque this will leave the value 4 on the deque.
> So is this a concatenative language? It satisfies many of the
> criteria, but I am not sure. If we could agree that this is or is not
> concatenative, it may prove useful.

By all three of the definitions I posted, as well as the Wikipedia one
(stripped of its parochial insistence on stacks), this qualifies. As a
bonus, my gut feeling is that it's concatenative. It's definitely more
complex than working with a stack, but there's nothing inherently
wrong about that -- and perhaps there's a data structure that's
inherently simpler than a stack.

OTOH, can a concatenative language ever be infix? I'd find it odd... A
fundamental property is syntactic associativity, and infix isn't
associative... Or can it be made so by means of currying?

> Agreed, I think there is value in refining the term concatenative.
> However, I think it is more important to define it here than somewhere
> else like a wiki where people with no knowledge of the subject can
> make arbitrary uninformed edits. Besides whatever is agreed upon in
> the list can serve as a source of citation for the Wikipedia article.

Granted, but a mailing list is ephemeral.

> - Christopher

-Wm

[John Nowak]

On Dec 31, 2008, at 3:21 PM, William Tanksley, Jr wrote:

> OTOH, can a concatenative language ever be infix? I'd find it odd...

The general idea that I've had for a prefix/infix language is as  
follows:

1. 'f g' denotes the composition of 'f' and 'g'
2. 'f g h' denotes the composition of 'g' with the construction of 'f'  
and 'h' (construction is basically a cleave combinator)
3. Grouping is to the right such that 'f g h i j k == f g (h i (j k))'
4. Composition is associative such that '(f g) h == f (g h)'
5. Literals (e.g. '42') are constant functions such that '42 f == 42'
6. Multiple arguments are passed via lists
7. 'a == head', 'b == head tail', 'c == head (head tail)', etc --  
these are essentially used to index into lists

As such, you write functions like this:

    discriminant = (sq b) - 4 * a * c

And here's the definition in use

    # composition of discriminant and the construction [1,3,-4]
    discriminant [1,3,-4]
    # expansion of discriminant
    ((sq b) - 4 * a * c) [1,3,-4]
    # fully parenthesized
    ((sq b) - (4 * (a * c))) [1,3,-4]
    # replacing infix with composition + construction
    (- [sq b, * [4, * [a, c]]) [1,3,-4]
    # law of associativity: (f g) h == f (g h)
    - ([sq b, * [4, * [a, c]]) [1,3,-4])
    # law of distributivity: [f0..fN] g == [f0 g..fN g]
    - [(sq b) [1,3,-4], * [4 [1,3,-4], (* [a, c]) [1,3,-4]]
    # simplification
    - [(sq b) [1,3,-4], * [4, (* [a, c]) [1,3,-4]]
    - [(sq b) [1,3,-4], * [4, * [1, -4]]
    - [sq (b [1,3,-4]), * [4, * [1, -4]]
    - [sq 3, * [4, * [1, -4]]
    - [sq 3, * [4, -4]]
    - [sq 3, -16]
    - [9, -16]
    25

The infix syntax makes the manipulation a little awkward, but I've  
found it often makes the definitions shorter and more readable. The  
fact that any function can be used infix is a nice touch.

So, is this concatenative? It's just composition and cleave combinators.

- John

[Adam-230]

Slava recently created a nice description of Concatenative languages
in the following four articles:

http://www.concatenative.org/wiki/view/Concatenative%20language

http://www.concatenative.org/wiki/view/Concatenative%20language/Name%20code%20not%20values

http://www.concatenative.org/wiki/view/Concatenative%20language/Multiple%20return%20values

http://www.concatenative.org/wiki/view/Concatenative%20language/Concatenation%20is%20composition

-Adam

--- In concatenative@..., John Nowak <john@...> wrote:

>
> The Wikipedia article on concatenative languages has a number of
> issues that I think should be addressed. I'm willing to make the
> changes, but I'd like to make sure I'm not off-base first.
>
> I realize many of these concerns are rather tired at this point. I
> apologize. However, that doesn't change the fact that they've gone
> unresolved. Indeed, there seems to be almost a resistance to resolving
> them. I personally think that the non-applicative style of programming
> has important properties and that it would be great to have a term for
> them so I could stop redefining "concatenative" every time I talk to
> someone (including those knowledgeable about concatenative languages).
>
> Here are my issues with the article:
>
> 1. Concatenative should not be conflated with "stack-based". I have
> already shown that the counter-examples are beyond mere curiosities.
>
> 2. It should be more clearly stressed that concatenative languages are
> not applicative. The reduction of a concatenative expression is the
> simplification of one function to another function (e.g. '1 2 + + ==>
> 3 +'). Never is it necessary to deal with objects or application, and
> much is gained by not doing so (as is mentioned at http://www.latrobe.edu.au/philosophy/phimvt/joy/j08cnt.htm)
> .
>
> 3. There is no reason concatenative languages must use a postfix
> syntax. A prefix syntax is also a valid approach. Other syntaxes are
> useful (as I've shown recently with my infix construction syntax
> similar to that of in FL and J) but ruled out by the need for
> concatenation to always denote composition (which I think is probably
> unfortunate).
>
> 4. Not all concatenative languages have parsing words or an equivalent
> to macros. Talking about them here makes as much sense as talking
> about macros on a page about applicative programming.
>
> 5. It should be stressed that concatenative languages are function-
> level and pointfree. They also go beyond languages like Backus's FP in
> that objects are entirely removed from the language; The expression
> '3' represents a *function*, not an object.
>
> 6. I dislike the sentence "The term 'concatenative' is not universally
> accepted as a particularly useful term". It's an objectively useful
> term if some care is given to its definition; What's "universally
> accepted" is unimportant. Hell, even Slava (who says it's unimportant)
> has started concatenative.org (which lists C++ and Java as
> "interesting languages"... ugh).
>
> So, should I make the changes or should I just define a new term so I
> that can communicate with people without boring myself? I did like
> Diggins's "compositional" suggestion which is more to the point; The
> fact that it is already used in various vague ways doesn't disturb me
> too much.
>
> Sorry for bringing this up *again*, but I'm trying to write a paper
> and keep stumbling over how to describe what it is that I'm talking
> about.
>
> - John
>

[Adam-230]

Also, concatenative.org is editable by the public as well if you register.

--- In concatenative@..., Adam <hiatoms@...> wrote:
>
> Slava recently created a nice description of Concatenative languages
> in the following four articles:
>
> http://www.concatenative.org/wiki/view/Concatenative%20language
>
>
http://www.concatenative.org/wiki/view/Concatenative%20language/Name%20code%20not%20values
>
>
http://www.concatenative.org/wiki/view/Concatenative%20language/Multiple%20return%20values
>
>
http://www.concatenative.org/wiki/view/Concatenative%20language/Concatenation%20is%20composition

>
> -Adam
>
> --- In concatenative@..., John Nowak <john@> wrote:
> >
> > The Wikipedia article on concatenative languages has a number of
> > issues that I think should be addressed. I'm willing to make the
> > changes, but I'd like to make sure I'm not off-base first.
> >
> > I realize many of these concerns are rather tired at this point. I
> > apologize. However, that doesn't change the fact that they've gone
> > unresolved. Indeed, there seems to be almost a resistance to resolving
> > them. I personally think that the non-applicative style of programming
> > has important properties and that it would be great to have a term for
> > them so I could stop redefining "concatenative" every time I talk to
> > someone (including those knowledgeable about concatenative languages).
> >
> > Here are my issues with the article:
> >
> > 1. Concatenative should not be conflated with "stack-based". I have
> > already shown that the counter-examples are beyond mere curiosities.
> >
> > 2. It should be more clearly stressed that concatenative languages are
> > not applicative. The reduction of a concatenative expression is the
> > simplification of one function to another function (e.g. '1 2 + + ==>
> > 3 +'). Never is it necessary to deal with objects or application, and
> > much is gained by not doing so (as is mentioned at

http://www.latrobe.edu.au/philosophy/phimvt/joy/j08cnt.htm)

> > .
> >
> > 3. There is no reason concatenative languages must use a postfix
> > syntax. A prefix syntax is also a valid approach. Other syntaxes are
> > useful (as I've shown recently with my infix construction syntax
> > similar to that of in FL and J) but ruled out by the need for
> > concatenation to always denote composition (which I think is probably
> > unfortunate).
> >
> > 4. Not all concatenative languages have parsing words or an equivalent
> > to macros. Talking about them here makes as much sense as talking
> > about macros on a page about applicative programming.
> >
> > 5. It should be stressed that concatenative languages are function-
> > level and pointfree. They also go beyond languages like Backus's FP in
> > that objects are entirely removed from the language; The expression
> > '3' represents a *function*, not an object.
> >
> > 6. I dislike the sentence "The term 'concatenative' is not universally
> > accepted as a particularly useful term". It's an objectively useful
> > term if some care is given to its definition; What's "universally
> > accepted" is unimportant. Hell, even Slava (who says it's unimportant)
> > has started concatenative.org (which lists C++ and Java as
> > "interesting languages"... ugh).
> >
> > So, should I make the changes or should I just define a new term so I
> > that can communicate with people without boring myself? I did like
> > Diggins's "compositional" suggestion which is more to the point; The
> > fact that it is already used in various vague ways doesn't disturb me
> > too much.
> >
> > Sorry for bringing this up *again*, but I'm trying to write a paper
> > and keep stumbling over how to describe what it is that I'm talking
> > about.
> >
> > - John
> >
>

[John Nowak]

On Dec 31, 2008, at 6:01 PM, Adam wrote:

> Slava recently created a nice description of Concatenative languages
> in the following four articles

Thanks, I had hadn't seen that before.

Slava's description seems decent enough. It is, however, stack-
focused. He says that concatenative languages and stack-based  
languages are similar, but then never clarifies the differences and  
goes on to conflate the two. I also have some minor niggles (in no  
particular order):

1. There's no reason a concatenative language has to support  
recursion. My initial version of 5th did not.
2. Not all concatenative languages have multiple programmer-accessible  
stacks. Forth and Factor do, Joy and Cat do not.
3. It isn't mentioned that the reduction of a function the  
transformation of one function to another. This is the critical thing  
I find lacking in FP and FL.
4. It says composition must be denoted by concatenation. I'd prefer to  
say that some sort of concatenation operator is the primary means of  
forming programs, be that operator whitespace, a dot, etc.
5. Quotation works quite differently in Factor and Joy compared to  
Cat. In Cat, quotation is an abstraction mechanism (as Chris has  
pointed out to me). In Factor and Joy, it is not. It is therefore not  
accurate to say a quotation is a sequence of objects.
6. There's no reason that only one stack be live at any given point.  
Joy's persistent stack semantics allow for parallel evaluation.  
Ignoring IO, you can reduce programs using rewrite rules applied in  
any order and/or simultaneously.
7. It it said that "literals are pushed onto the stack when  
encountered by the evaluator". This implies that '5' is an object, not  
a function, which I think is a less useful (and likely inaccurate)  
characterization.

- John

[John Nowak]

On Dec 31, 2008, at 6:12 PM, Adam wrote:

> Also, concatenative.org is editable by the public as well if you  
> register.

This is probably one of those "should wait 24 hours before sending  
emails", but oh well...

Concatenative.org feels more like the future Factor wiki to me than a  
general repository for information about concatenative languages. I  
understand that Factor is a useful language (in contrast to Joy, Cat,  
etc). I also understand that it's Slava's site. That said, I'd much  
prefer it if the Factor-specifics were separated into their own wiki  
(subdirectories on a wiki are meaningless) so the content could focus  
exclusively on the theory of concatenative languages.

The dead links everywhere to things like "C++" and "garbage  
collection" make it look like a bit of a wasteland and make the  
purpose of the site less clear. I've asked if I could remove them but  
was told not to. This is probably just be some overly territorial part  
of my primitive mammalian brain going off, but I'm not comfortable  
contributing to it in its current state.

A clear statement of intent for the site (and adherence to it) would  
help me out. I'm not really interested in contributing to "The Factor  
+ Some Concatenative Stuff Wiki". I'm sure such a thing is not Slava's  
explicit intent, but it seems to be drifting in that general direction.

Then again, perhaps this is just my problem. It wouldn't be the first  
time!

- John

[Don Groves]

On Dec 31, 2008, at 3:25 PM, John Nowak wrote:

>
> On Dec 31, 2008, at 6:01 PM, Adam wrote:
>
>> Slava recently created a nice description of Concatenative languages
>> in the following four articles
>
> Thanks, I had hadn't seen that before.
>
> Slava's description seems decent enough. It is, however, stack-
> focused. He says that concatenative languages and stack-based
> languages are similar, but then never clarifies the differences and
> goes on to conflate the two. I also have some minor niggles (in no
> particular order):

I haven't worked on this stuff for almost a year now, but when last
involved, I was fiddling with the terminology to eliminate the word
"stack," which is ingrained in the concatenative culture, but at times
not as descriptive as I would like. As these languages mature, their
operators become less and less stack-like.

I was leaning toward defining a concatenative (if that's the right
word) program as "a list of operators applied to a (possibly initially
empty) list of operands."

This definition seems to me to have two advantages: (1) it allows
for non-FIFO shuffle operations like swap, rot, etc..., which are fine
for a list but not so for a classically-defined stack; and (2) the order
of application is not specified.

Not being up on this topic at the moment, the order of application
may need to be specified -- [operand] [operators] -- I'm not sure
of this.

I'd appreciate any comments, as they may save me wasted effort
if/when I do return to this eternally intriguing subject (which is why
I've returned to it so often already ;-)
--
don

> 1. There's no reason a concatenative language has to support
> recursion. My initial version of 5th did not.
> 2. Not all concatenative languages have multiple programmer-accessible
> stacks. Forth and Factor do, Joy and Cat do not.
> 3. It isn't mentioned that the reduction of a function the
> transformation of one function to another. This is the critical thing
> I find lacking in FP and FL.
> 4. It says composition must be denoted by concatenation. I'd prefer to
> say that some sort of concatenation operator is the primary means of
> forming programs, be that operator whitespace, a dot, etc.
> 5. Quotation works quite differently in Factor and Joy compared to
> Cat. In Cat, quotation is an abstraction mechanism (as Chris has
> pointed out to me). In Factor and Joy, it is not. It is therefore not
> accurate to say a quotation is a sequence of objects.
> 6. There's no reason that only one stack be live at any given point.
> Joy's persistent stack semantics allow for parallel evaluation.
> Ignoring IO, you can reduce programs using rewrite rules applied in
> any order and/or simultaneously.
> 7. It it said that "literals are pushed onto the stack when
> encountered by the evaluator". This implies that '5' is an object, not
> a function, which I think is a less useful (and likely inaccurate)
> characterization.
>
> - John
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>

[John Nowak]

On Dec 31, 2008, at 6:54 PM, Don Groves wrote:

> I was leaning toward defining a concatenative (if that's the right
> word) program as "a list of operators applied to a (possibly initially
> empty) list of operands."

I don't think this is a satisfactory definition for a few reason:

1. What exactly is a "list of operators"? Do you mean a sequence of  
functions reified as a list of objects? I don't think that's necessary.
2. For me, the main advantage of a concatenative language is that you  
get rid of application. Manfred von Thun pointed this out in his "Joy  
compared with other functional languages" paper and I think it is  
critical to the definition of concatenative languages.
3. There's no reason that the data structure the functions operate on  
be a list or a stack. I recently proposed a language using vectors in  
the style of More's array theory. Earlier today, Chris proposed a  
language based on a deque. I believe XY works on a stack/queue tuple.  
Other possibilities are easy to dream up.

> the order of application is not specified.

This would depend on the language in question. Various evaluation  
strategies can be employed. In a language with side effects, the order  
of reduction is going to be important. One could even imagine a  
language with a term rewriting semantics that allows definitions of  
the form 'dup drop  -> id'. If your rewrite rules aren't confluent,  
the way in which you reduce will matter.

- John

[John Nowak]

On Dec 31, 2008, at 2:34 PM, Christopher Diggins wrote:

>>> 1. Concatenative should not be conflated with "stack-based". I have
>>> already shown that the counter-examples are beyond mere curiosities.
>>
>> Agreed entirely.
>>
>> I'd like to see your examples, specifically emphasizing how you know
>> it's concatenative. I didn't notice them.
>
> Allow me to present the deque language that I just made up.
> ...
> So is this a concatenative language?

Looks like it to me.

The question is, which criteria would it *not* satisfy? I can't think  
of any unless you restrict the forms of the language to composition  
and quotation. Such a restriction would admit all current  
"concatenative" languages but rule out things like language you  
proposed (due to the '!' form) and the recent things I've been  
proposing that use construction.

If that were the case, we could refer to concatenative languages as  
the subset of compositional languages (i.e. languages that use  
composition instead of application) that have quotation and  
composition as their only program forming operations. I seem to recall  
proposing this definition awhile back.

One issue with this definition is that Forth doesn't qualify as it  
doesn't offer quotation. My proposed second-order 5th wouldn't qualify  
either as it doesn't offer quotation and defines new combinators in  
terms of (statically reducible) substitution. As my gut tells me that  
both Forth and 5th should count, I think the composition+quotation  
restriction may be too severe. You can't argue with the gut after all.

- John

[William Tanksley, Jr]

John Nowak <john@...> wrote:
> The general idea that I've had for a prefix/infix language is as
> follows:

> 1. 'f g' denotes the composition of 'f' and 'g'
> 2. 'f g h' denotes the composition of 'g' with the construction of 'f'
> and 'h' (construction is basically a cleave combinator)
> 3. Grouping is to the right such that 'f g h i j k == f g (h i (j k))'
> 4. Composition is associative such that '(f g) h == f (g h)'

> So, is this concatenative? It's just composition and cleave combinators.

As I see it, no. The problem is that grouping is semantically
significant (rule 3), but not syntactically significant (rules 1&2).
It violates my rule that a concatenative language must have
associative semantics and syntax -- that means no required implicit
grouping.

> - John

-Wm

[Christopher Diggins]

Hi All,

I just posted my newest definition of concatenative language at
http://dobbscodetalk.com/index.php?option=com_myblog&show=What-is-a-Concatenative-Language.html&Itemid=29
with a deconstruction. I am happy to discuss it here (avoids the
headache of having to register to leave comments).

Cheers,
Christopher

[Don Groves]

On Dec 31, 2008, at 4:24 PM, John Nowak wrote:

> On Dec 31, 2008, at 6:54 PM, Don Groves wrote:
>
>> I was leaning toward defining a concatenative (if that's the right
>> word) program as "a list of operators applied to a (possibly  
>> initially
>> empty) list of operands."
>
> I don't think this is a satisfactory definition for a few reason:
>
> 1. What exactly is a "list of operators"? Do you mean a sequence of
> functions reified as a list of objects? I don't think that's  
> necessary.

As I now belatedly recall, no doubt prompted by your words, I was
using "sequence of operators" and "sequence of operands" rather
than lists.


> 2. For me, the main advantage of a concatenative language is that you
> get rid of application. Manfred von Thun pointed this out in his "Joy
> compared with other functional languages" paper and I think it is
> critical to the definition of concatenative languages.

I'll review that paper. Perhaps my use of of the word "application" to
indicate the catenation of two sequences, e.g., [a b] [+] is confusing.


> 3. There's no reason that the data structure the functions operate on
> be a list or a stack. I recently proposed a language using vectors in
> the style of More's array theory. Earlier today, Chris proposed a
> language based on a deque. I believe XY works on a stack/queue tuple.
> Other possibilities are easy to dream up.

The reason I picked "sequence" is that it seems to be the most basic
ordered structure.


>> the order of application is not specified.
>
> This would depend on the language in question. Various evaluation
> strategies can be employed. In a language with side effects, the order
> of reduction is going to be important. One could even imagine a
> language with a term rewriting semantics that allows definitions of
> the form 'dup drop  -> id'. If your rewrite rules aren't confluent,
> the way in which you reduce will matter.

Many thanks for taking the time to comment, John. I'll tuck this away
with my notes for when the urge strikes again...
--
don

> - John

[William Tanksley, Jr]

Christopher Diggins <cdiggins@...> wrote:
> I just posted my newest definition of concatenative language at
> http://dobbscodetalk.com/index.php?option=com_myblog&show=What-is-a-Concatenative-Language.html&Itemid=29
> with a deconstruction. I am happy to discuss it here (avoids the
> headache of having to register to leave comments).

That's a good definition.

I did like the one you posted in the last thread, though; the one I
listed as #2 in my list above. I like the fact that it explicitly
mentions concatenation (making the rationale for the name clear), and
it also depends on the concept of associativity, which directly drives
the ability to easily factor.

I do suspect that the definition might be a little improved by
hybridizing it with your newest one, perhaps something like this:

"A concatenative programming language is language in which terms
correspond to functions and in which the juxtaposition of terms
denotes an associative operation on functions."

Heh... That was simpler than I thought.

Is it TOO general? It seems to me to cover all the cases, even the
non-interesting ones (such as where the operation is multiplication).

> Christopher

-Wm

[John Nowak]

On Dec 31, 2008, at 8:56 PM, William Tanksley, Jr wrote:

> John Nowak <john@...> wrote:
>>
>
>> 1. 'f g' denotes the composition of 'f' and 'g'
>> 2. 'f g h' denotes the composition of 'g' with the construction of  
>> 'f'
>> and 'h' (construction is basically a cleave combinator)
>> 3. Grouping is to the right such that 'f g h i j k == f g (h i (j  
>> k))'
>> 4. Composition is associative such that '(f g) h == f (g h)'
>>
>> So, is this concatenative? It's just composition and cleave  
>> combinators.
>
> As I see it, no. The problem is that grouping is semantically
> significant (rule 3), but not syntactically significant (rules 1&2).
> It violates my rule that a concatenative language must have
> associative semantics and syntax -- that means no required implicit
> grouping.

So if I got rid of rules 2 and 3, would it be concatenative? It would  
have the same underlying semantics except concatenation is would  
always mean composition.

This:

    (sq b) - 4 * a * c

Would be written like this instead:

    - [sq b, * [4, * [a, c]]]

If your answer is yes, my problem with that is that we don't impose  
the same syntactic restrictions on the definition of an applicative  
language. Tons of syntaxes are employed (Lisp, Haskell, J, FP, etc),  
yet we still call them all applicative. Perhaps concatenative isn't  
the right term, but I'd very much like a term focused strictly on  
semantics like "applicative" is. Again, "compositional" or similar  
seems like the obvious choice with "concatenative" being a subset  
defined partially by its syntax.

- John

[John Nowak]

On Dec 31, 2008, at 10:48 PM, Christopher Diggins wrote:

> I just posted my newest definition of concatenative language at
> http://dobbscodetalk.com/index.php?option=com_myblog&show=What-is-a-Concatenative-Language.html&Itemid=29

Well lets see. Starting with your definition:

"A concatenative programming language is language in which terms  
correspond to functions and in which the juxtaposition of terms  
denotes the composition of functions."

The phrase "terms correspond to functions" is critical and I'm glad to  
see you're included it. What you don't mention is that the language is  
non-applicative. This is essentially a requirement of all terms being  
functions, but perhaps you could cram it in there.

Here it is again with a few small changes:

"A concatenative programming language is A NON-APPLICATIVE language in  
which ALL terms correspond to functions and in which the juxtaposition  
of terms denotes the composition of functions."

I'm fine with this. It doesn't admit some things I'm working on, but  
that's more than fine. The very term "concatenative" essentially  
requires that concatenation mean something, and function composition  
seems like the most likely choice. Yes, you could write a  
concatenative-like language where '.' denoted composition, but why  
would you? Narrowing the syntactic aspect of the definition without  
restricting things that are possibly useful makes it easier to give  
examples, state rules, etc. So yes, requiring juxtaposition mean  
composition is fine.

Your definition doesn't mention quotation. I think this is a good  
thing as Forth doesn't have it. It also leaves open the possibility  
for other forms like construction, conditional (as in Forth), etc.

In short, you seem to have captured the essentials. I like it,  
although I like it more with the non-applicative nature stressed.

I do have a question though. What about a language that allows  
definition of this form:

    dup drop => id

I think the answer is no because the terms denote *terms*, but I'd  
like your answer anyway.

As for the remainder of your article, I completely disagree with this:

"In practical terms a concatenative language is not really different  
from a functional language..."

If we consider Haskell a "functional language", then I think  
concatenative languages are very different both in practical and  
theoretical terms. Of course, it's not necessarily clear what you mean  
by "functional" (which is another horribly abused term).

- John

[John Nowak]

On Dec 31, 2008, at 11:07 PM, Don Groves wrote:

>> 3. There's no reason that the data structure the functions operate on
>> be a list or a stack. I recently proposed a language using vectors in
>> the style of More's array theory. Earlier today, Chris proposed a
>> language based on a deque. I believe XY works on a stack/queue tuple.
>> Other possibilities are easy to dream up.
>
> The reason I picked "sequence" is that it seems to be the most basic
> ordered structure.

They need not be ordered. Consider a language that passed around a  
dictionary. Primitive operations would assume their arguments were  
stored at particular names. Essentially, it would be something like a  
register machine (as opposed to a stack machine).

No, it isn't *useful*, but I'm not sure if you'd want to exclude it.

- John

[John Nowak]

On Jan 1, 2009, at 1:37 AM, William Tanksley, Jr wrote:

> I do suspect that the definition might be a little improved by
> hybridizing it with your newest one, perhaps something like this:
>
> "A concatenative programming language is language in which terms
> correspond to functions and in which the juxtaposition of terms
> denotes an associative operation on functions."
>
> Is it TOO general? It seems to me to cover all the cases, even the
> non-interesting ones (such as where the operation is multiplication).

I'd say yes. Ideally, we'd like to be both clear *and* precise. I  
think such a definition would satisfy the first requirement (it's  
clear) but not the latter (it's too broad to be useful). It might be  
worth considering if we had some other interesting associative  
operations to base a programming language on, but I (thankfully) can't  
think of any.

- John