[Swift-devel] Reconsidering function overloading

[Tim Armstrong]

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

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.

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).

Concretely, what happens currently when typechecking a function in STC:
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 (*[]).
2. Find the function type, and the type of the input argument at that
position
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)
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)
5. If there was no way to unify type variable bindings, typechecking fails
6.  Enumerate all possible function types that could arise from selecting a
type variable binding compatible with the input types.
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)
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).
9. Any type variables constrained by output argument types are bound if
needed. Any unconstrained type variables are bound to void

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.

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.

Calling an overloaded function would probably just require trial-and-error
of going through each overload, then selecting the one that fits.

So I guess, start with #3, but #4 might be a reasonable extension.

- Tim



On Wed, Jan 28, 2015 at 6:04 PM, Mihael Hategan <hategan at mcs.anl.gov> wrote:

> I personally didn't think that we would implement them (fn pointers and
> lambdas) separately. That was based on them being morally connected, but
> they are quite different in terms of implementation.
>
> My problem with my solution is that, while min(x, y) will remain nice,
> any use of min as a function pointer will actually require what is
> equivalent to having minFloat/minInt. whether by lambdas or by actually
> writing a minFloat/minInt.
>
> I think this has to be the cost. As before with overloading/keyword
> args, the language gains both abilities in general, with none of the
> corner case affecting anything that could have been done before cleanly.
> We could maybe improve things later by adding a terse casting operator.
>
> I don't think type inference (#5) will be simple if we support
> universally quantified types.
>
> f(T[] a, (T[] -> T) g) {
>   g(a);
> }
>
> f(a, min)
>
> You would basically end up with a constraint system similar to SML's.
> It's doable, but there are lots of moving parts.
>
> So I think ultimately #3 might be the reasonable choice.
>
> I would also add #6, which would be to do dynamic dispatch in cases
> where full static resolution fails. It probably comes with a can of
> worms if its own.
>
> Mihael
>
>
> On Wed, 2015-01-28 at 16:24 -0600, Tim Armstrong wrote:
> > I think lambdas are a nice orthogonal way to solve it here, but yeah, I
> > don't think they're in the plans in the immediate future.
> >
> > - Tim
> >
> > On Wed, Jan 28, 2015 at 2:39 PM, Mihael Hategan <hategan at mcs.anl.gov>
> wrote:
> >
> > > Which ultimately isn't much different from having to do:
> > >
> > > (float x) minFloat(float[] a) {
> > >   x = min(a);
> > > }
> > >
> > > reduce(a, minFloat);
> > >
> > > So maybe that isn't much progress.
> > >
> > > Mihael
> > >
> > > On Wed, 2015-01-28 at 12:23 -0800, Mihael Hategan wrote:
> > > > Here's another idea. If we do support lambda expressions, then:
> > > >
> > > > - a direct reference to an overloaded function when no parameter
> type is
> > > > available should result in an ambiguity error
> > > > - a user can resolve the issue by writing an explicit lambda
> expression
> > > > which calls the overloaded function, but this time with normal
> parameter
> > > > type information available
> > > >
> > > > E.g:
> > > >
> > > > min = reduce(a, min); // error
> > > > min = reduce(a, lambda(float x) { return min(x); });
> > > >
> > > > This requires no specialized casting mechanism. Of course, if lambda
> > > > expressions weren't in the plans, this might be more work.
> > > >
> > > > Mihael
> > > >
> > > > On Tue, 2015-01-27 at 21:42 -0600, Tim Armstrong wrote:
> > > > > Hi All,
> > > > >   I was just starting to look at implementing the function
> overloading
> > > > > support required by the current design of the standard library.
> I've
> > > just
> > > > > realised some of the complications and wanted to reassess the
> current
> > > > > design.
> > > > >
> > > > > .As soon as I looked at the changes needed, it was obvious that it
> > > > > interacts with function references in ways that are probably
> > > undesirable.
> > > > > The issue is that a function name maps to more than one function,
> and
> > > the
> > > > > compiler needs to be able to disambiguate wherever it is used: in a
> > > > > variable context as well as a function call context.
> > > > >
> > > > > For example, suppose we wanted to provide a reduce function with
> type
> > > > > reduce(T, T[], (T) f (T, T)).  It seems reasonable that we'd want
> to be
> > > > > able to write:
> > > > >
> > > > > reduce(0, [1, 10, 3, 4], max)
> > > > >
> > > > > But if max is overloaded, then we have to be able to infer from the
> > > type of
> > > > > the first and second arguments which max was meant.
> > > > >
> > > > > As an aside, there's a further level of difficulty in resolving
> things
> > > > > correctly if you consider that overloaded functions can take
> overloaded
> > > > > functions as arguments
> > > > >
> > > > > There seems to be a number of ways to get around this problem:
> > > > > 1. Don't support overloading at all, save complications at the
> expense
> > > of
> > > > > longer function names
> > > > > 2. Don't plan on supporting function references at all
> > > > > 3. Ban using overloaded functions as first-class functions, force
> > > users to
> > > > > work around it.
> > > > > 4. Attempt to do some basic type inference to disambiguate, give
> up if
> > > we
> > > > > can't disambiguate from local information. (C++ approach,
> essentially)
> > > > > 5. Full program-wide type inference (Haskell approach)
> > > > >
> > > > > #2 doesn't fit with overall plans for the project, I don't think.
> #3
> > > seems
> > > > > pretty unsatisfying and I think we're best to avoid bad programmer
> > > > > experiences when we have a cleanish slate to work from.   #5
> doesn't
> > > seem
> > > > > feasible without major changes to language and compiler.
> > > > > This leaves #1 and #4.  I think I could make #4 work in Swift/T,
> but it
> > > > > would be days of work and getting all the corner cases may be a
> > > challenge -
> > > > > realistically I might just not get it done.  I have no idea how
> > > feasible #4
> > > > > is in Swift/K. #1 seems like the best effort to reward ratio to me.
> > > > >
> > > > > Anyway, that was a bunch of detail - does anyone have any thoughts
> or
> > > > > opinions?  Have I missed anything?
> > > > >
> > > > > I'm already assuming that we just shouldn't support overloading
> > > functions
> > > > > with any other kind of polymorphic arguments - it's not really
> > > necessary
> > > > > and too complicated to implement
> > > > >
> > > > > - Tim
> > > > > _______________________________________________
> > > > > Swift-devel mailing list
> > > > > Swift-devel at ci.uchicago.edu
> > > > > https://lists.ci.uchicago.edu/cgi-bin/mailman/listinfo/swift-devel
> > > >
> > > >
> > > > _______________________________________________
> > > > Swift-devel mailing list
> > > > Swift-devel at ci.uchicago.edu
> > > > https://lists.ci.uchicago.edu/cgi-bin/mailman/listinfo/swift-devel
> > >
> > >
> > >
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/swift-devel/attachments/20150129/21735e90/attachment.html>