# Cat: updated manual and type inference algorithm description

## Christopher Diggins — 2006-11-09 17:00:02

    I've recently posted a new updated manual for the Cat language to

    http://www.cat-language.com/manual.html (dated November 8th).

    What may be of most interest to readers is that a somewhat rigorous

    explanation of the type inference algorithm is included.

    Any feedback on the manual would be much appreciated!

    Thanks in advance,

    Christopher

## William Tanksley, Jr — 2006-11-09 21:59:08

    Christopher Diggins <cdiggins@...> wrote:

     > Any feedback on the manual would be much appreciated!

     Just a quick note (I'm still reading the manual):

    You say "Unlike most other functional languages, Cat is based on the

    composition of functions rather than the application of functions."

    I'm not sure that sentance would make sense to someone who didn't

    already know concatenative theory well. In an applicative language,

    composition is done explicitly by means of application, so someone who

    only knew applicative languages would probably have no idea why that

    makes Cat special. Perhaps a closer approach would be:

    "Unlike most other functional languages, Cat is based on the implicit

    composition of functions rather than the explicit application of

    functions to parameters."

    That doesn't explain anything, but now it's clear to any reader that

    Cat is different, even if they will need to keep reading in order to

    find out why.

    I also notice that you refer to Cat as a "compositional" language.

    What's that mean? I only see one message in the group in which you

    brought that up... In that message, you asked why a syntactic

    classification ("concatenative") was used to name our group of

    languages. It seems natural to me that a syntactic term would describe

    a language; the study of languages is *defined* as the study of

    syntax. If you do a web search for "concatenative" you'll find that

    linguists (of human languages) also have a "concatenative"

    classification for the same reason.

    Hmm, I'm going to google for "compositional". Lots of philosophy, some

    problem analysis (looks like it has a similar root meaning)...

    But I'm not suggesting that you should mention that in the manual.

    Your approach is excellent as far as I can see. I'm only wondering.

     > Christopher

     -Billy

## Christopher Diggins — 2006-11-09 22:56:29

    On 11/9/06, William Tanksley, Jr <wtanksleyjr@...> wrote:

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

    > > Any feedback on the manual would be much appreciated!

    >

    > Just a quick note (I'm still reading the manual):

     Thanks!

     > You say "Unlike most other functional languages, Cat is based on the

    > composition of functions rather than the application of functions."

    >

    > I'm not sure that sentance would make sense to someone who didn't

    > already know concatenative theory well. In an applicative language,

    > composition is done explicitly by means of application, so someone who

    > only knew applicative languages would probably have no idea why that

    > makes Cat special. Perhaps a closer approach would be:

    >

    > "Unlike most other functional languages, Cat is based on the implicit

    > composition of functions rather than the explicit application of

    > functions to parameters."

     I do like that more!

     > That doesn't explain anything, but now it's clear to any reader that

    > Cat is different, even if they will need to keep reading in order to

    > find out why.

    >

    > I also notice that you refer to Cat as a "compositional" language.

    > What's that mean? I only see one message in the group in which you

    > brought that up...

     I lifted the term from one of Manfred's papers.

     > In that message, you asked why a syntactic

    > classification ("concatenative") was used to name our group of

    > languages. It seems natural to me that a syntactic term would describe

    > a language; the study of languages is *defined* as the study of

    > syntax.

     Regardless, semantics are signficiant to the study of programming

    languages, and arguably even more so than syntax.

     > If you do a web search for "concatenative" you'll find that

    > linguists (of human languages) also have a "concatenative"

    > classification for the same reason.

     As tempting as it may be, a discussion which includes the study of

    natural language in too broad to be useful. I think it is more

    beneficial to narrow it to a discourse to only programming languages.

    The syntax of a programming language, is largely uninteresting to

    programming language researchers, since it is considered mostly a

    trivial issue. The research community considers programming language

    semantics to be the more interesting topic, as well as a better method

    for categorizing languages.

    I want to also point out how programming languages with non-trivial

    macro systems in fact have a variable syntax. In my opinion this blows

    the lid off of any attempt to draw parallels between the study of

    natural language and programming language.

    My reason for not calling Cat "concatenative" is that concatenation in

    of itself is not a particularly descriptive method of categorizing a

    programming language. Just because two programs can be concatenated

    doesn't say anything about whether a language is functional,

    imperative, concurrent, etc.

     > Hmm, I'm going to google for "compositional". Lots of philosophy, some

    > problem analysis (looks like it has a similar root meaning)...

     I would also urge you to look through the programming language and

    mathematical research literature as well.

     > But I'm not suggesting that you should mention that in the manual.

    > Your approach is excellent as far as I can see. I'm only wondering.

     You are too kind!

    I think this is a very worthwhile debate to have, because I do plan on

    submitting to some peer reviewed journals eventually.

    Cheers,

    Christopher

## William Tanksley, Jr — 2006-11-10 16:32:29

    A side issue: I found a partial sentance in your manual. After

    presenting the type of the 'if' statement, you have a paragraph: "The

    type of if expresses the fact that the if function requires two

    functions with the same signature. More on what the type" [sic].

    Christopher Diggins <cdiggins@...> wrote:

     > William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > I also notice that you refer to Cat as a "compositional" language.

    > > What's that mean? I only see one message in the group in which you

    > > brought that up...

    > I lifted the term from one of Manfred's papers.

     I see! The paper might have been his FAQ:

    http://www.latrobe.edu.au/philosophy/phimvt/joy/faq.html

    Let me quote: "Any functional language which completely replaces

    application, by explicit or implicit "@", by composition, with

    explicit or implicit "." or ";", might be called a compositional

    functional language."

    For comparison, he explains concatenative functional languages as: "A

    language in which the concatenation of programs denote the composition

    of functions has been called a concatenative language."

    So Cat is both compositional and concatenative. Your Unimperative

    language is compositional but not concatenative. Interesting! It seems

    clear that every concatenative language is compositional, but not vice

    versa. Compositional languages can have additional syntax that

    concatenative language don't -- specifically, they can require an

    explicit operator to express concatenation of functions. I don't see

    any real use for the two names -- your "Unimperative" is to the best

    of my knowledge the only actual use for a language entirely without

    applicativity but with an explicit composition operator. (I have to

    admit that it's pretty cool, from what I've seen.)

    By the way, you write many times that mathematical notation always

    writes function composition such that f(g(x)) = (f.g)(x), and you've

    used that to claim that concatenative languages are backwards. That's

    not true -- different authors use different conventions, and the

    abstract algebra courses I took at UCSD went so far that they used

    postfix notation for function composition (oddly enough!), so that the

    mathematical notation was actually concatenative (although no

    combinators were used, unsurprisingly). The book we used, by the way,

    was by Herstein (I don't remember the title).

    I see that Wikipedia considers that an "alternative" notation which is

    now obsolete. Oh well, I don't feel THAT old, but maybe my prof was

    being a bit old-fashioned or something (what do I know).

    (Hmm, the definition of "concatenative" on Wikipedia may need some

    work -- it's totally specific to functional concatenative languages,

    and would be extremely hard to read for anyone not deeply educated in

    functional languages. No wonder the author mentioned twice that the

    defintion might be a bit controversial.)

     > > In that message, you asked why a syntactic

    > > classification ("concatenative") was used to name our group of

    > > languages. It seems natural to me that a syntactic term would describe

    > > a language; the study of languages is *defined* as the study of

    > > syntax.

    > Regardless, semantics are signficiant to the study of programming

    > languages, and arguably even more so than syntax.

     Semantics are certainly important, but I would certainly argue if you

    tried to say they're MORE important than syntax. They are simply

    different, and should not be conflated by attempting to place them on

    the same valuation scale.

    The value of the terms "concatenative" and "applicative" is precisely

    that they are orthogonal to semantic terms such as "pure functional"

    and "imperative". Manfred writes about "functional concatenative"

    languages, so Joy is a purely functional concatenative language;

    Forth, on the other hand, is quite imperative (NOT functional), yet

    just as concatenative (except for some other areas where the language

    allows access to the unparsed source, so there are parts of the

    language which are not purely concatenative).

    (At this point my web connection cut off, and I typed for 1/2 an hour,

    not realizing that gmail was entirely inaccessible... all gone. Grr.)

     > > If you do a web search for "concatenative" you'll find that

    > > linguists (of human languages) also have a "concatenative"

    > > classification for the same reason.

    > As tempting as it may be, a discussion which includes the study of

    > natural language in too broad to be useful. I think it is more

    > beneficial to narrow it to a discourse to only programming languages.

     Not borrowing from a related field seems to make the task too

    difficult. Both human languages and computer languages are languages;

    both have syntax and semantics; and both can be parsed by a computer

    algorithm (although the human language requires a "unification

    grammar", whose syntax is more complex than that of the most complex

    computer language grammar).

     > The syntax of a programming language, is largely uninteresting to

    > programming language researchers, since it is considered mostly a

    > trivial issue. The research community considers programming language

    > semantics to be the more interesting topic, as well as a better method

    > for categorizing languages.

     I would concede this, but I'd also say that this is a mistake on the

    part of the research community (although of course each researcher

    should study what is interesting to them). Semantics and syntax are

    different things which are both worthy of study. Most researchers and

    practitioners seem to have "given up" on studying pure syntax once

    LALR parsing was elaborated and PL/I was implemented (PL/I being

    probably the most elaborate use of a parser less than or equal to LR),

    but there are a huge amount of discoveries yet to be made. There are,

    for example, more types of applicative grammars that are far faster

    than LR and more natural to write in than LALR -- that's an example of

    pure syntax that's still interesting to research.

    Concatenative syntax is one of those discoveries, and it's WAY off the

    beaten path.

    If the researchers had done their jobs by studying syntax, perhaps

    Perl wouldn't have happened. (Zing!)

     > I want to also point out how programming languages with non-trivial

    > macro systems in fact have a variable syntax. In my opinion this blows

    > the lid off of any attempt to draw parallels between the study of

    > natural language and programming language.

     It seems to do the opposite -- in fact, you're drawing a parallel

    between them in order to prove that no parallels can be drawn. The

    simple fact that there are differences proves that the ideas are

    comparable.

    In fact, the entire study of computer languages is based on the study

    of human languages, and has recently (with the discovery of

    unification grammars) been able to contribute back to the study of

    natural language.

     > My reason for not calling Cat "concatenative" is that concatenation in

    > of itself is not a particularly descriptive method of categorizing a

    > programming language.

     First, let me say that I'm not at ALL against you calling Cat

    "compositional". It is certainly compositional, and perhaps you find

    that the name communicates more clearly to the audience you wish to

    reach.

    However, by Manfred's definition in the FAQ, "concatenative" is _more_

    descriptive and specific than "compositional". "Concatenative" means

    that the language is compositional AND composition is implicit.

     > Just because two programs can be concatenated

    > doesn't say anything about whether a language is functional,

    > imperative, concurrent, etc.

     And that's a good thing -- it means that the terms are orthogonal. Why

    should one word have to describe everything about a language? Manfred

    consistently uses the term "functional concatenative language" to

    refer to Joy; Factor is also functional, although impure; Forth makes

    no attempt whatsoever. But all are concatenative (although Forth,

    again, is not strictly pure, unsurprising since it was designed LONG

    before such things were known).

    Note that "compositional" does not imply "pure functional" either --

    it merely means that all application is discarded and composition

    (explicit or implicit) is used instead.

     > > Hmm, I'm going to google for "compositional". Lots of philosophy, some

    > > problem analysis (looks like it has a similar root meaning)...

    > I would also urge you to look through the programming language and

    > mathematical research literature as well.

     Before writing that I used Google and got nothing except what I

    described. I just tried Google Scholar (narrowed down to comp sci,

    math, and engineering) and also got nothing similar to what we're

    talking about. It seems that "compositional" is as much a neologism as

    "concatenative".

    How do you search, and what do you find?

     > > But I'm not suggesting that you should mention that in the manual.

    > > Your approach is excellent as far as I can see. I'm only wondering.

    > You are too kind!

     I hope you still think so :-).

     > I think this is a very worthwhile debate to have, because I do plan on

    > submitting to some peer reviewed journals eventually.

     Wow, that would be terrific!

     > Christopher

     -Billy

## Christopher Diggins — 2006-11-11 18:37:48

    On 11/10/06, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > A side issue: I found a partial sentance in your manual. After

    > presenting the type of the 'if' statement, you have a paragraph: "The

    > type of if expresses the fact that the if function requires two

    > functions with the same signature. More on what the type" [sic].

     Thank you for pointing that out.

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

    > > William Tanksley, Jr <wtanksleyjr@...> wrote:

    >

    > > > I also notice that you refer to Cat as a "compositional" language.

    > > > What's that mean? I only see one message in the group in which you

    > > > brought that up...

    >

    > > I lifted the term from one of Manfred's papers.

    >

    > I see! The paper might have been his FAQ:

    > http://www.latrobe.edu.au/philosophy/phimvt/joy/faq.html

    >

    > Let me quote: "Any functional language which completely replaces

    > application, by explicit or implicit "@", by composition, with

    > explicit or implicit "." or ";", might be called a compositional

    > functional language."

     Yes, that was it!

     > For comparison, he explains concatenative functional languages as: "A

    > language in which the concatenation of programs denote the composition

    > of functions has been called a concatenative language."

     I recall reading somewhere else a reference to the fact that a

    concatenative language could be defined as a language where the

    concatenation of two terms yields a new valid program. I believe

    Manfred's definition is too narrow. I can imagine languages where two

    terms concatenated together have a meaning other than composition but

    always yield valid a valid program. I would want to call such an

    imaginary language a non-compositional concatenative language.

     > So Cat is both compositional and concatenative. Your Unimperative

    > language is compositional but not concatenative. Interesting! It seems

    > clear that every concatenative language is compositional, but not vice

    > versa.

     Wether evey concatenative language is in fact compositional depends on

    the definition.

     > Compositional languages can have additional syntax that

    > concatenative language don't -- specifically, they can require an

    > explicit operator to express concatenation of functions. I don't see

    > any real use for the two names -- your "Unimperative" is to the best

    > of my knowledge the only actual use for a language entirely without

    > applicativity but with an explicit composition operator. (I have to

    > admit that it's pretty cool, from what I've seen.)

     Thanks, but that was simply due to the restrictions of C++.

     > By the way, you write many times that mathematical notation always

    > writes function composition such that f(g(x)) = (f.g)(x), and you've

    > used that to claim that concatenative languages are backwards. That's

    > not true -- different authors use different conventions, and the

    > abstract algebra courses I took at UCSD went so far that they used

    > postfix notation for function composition (oddly enough!), so that the

    > mathematical notation was actually concatenative (although no

    > combinators were used, unsurprisingly). The book we used, by the way,

    > was by Herstein (I don't remember the title).

     Thanks for correcting me.

     > I see that Wikipedia considers that an "alternative" notation which is

    > now obsolete. Oh well, I don't feel THAT old, but maybe my prof was

    > being a bit old-fashioned or something (what do I know).

    >

    > (Hmm, the definition of "concatenative" on Wikipedia may need some

    > work -- it's totally specific to functional concatenative languages,

    > and would be extremely hard to read for anyone not deeply educated in

    > functional languages. No wonder the author mentioned twice that the

    > defintion might be a bit controversial.)

     Every entry related to computer science in Wikipedia needs some work :-)

     > > > In that message, you asked why a syntactic

    > > > classification ("concatenative") was used to name our group of

    > > > languages. It seems natural to me that a syntactic term would describe

    > > > a language; the study of languages is *defined* as the study of

    > > > syntax.

    >

    > > Regardless, semantics are signficiant to the study of programming

    > > languages, and arguably even more so than syntax.

    >

    > Semantics are certainly important, but I would certainly argue if you

    > tried to say they're MORE important than syntax. They are simply

    > different, and should not be conflated by attempting to place them on

    > the same valuation scale.

     That is a valid point.

     > The value of the terms "concatenative" and "applicative" is precisely

    > that they are orthogonal to semantic terms such as "pure functional"

    > and "imperative". Manfred writes about "functional concatenative"

    > languages, so Joy is a purely functional concatenative language;

    > Forth, on the other hand, is quite imperative (NOT functional), yet

    > just as concatenative (except for some other areas where the language

    > allows access to the unparsed source, so there are parts of the

    > language which are not purely concatenative).

    >

    > (At this point my web connection cut off, and I typed for 1/2 an hour,

    > not realizing that gmail was entirely inaccessible... all gone. Grr.)

     :-(

     > > > If you do a web search for "concatenative" you'll find that

    > > > linguists (of human languages) also have a "concatenative"

    > > > classification for the same reason.

    >

    > > As tempting as it may be, a discussion which includes the study of

    > > natural language in too broad to be useful. I think it is more

    > > beneficial to narrow it to a discourse to only programming languages.

    >

    > Not borrowing from a related field seems to make the task too

    > difficult. Both human languages and computer languages are languages;

    > both have syntax and semantics; and both can be parsed by a computer

    > algorithm (although the human language requires a "unification

    > grammar", whose syntax is more complex than that of the most complex

    > computer language grammar).

     The list of differences is even greater.

     > > The syntax of a programming language, is largely uninteresting to

    > > programming language researchers, since it is considered mostly a

    > > trivial issue. The research community considers programming language

    > > semantics to be the more interesting topic, as well as a better method

    > > for categorizing languages.

    >

    > I would concede this, but I'd also say that this is a mistake on the

    > part of the research community (although of course each researcher

    > should study what is interesting to them). Semantics and syntax are

    > different things which are both worthy of study.

     Good point.

     > Most researchers and

    > practitioners seem to have "given up" on studying pure syntax once

    > LALR parsing was elaborated and PL/I was implemented (PL/I being

    > probably the most elaborate use of a parser less than or equal to LR),

    > but there are a huge amount of discoveries yet to be made. There are,

    > for example, more types of applicative grammars that are far faster

    > than LR and more natural to write in than LALR -- that's an example of

    > pure syntax that's still interesting to research.

    >

    > Concatenative syntax is one of those discoveries, and it's WAY off the

    > beaten path.

     Concatenative syntax is not so off the beaten path. There was a *lot*

    of research into Forth back in the day.

     > If the researchers had done their jobs by studying syntax, perhaps

    > Perl wouldn't have happened. (Zing!)

     :-)

     > > I want to also point out how programming languages with non-trivial

    > > macro systems in fact have a variable syntax. In my opinion this blows

    > > the lid off of any attempt to draw parallels between the study of

    > > natural language and programming language.

    >

    > It seems to do the opposite -- in fact, you're drawing a parallel

    > between them in order to prove that no parallels can be drawn. The

    > simple fact that there are differences proves that the ideas are

    > comparable.

     Yes, comparable but not synonymous. My only point was that you can't

    say X is true in natural languages, therefore (some conclusion about

    programming language).

     > In fact, the entire study of computer languages is based on the study

    > of human languages, and has recently (with the discovery of

    > unification grammars) been able to contribute back to the study of

    > natural language.

    >

    > > My reason for not calling Cat "concatenative" is that concatenation in

    > > of itself is not a particularly descriptive method of categorizing a

    > > programming language.

    >

    > First, let me say that I'm not at ALL against you calling Cat

    > "compositional". It is certainly compositional, and perhaps you find

    > that the name communicates more clearly to the audience you wish to

    > reach.

    >

    > However, by Manfred's definition in the FAQ, "concatenative" is _more_

    > descriptive and specific than "compositional". "Concatenative" means

    > that the language is compositional AND composition is implicit.

    >

    > > Just because two programs can be concatenated

    > > doesn't say anything about whether a language is functional,

    > > imperative, concurrent, etc.

    >

    > And that's a good thing -- it means that the terms are orthogonal. Why

    > should one word have to describe everything about a language? Manfred

    > consistently uses the term "functional concatenative language" to

    > refer to Joy; Factor is also functional, although impure; Forth makes

    > no attempt whatsoever. But all are concatenative (although Forth,

    > again, is not strictly pure, unsurprising since it was designed LONG

    > before such things were known).

     Can we really call Forth compositional? It seems so imperative.

     > Note that "compositional" does not imply "pure functional" either --

    > it merely means that all application is discarded and composition

    > (explicit or implicit) is used instead.

     Pure compositional seems to imply pure functional.

    I like what you are saying here. I am thinking that calling Cat

    "compositional concatenative" is the most accurate.

     > > > Hmm, I'm going to google for "compositional". Lots of philosophy, some

    > > > problem analysis (looks like it has a similar root meaning)...

    >

    > > I would also urge you to look through the programming language and

    > > mathematical research literature as well.

    >

    > Before writing that I used Google and got nothing except what I

    > described. I just tried Google Scholar (narrowed down to comp sci,

    > math, and engineering) and also got nothing similar to what we're

    > talking about. It seems that "compositional" is as much a neologism as

    > "concatenative".

    >

    > How do you search, and what do you find?

     I searched Google scholar and came up empty. Hence my very unsupported

    arguments :-)

    "Compostional languages" have been used, but only to describe

    languages which describe the composition of software component.

     > > > But I'm not suggesting that you should mention that in the manual.

    > > > Your approach is excellent as far as I can see. I'm only wondering.

    >

    > > You are too kind!

    >

    > I hope you still think so :-).

     Of course, I appreciate you taking the time to discuss this with me in

    such a respectful and informative manner.

     > > I think this is a very worthwhile debate to have, because I do plan on

    > > submitting to some peer reviewed journals eventually.

    >

    > Wow, that would be terrific!

     Would you mind reviewing the paper when it is ready for submission?

     > > Christopher

    >

    > -Billy

     Thanks,

    Christopher

