DOC PREVIEW
UA CSC 520 - Principles of Programming Languages

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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/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


View Full Document

UA CSC 520 - Principles of Programming Languages

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Recursion

Recursion

18 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Principles of Programming Languages
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Principles of Programming Languages and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Principles of Programming Languages 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?