# Cat article submission to Doctor Dobbs Journal

## Christopher Diggins — 2008-02-10 06:37:06

    First let me say, I really *really* appreciate all the feedback I have

    had on my past articles on Cat. So far all my article submissions have

    been rejected. :-(

    I submitted three different articles to International Conference of

    Functional Programming (ICFP), Compiler Construction (CC), Programming

    Language Design and Implementation (PLDI) ). These are high-end

    conferences with high-rejection rates. In retrospect they were out of

    my league, but I did have helpful reviews. Overall the reviews were

    encouraging, but were clear on the fact that I had a lot of work to

    do, and that I wasn't yet ready to play in the big leagues. I plan on

    incorporating the review feedback and resubmitting to an appropriate

    workshop or symposium.

    For the time being I have been contracted to provide Doctor Dobbs with

    an article about Cat. I talk quite a bit about Joy and concatenative

    languages in general. It is due Monday, but if anyone has time to

    share comments or suggestions before then I would be most

    appreciative. I have put a draft of the article online at

    http://docs.google.com/Doc?id=dgjz7z25_58f4zzg8dz . If I make any big

    mistakes, or inaccuracies, or I am unfair I apologize in advance.

    Please let me know so that I can correct it. I will have a chance to

    make small changes to the galley proof before the article goes to the

    printer.

    Hopefully this will help give a bit more mainstream recognition to the

    benefits of concatenative languages!

    Thanks,

    Christopher

## William Tanksley, Jr — 2008-02-10 07:19:13

    > For the time being I have been contracted to provide Doctor Dobbs with

    > an article about Cat. I talk quite a bit about Joy and concatenative

    > languages in general. It is due Monday, but if anyone has time to

     Congrats! Tell me which month so I can read it in print!

    Some notes:

    What is the [?] in "...very easy to create efficient implementations for [?],"?

    The phrase "upon which Manfred von Thun, based the Joy language"

    shouldn't have a comma.

    Now I find a real disagreement. First-class functions aren't at all

    part of the definition of "concatenative", nor are branch statements

    antithetical to concatenativity. Manfred's major innovation was to

    introduce and extensively use function literals, which are similar to

    lambdas in other functional languages; this innovation allowed Joy to

    be analyzed in much the same way as other functional languages. I'd

    really appreciate it if you'd alter this part of the article, if at

    all possible; the definition of "concatenative" may not be perfect,

    but it's FAR sharper than this. A possible replacement:

    "Manfred's primary innovation with Joy was to introduce first class

    functions and function literals (called quotations). The resulting

    language shares many of the advantages of functional languages (e.g.

    it is easy to reason about) and is particularly expressive."

    Unfortunately, this removes all mention of "concatenative" from your

    article, but since you didn't really discuss it I don't think it's a

    loss. I do think you could be more precise than "is particularly

    expressive", though... I'm not sure what you mean by it, although it

    looks like a compliment :-).

    Minor style note: "using the higher-order functions apply, if, while,

    etc." Using "etc" is not optimal; try "using higher-order functions

    such as apply, if, and while."

    ...I just got handed the baby. No more time! :-)

    -Wm

## Christopher Diggins — 2008-02-10 07:55:19

    Hi William,

    Thanks. I've responded to your comments below and already started

    tweaking the article as per your suggestions.

     On Feb 10, 2008 2:19 AM, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > For the time being I have been contracted to provide Doctor Dobbs with

    > > an article about Cat. I talk quite a bit about Joy and concatenative

    > > languages in general. It is due Monday, but if anyone has time to

    >

    > Congrats!

    Thanks.

    > Tell me which month so I can read it in print!

    I can't say yet, I'll let you know as soon as I know.

    > Some notes:

    >

    > What is the [?] in "...very easy to create efficient implementations for

    > [?],"?

    Reference place holders. Changed it to [ref]

    > The phrase "upon which Manfred von Thun, based the Joy language"

    > shouldn't have a comma.

    >

    > Now I find a real disagreement. First-class functions aren't at all

    > part of the definition of "concatenative"

    My bad, I didn't mean to imply that. They are key to why Joy is so

    interesting (to me at least) though.

    > nor are branch statements

    > antithetical to concatenativity.

    I really didn't mean to imply that one neither. My point was that the

    fact that Manfred leaving branch  statements (by which I mean goto

    statements) out was significant (is that contentious?). I wasnt trying

    to say anything there about concatenative languages in general. I've

    tried to clarify.

    >Manfred's major innovation was to

    > introduce and extensively use function literals, which are similar to

    > lambdas in other functional languages;  this innovation allowed Joy to

    > be analyzed in much the same way as other functional languages. I'd

    > really appreciate it if you'd alter this part of the article, if at

    > all possible; the definition of "concatenative" may not be perfect,

    > but it's FAR sharper than this.

    >

    > A possible replacement:

    >

    > "Manfred's primary innovation with Joy was to introduce first class

    > functions and function literals (called quotations). The resulting

    > language shares many of the advantages of functional languages (e.g.

    > it is easy to reason about) and is particularly expressive."

    I like that, but the goto removal is significant, and should be left

    because with gotos you wouldn't have the nice rewriting properties

    that you have now.

    > Unfortunately, this removes all mention of "concatenative" from your

    > article, but since you didn't really discuss it I don't think it's a

    > loss. I do think you could be more precise than "is particularly

    > expressive", though... I'm not sure what you mean by it, although it

    > looks like a compliment :-).

    By expressive I meant that we can say a lot with a little. (e.g. a few

    instructions can convey a sophisticated concept). I've tried to

    rephrase.

    > Minor style note: "using the higher-order functions apply, if, while,

    > etc." Using "etc" is not optimal; try "using higher-order functions

    > such as apply, if, and while."

    Good point.

    > ...I just got handed the baby. No more time! :-)

    >

    > -Wm

    I look forward to more of your comments, thanks!

    Gotta go to bed now,

    - Christopher