## William Tanksley, Jr — 2006-11-18 05:11:54

    Christopher Diggins <cdiggins@...> wrote:

     > On 11/10/06, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > Let me quote: "Any functional language which completely replaces

    > > application, by explicit or implicit "@", by composition, with

    > > explicit or implicit "." or ";", might be called a compositional

    > > functional language."

    > > For comparison, he explains concatenative functional languages as: "A

    > > language in which the concatenation of programs denote the composition

    > > of functions has been called a concatenative language."

    > I recall reading somewhere else a reference to the fact that a

    > concatenative language could be defined as a language where the

    > concatenation of two terms yields a new valid program. I believe

    > Manfred's definition is too narrow. I can imagine languages where two

    > terms concatenated together have a meaning other than composition but

    > always yield valid a valid program. I would want to call such an

    > imaginary language a non-compositional concatenative language.

     Manfred gave an example -- integer multiplication. Regular expressions

    occur to me as another example. Manfred's definition in the FAQ is too

    narrow, although in his defence I think his wording "has been called"

    makes it not a definition, but an example.

    So ... I'm wrong! :-)

    I still need to come up with a definition, but I'm in  no rush -- I'm

    only just beginning to understand. In particular, I'm starting to see

    a distinction between "compositional" and "concatenative" which, if I

    think hard enough (I'm not right now) might help me explain why source

    manipulations might be valid in some forms of concatenative or

    semi-concatenative languages. Maybe. Let me think about that for a few

    days.

     > > > > If you do a web search for "concatenative" you'll find that

    > > > > linguists (of human languages) also have a "concatenative"

    > > > > classification for the same reason.

    > > > As tempting as it may be, a discussion which includes the study of

    > > > natural language in too broad to be useful. I think it is more

    > > > beneficial to narrow it to a discourse to only programming languages.

    > > Not borrowing from a related field seems to make the task too

    > > difficult. Both human languages and computer languages are languages;

    > > both have syntax and semantics; and both can be parsed by a computer

    > > algorithm (although the human language requires a "unification

    > > grammar", whose syntax is more complex than that of the most complex

    > > computer language grammar).

    > The list of differences is even greater.

     But the differences are of the same order as the list of differences

    between Perl regexps and Ada. They're both languages, amenable to the

    same theory and parseable by Turing machines (although acting in

    different capacities). Listing the differences is useless until you

    recognise the similarities. Like listing the differences between the

    US Constitution and (the English version of) Wikipedia.

     > > Concatenative syntax is one of those discoveries, and it's WAY off the

    > > beaten path.

    > Concatenative syntax is not so off the beaten path. There was a *lot*

    > of research into Forth back in the day.

     Interesting. I knew there was something of a fad in it, but I didn't

    know any researchers were interested. I recall a story about the

    editor of an encyclopedia of languages turning down the entry for

    Forth with the statement "that's not a language". Of course, that's

    just an anecdote, and doesn't support my earlier claim that no

    researchers studied concatenative languages...

    But I can say two things: I don't know of any attempt prior to Joy to

    generalize what was different about Forth and Postscript, and I don't

    know any language research that took Forth itself seriously.

    (I do know one pure mathematician who took Forth seriously, but he

    didn't study the language; he used it. See

    http://math.ucsd.edu/~jwavrik/ for more, not related to this

    discussion though.)

     > > And that's a good thing -- it means that the terms are orthogonal. Why

    > > should one word have to describe everything about a language? Manfred

    > > consistently uses the term "functional concatenative language" to

    > > refer to Joy; Factor is also functional, although impure; Forth makes

    > > no attempt whatsoever. But all are concatenative (although Forth,

    > > again, is not strictly pure, unsurprising since it was designed LONG

    > > before such things were known).

    > Can we really call Forth compositional? It seems so imperative.

     Haskell monads can be both imperative and purely functional. A

    concatenative language has similar properties -- so Forth can be both

    purely compositional and imperative. (It's NOT purely functional, of

    course.)

     > > Note that "compositional" does not imply "pure functional" either --

    > > it merely means that all application is discarded and composition

    > > (explicit or implicit) is used instead.

    > Pure compositional seems to imply pure functional.

     It could be taken that way. I think it's more useful to separate the

    concerns... A pure compositional language would never use local

    variables, but global variables (the stack is technically a global

    variable, as is the system dictionary) are  perfectly okay. For a

    functional language, the truth is the other way around -- which means

    that a functional compositional language can use none of the above,

    but just pure dataflow (Enchilada does this by replacing talk about

    the stack with talk about textual transformations called

    "reductions").

     > I like what you are saying here. I am thinking that calling Cat

    > "compositional concatenative" is the most accurate.

     Well, I'm convinced, and I wasn't before :-).

     > "Compostional languages" have been used, but only to describe

    > languages which describe the composition of software component.

     Yes, and "concatenative" describes speech synthesis done by tagging

    together voice fragments.

     > > > I think this is a very worthwhile debate to have, because I do plan on

    > > > submitting to some peer reviewed journals eventually.

    > > Wow, that would be terrific!

    > Would you mind reviewing the paper when it is ready for submission?

     That would be a huge honor.

     > Christopher

     -Billy

