# CSC321: Programming Languages CSC321: Programming Languages Chapter 5: Types 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 Type Errors Static and Dynamic Typing Basic Types NonBasic Types Recursive Data Types Functions as Types

Type Equivalence Subtypes Polymorphism and Generics Programmer-Defined Types CSC321: Programming Languages 5-1 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. CSC321: Programming Languages

5-2 Type Problems 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.0 Floating point is inconsistent with real numbers in mathematics. CSC321: Programming Languages 5-3

Purpose of Types 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. CSC321: Programming Languages 5-4 Data Interpretation Machine data carries no type information. Basically, just a sequence of bits. Example: 0100 0000 0101 1000 0000 0000 0000 0000

The floating point number 3.375 The 32-bit integer 1,079,508,992 Two 16-bit integers 16472 and 0 Four ASCII characters: @ X NUL NUL CSC321: Programming Languages 5-5 Type Errors 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. CSC321: Programming Languages

5-6 Type Checking A 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 (e.g., C). Other languages (e.g., Perl) perform type checking at run time. Still others (e.g., Java) do both. CSC321: Programming Languages 5-7 Static and Dynamic Typing 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? CSC321: Programming Languages 5-8 Strongly 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.

Most dynamically typed languages associate a type with each value. CSC321: Programming Languages 5-9 Basic Types Terminology in use with current 32-bit computers: Nibble: 4 bits Byte: 8 bits Half-word: 16 bits Word: 32 bits Double word: 64 bits Quad 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)+c

Also in C-like languages, the equality and relational operators produce an int, not a Boolean CSC321: Programming Languages 5-10 Overloading 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 add floating point add string concatenation Mixed mode: one operand an int, the other floating point, or one string and the other int CSC321: Programming Languages

5-11 Type Conversion 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? C++/Java: Explicit narrowing conversion Implicit widening conversion How? CSC321: Programming Languages 5-12

Non-basic Types Enumeration: 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); CSC321: Programming Languages 5-13 Pointers

C, C++, Ada, Pascal Java??? Value is a memory address Indirect referencing Operator in C: * Example: A Simple Linked List in C struct Node { int key; struct Node* next; }; struct Node* head; CSC321: Programming Languages 5-14

Pointer Operations If T is a type and ref T is a pointer: & : T ref T * : ref T T For an arbitrary variable x: *(&x) = x Increment/decrement String Copy void strcpy(char *p, char *q) { while (*p++ = *q++) ; } CSC321: Programming Languages 5-15 Problems with Pointers

