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

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