Why Generics Constraints ? - Felix John COLIBRI.

• abstract : do generics really require constraints ?
  
• key words : generics - type parameters - constraints - compilation
  
• software used : Windows XP Home, Rad Studio 2007, Delphi 2009
  
• hardware used : Pentium 2.800Mhz, 512 M memory, 140 G hard disc
  
• scope : Rad Studio 2007, Delphi 2009
  
• level : Delphi developer
  
• plan :
  
  • Craig STUNTZ vs Sergey ANTONOV
    
  • A Generics Constraints Crash Course
    
  • From Interpreter to Compiler
    
  • Compiling Generic code
    
  • Your comments are Welcome
    

1 - Craig STUNTZ vs Sergey ANTONOV

• D2009 Generics and Type Constraints (2008 08 29), where he presents the Delphi version of the classical generic calculator, using a generic tAdder Class
  
• Building a Generic Statistics Library - part 1 to 5, which is a very concrete presentation of higher order functions.
  

Here is our interpretation of those explanations.

2 - Generics Constraints Crash Course

• a first piece of code defines some algorithms (say a container like a tList, or a dictionary with key-value pairs), like this

  type c_generic_stack<T>= class                            m_generic_array: Array of T;                            m_top_of_stack: Integer;                            constructor create_generic_stack(p_length: Integer);                            procedure push(p_gen: T);                            function f_pop: T;                          end; // c_generic_stack // ooo procedure c_generic_stack<T>.push(p_gen: T);   begin     if m_top_of_stack< Length(m_generic_array)       then begin           m_generic_array[m_top_of_stack]:= p_gen;           Inc(m_top_of_stack);         end;   end; // push

• in order to use this algorithm (push a value on a stack in our case), the "true" code must define the actual type which will be used in place of the generic T

  var l_c_integer_stack: c_generic_stack<Integer>;   l_c_integer_stack:= c_generic_stack<Integer>.create_generic_stack(5);   l_c_integer_stack.push(111); var l_c_string_stack: c_generic_stack<string>;   l_c_string_stack:= c_generic_stack<string>.create_generic_stack(5);   l_c_string_stack.push('abc');

  
  

• we look for an Interface which defines equality. This is the iEquatable Interface which has an Equals(T) Function

  In the generic Class, we constraint the generic type T to use this Interface, and can then use the Equals function on all T values:

  type c_find_array<T_data: iEquatable<T_data> >=          class            m_array: Array of T_data;            m_count: Integer;            constructor create_find_array(p_length: Integer);            procedure add_to_array(p_cell: T_data);            function f_index_of(p_cell: T_data): Integer;          end; // c_find_array // ooo function c_find_array<T_data>.f_index_of(p_cell: T_data): Integer;   var l_index: Integer;   begin     Result:= -1;     for l_index:= 0 to m_count- 1 do     begin       if m_array[l_index].Equals(p_cell)         then begin             Result:= l_index;             Break;           end;     end; // for l_index   end; // f_index_of

• when we want to use the generic array, the actual type must implement the iEquals Interface. It turns out that in .Net, all the usual value types are equatable: Integer, Double, String etc. So we could write

  var g_c_integer_array: c_find_array<Integer>;   g_c_integer_array:= c_find_array<Integer>.create_find_array(10);   g_c_integer_array.add_to_array(111);   g_c_integer_array.add_to_array(222);   writeln('index of 333 : ', f_index_of(222));

  
  

To decide this, the key points are

• how does a compiler translate the generic code into binary code
  
• can the compiler generate the binary without using constraints
  
• if he can, should he ?
  

3 - From Interpreter to Compiler

Basically the programmer types source code, and the customer runs binary code. To translate from one to the other, here are some of the possible techniques:

In this figure

• 3+'4' represents some operation (could be total:= amount+ taxes, or with litteral values, etc)
  
• push_i 3 is the translation in some pseudo-code (translation in the simple, standardized instruction set of a virtual processor)
  
• the virtual code is interpreted or translated into binary code of some concrete processor
  
