Polymorphism (20 Nov. 2012) A5 due 28 Nov. See the announcement re: niagara exclusive access signup Have a great Thanksgiving! =================================== Recall from chapter 3: ad hoc polymorphism: fancy name for overloading subtype polymorphism in OO languages allows code to do the "right thing" when a ref of parent type refers to an object of child type implemented with vtables (to be discussed in chapter 9) parametric polymorphism type is a parameter of the code, implicitly or explicitly implicit (true) language implementation figures out what code requires of object at compile-time, as in ML or Haskell at run-time, as in Lisp, Smalltalk, or Python lets you apply operation to object only if object has everything the code requires explicit (generics) programmer specifies the type parameters explcitly mostly what I want to talk about today ------------------- Generics found in Clu, Ada, Modula-3, C++, Eiffel, Java 5, C# 2.0, ... C++ calls its generics "templates". Allow you, for example, to create a single stack abstraction, and instantiate it for stacks of integers, stacks of strings, stacks of employee records, ... template class stack { T[100] contents; int tos = 0; // first unused location public: T pop(); void push(T); ... } ... stack S; I could, of course, do class stack { void*[100] contents; int tos = 0; public: void* pop(); void push(void *); ... } But then I have to use type casts all over the place. Inconvenient and, in C++, unsafe. Lots of containers (stacks, queues, sets, strings, mappings, ...) in the C++ Standard Template Library (STL). Similarly rich libraries exist for Java and C#. (Also for Python and Ruby, but those use implicit parametric polymorphism with run-time checking, ala Lisp.) Implemented via macro expansion in C++ v1; built-in in Standard C++. (BTW: be warned when using nested templates in pre-C++'11: pair> won't work, because >> is a single token; you have to say pair >. Yuck. Fixed in the latest standard. Compilers vary in whether they support it yet.) ------------------- Some languages (e.g. Ada and C++) allow things other than types to be passed as template arguments: template class stack { T[N] contents; int tos = 0; public: T pop(); void push(T); ... } ... stack S; ------------------- Implementation C# generics do run-time instantiation ("reification"). When you say stack, the run-time system invokes the JIT compiler and generates the appropriate code. Don't box native types if they don't need to -- more efficient. Java doesn't do run-time instantiation. Internally everything is stack. You avoid the casts in the source code, but you have to pay for boxing of native types. And since the designers were unwilling (for backward compatibility reasons) to modify the VM, you're stuck with the casts in the generated code (automatically inserted by the compiler), even though the compiler knows they're going to succeed. Also, because everything is an Object internally, reflection doesn't work. The Java implementation strategy is known as "erasure" -- the type paremters are simply erased by the compiler. One more disadvantage: you can't say "new T()", where T is generic parameter, because Java doesn't know what to create. C++ templates are handled completely at compile time. More below. ------------------- CONSTRAINTS The problem: If I'm writing a sorting routine, how do I insist that the elements in the to-be-sorted list support a less_than() method? If I'm writing a hash table, how do I insist that the keys support a hash() method? If I'm writing output formatting code, how do I insist that objects support a to_string() method? Related question: Do I (can I) type-check the generic code, independent of any particular instantiation, or do I type-check the instantiations independently? C++ is very flexible: every instantiation is independently type-checked. Constraints are implicit: if we try to instantiate a template for a type that doesn't support needed operations, the instance won't type-check. Leads to REALLY messy error messages. Most other languages type-check the generic itself, so you don't get any instantiation-specific error messages. To support this, they require that the operations supported by generic parameter types be explicitly listed. Java and C# leverage interfaces for this purpose. Java example: public static void sort(T A[]) { ... if (A[i].compareTo(A[j]) >= 0) ... ... } ... Integer[] myArray = new Integer[50]; ... sort(myArray); Note that Java puts the type parameters right in front of the return type of the function, rather than in a preceding "template" clause. "Comparable" is a standard library interface that includes the compareTo() method. Wrapper class Integer implements Comparable. C# syntax is similar: static void sort(T[] A) where T : IComparable { ... if (A[i].compareTo(A[j]) >= 0) ... ... } ... int[] myArray = new int[50]; ... sort(myArray); C# puts the type parameter between the function name and the parameter list and the constraints after the parameter list. Java won't let you use int as a generic parameter, but C# is happy to; it creates a custom version of sort for ints. C++ doesn't require that constraints be explicit. template void sort(T A[], int A_size) {... (C++ can't figure out the size of an array, so you have to pass it in. Alternatively you could make it another generic parameter.) As noted in the book, bad things happen if a parameter "accidentally" supports a needed operation, in the "wrong way". If we instantiate sort on an array of C strings (char*s), for example, we get sorting by location in memory, not lexicographic order (C++ string objects compare lexicographically). Constraints are often specified explicitly in C++ by convention make a function parameter inherit from a standard base class e.g., sort(SortableVector A), where SortableVector inherits from both Vector and Comparator provide required operations as generic parameters e.g. sort >(foo* A, int len) provide required operations as ordinary parameters e.g. sort(foo* A, int len, bool (*less_than)()) make sort the operator() of a class for which less_than() is a constructor argument e.g. sort = new Sorter(bool (*less_than)()), where Sorter has an operator() You'll be doing all of these for the final assignment. ------------------- IMPLICIT INSTANTIATION Several languages, including C++, Java, and C#, will instantiate generic functions (not classes) as you need them, using roughly the same resolution mechanism used for overloading. (Actually, in C++ it requires unification, because of the generality of generic parameters, including nested templates and specialization.) ------------------- INTERACTION WITH SUBTYPE POLYMORPHISM These two play nicely together. If I derive "queue" from "list" I want subclasses. But I may also want generics: derive "queue" from "list". The subtle part is conformance of argument and return types. Supose I want to be able to sort things in Java that don't implement Comparable. I could make the comparator be a constructor argument instead of a generic argument (the 4th by-convention option in C++ above): interface Comparator { public Boolean ordered(T a, T b); } class Sorter { Comparator comp; public Sorter(Comparator c) { comp = c; } public void sort(T A[]) { ... if (comp.ordered(A[i], A[j])) ... ... } } class IntComp implements Comparator { public Boolean ordered(Integer a, Integer b) { return a < b; } } Sorter s = new Sorter(new IntComp()); s.sort(myArray); This works fine, but it breaks if I try class ObjComp implements Comparator { public Boolean ordered(Object a, Object b) { return a.toString().compareTo(b.toString()) < 0; } } Sorter s = new Sorter(new ObjComp()); s.sort(myArray); The call to new fails because we're passing a Comparator rather than a Comparator. This is fixed in Java using type wildcards: class Sorter { Comparator comp; public Sorter(Comparator c) { comp = c; } More on this on the PLP CD, section 8.4.4.