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

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