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

On Feb 10, 2008 9:44 PM, John Nowak <[email protected]> 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