| |
 |
|
Imperative Mini Component Pascal with Generics (IMCPG) is the final language in the series of MCP formalisations. IMCPG is an extension of IMCPI with support for parametric polymorphism, or generics.
Language features
An introduction to generics
Parametric polymorphism (or 'generics') allows types and methods to be parameterised using type variables. Kennedy and Syme (2001) succinctly describe the benefits of generics as: 'safety (more bugs caught at compile time), expressivity (more invariants expressed in type signatures), clarity (fewer explicit conversions between data types), and efficiency (no need for run-time type checks)' -- although the last benefit depends on the implementation.
In languages that do not support parametric polymorphism -- for example, classic Java and C# and Mini Component Pascal up to IMCPI -- truly generic programming is simulated through the use of a paradigm based around inclusion polymorphism (i.e. the use of Object, ANYPTR, or other top-level types). Here is an extract from a linked-list example program for IMCP, which illustrates the deficiencies of this approach:
TYPE
(* A linked list of PDisplayable elements *)
List = EXTENSIBLE RECORD (Displayable)
head: PDisplayable;
tail: PList;
END;
PList = POINTER TO List;
(* ... *)
VAR
list: PList; (* the root node of our linked list *)
helper: PHelper; (* our helper object *)
head: PDisplayable; (* we will store the head of the list here *)
(* ... *)
BEGIN
(* ... *)
list.head := helper.NewPInteger(5);
list.Insert(helper.NewPInteger(10));
(* ... *)
head := list.Head();
WITH head: PInteger DO
util.WriteInt(head.val);
END;
END ListMod.
Here we have a linked-list which stores objects that are subtypes of PDisplayable (a kind of abstract supertype). However, after extracting an element of the list, we need to downcast it back to its run-time type (in this case, PInteger) in order to perform operations specific to that type. The problems with this approach are obvious -- the code becomes more complex than it needs to be, and there is a risk involved that the downcast may fail at run-time if the programmer accidentally inserts an element into the list that is not a PInteger.
Contrast this with an extract from the corresponding generic linked-list implementation:
MODULE GListMod;
TYPE
GList<X:PIDisplayable> =
EXTENSIBLE RECORD (ANYREC + IDisplayable)
head: X;
tail: PGList<X>;
END;
PGList<X:PIDisplayable> =
POINTER TO GList<X:PIDisplayable>;
(* ... *)
VAR
list: PGList<PInteger>;
helper: PHelper;
head: PInteger;
(* ... *)
BEGIN
(* ... *)
list.head := helper.NewPInteger(5);
list.Insert(helper.NewPInteger(10));
(* ... *)
head := list.Head();
util.WriteInt(head.val);
END ListMod.
Our linked-list is now parameterised on the PInteger type, which means that when we extract the head element by calling Head() we get an element which is of type PInteger -- there is no need to downcast it to extract its value field val. Therefore we have already seen two benefits here -- type safety (in the elimination of the downcast) and conciseness.
Generics in IMCPG
IMCPG allows record types, interface types, pointer types, and methods to be parameterised using type variables. The generics extension is similar both syntactically and semantically to those for Java and C#. In a type declaration, the type name is followed by an optional sequence of type parameters, inside angle brackets. Each type parameter has a set of bounds (or constraints); any instantiation of a type parameter must satisfy the bounds on that type parameter (i.e. it must be a subtype of all of the bounds). For the sake of simplicity, bounds on type parameters are mandatory.
Open types, pointer types, and the scope of type parameters
An open type is an uninstantiated generic type. An open type includes the type name and its sequence of type parameters and bounds. A closed type is an instantiated generic type. There are three places in which open types occur in IMCPG programs: in record type declarations; in pointer type declarations; and in method declarations. An open type must always contain a sequence of type parameters and instantiations. For example, returning to the example given above, the following type declarations are correct: In the 'strict' version of IMCPG presented in this chapter, it is not sufficient to write:
Ord<X:ANYPTR> = EXTENSIBLE INTERFACE RECORD END;
POrd<X:ANYPTR> = POINTER TO Ord; (* incorrect *)
or
Ord<X:ANYPTR> = EXTENSIBLE INTERFACE RECORD END;
POrd = POINTER TO Ord; (* incorrect *)
At first glance this may seem overly restrictive; since it is not possible to declare multiple types with the same name and different type parameters, no ambiguities can arise. Therefore, we have taken this approach for two reasons -- firstly, to ensure that all types, whether open or closed, can be considered to be well-formed; and secondly, to ensure that a record's type parameters are within the scope of that record's method declarations.
In the above examples, the type parameter lists of pointer types match those of their corresponding record types. This is enforced by the type rules; a pointer type is not allowed to have different type parameter lists to its corresponding record type. This reflects the nature of Component Pascal pointer types, which are simply a convenient means of instructing the compiler to use reference and heap-allocation semantics rather than value semantics. It could be argued that the duplication of type parameter lists is unnecessary, and that the shorthand:
Ord<X:ANYPTR> = EXTENSIBLE INTERFACE RECORD END;
POrd = POINTER TO Ord;
should not present any ambiguities. This shorthand is permitted by the IMCPG compiler.
F-bounded polymorphism
The style of type parameterisation supported by IMCPG is highly expressive, supporting full 'F-bounded' polymorphism. F-bounded polymorphism allows a type parameter to appear in its own bound; for example:
Ord<X:ANYPTR> = EXTENSIBLE INTERFACE RECORD END;
POrd<X:ANYPTR> = POINTER TO Ord<X:ANYPTR>;
Pair<X:POrd<X>> = EXTENSIBLE RECORD ... END;
PPair<X:POrd<X>> = POINTER TO Pair<X:POrd<X>>;
Restrictions
As with the previous languages in the MCP series, the design and implementation of GPCP has been a factor in the design of IMCPG. It is hoped that IMCPG can serve as the basis for the design of generics for GPCP. Since GPCP targets both the JVM and the .NET CLR, some consideration must be given as to how a design for generics can eventually target both back-ends. Version 2.0 of the .NET CLR provides in-built support for generics; the current implementation of IMCPG targets the CLR 2.0. However, since the JVM and CLR 1.x do not provide this direct support for generics, the compiler must adopt some translation scheme. It is likely that a translation scheme for GPCP will be based on homogeneous translation using type erasure. With these facts in mind, we have decided not to allow instantiation of type parameters with primitive types, since this would be difficult or impossible to implement with a type erasure translation scheme. This restriction also simplifies the language and type rules somewhat.
Also, for the sake of simplicity, we have not modeled type inference for generic method calls. This should not be particularly difficult, however, and could be the subject of further research.
|