## William Tanksley, Jr — 2008-02-10 17:25:20

    Christopher Diggins <cdiggins@...> wrote:

     > > Now I find a real disagreement. First-class functions aren't at all

    > > part of the definition of "concatenative"

    > My bad, I didn't mean to imply that. They are key to why Joy is so

    > interesting (to me at least) though.

     Definitely. You're right that they belong in the intro.

     > > nor are branch statements

    > > antithetical to concatenativity.

    > I really didn't mean to imply that one neither. My point was that the

    > fact that Manfred leaving branch  statements (by which I mean goto

    > statements) out was significant (is that contentious?). I wasnt trying

    > to say anything there about concatenative languages in general. I've

    > tried to clarify.

     What previous concatenative language had GOTO statements? I don't

    think Manfred "left them out"... They're a little hard to put in, so

    they were rare at best in other concatenative languages. I assumed you

    were talking about special syntax for conditionals, which Manfred

    removed the need for when he supplied function literals.

     > > A possible replacement:

    > > "Manfred's primary innovation with Joy was to introduce first class

    > > functions and function literals (called quotations). The resulting

    > > language shares many of the advantages of functional languages (e.g.

    > > it is easy to reason about) and is particularly expressive."

    > I like that, but the goto removal is significant, and should be left

    > because with gotos you wouldn't have the nice rewriting properties

    > that you have now.

     Good point... But that's because of the removal of syntax (or the

    regularization of syntax), not so much because of the removal of GOTOs

    (which are merely a particular type of syntax, and one which most

    concatenative languages don't have anyhow).

     > > Unfortunately, this removes all mention of "concatenative" from your

    > > article, but since you didn't really discuss it I don't think it's a

    > > loss. I do think you could be more precise than "is particularly

    > > expressive", though... I'm not sure what you mean by it, although it

    > > looks like a compliment :-).

    > By expressive I meant that we can say a lot with a little. (e.g. a few

    > instructions can convey a sophisticated concept). I've tried to

    > rephrase.

     Cool.

     > I look forward to more of your comments, thanks!

     Having skimmed the rest, I like what you have from there on... I could

    hunt for more nits to pick, but don't have the time and might not find

    any anyhow.

     > - Christopher

     -Wm

## Christopher Diggins — 2008-02-10 18:15:17

    On Feb 10, 2008 12:25 PM, William Tanksley, Jr <wtanksleyjr@...> wrote:

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

    > > > Now I find a real disagreement. First-class functions aren't at all

    > > > part of the definition of "concatenative"

    >

    > > My bad, I didn't mean to imply that. They are key to why Joy is so

    > > interesting (to me at least) though.

    >

    > Definitely. You're right that they belong in the intro.

    >

    >

    > > > nor are branch statements

    > > > antithetical to concatenativity.

    >

    > > I really didn't mean to imply that one neither. My point was that the

    > > fact that Manfred leaving branch statements (by which I mean goto

    > > statements) out was significant (is that contentious?). I wasnt trying

    > > to say anything there about concatenative languages in general. I've

    > > tried to clarify.

    >

    > What previous concatenative language had GOTO statements?

     Forth has BRANCH and BRANCH? Do you consider Forth a concatenative

    language? Either way I am talking explicitly about stack-based

    languages so Forth definitely has to be considered.

     >  I don't

    > think Manfred "left them out"... They're a little hard to put in, so

    > they were rare at best in other concatenative languages. I assumed you

    > were talking about special syntax for conditionals, which Manfred

    > removed the need for when he supplied function literals.

     I consider conditionals (and other control flow constructs) as simply

    syntactic sugar for branch statements. However, I will try to make it

    less contentious, and my intention more clear.

     > > > A possible replacement:

    >

    > > > "Manfred's primary innovation with Joy was to introduce first class

    > > > functions and function literals (called quotations). The resulting

    > > > language shares many of the advantages of functional languages (e.g.

    > > > it is easy to reason about) and is particularly expressive."

    >

    > > I like that, but the goto removal is significant, and should be left

    > > because with gotos you wouldn't have the nice rewriting properties

    > > that you have now.

    >

    > Good point... But that's because of the removal of syntax (or the

    > regularization of syntax), not so much because of the removal of GOTOs

    > (which are merely a particular type of syntax, and one which most

    > concatenative languages don't have anyhow).

     You keep saying concatenative languages, and I am talking about

    stack-based languages. I am still not sure which languages are

    technically concatenative (is Forth? is JVML? is PostScript?). I am

    referring to things like MSIL, JVML, and Forth all of which have

    explicit gotos (i.e. branches / jumps / conditionals / etc.).

    Historically branching is part of stack

    languages, because they lacked higher-order functions. However

    PostScript breaks this rule, and I am concerned that I may be beging

    inaccurate when we consider it. It seems that PostScript does have a

    notion of function literals before Joy, so I have to be careful how I

    refer to the contributions of Joy.

     > > > Unfortunately, this removes all mention of "concatenative" from your

    > > > article, but since you didn't really discuss it I don't think it's a

    > > > loss. I do think you could be more precise than "is particularly

    > > > expressive", though... I'm not sure what you mean by it, although it

    > > > looks like a compliment :-).

    >

    > > By expressive I meant that we can say a lot with a little. (e.g. a few

    > > instructions can convey a sophisticated concept). I've tried to

    > > rephrase.

    >

    > Cool.

    >

    >

    > > I look forward to more of your comments, thanks!

    >

    > Having skimmed the rest, I like what you have from there on... I could

    > hunt for more nits to pick, but don't have the time and might not find

    > any anyhow.

     Thank you very much!!

    - Christopher