## Christopher Diggins — 2006-11-18 22:55:09

    > I still need to come up with a definition, but I'm in no rush -- I'm

    > only just beginning to understand. In particular, I'm starting to see

    > a distinction between "compositional" and "concatenative" which, if I

    > think hard enough (I'm not right now) might help me explain why source

    > manipulations might be valid in some forms of concatenative or

    > semi-concatenative languages. Maybe. Let me think about that for a few

    > days.

     I'm glad you are working on the problem, I always appreciate rigorous

    and clear definitions.

    [snip]

     > They're both languages, amenable to the

    > same theory and parseable by Turing machines (although acting in

    > different capacities). Listing the differences is useless until you

    > recognise the similarities. Like listing the differences between the

    > US Constitution and (the English version of) Wikipedia.

     Hmm... this part of the discussion is starting to sound like a battle

    of the analogies ;-)

    I won't bother to debate the issue anymore, since we have different

    approaches and I do respect your line of reasoning. I look forward to

    your future proposed definitions.

     > > > Concatenative syntax is one of those discoveries, and it's WAY off the

    > > > beaten path.

    >

    > > Concatenative syntax is not so off the beaten path. There was a *lot*

    > > of research into Forth back in the day.

    >

    > Interesting. I knew there was something of a fad in it, but I didn't

    > know any researchers were interested. I recall a story about the

    > editor of an encyclopedia of languages turning down the entry for

    > Forth with the statement "that's not a language". Of course, that's

    > just an anecdote, and doesn't support my earlier claim that no

    > researchers studied concatenative languages...

     Well it seems that I overstated the case significantly:

    http://citeseer.ist.psu.edu/cis?q=forth+language&cs=1

    I had found a few interesting papers, but when I dug deeper it turns

    out they were from a handful of individuals and were cited

    surprisingly few times.

     > But I can say two things: I don't know of any attempt prior to Joy to

    > generalize what was different about Forth and Postscript, and I don't

    > know any language research that took Forth itself seriously.

    >

    > (I do know one pure mathematician who took Forth seriously, but he

    > didn't study the language; he used it. See

    > http://math.ucsd.edu/~jwavrik/ for more, not related to this

    > discussion though.)

     Some interesting research was outlined in the paper

    http://citeseer.ist.psu.edu/stoddart93type.html but it seems to have

    gone largely ignored. One other researcher, Jaanus Pöial

    (http://www.kodu.ee/%7Ejpoial/) has been apparently doing some very

    interesting research into type inference and lambda expressions in

    Forth over the last several years (

    https://www.etis.ee/portaal/isikuCV.aspx?TextBoxName=P%c3%b6ial&PersonVID=747&FromUrl0=isikud.aspx

    ) but also seems to unfortunately have been more or less overlooked by

    the general language research community (I base this on an apparent

    lack of citations, not to discredit his work which seems very valid).

     > > Can we really call Forth compositional? It seems so imperative.

    >

    > Haskell monads can be both imperative and purely functional. A

    > concatenative language has similar properties -- so Forth can be both

    > purely compositional and imperative. (It's NOT purely functional, of

    > course.)

     Good point.

     > > > Note that "compositional" does not imply "pure functional" either --

    > > > it merely means that all application is discarded and composition

    > > > (explicit or implicit) is used instead.

    >

    > > Pure compositional seems to imply pure functional.

    >

    > It could be taken that way. I think it's more useful to separate the

    > concerns... A pure compositional language would never use local

    > variables, but global variables (the stack is technically a global

    > variable, as is the system dictionary) are perfectly okay. For a

    > functional language, the truth is the other way around -- which means

    > that a functional compositional language can use none of the above,

    > but just pure dataflow (Enchilada does this by replacing talk about

    > the stack with talk about textual transformations called

    > "reductions").

     Interstingly I could describe Cat or Joy as if they were imperative or

    as if they were functional, and both descriptions would be valid and

    accurate. This proves to me that there is no real difference between

    functional and imperative programming languages.

     > > I like what you are saying here. I am thinking that calling Cat

    > > "compositional concatenative" is the most accurate.

    >

    > Well, I'm convinced, and I wasn't before :-).

     Unfortunately the more literature I read about type systems and

    programming languages, the more I am realizing that the more

    acceptable terminology for Cat (from the researcher viewpoint) would

    seem to be a "functional stack based language".

     > > "Compostional languages" have been used, but only to describe

    > > languages which describe the composition of software component.

    >

    > Yes, and "concatenative" describes speech synthesis done by tagging

    > together voice fragments.

    >

    > > > > I think this is a very worthwhile debate to have, because I do plan on

    > > > > submitting to some peer reviewed journals eventually.

    > > > Wow, that would be terrific!

    > > Would you mind reviewing the paper when it is ready for submission?

    >

    > That would be a huge honor.

     Much appreciated! I'll let you know when a draft is ready.

    Christopher

## Christopher Diggins — 2006-11-20 07:00:36

    > > > Concatenative syntax is not so off the beaten path. There was a *lot*

    > > > of research into Forth back in the day.

    > >

    > > Interesting. I knew there was something of a fad in it, but I didn't

    > > know any researchers were interested. I recall a story about the

    > > editor of an encyclopedia of languages turning down the entry for

    > > Forth with the statement "that's not a language". Of course, that's

    > > just an anecdote, and doesn't support my earlier claim that no

    > > researchers studied concatenative languages...

    >

    > Well it seems that I overstated the case significantly:

    > http://citeseer.ist.psu.edu/cis?q=forth+language&cs=1

    >

    > I had found a few interesting papers, but when I dug deeper it turns

    > out they were from a handful of individuals and were cited

    > surprisingly few times.

     For interest's sake I found the following paper about Forth's academic

    standing in 1993:

    http://citeseer.ist.psu.edu/knaggs93look.html

    - Christopher