Delphi (as Pascal descendant) has always had powerful type system. Consider the following sample code implementing simple insertion sort algorithm (I use Delphi 2009):
unit InsSort; interface type TItem = Integer; TArray = array of TItem; procedure InsertionSort(var A: TArray); implementation procedure InsertionSort(var A: TArray); var I, J: Integer; Item: TItem; begin for I:= 1 + Low(A) to High(A) do begin Item:= A[I]; J:= I - 1; while (J >= Low(A)) and (A[J] > Item) do begin A[J + 1]:= A[J]; Dec(J); end; A[J + 1]:= Item; end; end;
The above code sorts integer array; if we need to sort array of strings, all we have to do is to switch TItem type declaration from Integer to string:
type TItem = string;
If our task is to sort both integer and string arrays we should have two separate source code units (though they differ just by one word). Clearly that is code duplication that can’t be solved in plain Pascal. But Delphi has generics, let us try generics. Naive
procedure InsertionSort<TItem>(var A: array of TItem);
does not compile, we need class to use generics; we also need some means to compare generic types, so I have written the following simple generic class:
type TArray<TItem> = class class function Compare(const L, R: TItem): Integer; static; class procedure InsertionSort(var A: array of TItem); static; end; implementation uses SysUtils, TypInfo; class function TArray<TItem>.Compare(const L, R: TItem): Integer; var P: PTypeInfo; begin P:= TypeInfo(TItem); case P^.Kind of tkInteger: begin if PInteger(@L)^ < PInteger(@R)^ then Result:= -1 else if PInteger(@L)^ > PInteger(@R)^ then Result:= 1 else Result:= 0; end; tkUString: Result:= CompareStr(PString(@L)^, PString(@R)^); end; end; class procedure TArray<TItem>.InsertionSort(var A: array of TItem); var I, J: Integer; Item: TItem; begin for I:= 1 + Low(A) to High(A) do begin Item:= A[I]; J:= I - 1; // while (J >= Low(A)) and (A[J] > Item) do begin while (J >= Low(A)) and (Compare(A[J], Item) > 0) do begin A[J + 1]:= A[J]; Dec(J); end; A[J + 1]:= Item; end; end;
It works but it looks ugly. Think also of crazy overhead of generic comparison, especially for plain types like Integers that are normally compared by just a single assembler instruction. Delphi 2009 Rtl (Generics.Defaults.pas unit) provides more elegant (and more lengthy) solution based on IComparer generic interface, but it boils down to the same inefficient runtime type information usage.
But why we need the ‘Compare’ function at all? By the time the compiler generates code for generic TItem type the compiler should already know actual type to substitute for TItem, and using the actual type it can compile the elegant line
while .. (A[J] > Item) ..
much more efficiently than the ugly
while .. (Compare(A[J], Item) > 0) ..
The idea of direct efficient Generic comparison also invokes Haskell’s ‘type class’ concept. The ‘Type class’ is something very different from OOP class. In Haskell every type is an instance of many type classes. For example integer type is an instance of ‘Eq’ type class because integers can be compared for equality, of ‘Ord’ type class because all comparison operation (<, <=, >, >=) are applicable to integers, of ‘Show’ type class because integers can be converted to string, etc. In our case the generic TItem type should be an instance of ‘Ord’ type class.