## Stevan Apter — 2008-02-10 18:38:46

    chris:

     > You keep saying concatenative languages, and I am talking about

    > stack-based languages. I am still not sure which languages are

    > technically concatenative (is Forth? is JVML? is PostScript?).

     i've been up and down this road so many times i'm giving names to

    the rocks.  am i wrong in thinking that the languages we're

    concerned with (in this group) are those in which wholes are built

    from parts by concatenation and where concatenation denotes a

    fundamental operation, either composition or application (or

    something else)?

    joy and its descendents satisfy that definition.  other languages

    can be restricted in various ways to satisfy it.

## Christopher Diggins — 2008-02-10 19:00:31

    On Feb 10, 2008 1:38 PM, Stevan Apter <sa@...> wrote:

     > chris:

    >

    >

    > > You keep saying concatenative languages, and I am talking about

    > > stack-based languages. I am still not sure which languages are

    > > technically concatenative (is Forth? is JVML? is PostScript?).

    >

    > i've been up and down this road so many times i'm giving names to

    > the rocks. am i wrong in thinking that the languages we're

    > concerned with (in this group) are those in which wholes are built

    > from parts by concatenation and where concatenation denotes a

    > fundamental operation, either composition or application (or

    > something else)?

    >

    > joy and its descendents satisfy that definition. other languages

    > can be restricted in various ways to satisfy it.

     Hi Stevan,

    This seems more or less like the definition that majority of the group

    has agreed upon. In your opinion what languages other than Joy does it

    include?

    - Christopher

## Stevan Apter — 2008-02-10 19:23:11

    ----- Original Message -----

    From: "Christopher Diggins" <cdiggins@...>

    To: <concatenative@yahoogroups.com>

    Sent: Sunday, February 10, 2008 2:00 PM

    Subject: Re: [stack] Cat article submission to Doctor Dobbs Journal

    > On Feb 10, 2008 1:38 PM, Stevan Apter <sa@...> wrote:

    >> chris:

    >>

    >>

    >> > You keep saying concatenative languages, and I am talking about

    >> > stack-based languages. I am still not sure which languages are

    >> > technically concatenative (is Forth? is JVML? is PostScript?).

    >>

    >> i've been up and down this road so many times i'm giving names to

    >> the rocks. am i wrong in thinking that the languages we're

    >> concerned with (in this group) are those in which wholes are built

    >> from parts by concatenation and where concatenation denotes a

    >> fundamental operation, either composition or application (or

    >> something else)?

    >>

    >> joy and its descendents satisfy that definition. other languages

    >> can be restricted in various ways to satisfy it.

    >

    > Hi Stevan,

    >

    > This seems more or less like the definition that majority of the group

    > has agreed upon. In your opinion what languages other than Joy does it

    > include?

    just a guess -- billy will correct me if i'm wrong:  the tacit part

    of J (application), point-free haskell, one (or more?) of jot/zot/iota,

    chris okasaki's flattened combinator language, lee spector's PUSH,

    van Oormerssen's False.  i'm still not sure in what sense or under

    what restrictions Forth or Postscript satisfy the definition.  it

    would be good to be able to answer the question "is this language

    concatenative, and if not, why not?"

    >

    > - Christopher

    >

