Chapter 5: Types - Types are the leaven of computer programming; they make it digestible

Programming Languages2nd editionTucker and NoonanChapter 5TypesTypes are the leaven of computer programming;they make it digestible. Robin Milner 5.1 Type Errors5.2 Static and Dynamic Typing5.3 Basic Types5.4 NonBasic Types5.5 Recursive Data Types5.6 Functions as Types5.7 Type Equivalence5.8 Subtypes5.9 Polymorphism and Generics5.10 Programmer-Defined Types A type is a collection of values and operations on those values.Example: Integer type has values ..., -2, -1, 0, 1, 2, ... and operations +, -, *, /, <, ...The Boolean type has values true and false and operations , , . Computer types have a finite number of values due to fixed size allocation; problematic for numeric types.Exceptions: Smalltalk uses unbounded fractions.Haskell type Integer represents unbounded integers.Floating point problems? Even more problematic is fixed sized floating point numbers: 0.2 is not exact in binary.So 0.2 * 5 is not exactly 1.0Floating point is inconsistent with real numbers in mathematics. In the early languages, Fortran, Algol, Cobol, all of the types were built in.If needed a type color, could use integers; but what does it mean to multiply two colors.Purpose of types in programming languages is to provide ways of effectively modeling a problem solution.5.1 Type ErrorsMachine data carries no type information.Basically, just a sequence of bits.Example: 0100 0000 0101 1000 0000 0000 0000 0000 0100 0000 0101 1000 0000 0000 0000 0000The floating point number 3.375The 32-bit integer 1,079,508,992Two 16-bit integers 16472 and 0Four ASCII characters: @ X NUL NUL A type error is any error that arises because an operation is attempted on a data type for which it is undefined.Type errors are common in assembly language programming.High level languages reduce the number of type errors.A type system provides a basis for detecting type errors.5.2 Static and Dynamic TypingA type system imposes constraints such as the values used in an addition must be numeric. Cannot be expressed syntactically in EBNF.Some languages perform type checking at compile time (eg, C).Other languages (eg, Perl) perform type checking at run time.Still others (eg, Java) do both. A language is statically typed if the types of all variables are fixed when they are declared at compile time.A language is dynamically typed if the type of a variable can vary at run time depending on the value assigned.Can you give examples of each? 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.Most dynamically typed languages associate a type with each value.5.3 Basic TypesTerminology in use with current 32-bit computers: Nibble: 4 bitsByte: 8 bitsHalf-word: 16 bitsWord: 32 bitsDouble word: 64 bitsQuad word: 128 bits In most languages, the numeric types are finite in size.So a + b may overflow the finite range.Unlike mathematics: a + (b + c)  (a + b) + cAlso in C-like languages, the equality and relational operators produce an int, not a Boolean An operator or function is overloaded when its meaning varies depending on the types of its operands or arguments or result.Java: a + b (ignoring size)integer addfloating point addstring concatenationMixed mode: one operand an int, the other floating point A type conversion is a narrowing conversion if the result type permits fewer bits, thus potentially losing information.Otherwise it is termed a widening conversion.Should languages ban implicit narrowing conversions?Why?5.4 Nonbasic TypesEnumeration:enum day {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday};enum day myDay = Wednesday;In C/C++ the above values of this type are 0, ..., 6.More powerful in Java:for (day d : day.values()) Sytem.out.println(d);PointersC, C++, Ada, PascalJava???Value is a memory addressIndirect referencingOperator in C: *Examplestruct Node { int key; struct Node* next;};struct Node* head; Fig 5.4: A Simple Linked List in C Bane of reliable software developmentError-proneBuffer overflow, memory leaksParticularly troublesome in C float sum(float a[ ], int n) {int i;float s = 0.0;for (i = 0; i<n; i++) s += a[i];return s; float sum(float *a, int n) {int i;float s = 0.0;for (i = 0; i<n; i++) s += *a++;return s;void strcpy(char *p, char *q) { while (*p++ = *q++) ;}strcpyPointer OperationsIf T is a type and ref T is a pointer:& : T → ref T* : ref T → TFor an arbitrary variable x:*(&x) = xArrays and Listsint a[10];float x[3][5]; /* odd syntax vs. math */char s[40];/* indices: 0 ... n-1 */Indexing Only operation for many languagesType signature[ ] : T[ ] x int → TExamplefloat x[3] [5];type of x: float[ ][ ]type of x[1]: float[ ]type of x[1][2]: float Equivalence between arrays and pointersa = &a[0]If either e1 or e2 is type: ref Te1[e2] = *((e1) + (e2))Example: a is float[ ] and i inta[i] = *(a + i)