I typed up this little example for a tutorial: ///////////////// fun catmap[T,N with Str[T]] (sep:string) (f:T -> T) (x:array[T,N]) => fold_left (fun (acc:string) (x:T) => acc+sep+str (f x)) "" x ;
var x = 1.0,2.0,2.5,3.0; println$ "The squares of " + str x " are" + catmap " " (fun (x:double)=> x * x) x ; //////////// and was a bit annoyed when it didn't work. After some debugging I found the problem. If I do this instead: fun catmap[T,N with Str[T]] (sep:string) (f:T -> T) (x:array[T,N]) : string => it works fine. The problem is that when the return type of a function isn't known, it is initially set to TYP_none. When the function is added to the symbol table, if the return type is TYP_none it is replaced by TYP_var i where i is the table index of the function. When we look at some type with type variables in it, we can tell if they're bound variables (vars of the enclosing function) or these special unbound variables, by simply looking up the index to see if it is a function. Felix actually does genuine Hindley-Milner style type inference for these type variables (its the only part of Felix that uses general inference: the rest of the system only permits bottom-up inference, which I call deduction). There is a special routine which stores discovered values of these variables in a global cache. It only caches variables whose index is the same as a function. It's basically a trick to save another term type or symbol table entry. The problem is that when you write a function like catmap above, it is desugared into a function which returns a function which returns a function, and they all get return type TYP_none and then later their own type variables. Now, when overload resolution sees catmap: string -> Ti it can't unify that with the arguments in the program above which are string -> (double -> double) -> array[double,4] to discover T=double and N=4. The type variable is always replaced in the bound symbol table, but overloading uses unbound symbols. What should happen is this: fun catmap[T,N with Str[T]] (sep:string) (f:T -> T) (x:array[T,N]) : Ti => where i is the index of the inner most function being returned, but the problem is the currying routine which deconstructs the multi-argument function in to nested single argument functions is done at desugaring time before there actually is an assigned index, so it just puts TYP_none for all the nested functions. If it put TYP_none only on the inner function and calculated the partially complete return types for the others, there's be no way to tell where the nested TYP_none came from: string -> (T->T) -> TYP_none has to be replaced later by string -> (T -> T) -> Ti where i is the index of the inner function, but there's no way to know this on seeing the first formula. If the return type is just plan TYP_none we know it because we're examining the function going into slot i of the symbol table "right now". To fix this: if I put some type variable in right away instead of TYP_none, during desugaring, I need to maintain a list of these type variables so it is possible to tell if they're bound or not. Another way is to use a new term like: TYP_unknown i However this is not so simple, because now unification has to handle two kinds of type variables instead of just one. Keeping the old system, overloading might work if the type variables were already calculated. For example if we have: T9 = string T8 = array[T,N] -> T8 T7 = (T -> T) -> T8 T6 = string -> T7 then we can resolve T9, and this actually happens now. But if T9 isn't known yet, we'd just get: T6 = string -> (T -> T) -> array[T,N] T9 but that's quite good enough for overload resolution when it is checking multiple arguments: it doesn't care about the final return type in the chain, only the signature of the top level function, which is catmap of (string -> (T->T) -> array[T,N] and now overload resolution would find T and N and be able to do a match. The reason it works when we specify the return type is "string" is that then the desugaring routine specifies all the return types without any TYP_none. A curious problem! -- john skaller skal...@users.sourceforge.net ------------------------------------------------------------------------------ Learn how Oracle Real Application Clusters (RAC) One Node allows customers to consolidate database storage, standardize their database environment, and, should the need arise, upgrade to a full multi-node Oracle RAC database without downtime or disruption http://p.sf.net/sfu/oracle-sfdevnl _______________________________________________ Felix-language mailing list Felix-language@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/felix-language