## Christopher Diggins — 2008-02-10 21:48:57

    On Feb 10, 2008 2:23 PM, Stevan Apter <sa@...> wrote:

     > ----- Original Message -----

    > From: "Christopher Diggins" <cdiggins@...>

    > To: <concatenative@yahoogroups.com>

    > Sent: Sunday, February 10, 2008 2:00 PM

    > Subject: Re: [stack] Cat article submission to Doctor Dobbs Journal

    >

    > > On Feb 10, 2008 1:38 PM, Stevan Apter <sa@...> wrote:

    > >> chris:

    > >> > You keep saying concatenative languages, and I am talking about

    > >> > stack-based languages. I am still not sure which languages are

    > >> > technically concatenative (is Forth? is JVML? is PostScript?).

    > >>

    > >> i've been up and down this road so many times i'm giving names to

    > >> the rocks. am i wrong in thinking that the languages we're

    > >> concerned with (in this group) are those in which wholes are built

    > >> from parts by concatenation and where concatenation denotes a

    > >> fundamental operation, either composition or application (or

    > >> something else)?

    > >>

    > >> joy and its descendents satisfy that definition. other languages

    > >> can be restricted in various ways to satisfy it.

    > >

    > > Hi Stevan,

    > >

    > > This seems more or less like the definition that majority of the group

    > > has agreed upon. In your opinion what languages other than Joy does it

    > > include?

    >

    > just a guess -- billy will correct me if i'm wrong: the tacit part

    > of J (application), point-free haskell, one (or more?) of jot/zot/iota,

    > chris okasaki's flattened combinator language, lee spector's PUSH,

    > van Oormerssen's False.

     This is a pretty good list, thank you! You left out XY.

     > i'm still not sure in what sense or under

    > what restrictions Forth or Postscript satisfy the definition.

     Yeah, that's the tricky part. I believe there are valid phrases in

    Forth which can't be concatenated (and/or split) to create other valid

    phrases (e.g. using BRANCH). I don't know about PostScript.

     > it

    > would be good to be able to answer the question "is this language

    > concatenative, and if not, why not?"

     Yes, I agree. Having a laundry list of concatenative languages is a

    good first step though I think. At least we can compare other

    languages to the existing list, and state what the characteristics it

    shares and

    On another topic I was reviewing PostScript and your interview with

    Manfred (thanks for doing that and sharing it by the way, I love

    getting into Manfred's mind) and I found this quote:

    "What distinguishes Joy from (the functional subsets of) Forth and

    Postscript is the datatype of quoted programs". Well in PostScript

    there appears to be quoted programs, they are just called executable

    arrays. However, there are no *literal* quotations. Rather there are

    operators for constructing quoted programs (i.e. "{" and "}"). A

    somewhat pedantic difference but one worth noting I think. I've

    udpated the introduction of my article a bit to reflect this

    observation. Does anyone agree/disagree?

    On another topic I wonder if in PostScript you can write:

    \f { { } def

    \g { } } def

    This would possibly break concatenativity.

    - Christopher

## John Nowak — 2008-02-11 01:40:27

    I'll be quick here, as I haven't the time I wish I had.

    The introduction seems weak. Simplicity doesn't come from a low number

    of concepts. If it did, the SK-calculus would be the language all new

    programmers would be starting with. It seems like offering a hook

    beyond how "simple" it is should be part of your introduction. There

    is the discussion of efficiency, but at least for me, this is one of

    the least interesting parts about Cat. That said, I'm not sure how I'd

    rework this...

     > In the Cat specification instructions are referred to as functions,

    > whether or not they have side-effects.

     Do functions actually have side-effects? If all functions are unary

    functions of stacks to stacks, it's easy to thread an implicit world

    state through the entire program. I believe Backus's FL did something

    similar. As far as I'm concerned, Cat is purely functional. Functions

    of the type A ~> B are  functions that read/write the world state on

    the top of the stack. All other operations work below it.

     > Functions can not be redefined, and are only visible after they are

    > defined.

     Does this mean recursive definitions are disallowed?

     > In Joy parlance this is called a quotation, but I prefer to think of

    > it as either an anonymous function or lambda expression.

     Lambda expression might not be the term to use here as there are no

    variables involved.

     > A possible definition of bin_rec is shown Figure X.

     So bin_rec must be a primitive? If so, that should probably be stated.

    I assume that's the case for reasons related to the type system, as I

    believe you can write it in Joy.

     > For those who like big Greek words

     I don't know who the intended audience of this is (I'm not familiar

    with Doctor Dobbs), but I find this level of informality off-putting.

     > Metadata is a form of structured comment that can be associated with

    > a Cat program. I use it to document functions, and provide automatic

    > unit tests.

     Again, not sure on the audience, but "I use it" as opposed to "Its

    intended use is" strikes me as odd.

     > Static type systems are useful for documentation, static

    > verification of code, and optimization.

     And more!

     > It is common practice in stack languages to document the stack

    > effects of each instruction, i.e. what type of values are remove

    > from the stack (the consumption), and what type of values are placed

    > on the stack (the production).

     That should be 'e.g.', not 'i.e.'.

     > If the type annotation is omitted, Cat is able to infer the type

    > automatically, using a variant of the Hindley-Milner algorithm [X]

     Should be: "If a type annotation is omitted, Cat is able to infer a

    type automatically using a variant of the Hindley-Milner algorithm [X]."

     > Using the Cat interpreter "#t" will give you the type of any

    > function on the stack.

     I don't quite understand this sentence. Perhaps "Using '#t' in the Cat

    interpreter"?

     > The most important properties are: whether the required input types

    > for a function are being supplied when it is called

     Perhaps "values of the correct types" is better.

     > A somewhat novel feature of the Cat type system is that all

    > functions are row polymorphic [ref] (also called tail polymorphic)

     I don't have time to get into this now, but I think there are cases

    when you don't want functions to be row polymorphic. A trivial

    example: Supplying a function that takes two arguments for use in a

    callback. Simply requiring the function to unify with (A b c -> A)

    would be insufficient, as you'd be allowed to pass something like (A b

    c d e -> A b). I've had to introduce an additional concept to my type

    system to address this. First-class stacks (evaluated on via Joy's

    'infra') also seem to require this. I'll post in more detail soon I'm

    sure...

     > define quadratic { [dupd [sqr] dip swap [*] dip] dipd [* +] dip + }

     If you take the arguments in reverse order, as you typically would,

    you can do this:

        2dup [* * swap] dip * + +

     > Now we partially evaluate the "papply" functions:

     Better than 'curry'. :)

    Anyway, I hope something in there helped. Sorry I don't have time for

    a more thorough reading.

    - John

