The Nemerle Project Blog

This is RFC. There is a problem with new type inference engine and intersection types. Or maybe intersection types in general. But, from the beginning.

The type inference algorithm works by assigning type variables, that are yet-uninitialized types, to various parts of the program and trying to deduce something about the type of the program. For example:

class C { static foo (x : int) : string { ... } static bar[T] (x : T) : list[T] { ... } static Main () : void { def x = 3; // easy, x has type int def y = foo (x); // again easy, y has type string def z = bar (y); // harder -- z has type list[type_of y], // so it has type list[string] ... } }

Now consider lists:

class list {...} class Cons : list {...} // head and tail class Nil : list {...} // empty list

This is mostly how the lists look in Nemerle -- two subclasses of a list class. Now, let's have a look at how the list is constructed (the new keyword is skipped in Nemerle):

def empty = Nil (); def my_list = Cons (some_elem, empty);

There is no problem -- empty gets type Nil and Cons takes list as a second argument. But Nil is subtype of list, so the call to the Cons constructor is happily typed, and my_list gets type Cons.

But lets tell, we want to reuse variable first for empty list, and then for a non-empty one:

mutable the_list = Nil (); the_list = Cons (some_elem, the_list);

In the first line the_list gets type Nil. Now in the second line, the call to Cons is typed without a problem, like in the previous example. However it results in Cons type. And type Cons cannot be assigned to a cell of type Nil. The code like the above is quite common in Nemerle -- the syntax a little bit different:

mutable the_list = []; the_list = some_elem :: the_list;

But the meaning is the same. What can the user do is to explicitly upcast the_list to type list and everything is OK. But upcasts are supposed to be automatic. The previous inference algorithm had an hack here -- the constructors Cons and Nil had type list, so the upcast wasn't needed. But we sometimes want to use full Cons type, not the poorer list version. Therefore the new algorithm was supposed to lift this restriction, and do something about it.

The actual solution is to assign a special type at-most-Nil to the_list. Then, upon assignment, the type is changed to biggest common supertype of Nil and Cons, that is list. And everyone is happy -- we can use Nil() with its full Nil type and assignments work OK.

However there is a problem. Consider:

mutable x = 3; x = "string";

First off, this is most likely a bug. If the smallest common supertype of string and int were object it wouldn't be that big of a problem -- even now we just forbid two types, different than the object itself, to sum up to object -- because it is a bug in more than 50% of cases. However beside object they share three interfaces (IComparable, IFormattable, IConvertible). So the smallest common supertype of int and string is intersection of types IComparable, IFormattable and IConvertible. This is how NTE currently handles it. But we clearly (?) don't want this intersection type here. We want an error message.

So now the RFC -- my idea was to drop this beautiful intersection types -- that is if we want to sum up two types that have more than one most specific common supertype (like in the case above) -- to bomb out with an error. This is what constraint solver in Generic Java does. Generic C# doesn't have any constraint solver I'm aware of. The example with list would still work of course.

-- Michal

Unless you are doing a dynamic dispatch to determine what the 'core type' of arguments are on method invocation, Trying to 'cast up' to a common interface seems a bad idea. The user may expect a Nil() type, they may expect a Cons() type, they may expect IList or they may expect something else.

When they call a method which is overloaded to accept multiple choices for an argument, their understanding of which version is being called may be different than what you expect.

The type of a variable should always be assumed to be the return type of what ever expression is evaluated. If the user intends to use that variable to store multiple variables as part of their logic, the user should be responsible for declaring an appropriate type.

This is a valid point. I just had an idea, that it would be possible to
assign range types to mutable values upon intialization with variants.

The list example in Nemerle is a special kind of type, a variant, not a
regular class. You cannot add new methods in variant options (like Cons
and Nil), only in the base variant tyle (list). So choosing this or another
type here doesn't affect overloads.

The idea would be to assign x a type like (list TILL Nil) upon
``mutable x = Nil ();''. This would make the list example still work,
but prevent any assign-string-to-int patology.

Have to think about it more, thanks!

I agree that changing variable's type to intersection with only interfaces / object is bad (the string/int example is plainly the simplest, but such "strange" things will just happen more often). Simply the same way as we refuse automatic lifting of already concrete type to object, we should refuse to do so for interfaces.

> When they call a method which is overloaded to accept multiple choices for
> an argument, their understanding of which version is being called may be
> different than what you expect.

I do not expect any *new* problems here. Most OO languages can already do strange upcasts when choosing an overload. Simply method with the most specific known types will be called, and this should be the rule. No matter if upcast will be performed at passing parameter to call or at assignment of value to this variable.

> The type of a variable should always be assumed to be the return type of
> what ever expression is evaluated. If the user intends to use that variable
> to store multiple variables as part of their logic, the user should be
> responsible for declaring an appropriate type.

The same as above. I guess for classes A : C, B : C we can often expect code like:
mutable x = A();
x = B();

and I really wouldn't like to manually specify
mutable x = A() : C;

I only wouldn't like things described here http://cakoose.com/wiki/simple_type_inference to happen, where
author suggests linking type inference with control flow and letting variables to have different types in various branches of computation (which would mean that different methods will be chosen for overloading in various places of code using it). Fortunately .NET seems to do not allow that and we SHALL NOT do automatic casting to override it.

Finally I think that *proper* solution is to allow <tt>intersection</tt> types as long as they contain at least one non-object/interface concrete type.

How about this:
1) Type cast rule 1: If the left side of the assignment operator is a subtype of the right, then the right should be implicitly upcast to the left, and the type of the left will therefore remain the same.
Ex. left side is already Cons and this time, the right side is []. Then the right side should be converted to Cons and then assigned.

2) Type cast rule 2: If the left side's type is known and the right side is a descendant of the left, then the left side should take on the type of the right.
Ex.
mutable the_list = [];
the_list = some_elem :: the_list;
// Here, the right side is a subtype of the left, so 'the_list' takes the type of the right and becomes Cons.

