Lambda the Ultimate

The biggest problem with OO is not type inference itself, but subtyping with type inference. OO rely a lot on subtyping, which is difficult to handle by using classic unification. You can have a look at haXe that implements both type inference and subtyping.

Scala is an OO language that supports type inference (ETM).

I know that I have run into headaches with Object Pascal's lack of subtype polymorphism.

Imagine that you have this taxonomy:


// interface
-------------------------------------------
type TItemClass = class
public
SomeData : String;
.
.
.
end;
-------------------------------------------
type TContainerClass = class
private
FList : TObjectList; // container for objects
FCurrentObj : Integer; // index of currently referenced item
public
function CurrentObject : TItemClass;
end;
-------------------------------------------
Type TItemClassA = class(TItemClass)
ClassASpecificMember : String;
end;
-------------------------------------------
Type TItemClassB = class(TItemClass)
.
end;
-------------------------------------------
Type TContainerClassA = class(TContainerClass)
procedure DoSomething;
end;
-------------------------------------------
Type TContainerClassB = class(TContainerClass)
...
end;
-------------------------------------------
etc...
.
.
.
-------------------------------------------
// Implementation
Function TContainerClass.CurrentObject : TItemClass;
begin
result := FList[fCurrentObj] as TItemClass;
end;


Now, imagine that TContainerClassA will only ever contain instances of TItemClassA, and TContainerClassB will only ever contain instances of TItemClassB, and so on.

The problem comes in when you try and use the CurrentObject function: The compiler only, and only ever, returns the object as the parent class (TItemClass) - not the true subtype of the item, as the RTTI should identify it.

Thus you cannot do the following:


-------------------------------------------
procedure TContainerClassA.DoSomething;
begin
print(CurrentObject.ClassASpecificMember); // compile-time error
end;


The only way to do this is to either typecast the CurrentObject reference EVERY time us use it within TContainerClassA, for example:


-------------------------------------------
procedure TContainerClassA.DoSomething;
begin
print(TItemClassA(CurrentObject).ClassASpecificMember); // compile-time error
end;


or else, override the CurrentObject method for each subclass of TContainerClass, i.e.


-------------------------------------------
type TContainerClassA = class(TContainerClass)
.
.
function CurrentObject : TItemClassA; reintroduce;
end;
-------------------------------------------
function TContainerClassA.CurrentObject : TItemClassA;
begin
result := FList[fCurrentObj] as TItemClassA;
end;


This approach solves the need to cast the returned object of CurrentObject every time you you use it in your code, but the need to override it in every subclass defeats the purpose of having it declared in the base class in the first place.

The solution would be for the compiler to do proper evaluation of the members accessed, and use the least general type which still allow unambigous compilation. Or else defer evaluation and polymorph ("quack-ify(tm)") the type according to RTTI.

i.e.

print(CurrentObject.ClassASpecificMember); // member is unambigous so use the correct type, dammit.


See Nemerle. Depends how much you want inferenced though, as Nemerle still requires type annotations at the method level.

There's also Chuck, which employs a Demand-Driven, subgoal Pruning (DDP) algorithm to do type inference for Squeak.

From the site:

To my knowledge, DDP is the first type inference algorithm that is effective on larger programs (100+ kloc) in Smalltalk-like languages, while still giving context-sensitive results.

See Lex Spoon's dissertation or his papers on the subject for more info.