## Christopher Diggins — 2008-02-11 02:04:28

    Hi John,

    Thanks a lot for the comments.

     On Feb 10, 2008 8:40 PM, John Nowak <john@...> wrote:

    > I'll be quick here, as I haven't the time I wish I had.

    Sorry about that.

    > The introduction seems weak. Simplicity doesn't come from a low number

    > of concepts.

    I'm a little confused: a low number of concepts seems to be the very

    definition of simplicity.

    > If it did, the SK-calculus would be the language all new

    > programmers would be starting with.

    You seem to be saying here more that a low number of concepts doesn't

    neccessarily make a language appropriate for beginners. Is this

    correct? If so I do agree with you. The other reason, which I should

    perhaps include is the fact that the model of computation closely

    resembles what actually happens in a computer.

    > It seems like offering a hook

    > beyond how "simple" it is should be part of your introduction.

    Fair enough, I'll see if I can do better.

    > There

    > is the discussion of efficiency, but at least for me, this is one of

    > the least interesting parts about Cat.

    What do you think is the most interesting part of Cat, if any? And I'm

    not just fishing for compliments, honest :-)

    >  That said, I'm not sure how I'd

    > rework this...

    >

    > > In the Cat specification instructions are referred to as functions,

    > > whether or not they have side-effects.

    >

    > Do functions actually have side-effects?

    In Cat they do (according to my definition of function).

    > If all functions are unary

    > functions of stacks to stacks, it's easy to thread an implicit world

    > state through the entire program.

    It's possible, but I wouldn't call it easy. I struggled for a long

    time to figure out how to do it in Cat. Then again "easy" is always

    relative, I'm sure it was easier for you. :-)

    >  I believe Backus's FL did something

    > similar. As far as I'm concerned, Cat is purely functional. Functions

    > of the type A ~> B are functions that read/write the world state on

    > the top of the stack. All other operations work below it.

    >

    > > Functions can not be redefined, and are only visible after they are

    > > defined.

    >

    > Does this mean recursive definitions are disallowed?

    No. I see your point though, it is unclear. Thanks for pointing it out.

    > > In Joy parlance this is called a quotation, but I prefer to think of

    > > it as either an anonymous function or lambda expression.

    >

    > Lambda expression might not be the term to use here as there are no

    > variables involved.

    Good point.

    > > A possible definition of bin_rec is shown Figure X.

    >

    > So bin_rec must be a primitive?

    No, why do you ask? I am intending to show that it can be defined in a

    library, so it doesn't have to be made a primitive.

    I am probably not being clear. The Cat primitive set is somewhat

    arbitrary, different implementations would choose different operations

    to implement as predefined primitives.

    > If so, that should probably be stated.

    > I assume that's the case for reasons related to the type system, as I

    > believe you can write it in Joy.

    Yes you can.

    > > For those who like big Greek words

    >

    > I don't know who the intended audience of this is (I'm not familiar

    > with Doctor Dobbs), but I find this level of informality off-putting.

    I can understand. I was on the fence here, I was just trying to add a

    bit of levity, and to laugh a bit at the tendency of the community to

    overuse greek-like words (I am not convinced that those are real

    words). DDJ is a trade magazine intended for software development

    professionals.

    > > Metadata is a form of structured comment that can be associated with

    > > a Cat program. I use it to document functions, and provide automatic

    > > unit tests.

    >

    > Again, not sure on the audience, but "I use it" as opposed to "Its

    > intended use is" strikes me as odd.

    >

    > > Static type systems are useful for documentation, static

    > > verification of code, and optimization.

    >

    > And more!

    I could use some inspiration here. ;-)

    Any suggestions?

    > > It is common practice in stack languages to document the stack

    > > effects of each instruction, i.e. what type of values are remove

    > > from the stack (the consumption), and what type of values are placed

    > > on the stack (the production).

    >

    > That should be 'e.g.', not 'i.e.'.

    Why is that? I thought it was more of an elaboration than an example.

    > > If the type annotation is omitted, Cat is able to infer the type

    > > automatically, using a variant of the Hindley-Milner algorithm [X]

    >

    > Should be: "If a type annotation is omitted, Cat is able to infer a

    > type automatically using a variant of the Hindley-Milner algorithm [X]."

    Okay.

    > > Using the Cat interpreter "#t" will give you the type of any

    > > function on the stack.

    >

    > I don't quite understand this sentence. Perhaps "Using '#t' in the Cat

    > interpreter"?

    Yes, thanks.

    > > The most important properties are: whether the required input types

    > > for a function are being supplied when it is called

    >

    > Perhaps "values of the correct types" is better.

    Yep,

    > > A somewhat novel feature of the Cat type system is that all

    > > functions are row polymorphic [ref] (also called tail polymorphic)

    >

    > I don't have time to get into this now, but I think there are cases

    > when you don't want functions to be row polymorphic. A trivial

    > example: Supplying a function that takes two arguments for use in a

    > callback. Simply requiring the function to unify with (A b c -> A)

    > would be insufficient, as you'd be allowed to pass something like (A b

    > c d e -> A b).

    This is interesting, I will have to look at the issue carefully before

    I comment on it.

    >  I've had to introduce an additional concept to my type

    > system to address this. First-class stacks (evaluated on via Joy's

    > 'infra') also seem to require this.

    I don't support first-class stacks in Cat.

    > I'll post in more detail soon I'm

    > sure...

    I look forward to it.

    > > define quadratic { [dupd [sqr] dip swap [*] dip] dipd [* +] dip + }

    >

    > If you take the arguments in reverse order, as you typically would,

    > you can do this:

    >

    > 2dup [* * swap] dip * + +

    That is interesting. Personally I wouldn't typically do that, because

    I would like to write things like:

    define quad234 { 2 3 4 quadratic }

    > > Now we partially evaluate the "papply" functions:

    >

    > Better than 'curry'. :)

    :-)

    I can't help but think that maybe "partial curry" would be a more

    accurate term, but history wins here.

    > Anyway, I hope something in there helped. Sorry I don't have time for

    > a more thorough reading.

    >

    > - John

    I really appreciate your comments, thanks a lot!

    - Christopher