3) Interface rule: If the left side is an interface and right side's interface is a superset of the left side's interface, then the left side should take on the type of the right.
Ex.
mutable some_comparable = some_obj.ReturnsIComparable();
some_comparable = "String"; // Okay, becuase string supports IComparable
// Should some_comparable take the type string or just its interface?
// Although just taking the interface might seem more natural, taking the type seems like it would be best because it would allow you to:
mutable some_comparable = some_obj.ReturnsIComparable();
some_comparable = "String"; // Okay, becuase string supports IComparable
some_comparable = Nil(); // Okay, because of rule one
// If some_comparable had taken just the interface, assignment to Nil wouldn't be possible (by rule 3).

4) Anything else should throw an error.
Ex.
mutable x = 3;
x = "string";
// Here, although int and string share parts of their interface, int is not a descendant of string, and string is not a descendant of int. Therefore, the compiler should report that the cast in invalid.

Ex2.
mutable x = some_obj.ReturnsIComparable();
x = "string";
// Fails because string may not be a decendant of the type returned by the method even though string supports IComparable. For example, x may be an int

In short, if the right can be cast to the left, it should and the left's type should go unchanged. If the left's type can be cast to the right's type, then the left's type should become the type of the right. The assignemnt operator should never result in the left side's type changing to a supertype or the shared interface, allowing you to do this:

mutable x = SuperString(); // A class derived from String
if blah
x = "hello"; // "hello" is cast to SuperString, and x's type is unchanged
else
x = "world";
x.SomeSuperStringMethod(); // Okay, because x is still type SuperString

By the way, isn't the smallest common supertype of int and string the 'union' of IComparable, IFormattable and IConvertible?

Looks like I contradicted myself with Rule 3 and the last example of Rule 4. The example in rule 4 should indeed fail, therefore Rule 3 should be tossed and assignments should not be allowed to any variable when the concrete type is unknown.

> The same as above. I guess for classes A : C, B : C we can often expect
> code like:
> mutable x = A();
> x = B();
>
> and I really wouldn't like to manually specify
> mutable x = A() : C;

Do you really expect this code to happen ,,often''? At least one in
1000 lines?

> Finally I think that *proper* solution is to allow <tt>intersection</tt>
> types as long as they contain at least one non-object/interface concrete
> type.

Could you please post an example of code where it is needed? The code above
doesn't need intersection types. Something like this would be required for
intersection types to be needed:

class A {}
class B : A, IFoo {}
class C : A, IFoo {}

mutable x = B ();
x = C ();
x.MethodOfIFoo ();
x.MethodOfA ();

The second method call would require either a heavy compiler magic (so
we could really support intersection type [A,IFoo] as local variable
type), or be just rejected. Again, I don't see it happen.

> Ex. left side is already Cons and this time, the right side is []. Then the right side should be converted to Cons and then assigned.

This can't be done - Cons and Nil are incompatible, so you cannot cast Nil to
Cons with the same reason why you can't cast string to int.

> mutable the_list = [];
> the_list = some_elem :: the_list;
> // Here, the right side is a subtype of the left, so 'the_list' takes the type of the right and becomes Cons.

No, the type of 'the_list' is first Nil, then you want to assign it Cons. You
cannot cast neither Cons to Nil, nor otherwise. Also in finally compiled code
you cannot change type of local variable. So the only valid type for above
declaration + assignment is list.

> 3) Interface rule: If the left side is an interface and right side's interface is a superset of the left side's interface, then the left side should take on the type of the right.
Ex.

This indeed is currently being done. First variable gets type IFirst and then it
is lifted to ISecond (IFirst : ISecond). This is ok, because IFirst and ISecond
are related, so we can clearly use valid type, which is both IFirst and ISecond.

> mutable x = 3;
> x = "string";
> // Here, although int and string share parts of their interface, int is not a descendant of string, and string is not a descendant of int. Therefore, the compiler should report that the cast in invalid.

But they DO share common interface - IComparable, etc. And the general question
was just if we should allow it to become the real type of variable.

> mutable x = some_obj.ReturnsIComparable();
> x = "string";
> // Fails because string may not be a decendant of the type returned by the method even though string supports IComparable. For example, x may be an int

This is perfectly ok. First x gets IComparable, then it is assigned with value,
which also is already IComparable... If the real type of variable is
IComparable, it can be safely assigned with both string and int.

> x = "hello"; // "hello" is cast to SuperString, and x's type is unchanged

Such cast not only may, but WILL fails. String can never be SuperString and
runtime will not allow it.

> By the way, isn't the smallest common supertype of int and string the 'union' of IComparable, IFormattable and IConvertible?

Hmm, I guess you are right. The name is misleading, common type of int and
string is object OR IComparable OR IConvertible, etc. The Intersection would
come with AND, which btw is also not expressible in .NET runtime (ok, it is for
interfaces, by creating some additional faked interfaces grouping those from
intersection).

> > and I really wouldn't like to manually specify
> > mutable x = A() : C;
>
> Do you really expect this code to happen ,,often''? At least one in
> 1000 lines?

When you deal much with large inheritance space, I expect it to be often. Like

mutable element = foo_returningTreeView ();
element.methodOfGuiElement ();
element = foo_returningWindow ();
element.other_method_OfGuiElement ();

> Could you please post an example of code where it is needed? The code above
> doesn't need intersection types. Something like this would be required for
> intersection types to be needed:
>
> class A {}
> class B : A, IFoo {}
> class C : A, IFoo {}
>
> mutable x = B ();
> x = C ();
> x.MethodOfIFoo ();
> x.MethodOfA ();

You just answered your own question. If we throw out x.MethodOfA, we get valid
code representible in runtime easily - by having x the type of IFoo... but
right, that won't work anyway. Compiler will HAVE TO choose some type
as a real type of variable.

> The second method call would require either a heavy compiler magic (so
> we could really support intersection type [A,IFoo] as local variable
> type), or be just rejected. Again, I don't see it happen.

Yes, but without compiler magic (choosing some type and casting in each case,
where you need other) intersection types can only be used for typing engine's
temporary state - they won't survive to runtime in their state. But nothing
forces us not to use them as such thing. For example

mutable x = B ();
x = C ();
// here we have type {A | IFoo}, which you would like to forbid
x.MethodOfIFoo (); // here we have type IFoo, which is ok

