On 03/01/2011, at 1:05 AM, john skaller wrote:
> I typed up this little example for a tutorial:
>
I have now made a change to overload resolution so it tries to find a
function type in the bound symbol table first, before using the unbound symbol
table and then binding the result.
This is a small performance optimisation, it won't always work. As a result this
works:
//////////////////////
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
;
proc testit() {
var x = 1.0,2.0,2.5,3.0;
println$ "The squares of " + str x " are" +
catmap " " (fun (x:double)=> x * x) x
;
}
testit;
/////////////
which it didn't before, because it happens catmap is already bound when it is
called,
and so the real return type is found. But this does not work:
///////////////////////
proc testit() {
var x = 1.0,2.0,2.5,3.0;
println$ "The squares of " + str x " are" +
catmap " " (fun (x:double)=> x * x) x
;
}
testit;
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
;
/////////////
for the simple reason that testit() is bound first (well, there's an attempt
to bind it, which fails).
in general, the return type still has to be declared, which is no good.
In particular, it will never work for a multi-argument recursive function,
because it can't possibly be bound before it is called, since binding
it requires overload resolution on the recursive call.
Until I fix this properly the rule is: declare return types! In particular for
multi-argument functions.
Note that for one argument recursive functions it doesn't matter because
overload
resolution doesn't need to know the return type: it's only required for multiple
arguments.
The fix I was thinking of probably won't work anyhow: the do_unify routine
doesn't actually
need to check if a type variable index is equal to a function index to determine
its an unbound type variable: it's enough to check if the variable is in the
symbol
table: all bound variables get put in the symbol table. Unbound variables don't.
So all I would need to do is a small change to do_unify, then I can fix desugar
to make it introduce fresh indices for the type variables.
For multi-argument functions the inner most function gets a type variable,
but the enclosing functions have return types using that type variable.
The problem is, the resulting types are still wrong for overloading, even though
the inner most return type is not used, until the unbound variable is replaced
by
the computed return value. Dang! At least I didn't do it :)
In fact, I was wrong in my previous post: overload resolution doesn't need to
recurse.
That's what causes the actual problem: the return type of a function is always
available, even if it is the unbound type variable (if it had recursed, the
problem would
not have occurred: recursion is only blocked when the type recurses and in the
example "catmap" isn't recursive!)
I'm not sure of the fix now: for non-recursive functions it's possible if you
can
force a suitable binding order, but there may not be one: remember, a function
doesn't depend on just one other function, it may call lots of them, so it only
needs some recursion to stop a linear ordering, not necessarily recursion
on the problem call.
Note that recursion doesn't stop types being bound: Felix not only knows how
to bind types with recursive calls, it knows how to bind recursive types.
It doesn't do this in overloading directly simply because keeping track
of when to intoduce a fixpoint binder into a type is quite tricky and already
done in bind type (which may call overload resolution: however in this
case overloading is allowed to fail provided *one* branch of a conditional
binds correctly. And even that isn't necessary if the return type is declared.
The bottom line is that Felix requires you to declare the return types of
functions, but this implementation lets you leave them off *sometimes*
in a way that is not entirely predictable. It can be fixed but it turns out
to be less simple than I thought.
--
john skaller
[email protected]
------------------------------------------------------------------------------
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
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