## John Nowak — 2008-02-11 02:44:20

    On Feb 10, 2008, at 9:04 PM, Christopher Diggins wrote:

     > I'm a little confused: a low number of concepts seems to be the very

    > definition of simplicity.

     What I mean to say is that a language with a few, simple concepts can

    have unavoidably complex implications. The language I typically cite

    here is Io; you can understand the concepts in about five minutes, but

    after a year of poking at it, it still surprises me in horrible ways.

    I'm not suggesting Cat does the same of course, but I am suggesting

    that simplicity requires more than just a small number of components;

    it requires their interaction to be simple as well.

     > What do you think is the most interesting part of Cat, if any? And I'm

    > not just fishing for compliments, honest :-)

     Simplicity! But simplicity in how one can reason about a program, not

    just in a superficial count of lines in the manual. Cat also has the

    potential to be a very expressive language. After dealing with Joy for

    any period of time, I find returning to Scheme (or even Haskell) quite

    painful. In your paper, you tend to make Cat look like a verbose

    language (with the exception of the qsort example perhaps). Maybe it

    would be possible to give an example of something more painful in

    another language? Something that really makes use of multiple return

    values?

    I don't really disagree with your assessment of Cat's benefits.

    Perhaps I'd just like a stronger argument.

     >> If all functions are unary

    >> functions of stacks to stacks, it's easy to thread an implicit world

    >> state through the entire program.

    >

    > It's possible, but I wouldn't call it easy. I struggled for a long

    > time to figure out how to do it in Cat. Then again "easy" is always

    > relative, I'm sure it was easier for you. :-)

     Well, when I say "implicit", you don't actually have to thread

    anything. It's just a matter of how you conceptualize it. For example,

    you could technically give the types of functions as such:

         dip   :: 'A 'b ('A World -> 'B World) World -> 'B World

         swap  :: 'A 'b 'c World -> 'A 'b 'c World

         print :: 'A String World ~> A World

     >> So bin_rec must be a primitive?

    >

    > No, why do you ask?

     I was reading quickly, saw the "define bin_rec(a, b, c)", and thought

    it was pseudocode for some other language. Ooops. Forgot Cat can do

    that...

     >>> Static type systems are useful for documentation, static

    >>> verification of code, and optimization.

    >>

    >> And more!

    >

    > I could use some inspiration here. ;-)

    > Any suggestions?

     Safe refactoring and better/easier tool support might be benefits that

    software development professionals would react positively to.

     >>> That should be 'e.g.', not 'i.e.'.

    >

    > Why is that? I thought it was more of an elaboration than an example.

     You're right -- I was reading too quickly.

     >>> A somewhat novel feature of the Cat type system is that all

    >>> functions are row polymorphic [ref] (also called tail polymorphic)

    >>

    >> I don't have time to get into this now, but I think there are cases

    >> when you don't want functions to be row polymorphic. A trivial

    >> example: Supplying a function that takes two arguments for use in a

    >> callback. Simply requiring the function to unify with (A b c -> A)

    >> would be insufficient, as you'd be allowed to pass something like

    >> (A b

    >> c d e -> A b).

    >

    > This is interesting, I will have to look at the issue carefully before

    > I comment on it.

     Quick example, where {} represents a stack (and I get sick of writing

    '):

         infra   :: A {B} (B -> C) -> A {C}

         push    :: A {B} c -> A {B c}

         null    :: A -> A [b]

         nullstk :: A -> A {B} # this is wrong

         # Then, at the start of your program, this gets assigned the type

         # A -> A {B int}

         nullstk 5 push [+] infra

    But of course that's wrong and will underflow! The problem is that

    there's no way to give the correct type for "nullstk" without some way

    of representing the "bottom" of a stack. You don't need to do this for

    lists (null :: A -> A [b]) because taking the head of a null list is a

    runtime error. Here, however, you get a stack underflow. I hope that

    makes some sense...

    The solution is relatively easy: Introduce an "empty" vector type.

    Unifying "_ a" and "B int" yields "_ int" as "_" gets unified with

    "B". You then need to make it illegal to unify anything but a vector

    with an empty vector. For example, you can't unify "_ a" and "B int

    int" because you can't unify "_" with "B int". Again, as I've been

    promising, I'll post an example inference algorithm any day now...

     > I don't support first-class stacks in Cat.

     Even if you don't support them, you can use the above typing scheme to

    avoid having to special-case the "main" function requiring to work on

    an empty stack. Instead of typing the program starting with a function

    of "A -> A", you start with the function "_ -> A". The introduction of

    "_" just for this purpose though probably isn't useful enough to

    warrant it.

    - John

## John Nowak — 2008-02-11 02:53:56

    Briefly, just to give the correct types for functions involving first-

    class stacks:

         infra   :: A {B} (B -> C) -> A {C}

         push    :: A c {B} -> A {B c}

         pull    :: A {B c} -> A c {B}

         nullstk :: A -> A {_}

         stack   :: A -> A {A}

         unstack :: A {B} -> B

         swapstk :: A {B} -> B {A}

    swapstk can be defined in terms of the other functions.

    - John

## Christopher Diggins — 2008-02-11 03:27:13

    On Feb 10, 2008 9:44 PM, John Nowak <john@...> wrote:

     > On Feb 10, 2008, at 9:04 PM, Christopher Diggins wrote:

    >

    > > I'm a little confused: a low number of concepts seems to be the very

    > > definition of simplicity.

    >

    > What I mean to say is that a language with a few, simple concepts can

    > have unavoidably complex implications.

     That is a very lucid point.

     > Simplicity! But simplicity in how one can reason about a program, not

    > just in a superficial count of lines in the manual. Cat also has the

    > potential to be a very expressive language. After dealing with Joy for

    > any period of time, I find returning to Scheme (or even Haskell) quite

    > painful. In your paper, you tend to make Cat look like a verbose

    > language (with the exception of the qsort example perhaps).

     Good point.

     > Maybe it

    > would be possible to give an example of something more painful in

    > another language? Something that really makes use of multiple return

    > values?

     My classic example is "mapreduce". Perhaps I will throw it in.

     > I don't really disagree with your assessment of Cat's benefits.

    > Perhaps I'd just like a stronger argument.

     I understand.

     > Well, when I say "implicit", you don't actually have to thread

    > anything. It's just a matter of how you conceptualize it. For example,

    > you could technically give the types of functions as such:

    >

    > dip :: 'A 'b ('A World -> 'B World) World -> 'B World

    > swap :: 'A 'b 'c World -> 'A 'b 'c World

    > print :: 'A String World ~> A World

     I am not sure what this means though, and what the type inference

    rules are. I just don't feel that by saying instructions pass the

    world makes a language pure. I don't have the capacity at this point

    to reason about it formally though.

     > >> So bin_rec must be a primitive?

    > >

    > > No, why do you ask?

    >

    > I was reading quickly, saw the "define bin_rec(a, b, c)", and thought

    > it was pseudocode for some other language. Ooops. Forgot Cat can do

    > that...

     Yeah, it gets translated by a pre-processor into regular ole

    concatenative code.

     >

    > >>> Static type systems are useful for documentation, static

    > >>> verification of code, and optimization.

    > >>

    > >> And more!

    > >

    > > I could use some inspiration here. ;-)

    > > Any suggestions?

    >

    > Safe refactoring and better/easier tool support might be benefits that

    > software development professionals would react positively to.

     Good point.

     > >>> That should be 'e.g.', not 'i.e.'.

    > >

    > > Why is that? I thought it was more of an elaboration than an example.

    >

    > You're right -- I was reading too quickly.

    >

    > >>> A somewhat novel feature of the Cat type system is that all

    > >>> functions are row polymorphic [ref] (also called tail polymorphic)

    > >>

    > >> I don't have time to get into this now, but I think there are cases

    > >> when you don't want functions to be row polymorphic. A trivial

    > >> example: Supplying a function that takes two arguments for use in a

    > >> callback. Simply requiring the function to unify with (A b c -> A)

    > >> would be insufficient, as you'd be allowed to pass something like

    > >> (A b

    > >> c d e -> A b).

    > >

    > > This is interesting, I will have to look at the issue carefully before

    > > I comment on it.

    >

    > Quick example, where {} represents a stack (and I get sick of writing

    > '):

    >

    > infra :: A {B} (B -> C) -> A {C}

    > push :: A {B} c -> A {B c}

    > null :: A -> A [b]

    > nullstk :: A -> A {B} # this is wrong

    >

    > # Then, at the start of your program, this gets assigned the type

    > # A -> A {B int}

    > nullstk 5 push [+] infra

    >

    > But of course that's wrong and will underflow! The problem is that

    > there's no way to give the correct type for "nullstk" without some way

    > of representing the "bottom" of a stack. You don't need to do this for

    > lists (null :: A -> A [b]) because taking the head of a null list is a

    > runtime error. Here, however, you get a stack underflow. I hope that

    > makes some sense...

     Sure, but I suspect that this is only an artefact of allowing infra

    and first class stacks. Do you have an example of it causing a problem

    outside of those cases?

     > The solution is relatively easy: Introduce an "empty" vector type.

    > Unifying "_ a" and "B int" yields "_ int" as "_" gets unified with

    > "B". You then need to make it illegal to unify anything but a vector

    > with an empty vector. For example, you can't unify "_ a" and "B int

    > int" because you can't unify "_" with "B int". Again, as I've been

    > promising, I'll post an example inference algorithm any day now...

     I look forward to it. Any day now I will post mine as well. :-)

     > > I don't support first-class stacks in Cat.

    >

    > Even if you don't support them, you can use the above typing scheme to

    > avoid having to special-case the "main" function requiring to work on

    > an empty stack.

     I will look into possibly extending the Cat type system as a result.

    Thanks for the ideas!

     > Instead of typing the program starting with a function

    > of "A -> A", you start with the function "_ -> A". The introduction of

    > "_" just for this purpose though probably isn't useful enough to

    > warrant it.

     Having "infra" or something similar would be a very nice addition.

    Cheers,

    Christopher

