C 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/values◆ Denotational view: a type is a set (of values): Pascal" type 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 int◆ Induced 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 rules! Declaration (naming): introduce new name & bind to scope! Definition (description):◆ Primitive: booleans, characters, integers, fixedpoint, floating point◆ Enumeration: 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 rules! Name equivalence◆ Each definition a new type◆ Equivalent only if declared as same primitive or pre-defined typeAda distinct types: a,b: array(1..10) of BOOLEAN;! Declaration equivalence◆ Same 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 rules! Argument/parameter compatibility; assignment compatibility! Types might be different but compatible; rules differ widely◆ Ada : a subtype is compatible with a supertype & arrays of same size & base type are compatible◆ C: 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 exists" Ada strongly typed. Bliss untyped. ANSI C in middle◆ Static 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 Rules! Rules for typing an expression given the types of its components◆ Type of x = y; is type of x◆ Type of b?a:b is the (common) type of a, b etc, etc◆ Ada: “con” & “cat” (both array[1..3] of char) returns array[1..6] of char! Subranges x:INTEGER range 0..40; y:INTEGER range 10..20; type of x + y ? ! Can be complex, and involve coercion◆ Recall PL/I example with fixed bin and fixed dec operands! Some inferences impossible at compile time! Inference 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 parameter! max(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 max! Even 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 instantiated! Adagenerictype 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 another! Fortranfunction rmax(x,y) real xreal yrmax=xif (y .GT. x) rmax=yreturnend! In k=rmax(i,j) causes args to be coerced to floating point & return value truncated to integer! Although 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 types! Parametric polymorphism: the type value is passed explicitly as an argument. There is a type called type in CLU:sorted_bag = cluster[t:type] is create, insert, …where t has lt,eq: proctype(t,t) returns (bool);…wordbag := sorted_bag[string]; -- create clusterwb: wordbag := wordbag$create(); -- instance…wordbag$insert(wb, word); -- mutate instanceC SC 520 Principles of Programming Languages12Kinds of Polymorphism(cont.)! Type variable polymorphism: a type signature with type variables is derived for
View Full Document