<div dir="ltr"><div>I thought about dynamic dispatch too.  I don't think it's any more powerful than static dispatch unless you want to dispatch based on subtype, e.g. if you have type T2 that's derived from T1 and you have overloaded f(T1) and f(T2).  You can implement static dispatch at runtime by emitting the type information from the compiler and having a series of conditionals that look at the type information <br><br></div><div>I avoided implementing Swift functions with type variable arguments for that reason.  I agree you end up needing something like SML's constraints or Haskells typeclasses to write useful code.  Well.. unless you do it the C++ templates way and just try substituting the types and see what happens.<br><br></div><div>The type inference might not be too bad...  the way STC handles it is in a two phase way where full type information propagates up the tree, and then evaluation propagates down.  When propagating up, we can have non-concrete types like option types and wildcard types.  When evaluating, we need to narrow those to a concrete type based on context (or picking the first valid option if multiple are valid).<br><br></div><div>Concretely, what happens currently when typechecking a function in STC:<br></div><div>1. Work out the type of the input argument expression.  This is an option type T1|T2|T3|etc.  Each of the options can include wildcard types.  E.g. the type of [1] is (int[] | float[]) and the type of [] is (*[]).<br></div><div>2. Find the function type, and the type of the input argument at that position<br></div><div>3. Match up the argument expression type with the argument type, and record any type variables bound during matching.  (NOTE: some things not supported, like combining option types and type variables because that causes problems at this step)<br></div><div>4. Once we've done that for all input arguments, try to unify them if there were multiple bindings for a type variable (NOTE: only do this for option types, but could do for subtypes too)<br></div><div>5. If there was no way to unify type variable bindings, typechecking fails<br></div><div>6.  Enumerate all possible function types that could arise from selecting a type variable binding compatible with the input types.<br></div><div>7. The output argument types of these possible function types give the types for the function expression, e.g. (T0, T1) | (T2, T3) | (T4, T5)<br></div><div>8. When it comes time to evaluate the function call, one of these alternatives is selected based on context (e.g. it the possible types are float | int and the function is in an expression context where we need a float).<br></div><div>9. Any type variables constrained by output argument types are bound if needed. Any unconstrained type variables are bound to void<br><br></div><div>I think having input argument expressions with type variables doesn't greatly affect the process so long as you're not trying to do function-level type inference (e.g. inferring constraints on function arguments based on how they're used in the function) - it's just another case to consider in step 3.  Also it would need to carefully disambiguate type variables with the same name from the function you're in versus the function you're calling.<br><br></div><div>I think overloading, if an overloaded function is an argument, can be handled at steps 1. and 8. by representing the overload as an option type, then selecting the implementation based on which option is chosen.<br><br>Calling an overloaded function would probably just require trial-and-error of going through each overload, then selecting the one that fits.<br><br></div><div>So I guess, start with #3, but #4 might be a reasonable extension.<br></div><div><br></div><div>- Tim<br></div><br><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jan 28, 2015 at 6:04 PM, Mihael Hategan <span dir="ltr"><<a href="mailto:hategan@mcs.anl.gov" target="_blank">hategan@mcs.anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I personally didn't think that we would implement them (fn pointers and<br>
lambdas) separately. That was based on them being morally connected, but<br>
they are quite different in terms of implementation.<br>
<br>
My problem with my solution is that, while min(x, y) will remain nice,<br>
any use of min as a function pointer will actually require what is<br>
equivalent to having minFloat/minInt. whether by lambdas or by actually<br>
writing a minFloat/minInt.<br>
<br>
I think this has to be the cost. As before with overloading/keyword<br>
args, the language gains both abilities in general, with none of the<br>
corner case affecting anything that could have been done before cleanly.<br>
We could maybe improve things later by adding a terse casting operator.<br>
<br>
I don't think type inference (#5) will be simple if we support<br>
universally quantified types.<br>
<br>
f(T[] a, (T[] -> T) g) {<br>
  g(a);<br>
}<br>
<br>
f(a, min)<br>
<br>
You would basically end up with a constraint system similar to SML's.<br>
It's doable, but there are lots of moving parts.<br>
<br>
So I think ultimately #3 might be the reasonable choice.<br>
<br>
I would also add #6, which would be to do dynamic dispatch in cases<br>
where full static resolution fails. It probably comes with a can of<br>
worms if its own.<br>
<span class="HOEnZb"><font color="#888888"><br>
Mihael<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
On Wed, 2015-01-28 at 16:24 -0600, Tim Armstrong wrote:<br>
> I think lambdas are a nice orthogonal way to solve it here, but yeah, I<br>
> don't think they're in the plans in the immediate future.<br>
><br>
> - Tim<br>
><br>
> On Wed, Jan 28, 2015 at 2:39 PM, Mihael Hategan <<a href="mailto:hategan@mcs.anl.gov">hategan@mcs.anl.gov</a>> wrote:<br>
><br>
> > Which ultimately isn't much different from having to do:<br>
> ><br>
> > (float x) minFloat(float[] a) {<br>
> >   x = min(a);<br>
> > }<br>
> ><br>
> > reduce(a, minFloat);<br>
> ><br>
> > So maybe that isn't much progress.<br>
> ><br>
> > Mihael<br>
> ><br>
> > On Wed, 2015-01-28 at 12:23 -0800, Mihael Hategan wrote:<br>
> > > Here's another idea. If we do support lambda expressions, then:<br>
> > ><br>
> > > - a direct reference to an overloaded function when no parameter type is<br>
> > > available should result in an ambiguity error<br>
> > > - a user can resolve the issue by writing an explicit lambda expression<br>
> > > which calls the overloaded function, but this time with normal parameter<br>
> > > type information available<br>
> > ><br>
> > > E.g:<br>
> > ><br>
> > > min = reduce(a, min); // error<br>
> > > min = reduce(a, lambda(float x) { return min(x); });<br>
> > ><br>
> > > This requires no specialized casting mechanism. Of course, if lambda<br>
> > > expressions weren't in the plans, this might be more work.<br>
> > ><br>
> > > Mihael<br>
> > ><br>
> > > On Tue, 2015-01-27 at 21:42 -0600, Tim Armstrong wrote:<br>
> > > > Hi All,<br>
> > > >   I was just starting to look at implementing the function overloading<br>
> > > > support required by the current design of the standard library.  I've<br>
> > just<br>
> > > > realised some of the complications and wanted to reassess the current<br>
> > > > design.<br>
> > > ><br>
> > > > .As soon as I looked at the changes needed, it was obvious that it<br>
> > > > interacts with function references in ways that are probably<br>
> > undesirable.<br>
> > > > The issue is that a function name maps to more than one function, and<br>
> > the<br>
> > > > compiler needs to be able to disambiguate wherever it is used: in a<br>
> > > > variable context as well as a function call context.<br>
> > > ><br>
> > > > For example, suppose we wanted to provide a reduce function with type<br>
> > > > reduce(T, T[], (T) f (T, T)).  It seems reasonable that we'd want to be<br>
> > > > able to write:<br>
> > > ><br>
> > > > reduce(0, [1, 10, 3, 4], max)<br>
> > > ><br>
> > > > But if max is overloaded, then we have to be able to infer from the<br>
> > type of<br>
> > > > the first and second arguments which max was meant.<br>
> > > ><br>
> > > > As an aside, there's a further level of difficulty in resolving things<br>
> > > > correctly if you consider that overloaded functions can take overloaded<br>
> > > > functions as arguments<br>
> > > ><br>
> > > > There seems to be a number of ways to get around this problem:<br>
> > > > 1. Don't support overloading at all, save complications at the expense<br>
> > of<br>
> > > > longer function names<br>
> > > > 2. Don't plan on supporting function references at all<br>
> > > > 3. Ban using overloaded functions as first-class functions, force<br>
> > users to<br>
> > > > work around it.<br>
> > > > 4. Attempt to do some basic type inference to disambiguate, give up if<br>
> > we<br>
> > > > can't disambiguate from local information. (C++ approach, essentially)<br>
> > > > 5. Full program-wide type inference (Haskell approach)<br>
> > > ><br>
> > > > #2 doesn't fit with overall plans for the project, I don't think. #3<br>
> > seems<br>
> > > > pretty unsatisfying and I think we're best to avoid bad programmer<br>
> > > > experiences when we have a cleanish slate to work from.   #5 doesn't<br>
> > seem<br>
> > > > feasible without major changes to language and compiler.<br>
> > > > This leaves #1 and #4.  I think I could make #4 work in Swift/T, but it<br>
> > > > would be days of work and getting all the corner cases may be a<br>
> > challenge -<br>
> > > > realistically I might just not get it done.  I have no idea how<br>
> > feasible #4<br>
> > > > is in Swift/K. #1 seems like the best effort to reward ratio to me.<br>
> > > ><br>
> > > > Anyway, that was a bunch of detail - does anyone have any thoughts or<br>
> > > > opinions?  Have I missed anything?<br>
> > > ><br>
> > > > I'm already assuming that we just shouldn't support overloading<br>
> > functions<br>
> > > > with any other kind of polymorphic arguments - it's not really<br>
> > necessary<br>
> > > > and too complicated to implement<br>
> > > ><br>
> > > > - Tim<br>
> > > > _______________________________________________<br>
> > > > Swift-devel mailing list<br>
> > > > <a href="mailto:Swift-devel@ci.uchicago.edu">Swift-devel@ci.uchicago.edu</a><br>
> > > > <a href="https://lists.ci.uchicago.edu/cgi-bin/mailman/listinfo/swift-devel" target="_blank">https://lists.ci.uchicago.edu/cgi-bin/mailman/listinfo/swift-devel</a><br>
> > ><br>
> > ><br>
> > > _______________________________________________<br>
> > > Swift-devel mailing list<br>
> > > <a href="mailto:Swift-devel@ci.uchicago.edu">Swift-devel@ci.uchicago.edu</a><br>
> > > <a href="https://lists.ci.uchicago.edu/cgi-bin/mailman/listinfo/swift-devel" target="_blank">https://lists.ci.uchicago.edu/cgi-bin/mailman/listinfo/swift-devel</a><br>
> ><br>
> ><br>
> ><br>
<br>
<br>
</div></div></blockquote></div><br></div>