Re: [stack] typing higher-order concatenative languages with standard hindley-milner

On May 31, 2008, at 1:28 AM, John Nowak wrote:

> In short, it seems standard Hindley-Milner alone is enough to do
> everything we want! As a downside, we need several versions of fixed-
> arity higher order combinators like 'dip' and 'i'. This is not a
> problem as the general versions can be used in cases where there's no
> need for fixed arities (i.e. most of them). This gives us a
> concatenative language that's truly useful and never requires type
> annotations.

Well, as we're seeing already, perhaps not. In particular, row  
variables may be required to handle recursive definitions properly.  
(Okasaki's paper does give a solution to this problem, but it's  
nothing you want to use. Perhaps there's a nice way of hiding it.)

In either case, there's a trivial restriction to allow a language with  
row variables and non-row polymorphic functions to have principal  
types. You simply disallow the unification of a row variable with a  
vector greater than length zero that is not also row polymorphic. In  
other words, you could restrict the type of (A -> B) to ( -> ), but  
not (a -> b c) or (b -> ). As such, the principal types property of HM  
is nothing to be excited about here. (I apologize for, on occasion,  
being easily excitable.) It is rather interesting though how close we  
can get in Haskell.

- John