• MOV AX, 3 is the representation of this binary code. We represented the "assembler" side, the real stuff being a sequence of bytes ($A9 etc). This is the only thing that the processor will ever understand. Everything before, including our source code are intermediate steps
  

• green arrow represent the handling on the programmer's side
  
• blue arrow, the handling at the customer's side
  
• red bar the compiler detected errors, fuchsia arrow the run-time detected errors
  

• with a pure Basic interpreter
  
  • the programmer only writes the source code
    
  • on the user PC, the interpreter analyzes and runs the code. Errors (usually all called "syntax error") are detected there
    
• with the Apple ][ UCSD system
  
  • the source code is translated in some "pseudo processor code", and all type checking is performed at this time.
    
  • the interpreter runs this code (by calling routine which translate each P-code instruction in binary), and runtime errors are flagged there
    
• with the C# environment
  
  • on the developer's site:
    
    • the source code is translated in MSIL (Microsoft Intermediate Language), and all type checking is performed at this time.
      
    • when the programmers tests his code, the Just In Time Compiler translates this Byte Code (another name for P-code) into binary
      
  • this binary is deployed, and runtime error catched then
    
• with source to binary compiler, like Turbo Pascal, Delphi, usually all C / C++ compilers
  • the source code is translated into binary and all type checking is performed at this time (except for C compilers which do not check anything, since any programmer writing code in C is by definition a system programmer, and we all know those never make any error, so therefore there's nothing to check anyway).
    
  • this binary is deployed, and runtime error catched then
    

Compiling Generics - Generics implementation

4.1 - The Goal

• the developer writes two pieces of code
  
  • the generic code, telling about, say, adding a value of some generic type A, and another value of type B (noted A+B, although in the code you add "values of type A" to "values of type B". The concrete types A and B are not specified at this stage
    
  • the "specialization code", where he specifies that type A and B actually are: Integer, Double, tDateTime, Complex number or whatever
    
• at the customer end of the transformation, a usual, only binary can be used. So the transformation must convert the "A / Integer" in a processor instruction ADD, but "A / Double" into a call to the FPU
  

4.2 - C++ templates

When the compiler finds some actual type, he reads the blueprint of the algorithm in the template, and compiles this template replacing the generic type (A) with the actual type (Integer)

This can be represented like this:

The ETH people stressed over and over again that this kind of "macro generics" were not "true generics", and their Oberon language had more "compiled generics".

However this techniques allows a lot of flexibility when you are writing generics, since there is theoretically no need to impose any limitation on the operations performed on generic types, since by the time the code reaches the compiler they have been replaced by the macro processor in generic-free code, and the compiler performs his usual type checks on this code.

4.3 - The C# implementation

When some class specializes a generic class, additional tests check that the actual type meets the generic ancestor's constraints.

As we wrote in our tutorial,

generics are implemented at the .Net intermediate language level (IL: Intermediate Language= C# pseudo code) and the CLR level (Common Language Runtime: the library managing the code, containing, the IL-to-native compiler, the type checker, the loader, the memory manager etc).

The intermediate language contains :

• the parameterized types, along with the standard types
  
• markers for the type arguments
  
• informations about generics included in the IL meta data
  

When the intermeditate code is compiled into binary code (x386 assembler)

• when the code defines type arguments, the metadata is used to update the generic metatdata with the argument metadata
  
• the JIT compiler can then perform its type checking
  
• if the type argument is a value type (Integer, Double etc), the parameters are replaced with the actual type, and the corresponding code is generated. Therefore, there is no boxing / unboxing for those actual types. In addition, if the type is used in some other places, the compiler uses a reference pointing to the compiled code
  
• if the type argument is a reference type (classe, arrays, lists etc), the type parameter is replaced by tObject. The native code uses a reference pointing to the object, and this without any casting.
  

This can be represented like this:

4.4 - The Delphi 2009 Generics

So in Delphi, the compiler

• transforms the generic code in units
  
• for the units deriving new classes from generic classes by providing the actual type, the generic units are read back and the binary generated
  

The big difference is that in Delphi 2009, the compiler is the sole involved in generating the code, whereas the C# system uses 2 steps:

• the compiler which generates the IL
  
• the JIT compiler which transforms this in binary code.
  

4.5 - With or Without Constraints ?

In C#, since there are 2 compilers, they had the choice

• either you use no constraints, and write code with any operator, say addition, and no checks. The JIT then flags the inconsistencies
  
• or you want earlier checks, and use constraints to perform them.
  

• no constraints on the generic code, and the compilation of the units with the actual type will ferret out the errors. However this will be performed only during the compilation of the .EXE, and the compiler can even display the incorrect line.

  The only difference with the current Delphi 2009 "with constraints" choice is that no checks are performed on the type when compiling the generic Units (our red circle)

• or with constraints, and the compiler can reject mistakes even while compiling the generic code
  

• the errors are flagged earlier. So this will be a big help to the developer who writes the generic Unit
  
• even more compelling, if there is no constraint, when the code with the actual type finds an error, there is a temptation to change the generic code to fix this problem, but maybe thereby invalidate other Units using the same generic ancestor. In addition the user of the generic library would have to dwelve in the generic code, which he maybe would not like to do.
  

4.6 - Security vs Flexibility

On the security side:

• if you can spot some error, the compiler can. And, as Niklaus WIRTH emphasized, he must, and stop right there, and tell you about, and don't move until you correct it. "The compiler will shoot into the foot" (the quote from the joke Shoot yourself in the foot)
  
• the general idea being that a mistake caught by the compiler will cost 100 time less than taking a plane to the customer premisses, understand and fix the bug, not talking about inviting him to a nice restaurant to try to forget about the whole incident.
  

• writing the generic code without having to bother about which Interface has the required operation is obviously both quicker and more readable
  
• years ago, I remember people mentioning Python as a good language which did not require Types, while still guaranteeing type safety
  
• the same goes for Type Inference (from the Delphi .Net draft documentation by Yooichi TAGAWA, with our identifier notation style):

  Type t_my_procedure<Y> = Procedure(p_1, p_2: Y) Of Object;      c_my_class = Class                     Procedure my_procedure<T>(p_a, p_b: T);                     Procedure test;                   end; // c_my_class Procedure c_my_class.my_procedure<T>(p_a, p_b: T);   begin     Write(p_a.ToString, p_b.ToString);   end; // my_procedure Procedure c_my_class.test;   begin     my_procedure<String>('Hello', 'World');     my_procedure('Hello', 'World');     my_procedure<Integer>(10, 20);     my_procedure(10, 20);   end; // test // ooo var l_my_procedure: t_my_Procedure<Integer>;   l_my_procedure := my_procedure<Integer>;   l_my_procedure(40, 50);

  It certainly is more readable to avoid to type <Integer> or <String> before each call of a generic method
  

5 - Your comments are welcome

• we welcome any comment, criticism, enhancement, other sources or reference suggestion. Just send an e-mail to fcolibri@felix-colibri.com.
  
• or more simply, enter your (anonymous or with your e-mail if you want an answer) comments below and clic the "send" button

  Name :
  E-mail :
  Comments * :

  
  

6 - References

• D2009 Generics and Type Constraints (2008 08 29), where he presents the Delphi version of the classical generic calculator, using a generic tAdder Class
  
• Building a Generic Statistics Library - part 1 to 5, which is a very concrete presentation of higher order functions.
  
• Shoot yourself in the foot
  
• Delphi .Net generics tutorial which I wrote when Rad Studio 2007 (Delphi .Net) came out
  

We all see the writing on the wall: functional programming is the obvious way to go. For one main reason: mathematics. In the same way that relational databases did overcome the other (hierarchical, navigational) database models (because of Codd's mathematical insight), the functional programming model will allow us to perform, some day, program validation and verification. No longer fiddling to check whether it works, but quietly moving from concept to implementation.

7 - The author