Overload resolution simplification
Howard Lovatt
howard.lovatt at gmail.com
Tue Aug 20 23:09:59 PDT 2013
Possible type inference algorithm using type checking of Lambdas (with
examples below to show that it works well):
I. Start with the outer-most method call, declaration, or assignment and
work inwards and then left to right.
II. For methods select a set of candidate methods based on known types,
method name, and number of arguments and note the lambda candidate types.
For declared types note the type. For assignments note the destination type.
III. For each candidate type signature check the lambda including the
return type against the candidate types and if the type check fails
eliminate that candidate. This step whilst primarily eliminating candidates
may add candidates because there may be multiple candidates for a given
method/declaration/assignment based on multiple super-types of signatures.
This stage, III., and the next, IV., may be usefully combined to make the
process quicker. The process may also be carried out in parallel.
IV. Choose from the remaining candidates the candidate method that is the
best fit (least number of conversions - sum of conversion required for
argument types and return type).
V. If there are methods that are equally good fit issue an error giving the
possible methods.
The above algorithm is simple and doesn't involve complicated speculation
about types, i.e. it works in a forward direction form signatures through
lambda argument types to the lambda's return type. As shown below through a
series of examples the algorithm works well and doesn't produce any
surprises.
In all cases below the unkown type of a single lambda argument, a, is A and
for multiple arguments, a1, a2, ..., the types are A1, A2, ..., similarly
an unknown return type is R and multiple are R1, R2, ...
Maurizio's Examples (Lambda Experts Group email)
================================================
class Mappers<T> {
IntSream map(IntFunction<T> if) {...}
<Z> Stream<Z> map(Function<T, Z> f) {...}
<U> IntStream map(Stream<U> s, IntFunction<U> if) {...}
<U, V> Stream<V> map(Stream<U> s, Function<U, V> f) {...}
}
Mappers<String> ms = ...;
ms.map(a->1); // Ex. 1
ms.map(a->'A'); // Ex. 2
Stream<String> ss = ...;
Mappers.map(ss, a->1); // Ex. 3
Mappers.map(ss, a->'A'); // Ex. 4
Ex. 1: ms.map(a->1)
-------------------
1. From the scope, function name, and number of arguments there are two
possible functions map(IntFunction<String>) and map(Function<String, Z) and
in both cases A = String and therefore A must be String.
2. Therefore (String a)->1 is either i. an IntFunction<String> (R = int) or
ii. a Function<String, Z> (R = Object).
3. Type check option i., R = int, and this is OK since 1 is an int.
4. Type check option ii., R = Object, and this is OK since 1 could be
autoboxed to an Integer.
5. Choose option i. because it doesn't require boxing.
Ex. 2: ms.map(a->'A')
---------------------
1. From the scope, function name, and number of arguments there are two
possible functions map(IntFunction<String>) and map(Function<String, Z) and
in both cases A = String and therefore A must be String.
2. Therefore (String a)->'A' is either i. an IntFunction<String> (R = int)
or ii. a Function<String, Z> (R = Object).
3. Type check option i., R = int, and this fails since 'A' is not
automatically convertible to int.
4. Type check option ii., R = Object, and that is OK since 'A' could be
autoboxed to a Character.
5. Therefore ii.
Ex. 3: Mappers.map(ss, a->1)
----------------------------
1. From the scope, function name, and number of arguments there are two
possible functions map(Stream<String>, IntFunction<String>) and
map(Stream<String>, Function<String, Z) and in both cases U = A = String
and therefore both U and A must be String.
2. Therefore (String a)->1 is either i. an IntFunction<String> (R = int) or
ii. a Function<String, Z> (R = Object).
3. Type check option i, R = int, and this is OK since 1 is an int.
4. Type check option ii, R = Object, and this is OK since 1 could be
autoboxed to an Integer.
5. Choose option i. because it doesn't require boxing.
Ex. 4: Mappers.map(ss, a->'A')
------------------------------
1. From the scope, function name, and number of arguments there are two
possible functions map(Stream<String>, IntFunction<String>) and
map(Stream<String>, Function<String, Z) and in both cases U = A = String
and therefore U and A must be String.
2. Therefore (String a)->'A' is either i. an IntFunction<String> (R = int)
or ii. a Function<String, Z> (R = Object).
3. Type check option i., R = int, and this fails since 'A' is not
automatically convertible to int.
4. Type check option ii., R = Object, and that is OK since 'A' could be
autoboxed to a Character.
5. Therefore ii.
Eric's Pt. 1 Examples Converted to Java (
http://blogs.msdn.com/b/ericlippert/archive/2007/01/10/lambda-expressions-vs-anonymous-methods-part-one.aspx
)
==============================================================================================
Function<Integer, Integer> f2 = a->a+1; // Ex.
5
Function<Integer, Integer> f4 = a->a.toString(); // Ex. 6
// Have a method: bool m1(short)
Function<Integer, String> f6 = a->m1(a) ? a.toString() : ""; // Ex. 7
Ex. 5: Function<Integer, Integer> f4 = a->a+1
---------------------------------------------
1. From the scope, the lambda must be a Function<Integer, Integer>, i.e. A
= R = Integer.
2. Type check (Integer a)->a+1, R = Integer, and this is OK since a could
be auto-unboxed to an int and a+1 could be autoboxed to an Integer.
Ex. 6: Function<Integer, Integer> f2 = a->a.toString()
------------------------------------------------------
1. From the scope, the lambda must be a Function<Integer, Integer>, i.e. A
= R = Integer.
2. Type check (Integer a)->a.toString, R = Integer, and this fails (as
expected) since Integer's toString method returns a String and String is
not auto-convertible to an Integer.
Ex. 7: Function<Integer, String> f6 = a->m1(a) ? a.toString() : ""
------------------------------------------------------------------
1. From the scope, the lambda must be a Function<Integer, String>, i.e. A =
Integer and R = String.
2. Type check (Integer a)->m1(a) ? a.toString : "", R = Integer, and this
fails (as expected) since a (an Integer) cannot be auto-converted to short
(m1(short)).
Eric's Pt. 4 Examples Converted to Java (
http://blogs.msdn.com/b/ericlippert/archive/2007/03/26/lambda-expressions-vs-anonymous-methods-part-four.aspx
)
=================================================================================================
static Integer m(Function<Integer, Integer> f){ /* whatever ... */ }
static String m(Function<String, String> f){ /* whatever ... */ }
m(a->a.toUpperCase());
// Ex. 8
m(a1->m(a2->a1.toLowerCase() + a2.toUpperCase())); // Ex.
9
Ex. 8: m(a->a.toUpperCase())
----------------------------
1. From the scope, the lambda must be either i. a Function<Integer,
Integer>, i.e. A = R = Integer, or ii. Function<String, String>, A = R =
String.
2. Type check i. (Integer a)->a.toUpperCase(), R = Integer, and fails since
an Integer does not have a toUpperCase method.
3. Type check ii. (String a)->a.toUpperCase(), R = String, and this is OK
since a String does have a toUpperCase method and it returns a String (R =
String).
4. Therefore ii.
Ex. 9: m(a1->m(a2->a1.toLowerCase() + a2.toUpperCase()))
--------------------------------------------------------
1. From the scope, the outer lambda, 1, must be either 1.i. a
Function<Integer, Integer>, i.e. A1 = R1 = Integer, or 1.ii.
Function<String, String>, A1 = R1 = String.
2. Type check 1.i. (Integer a1)->m(a2->a1.toLowerCase() +
a2.toUpperCase())), R1 = Integer.
2.a. From the scope, the inner lambda, 2, must be either 2.i. a
Function<Integer, Integer>, i.e. A2 = R2 = Integer, or 2.ii.
Function<String, String>, A2 = R2 = String.
2.b. Type check 2.i. (Integer a2)->a1.toLowerCase() + a2.toUpperCase())),
A1 = R2 = Integer, and this fails because A1 = Integer and Integer doesn't
have a toLowerCase method.
2.c. Type check 2.ii. (String a2)->a1.toLowerCase() + a2.toUpperCase())),
A1 = Integer and R2 = String, and this fails because A1 = Integer and
Integer doesn't have a toLowerCase method.
2.d. Therefore 1.i fails.
3. Type check 2.i. (String a1)->m(a2->a1.toLowerCase() +
a2.toUpperCase())), R1 = String.
3.a. From the scope, the inner lambda, 2, must be either 3.i. a
Function<Integer, Integer>, i.e. A2 = R2 = Integer, or 3.ii.
Function<String, String>, A2 = R2 = String.
3.b. Type check 3.i. (Integer a2)->a1.toLowerCase() + a2.toUpperCase())),
A1 = String and R2 = Integer, and this fails because A2 = Integer and
Integer doesn't have a toUpperCase method.
3.c. Type check 3.ii. (String a2)->a1.toLowerCase() + a2.toUpperCase())),
A1 = String and R2 = String, and this is OK.
4. Therefore 1.ii.
On 20 August 2013 23:03, Ali Ebrahimi <ali.ebrahimi1781 at gmail.com> wrote:
> Hi Maurizio,
> This is my current updated proposal, I think this makes things more clear.
> Updated proposal:
>
> Step 1: type argument inference
> for all overloads infer type arguments
> if all overloads agree on same type for type args goto step 2, otherwise
> ERROR.
>
> Step 2: Scan lambda body for implicit nested lambdas
> if does not exist any implicit nested lambdas goto step 3, otherwise ERROR.
>
> Step 3: Lambda body type checking
> Type check lambda body with provided input params. If type checking is
> successful, goto step 4, otherwise ERROR.
> Do this step only once for all overloads, since you have same input types.
> Note: In this step we only type checks lambda body for body errors not type
> mismatch in return type, since we don't do this step against any target.
> Suppose we have function types in language and try to compute function type
> (type descriptor) of lambda. We don't do SAM comversion in this step.
>
> I think this step would be an forward compatible step if we one day add
> function types to language.
>
> Step 4: Overload Selection (Most specific applicable overload selection)
> We have obtained one function type or type descriptor for lambda from step
> 3, and do structural type checking against each overload's target.
> We do this process in four phase or mode
>
> 1) Without Boxing, Unboxing, Widening and Upcasting(can not do boxing,
> unboxing, widening and upcasting)
> 2) Without Boxing, Unboxing and Upcasting but with Widening (can not do
> boxing, unboxing and upcasting but can do widening)
> 3) With Boxing, Unboxing and Widening but without Upcasting(can do boxing,
> unboxing and widening but can not do upcasting)
> 4) With Boxing, Unboxing, Widening and Upcasting(can do boxing, unboxing,
> widening and upcasting)
>
>
> for each mode x (1..4) do:
> for each overload's target t
> 1) Verify type descriptor of lambda with t's type based on
> constraints of mode x, if lambda is compatible with target
> t, add t's corresponding overload method m to
> mode x's applicable overload list.
> //end for t
> if x's applicable overload list is empty continue x's for loop
> if x's applicable overload list have only one element, you have succeed
> and that is most
> specific overload.
> if x's applicable overload list have more than one element, you have
> failed and you got
> ambiguity ERROR
> //end for x
>
> You have not fund any applicable overload So ERORR.
>
> END
>
>
> Best Regards,
> Ali Ebrahimi
>
>
>
> On Tue, Aug 20, 2013 at 2:11 PM, Maurizio Cimadamore <
> maurizio.cimadamore at oracle.com> wrote:
>
> > On 19/08/13 20:42, Ali Ebrahimi wrote:
> >
> >> What about if type error does not occur, and lambda body satisfy all
> >> targets. In this case we only do most specific selection as we do in
> >> overload resolution phase. So I think with this reduced problem space
> >> Brittleness problem doesn't occur.
> >> if we have same input for lambda against all overloads, in that case
> >> problem mostly (not sure 100%, help me) would be equivalent to when we
> >> don't have any input.(nilary lambdas: () -> ...).
> >>
> > I guess I still don't get what happens if, for a given target you get an
> > type-checking error - how is your logic supposed to handle that? Note
> that
> > we tried both flavours and they both weren't good enough - for different
> > reasons:
> >
> > *) making a method not applicable because of a type-checking error in a
> > lambda is brittle (see my previous email)
> > *) making a method applicable because of a type-checking error leads to
> > can of worms spec-wise (as now you'll have to specify how all the
> > type-checking routines are supposed to be working in the face of errors -
> > uuugh)
> >
> > Maurizio
> >
> >
> >
> >
> >
>
--
-- Howard.
More information about the lambda-spec-observers
mailing list