Bane of reliable software development Error-prone Buffer overflow, memory leaks Particularly troublesome in C float sum(float a[ ],int n) { int i; float s = 0.0; for (i = 0; i

float sum(float *a,int n) { int i; float s = 0.0; for (i = 0; i

Dangling reference may be caused by Deallocation operations: a storage that is being pointed to by a pointer has been deallocated. Procedure/function/method returns: the address of a local variable in a procedure is returned as the return value. Consider the following situation (C/C++): CSC321: Programming Languages 5-17 Arrays A set of elements, but different languages have different ways to deal with arrays Basically, an array has the following attributes: Data type the type of all elements Dimension number of dimensions: 1-dim, 2-dim, 3-dim, etc Range of dimensions lower and upper

bound for each dimension Subscripts index. Most languages use integer, but others such as Pascal/Ada allow any discrete types CSC321: Programming Languages 5-18 Arrays Layout 1-dim array: consecutive locations High-dim array: Row-major layout: consecutive locations arranged row by row e.g. a: a[0,0], a[0,1], a[0,2], a[1,0], a[1,1], a[1,2], a[2,0], a[2,1], a[2,2] Column-major layout: arranged column by column e.g. a: a[0,0], a[1,0], a[2,0], a[0,1], a[1,1], a[2,1], a[0,2], a[1,2], a[2,2]

CSC321: Programming Languages 5-19 Arrays Element Accessing Element notation: C/C++, Java, Algol: a[i][j][k] Pascal: a[i, j, k] Fortran: a(i, j, k), same as a function. Actually, Fortran treats accessing array elements as performing function evaluation Pointer accessing: C/C++ can use pointers to access array elements CSC321: Programming Languages 5-20

Arrays and Pointers Equivalence between arrays and pointers: a = &a If either e1 or e2 is type: ref T: e1[e2]=*((e1)+ (e2)) Example: a is float[ ] and i int: a[i] = *(a + i) double a; double *b; b = &a; // assign the base address of a to b b++; // move b to the next location: a

b + i; // move b to the next i-th location: a[i+1] CSC321: Programming Languages 5-21 Arrays Indexing Index computation: Loc Assume: base the location of the first element low the lower bound upp the upper bound w the length of one element 1-dim: Loc(a[i]) = base + w*(i-low) = (base low *w) + i*w = c + i*w, where c = base low*w is a constant 2-dim: Loc(a[i,j]) = base + w*[ r*(i-low1) + (j-low2) ]

= base - w*( r*low1 + low2) + w*(r*i + j) where r = the number of rows above a[i,j], which is (upp2-low2 + 1) 3-dim: Loc(a[i,j,k]) = base + w*[r2*(r1*(i-low1) + (j-low2)) + (k-low3)] where r1 = (upp2-low2+1), r2 = (upp3-low3+1) ?? CSC321: Programming Languages 5-22 Arrays Binding Name-size binding bound evaluation: how many storage cells should be allocated to an array Static binding static evaluation: fixed size, determined at compile time, allocated at load time Advantages: easy; efficient Disadvantages: inflexible, waste storage Dynamic binding dynamic evaluation: changeable size,

determined at run time, allocated dynamically E.g. Java: Create: Declare: double a[]; a = new double; a = new double; Extendable arrays: APL, SNOBOL, Perl Java also has a kind of extendable array: Vector v = new Vector(5); CSC321: Programming Languages 5-23 Arrays Binding

Semi-dynamic binding evaluation upon procedure entry: Ada, Pascal, C/C++, Java The size (range of dimension) is a parameter. Once the parameter is determined, the array size is fixed E.g. C/C++: double fun(int n) { double a[n]; } Ada: declare m, n: Integer; begin declare type Matrix is array(Integer range<>, Integer range<>) of Real; a: Matrix(1..m, 1..n); begin end end CSC321: Programming Languages

5-24 Array Attributes Some languages treat array as object/package, and maintain its attributes E.g. Java: length --a.length the size of a Ada: range: arange Lower bound: afirst Upper bound: alast With these attributes, when an array is passed as a parameter, do not need to specify the number of elements in the array However, some languages have to specify the length as a parameter E.g. in C, array is passed by reference (call-by-reference) and does

not have the length attribute. CSC321: Programming Languages 5-25 Strings A special kind of array Now so fundamental, directly supported. In C, a string is a 1D array with the string value terminated by a NUL character (value = 0). In Java, Perl, Python, a string variable can hold an unbounded number of characters. Libraries of string operations and functions.

Comparison, selection of substring, searching, matching (Most languages) Replacement, appending, substring deletion (SNOBOL) Concatenation: produce a new string Java: String (static) and StringBuffer (dynamic) CSC321: Programming Languages 5-26 Structures/Records Composed from simpler data items Each data item (field) has a name Data items may have different types (recall array, all elements must be in the same type) Access to fields mostly uses .(dot) expression

Pascal: type Date = record day: Integer; month: Integer; year: Integer; end var adate: Date; Access: adate.day C/C++: struct Date { int day; int month; int year; } C: struct Date adate; C++: Date adate;

Access: adate.day CSC321: Programming Languages 5-27 Structures/Records The order of fields in the record has no effect on the meaning When a variable of record is declared, it is allocated storage Record assignment is to assign all fields in a record Collection of elements of different types Used first in Cobol, PL/I Absent from Fortran, Algol 60 Common to Pascal-like, C-like languages Omitted from Java as redundant CSC321: Programming Languages

5-28 Comparison of Arrays and Records Component: all elements in an array have the same type, while components (fields) of a record may be different Access: array elements are accessed by subscripts and element locations are determine at run time, while record components are accessed by dot expression and component names are determined at compile time Assignment: array assignment is to assign the base location, while record assignment is to assign all components CSC321: Programming Languages 5-29

Unions C: union type union = record Pascal: case-variant case b : boolean of record true : (i : integer); Logically: multiple false : (r : real); views of same end; var tagged : union; storage begin tagged := Useful in some (b => false, r => 3.375); systems applications put(tagged.i); -- error

end CSC321: Programming Languages 5-30 Simulated union type class Value extends Expression { // Value = int intValue | boolean boolValue Type type; int intValue; boolean boolValue; Value(int i) { intValue = i; type = new Type(Type.INTEGER); } Value(boolean b) { boolValue = b; type = new Type(Type.BOOLEAN); } } CSC321: Programming Languages

5-31 Recursive Data Type Type definition refers to another type that refers to the current type definition E.g. type link = cell; // refer to cell type cell = record data: integer; next: link; // refer to link end; CSC321: Programming Languages 5-32 Dynamic Data Type

With dynamic data structures, you can not only operate on the data items in the structure, but also change the structure Usually constructed with static data structures (such as arrays and records) and pointers E.g. Linked lists, Trees The basic components of these structures are records that contain pointers: nodes. Usually, each node has two parts: data items, and links (pointers/references) CSC321: Programming Languages 5-33 Functions as Types Pascal example: function newton(a, b: real; function f: real): real;

Know that f returns a real value, but the arguments to f are unspecified. Java example public interface RootSolvable { double valueAt(double x); } public double Newton(double a, double b, RootSolvable f); CSC321: Programming Languages 5-34 Type Names and Equivalence Type names Each type may or may not have a name, such as int, Integer, Char, etc. are type names; while array [0..9] of integer is an

anonymous type.Name equivalence Type equivalence Name equivalence Structural equivalence CSC321: Programming Languages 5-35 Type Name Equivalence Name equivalence: have the same name type Pure name equivalence: exactly same name Transitive name equivalence: if S is equivalent to T which is equivalent to U, then S is equivalent to U Type expression equivalence: A type name is equivalent to itself.

Two type expressions are equivalent if they are formed by applying the same constructor to equivalent expressions. CSC321: Programming Languages 5-36 Type Structural Equivalence Two type expressions are structurally equivalent if and only if they are equivalent under the following three rules A type name is structurally equivalent to itself Two types are structurally equivalent if they are formed by applying the same type constructor to structurally equivalent types After a type declaration, type n = T, the type name n is structurally equivalent to T Examples

integer is structurally equivalent to integer Types S and T are structurally equivalent if they are declared as type S = array [0..9] of integer; type T = array [0..9] of integer; Types S and integer are structurally equivalent if S is declared as: type S = integer; CSC321: Programming Languages 5-37 Type Equivalence struct complex { float re, im; }; struct polar { float x, y; }; struct { float re, im; } a, b;

struct complex c, d; struct polar e; int f, g; which are equivalent types: a, b, c, d, e, f, g? CSC321: Programming Languages 5-38 Type Equivalence Implementations Pascal uses name equivalence, but ambiguous. Modula-2 (the successor of Pascal) defines two types S and T to be compatible if S and T are the same name, or S = T is a type declaration: type S = T; or type T = S; or One is a subrange of the other; or Both are subranges of the same basic types

C uses structural equivalence for all types except records (struct) CSC321: Programming Languages 5-39 Subtypes A subtype is a type that has certain constraints placed on its values or operations. In Ada subtypes can be directly specified. subtype one_to_ten is Integer range 1 .. 10; type Day is (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday); subtype Weekend is Day range Saturday .. Sunday; type Salary is delta 0.01 digits 9 range 0.00 .. 9_999_999.99; subtype Author_Salary is Salary digits 5 range 0.0 .. 999.99;

Integer i = new Integer(3); ... Number v = i; ... Integer x = (Integer) v; //Integer is a subclass of Number, // and therefore a subtype CSC321: Programming Languages 5-40 Polymorphism and Generics A function or operation is polymorphic if it can be applied to any one of several related types and achieve the same result. An advantage of polymorphism is that it enables code reuse.

CSC321: Programming Languages 5-41 Polymorphism Comes from Greek, and means having many forms Example: overloaded built-in operators and functions + - * / == != ... Ada, C++: define + - ... for new types Java overloaded methods: number or type of parameters Example: class PrintStream print, println defined for: boolean, char, int, long, float, double, char[ ] String, Object Java: + also used for string concatenation Java: instance variable, method: e.g., name, name( ) CSC321: Programming Languages

5-42 Generics Ada generics: generic sort (Figs. 5.10 and 5.11) parametric polymorphism type binding delayed from code implementation to compile time procedure sort is new generic_sort(integer); Java generic classes C/C++ templates CSC321: Programming Languages 5-43 Programmer-defined Types Recall the definition of a type:

A set of values and a set of operations on those values. Structures allow a definition of a representation Problems: Representation is not hidden Type operations cannot be defined Solutions: ADT Abstract Data Types CSC321: Programming Languages 5-44
{"ft_lang_label":"__label__en","ft_lang_prob":0.7763049,"math_prob":0.94388545,"size":16718,"snap":"2021-04-2021-17","text_gpt3_token_len":4067,"char_repetition_ratio":0.16937897,"word_repetition_ratio":0.015636634,"special_character_ratio":0.26073694,"punctuation_ratio":0.17910448,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.95251006,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-01-24T00:04:13Z\",\"WARC-Record-ID\":\"<urn:uuid:e62e0d92-4938-46c9-b38b-7cc3ccdfc3cf>\",\"Content-Length\":\"290184\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:1c1baebc-115f-4c93-9d6d-4ab6d0b7258a>\",\"WARC-Concurrent-To\":\"<urn:uuid:dbc06d64-c8a4-461d-b228-afe712492807>\",\"WARC-IP-Address\":\"172.67.212.84\",\"WARC-Target-URI\":\"https://slideread.com/slide/csc321-programming-languages-ahohdk\",\"WARC-Payload-Digest\":\"sha1:OHUGDEK7EWQHBIRXT7VXXQOVYDUD5CRY\",\"WARC-Block-Digest\":\"sha1:H7YZXKTKAG5HAFKNZ7U4PYTHI3VJ66QL\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-04/CC-MAIN-2021-04_segments_1610703538741.56_warc_CC-MAIN-20210123222657-20210124012657-00120.warc.gz\"}"}