## John Nowak — 2008-02-11 04:14:01

    On Feb 10, 2008, at 10:27 PM, Christopher Diggins wrote:

     >> dip :: 'A 'b ('A World -> 'B World) World -> 'B World

    >> swap :: 'A 'b 'c World -> 'A 'b 'c World

    >> print :: 'A String World ~> A World

    >

    > I am not sure what this means though, and what the type inference

    > rules are.

     World is just an atomic type like Int. What it means, in the case of

    dip, is that the function on top of the stack is called with the

    current world and yields a new world which is seen in the production

    of dip. Something like this:

         dip :: 'A 'b ('A World/1 -> 'B World/2) World/1 -> 'B World/2

     > I just don't feel that by saying instructions pass the

    > world makes a language pure.

     You may want to read this paper on FL and how "history" is handled

    implicitly (section 2.5):

    http://www.cs.berkeley.edu/~aiken/ftp/FL.ps

    This passing around of the world is also used in Clean. However,

    unlike Clean, Cat (and Joy, etc) do not need any notion of uniqueness

    types to do similarly since all functions are already monadic. Yes, it

    may seem like cheating because it's so easy, but that doesn't mean it

    isn't the case!

    This same monadic nature is what allows Cat to be linear without the

    explicit management seen in Baker's "Linear Lisp" papers. You can even

    do away with garbage collection entirely if you have properly designed

    primitive data types. I consider the monadic nature of compositional

    languages to be a huge advantage, and perhaps in some future paper,

    you could include more about this. I plan on tackling this in a few

    months when I'll need to submit something as well.

     > Sure, but I suspect that this is only an artefact of allowing infra

    > and first class stacks. Do you have an example of it causing a problem

    > outside of those cases?

     You are correct: It only causes problems when dealing with first-class

    stacks. Provided that you don't have first-class stacks and do have a

    special check that the "main" function of a program does not require

    any values to be on the stack, you don't need any additional type

    system features. I believe Cat already performs this "main" check.

    - John

