Principles of Programming LanguagesTypesTypes (cont.)Type SystemType System(cont.)Type System (cont.)PolymorphismPolymorphism(cont.)Slide 9Slide 10Kinds of PolymorphismKinds of Polymorphism(cont.)Slide 13Slide 14Slide 15Slide 16Slide 17ML: Strong Typing & PolymorphismML (cont.)Slide 20ML: Polymorphic Reference TypesML: Reference Types (cont.)ML: Static TypingML & -CalculusML & -Calculus (cont)Slide 26C SC 520 Principles of Programming Languages1Principles of ProgrammingLanguagesLecture 04Types and PolymorphismC SC 520 Principles of Programming Languages2Types•What is a type? An equivalence class of objects/valuesDenotational view: a type is a set (of values): Pascaltype weekday = (sun, mon, tue, wed, thu, fri, sat);Constructive view: a type is the result of an expression consisting of primitive types operated upon by type constructors: Adatype computer is recordserial : array (1..10) of integer;age: integer;end record;Abstraction view: a type is an interface, providing a set operations on objects of the type; an abstract data type (ADT): Pascal: pred(), succ(), <, =, >Class declaration{ , , , , , , }Weekday sun mon tue wed thu fri sat=C SC 520 Principles of Programming Languages3Types (cont.)•What has a type?Literals 1.25 ‘abc’ Variables var x: integer;Expressions x:int + y ML type intInduced by types of variables, literals, operators (casting ops included), and any implicit coercion (conversion) rules Objects Stack<int> s;Functions -fun area(r) = 3.141582818*r*r; val area = fn : real -> real;References int& x; x:ref int;Pointers int i = 3; int& r = i; int* p = &r;C SC 520 Principles of Programming Languages4Type System•Type definition rulesDeclaration (naming): introduce new name & bind to scopeDefinition (description):Primitive: booleans, characters, integers, fixedpoint, floating pointEnumeration: Ada type weekday is (sun, … ,sat);Subtype: subtype weekend is weekday range sat..sun;Composite: record, union, array, reference, list (type “operators”)Function: C++: int max(int a, int b){return a>b?a:b;}Derived: Ada: type mass is new REAL;•Type equivalence rulesName equivalenceEach definition a new typeEquivalent only if declared as same primitive or pre-defined typeAda distinct types: a,b: array(1..10) of BOOLEAN;Declaration equivalenceSame declaration implies same type (example above is dec. equiv.)C SC 520 Principles of Programming Languages5Type System(cont.)Structural Equivalence: have same type-operator expression•Type compatibility rulesArgument/parameter compatibility; assignment compatibilityTypes might be different but compatible; rules differ widelyAda : a subtype is compatible with a supertype & arrays of same size & base type are compatibleC: short int s; unsigned long int l; … ; s = l;C: void* p; int* q; … ; q = p;Coercion: implicit type conversion defined by language ( cast)Type Checking: verifying a program adheres to type compatibility rules (e.g. lint a type checker for a weakly typed C)Strong typing: prohibits an op when incompatibility existsAda strongly typed. Bliss untyped. ANSI C in middleStatic type checking: compile time (Ada, C++)Dynamic type checking: late binding (Lisp, Scheme, Smalltalk)C SC 520 Principles of Programming Languages6Type System (cont.)•Type Inference RulesRules for typing an expression given the types of its componentsType of x = y; is type of xType of b?a:b is the (common) type of a, b etc, etcAda: “con” & “cat” (both array[1..3] of char) returns array[1..6] of charSubranges x:INTEGER range 0..40; y:INTEGER range 10..20; type of x + y ? Can be complex, and involve coercionRecall PL/I example with fixed bin and fixed dec operandsSome inferences impossible at compile timeInference is a kind of “evaluation” of expressions having coarse values; types have their own arithmeticC SC 520 Principles of Programming Languages7Polymorphism•A polymorphic subroutine is one that can accept arguments of different types for the same parametermax(x,y){ max = x>y?x:y } could be reused for any type for which > is well-defined•A polymorphic variable(parameter) is one that can refer to objects of multiple types. ML: x : ‘a•True (or “pure”) polymorphism always implies code reuse: the same code is used for arguments of different types.•What polymorphism is not:Not overloading. Not generics. Not coercion.All 4 aim at off-loading effort from programmer to translator, but in different waysC SC 520 Principles of Programming Languages8Polymorphism(cont.)•Overloading An overloaded name refers to several distinct objects in the same scope; the name’s reference (denotation) is resolved by context. Unfortunately sometimes called “ad hoc polymorphism”(!)C++int j,k; float r,s;int max(int x, int y){ return x<=y?y:x }float max(float x, float y){ return y>x?y:x }… max(j,k); // uses int maxmax(r,s); // uses float maxEven constants can be overloaded in Ada:type weekday is (sun, mon, …);type solar is (sun, merc, venus, …);planet: solar; day: weekday;day := sun; planet := sun; -- compatibleday := planet; -- type errorC SC 520 Principles of Programming Languages9Polymorphism(cont.)•Generic subroutines A generic subroutine is a syntactic template containing a type parameter that can be used to generate different code for each type instantiatedAdagenerictype T is private;with function “<=“(x, y : T) return Boolean;function max(x,y : T) return T isbegin if x <= y then return y; else return x; end if;end min;function bool_max is new max(BOOLEAN,implies); function int_max is new max(INTEGER,”<=“);C SC 520 Principles of Programming Languages10Polymorphism(cont.)•Coerced subroutine arguments A coercion is a built-in compiler conversion from one type to anotherFortranfunction rmax(x,y) real xreal yrmax=xif (y .GT. x) rmax=yreturnendIn k=rmax(i,j) causes args to be coerced to floating point & return value truncated to integerAlthough same code is used for both arg types, this is not true polymorphismC SC 520 Principles of Programming Languages11Kinds of Polymorphism•Pure polymorphism: a single subroutine can be applied to arguments of a variety of typesParametric polymorphism: the type value is passed explicitly as an argument. There is
View Full Document