Re: [stack] stackless fixed-arity concatenative languages

On May 20, 2008, at 7:17 PM, William Tanksley, Jr wrote:

>>> At this point, it would seem convenient to add some syntax for
>>> staticly-known (and required) parameters. Perhaps (i 4 4) would be  
>>> an
>>> example of such syntax.
>>
>> it would be rather annoying to have to do '[+] (dip 2 1)' instead.
>
> Agreed; this should tie in with type inference and annotation. This
> stack effect notation is really an abbreviated form of type notation
> and static polymorphism / function overloading, so perhaps it should
> be clearly annotated as such (rather than simply looking like a macro,
> as I suggested).

It seems to me that the way to handle this is to simply require a  
normal type annotation that provides enough information to figure  
these things out. There is a simple rule for determining if all  
arities for all function instances within a function are known by  
looking at the row variables, so this wouldn't introduce too much  
complication. The rule is that the row variable for the outermost  
function must be the same in the consumption and production. (There  
are ways to break this with stack-saving/restoring primitives, so  
they'd need to be special forms if they were to exist at all.) In  
other words, 'A (B -> C) d -> A d (B -> C)' is fine, but 'A (A -> B) d  
-> B d' isn't.

Specifying arities directly seems like it would be too much of a pain.  
The reason is that I use normal functions to deconstruct sum types  
where each quotation provided to the function indicates what to do if  
the sum type was constructed via a particular constructor. It would be  
way too inconvenient to have to specify arities for all of these.  
They'd also no longer be "normal functions" if they somehow were  
allowed to get around the arity rule. This applies to something like  
'dip' as well. If you require all user-written functions to have a  
fixed arity, something harmless like 'foo = dip' would not be valid.

It seems what is required is two classes of functions, ones with fixed  
arities and ones without. For functions with known arities, you could  
do something like '(define foo [+] dip)'. For functions without known  
arities, you could do something like '(define-nary bar [dip] dip)'.  
Functions that are defined as n-ary functions would act like macros;  
code would not be generated for them until they are instantiated in  
such a way that the arity is known for that particular instance. This  
seems like a reasonable requirement, makes rules for separate  
compilation simple, and encourages fixed arity functions while  
allowing n-ary functions where necessary.

>> You could then do something like '(dip-with +)'. This way,
>> it is at least clear that you can't split between '+' and 'dip-with'.
>
> For that to work consistently, the type system would have to produce
> an error whenever annotation was missing, even if the inference could
> theoretically be made.

Yes, this is the general problem with ensuring that you can break  
functions apart: You either deal with unnecessary restrictions or  
resort to some form of whole program analysis. The type system I'm  
working on now is essentially a clever way of doing whole program  
analysis by delaying certain things when doing local inference, but it  
doesn't interact well with type annotations which will be necessary  
for restricting n-ary functions to fixed arities so that code can be  
generated for them when doing separate compilation.

I'm possibly just talking to myself at this point, but it seems like I  
should just give up on the idea of preserving cut-and-paste factoring  
in all cases, use a simpler yet highly expressive type system that  
occasionally requires annotations like Leijen's HMF or HML, drop  
macros (since we have no binding forms to deal with, we have a  
lightweight syntax for quotations, we don't build abstractions around  
things like SET!, postfix syntax is already quite good for DSLs, etc),  
and just get on with writing an implementation already.

- John

P.S. Apologies if this message ends up on the list twice. My first  
attempt was rejected.