Types are pushed into operators incorrectly

[UlfNorell]

Currently the rules for pushing types into arithmetic operator applications in type_check_arith_op_in says (the other operator rules are similar):

  subtype(R, number)
  check(A, R)
  check(B, R)
  ------------------
  check(A op B, R)

This subtype constraint goes the wrong way, as shown in this example:

-spec f(integer(), integer()) -> integer() | divide_by_zero.
f(_X, 0) -> divide_by_zero;
f(X, Y)  -> X div Y.
%% The operator 'div' on line 8 is given a non-integer argument of type integer() | divide_by_zero

The error message is a bit strange as well, since it's the subtype(R, number) constraint that fails and not anything to do with the arguments.

The reason for having the subtyping this way around (I suspect) is to make this fail:

-spec g(number(), number()) -> integer().
g(X, Y) -> X + Y.
%% The variable 'X' on line 12 has type integer() | float() but is expected to have type integer()

I believe the correct rule is

  S = infer(A)
  T = infer(B)
  U = compat_arith_type(S, T)
  subtype(U, R)
  --------------------
  check(A op B, R)

[UlfNorell]

A problem is that inferring the type using type_check_expr is likely to return any() for non-trivial arguments, which will make the whole thing vacuously true.

[zuiderkwast]

More type inference can be done using type_check_expr(Env#env{infer = true}, Expr). Do you see any problem in doing inference in this case with respect to the graduality property AKA gradual guarrantee from the papers?

[josefs]

Thanks for the thorough analysis. I suspect that there are a few similar problems lurking in the code.

The solution might be to compute the greatest lower bound of the result type and number() (in the case of addition). Something like this:

L = glb(number, R)
check(A, L)
check(B, L)
------------------
check(A + B, R)

Note that the glb-operator would be a partial operation and if it doesn't find a lower bound it would result in a type error.

Your thoughts on this solution, @UlfNorell?

EDIT: The glb-operator would technically not be partial, as it can always return none(); the bottom of the subtyping hierarchy. But if glb returns none() we should report a type error because it better matches programmer expectation.

[UlfNorell]

I think this makes sense, although you can construct examples where one could argue that the "right" thing to do is not failing on none():

-spec much_type_very_code(none()) -> none().
much_type_very_code(X) -> X + X.

[josefs]

Yes, there would have to be a special case for when the result is expected to be none().

[UlfNorell]

Forgot to tag any of the commits with a "fix" message.