## Joe Bowbeer — 2008-02-11 20:10:10

    On Feb 10, 2008 8:14 PM, John Nowak wrote:

     >

    > You may want to read this paper on FL and how "history" is handled

    > implicitly (section 2.5):

    > http://www.cs.berkeley.edu/~aiken/ftp/FL.ps

    >

     Here's a PDF:

      http://theory.stanford.edu/~aiken/publications/trs/FLProject.pdf

    at Aiken's new location:

      http://theory.stanford.edu/~aiken/publications/publications.html

## William Tanksley, Jr — 2008-02-27 04:08:28

    Stevan Apter <sa@...> wrote:

     >  From: "Christopher Diggins" <cdiggins@...>

    >  >> > You keep saying concatenative languages, and I am talking about

    >  >> > stack-based languages. I am still not sure which languages are

    >  >> > technically concatenative (is Forth? is JVML? is PostScript?).

    >  >> i've been up and down this road so many times i'm giving names to

    >  >> the rocks. am i wrong in thinking that the languages we're

    >  >> concerned with (in this group) are those in which wholes are built

    >  >> from parts by concatenation and where concatenation denotes a

    >  >> fundamental operation, either composition or application (or

    >  >> something else)?

    >  >> joy and its descendents satisfy that definition. other languages

    >  >> can be restricted in various ways to satisfy it.

    >  > This seems more or less like the definition that majority of the group

    >  > has agreed upon. In your opinion what languages other than Joy does it

    >  > include?

     It's close. I think our last discussion fruitfully concluded that a

    concatenative language:

    1. Syntactically is concatenated from a set of primitives;

    2. Semantically maps concatenation to an associative operation.

    I'm not certain whether we MUST make function composition the only

    associative operation; I'm also not certain that it's strictly

    necessary to specify the semantic mapping (because concatenation is

    itself associative), but I like having it explicit, because it makes

    it clear that the semantics and the syntax have the same property

    (associativity). There's a beautiful symmetry there... Beauty is

    truth, and truth beauty.

    Application doesn't work because it's not associative.

     >  just a guess -- billy will correct me if i'm wrong:  the tacit part

    >  of J (application), point-free haskell, one (or more?) of jot/zot/iota,

    >  chris okasaki's flattened combinator language, lee spector's PUSH,

    >  van Oormerssen's False.

     Most of these don't meet that definition, I think. I still haven't

    figured out jot, zot, and iota... I'd like to know whether they're

    concatenative.

     >  i'm still not sure in what sense or under

    >  what restrictions Forth or Postscript satisfy the definition.  it

    >  would be good to be able to answer the question "is this language

    >  concatenative, and if not, why not?"

     I think the recent consensus gives a clear test. I can't answer for

    jot etc because I can't read their notation.

    -Wm

## William Tanksley, Jr — 2008-02-27 04:14:31

    Christopher Diggins <cdiggins@...> wrote:

     > Stevan Apter <sa@...> wrote:

    >  > i'm still not sure in what sense or under

    >  > what restrictions Forth or Postscript satisfy the definition.

    >  Yeah, that's the tricky part. I believe there are valid phrases in

    >  Forth which can't be concatenated (and/or split) to create other valid

    >  phrases (e.g. using BRANCH). I don't know about PostScript.

     By my old definition, Forth is entirely concatenative and mostly flat.

    By the new definition, Forth does have a concatenative sublanguage

    which contains most of Forth. (The new definition doesn't need to

    worry about "flat", which IMO is a good thing.)

     >  arrays. However, there are no *literal* quotations. Rather there are

    >  operators for constructing quoted programs (i.e. "{" and "}"). A

    >  somewhat pedantic difference but one worth noting I think.

     I didn't know that!

    Does that mean that Postscript quotations can't nest?

     >  On another topic I wonder if in PostScript you can write:

    >  \f { { } def

    >  \g { } } def

    >  This would possibly break concatenativity.

     I don't see why.

     >  - Christopher

     -Wm