Cat article submission to Doctor Dobbs Journal

[Christopher Diggins]

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]

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

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]

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]

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]

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]

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]

----- Original Message -----
From: "Christopher Diggins" <cdiggins@...>
To: <concatenative@...>
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]

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

> ----- Original Message -----
> From: "Christopher Diggins" <cdiggins@...>
> To: <concatenative@...>
> 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]

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]

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]

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]

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]

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