So my "new point" is to allow intersection types, but make conservative use of
them, like usage of one of its elements' type makes it set to this type.
And I mean any usage (I'm not sure if you treat x.Foo as a constraint on type),
like
foo (x) // new constraint on x
or
x.foo // if it is allowed to contrainf {A, IFoo} to {A} or {IFoo}

<code>
mutable the_list = Nil ();
the_list = Cons (some_elem, the_list);
</code>

I'm guessing this pattern is most commonly used in code that incrementally adds things to a list. In a purely functional language, this would be done through recursion and since call will result in the list being bound to a fresh variable, you wont have this problem. What if there were a way to (in the analysis phase) convert code that uses a mutable variable into functional code?

For example, maybe it is possible to detect the pattern where a value is incrementally updated. One *possible* heuristic would be to see if an assignments LHS variable is also used on the RHS. Another might be to exclude the first assignment when deciding how to generalize the type. (These are just off of the top of my head; you guys could probably come up with better ones).

I believe Nermerle only does function-local inference, which makes this sort of analysis feasible; type errors that slip through your more lenient inference algorithm will probably be caught by the explicitly-typed function signature. I guess the problem becomes one of providing useful error messages that expose the type engine's reasoning.

> mutable the_list = Nil ();
> the_list = Cons (some_elem, the_list);

As you noted, it is the mutable variable that causes this problem. Functional programming languages don't have to worry about this because they use recursion to do similar things, and so you get a fresh variable every time.

I wonder if it's possible to detect the common patterns with data-flow analysis (like SSA) and allow some leniency with type conversion. One possible technique might be to check for recursive assignment (when the LHS of the assignment also appears on the RHS). Another might be to allow only the first type to be generalized. (These are off the top of my head, I'm sure you compiler writers could come up with better ones :)

As Nemerle (I believe) only performs inference on local variables, I don't think such leniency would cause too many problems. Even if the inferencer lets a logical type error get through, the explicit function signatures would probably catch it.

> I'm guessing this pattern is most commonly used in code that incrementally
> adds things to a list. In a purely functional language, this would be done
> through recursion and since call will result in the list being bound to a
> fresh variable, you wont have this problem. What if there were a way to
> (in the analysis phase) convert code that uses a mutable variable into
> functional code?

This is kinda funny -- we do exactly the opposite in the code generation
phase ;) That is we transform tail calls to loops and assignments. But this
is what every decent functional compiler does, and it happens after the
typing, so it's not very relevant here.

Anyway the problem with intersection types will appear in container types.
For example consider:

def ht = Hashtable ();
ht ["foo"] = "bar";
ht ["bar"] = 1;

(this is again imperative code, but this one is not that easy to
transform).

> I believe Nermerle only does function-local inference, which makes this
> sort of analysis feasible; type errors that slip through your more lenient
> inference algorithm will probably be caught by the explicitly-typed
> function signature. I guess the problem becomes one of providing useful
> error messages that expose the type engine's reasoning.

Yes, this is the real problem -- we can do many things, but proper error
reporting is crucial, if the language is to be used.

Well, we already do things like transformation of imperative-like code to functional - loops are transformed to local functions:

macro while_macro (cond, expr) {
<[ def while_loop () {
when ($cond) {
$expr;
while_loop ()
}
while_loop ()
]>
}

But it is done for control constructs. IMHO transforming code to do not use mutable values, which user write isn't a good idea. We would very quickly hit the code, which is impossible to transform - for example sequence of assignments or ref/out parameters:

mutable x = [];
x = 1 :: x;
foo (ref x);
match (x) {
| [1, 2, 3] => x = []
| _ => assert (false)
}

I just can't imagine getting out of mutables here automatically.

So we have to deal with assignments changing (or not changing) the infered type of local variable. The problem is indeed the readable error message. Currently the int/string code gives:

expected string-, got int in assignment: common super type of types [string, int] is a set of interfaces [System.IComparable, System.IConvertible]. This is not supported

Note the "not supported" at the end. We could support giving x such type, but then error message for

assert (x == "2");

would be very ugly - that there is no == operator for types [System.IComparable, System.IConvertible] and string, which in context of assigning string to variable initially, would be quite strange.

Hi! http://www.insurance-top.com/company/ car site insurance. compare car insurance, auto insurance, insurance car. from website .

http://www.ringtones-dir.com/get/ ringtones site. ringtones site free, ringtones site, Free nokia ringtones here. From website .

The Blog

13 Mar 2005: Intersection types