Types and Parametric PolymorphismReading AssignmentTypeUses for Types Operations on Typed ValuesType Errors Static vs. Dynamic TypingStrong vs. Weak TypingCompile- vs. Run-Time CheckingExpressiveness vs. SafetyRelative Type Safety of Languages Enumeration TypesPointersArraysStringsStructuresUnionsRecursive DatatypesFunctions as TypesType EquivalenceSubtypesOverloadingFunction Overloading in C++Overloading Infix Operators in C++Operator Overloading in MLUser-Defined Infix Operators in MLPolymorphism and GenericsPolymorphism vs. OverloadingType Checking vs. Type InferenceMotivationML Type InferenceHow Does This Work? Application and Abstraction Types with Type Variables Using a Polymorphic FunctionRecognizing Type ErrorsAnother Type Inference Example Polymorphic DatatypesType Inference with RecursionType Inference SummaryCosts of Type InferenceInformation From Type InferenceParam. Polymorphism: ML vs. C++Example: Swap Two ValuesImplementationAnother ExampleML Overloading and Type InferenceSummaryslide 1Vitaly ShmatikovCS 345Types andParametric Polymorphismslide 2Reading AssignmentMitchell, Chapter 6C Reference Manual, Chapters 5 and 6slide 3TypeA type is a collection of computable values that share some structural propertyExamples• Integers• Strings• int → bool• (int → int) →bool“Non-examples”• {3, true, λx.x}• Even integers• {f:int → int | if x>3 then f(x) > x*(x+1)}Distinction between sets that are types and sets that are not types is language-dependentslide 4Uses for Types Program organization and documentation• Separate types for separate concepts– Represent concepts from problem domain • Indicate intended use of declared identifiers– Types can be checked, unlike program commentsIdentify and prevent errors• Compile-time or run-time checking can prevent meaningless computations such as 3 + true - “Bill”Support optimization• Example: short integers require fewer bits• Access record component by known offsetslide 5Operations on Typed ValuesOften a type has operations defined on values of this type• Integers: + - / * < > … Booleans: ∧∨¬…Set of values is usually finite due to internal binary representation inside computer• 32-bit integers in C: –2147483648 to 2147483647• Addition and subtraction may overflow the finite range, so sometimes a + (b + c) ≠ (a + b) + c• Exceptions: unbounded fractions in Smalltalk, unbounded Integer type in Haskell• Floating point problemsslide 6Type Errors Machine data carries no type information• 01000000010110000000000000000000 means…• Floating point value 3.375? 32-bit integer 1,079,508,992? Two 16-bit integers 16472 and 0? Four ASCII characters @ X NUL NUL?A type error is any error that arises because an operation is attempted on a value of a data type for which this operation is undefined• Historical note: in Fortran and Algol, all of the types were built in. If needed a type “color,” could use integers, but what does it mean to multiply two colors?slide 7Static vs. Dynamic TypingType system imposes constraints on use of values• Example: only numeric values can be used in addition• Cannot be expressed syntactically in EBNFLanguage can use static typing• Types of all variables are fixed at compile time• Example?… or dynamic typing• Type of variable can vary at run time depending on value assigned to this variable• Example?slide 8Strong vs. Weak TypingA language is strongly typed if its type system allows all type errors in a program to be detected either at compile time or at run time• A strongly typed language can be either statically or dynamically typed!Union types are a hole in the type system of many languages (why?)Most dynamically typed languages associate a type with each valueslide 9Compile- vs. Run-Time CheckingType-checking can be done at compile time• Examples: C, ML f(x) must have f : A → B and x : A… or run time• Examples: Perl, JavaScriptJava does bothBasic tradeoffs• Both prevent type errors• Run-time checking slows down execution• Compile-time checking restricts program flexibility– JavaScript array: elements can have different types– ML list: all elements must have same type Which gives betterprogrammer diagnostics?slide 10Expressiveness vs. SafetyIn JavaScript, we can write function likefunction f(x) { return x < 10 ? x : x(); }Some uses will produce type error, some will notStatic typing always conservative if (big-hairy-boolean-expression) then f(5);else f(10);Cannot decide at compile time if run-time error will occur, so can’t define the above functionslide 11Relative Type Safety of Languages Not safe: BCPL family, including C and C++• Casts, pointer arithmeticAlmost safe: Algol family, Pascal, Ada • Dangling pointers.– Allocate a pointer p to an integer, deallocate the memory referenced by p, then later use the value pointed to by p – No language with explicit deallocation of memory is fully type-safeSafe: Lisp, ML, Smalltalk, JavaScript, and Java • Lisp, Smalltalk, JavaScript: dynamically typed • ML, Java: statically typedslide 12Enumeration TypesUser-defined set of values• enum day {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday};enum day myDay = Wednesday;• In C/C++, values of enumeration types are represented as integers: 0, ..., 6More powerful in Java:• for (day d : day.values())System.out.println(d);slide 13PointersC, C++, Ada, PascalValue is a memory address• Remember r-values and l-values?Allows indirect referencingPointers in C/C++• If T is a type and ref T is a pointer: & : T → ref T * : ref T → T *(&x) = xExplicit access to memory via pointers can result in erroneous code and security vulnerabilitiesslide 14ArraysExample: float x[3][5];Indexing []• Type signature: T[ ] x int → T• In the above example, type of x: float[ ][ ], type of x[1]: float[ ], type of x[1][2]: floatEquivalence between arrays and pointers• a = &a[0]• If either e1 or e2 is type: ref T, then e1[e2] = *((e1) + (e2))• Example: a is float[ ] and i int, so a[i] = *(a + i)slide 15StringsNow so fundamental, directly supported by languagesC: a string is a one-dimensional character array terminated by a NULL character (value = 0)Java, Perl, Python: a string variable can hold an unbounded number of charactersLibraries of string operations