1 of 26

Type Checking

2 of 26

Outline

  • Side effects and order of evaluation
  • Scopes and lifetimes
  • Types

2

3 of 26

Expressions and Statements

  • Expressions are used to produce values
    • Constants, variables, operators, function calls, etc.
    • Some expressions may have side effects: change the state of the memory (arguably, a bad idea)
  • Statements do not produce values, and are used only because of their side effects
    • E.g., an assignment statement
    • Expressions are evaluated, statements are executed

​

3

4 of 26

Side Effects of Expression Evaluation

  • Desirable principle: we can replace an expression with the r-value of this expression

x = 5; y = 1 + x++; if (y == x) printf("OK");

x = 5; y = 1 + 5; if (y == x) printf("OK");

    • Known as referential transparency
    • Not possible when expressions have side effects
  • Expressions in C
    • Operators = ++ -- += etc. have side effects
      • E.g., x=expr evaluates to the value assigned to x
      • E.g., a[v = x++] = y = z++ + w is a valid expression
    • No assignment statement, but expression statement
      • expr; – evaluate the expression and throw away the value

​

4

5 of 26

Order of Evaluation

  • Precedence and associativity are not enough
    • E.g., in a – f(b) – c*d will f(b) be evaluated before or after a? Will a – f(b) be evaluated before/after c*d?
      • What if f(b) has side effects – e.g., changes a, c, or d?
  • Order for function arguments: e.g., f(a, g(b), h(c))
  • The language semantics has to state this order
    • To clarify the behavior in the presence of side effects
    • To enable compiler optimizations: e.g., computing c*d before f(b) requires a register to remember the value during the call to f (may be bad for performance)
    • E.g., C does not specify order for operands/arguments (aim: performance) but Java does (aim: correctness)

​

5

6 of 26

Defined Order of Evaluation in C

  • Boolean expressions: e1 && e2 and e1 || e2
    • e1 is evaluated before e2
    • Short-circuit semantics: e2 may never be evaluated
      • &&: if e1 evaluates to false; ||: if e1 evaluates to true
  • Comma operator: e1 , e2
    • e1 is evaluated before e2: e.g., a=f(b) , c=g(d)
  • Conditional operator: e1 ? e2 : e3
    • e1 is evaluated before e2 and e3
  • At the end of an expression statement: e1; e2;
    • e1 is evaluated before e2

​

​

​

6

7 of 26

Scopes

Global variables

  • Lifetime: entire execution
  • Storage: global segment of memory

Local variables

  • Lifetime: execution of function (or nested scope)
  • Storage: thread's call stack

Dynamically allocated memory

  • Lifetime: from new to free/delete/GC
  • Storage: heap

7

8 of 26

Types

  • Organization of untyped values
    • Untyped universes: bit strings, S-expr, …
    • Categorize based on usage and behavior
  • Type = set of computational entities with uniform behavior
  • Constraints to enforce correctness
    • Check the applicability of operations
      • Should not try to multiply two strings
      • Should not use a character value as a condition of an if-statement
      • Should not use an integer as a pointer

8

9 of 26

Examples of Type Checking

  • Built-in operators should get operands of correct types
  • Type of left-hand side must agree with the value on the right-hand side
  • Procedure calls: check number and type of actual arguments
  • Return type should match returned value

9

10 of 26

Static Typing

  • Statically typed languages: expressions in the code have static types
    • static type = claim about run-time values
    • Types are either declared or inferred
    • Examples: C, C++, Java, ML, Pascal, Modula-3, Quandary
  • A statically typed language typically does some form of static type checking
    • E.g., at compile time Java checks that the [] operator is applied to a value of type “array”
    • May also do dynamic (run-time) checking
      • e.g., Java checks at run time for array indices out of bounds and for null pointers

10

11 of 26

Dynamic Typing

  • Dynamically-typed languages: entities in the code do not have static types
    • Examples: Lisp, Scheme, CLOS, Smalltalk, Perl, Python
    • Entities in the code do not have declared types, and the compiler does not try to infer types for them
  • Dynamic type checking
    • Before an operation is performed at run time
    • E.g., in Scheme: (+ 5 #t) fails at run time, when the evaluation expects to see two numeric atoms as operands of +

11

12 of 26

Type (and memory) safety

  • Type-safe languages: type-incorrect operations are not performed at run time
    • Things cannot “go wrong”: no undetected type errors
    • Certain run-time errors are possible but clearly marked as such
      • i.e. array index out of bounds, null pointer
    • C/C++: type unsafe
    • Java: type safe
  • Independent of static vs. dynamic
    • Lisp, Scheme, Python: dynamically typed; type safe
    • Forth: dynamically typed; type unsafe

12

13 of 26

Examples of Types

  • Integers
  • Arrays of integers
  • Pointers to integers
  • Records with fields int x and int y
    • e.g., “struct” in C
  • Objects of class C or a subclass of C
    • e.g., C++, Java, C#
  • Functions from any list to integers

13

14 of 26

Numeric Types

  • Varied from language to language
  • C does not specify the ranges of numeric types
    • Integer types: char, short, int, long, long long
      • Includes “unsigned” versions of these
    • Floating-point types: float, double, long double
  • Java specifies the ranges of numeric types
    • byte: 8-bit signed two's complement integer [-128,+127]
    • short: 16-bit signed two's complement integer [-32768,+32,767]
    • int: 32-bit signed two's complement integer [-2147483648,+2147483647]
    • long: 64-bit signed two's complement integer [-9223372036854775808, +9223372036854775807]
    • float/double: single/double-precision 32-bit IEEE 754 floating point
    • char: single 16-bit Unicode character; minimum value of '\u0000' (or 0) and a maximum value of '\uffff' (or 65535)

14

15 of 26

Enumeration Types

  • C: a set of named integer constant values
    • Example from the C specification

enum hue { chartreuse, burgundy, claret=20, winedark };

/* the set of integer constant values is { 0, 1, 20, 21 } */

enum hue col, *cp;

col = claret; cp = &col;

if (*cp != burgundy) …

  • Java: a fixed set of named items (not integers)

enum Day { SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY }

    • In reality, it is like a class: e.g., it can contain methods

​

15

16 of 26

Types as Sets of Values

  • Integers
    • Any number than can be represented in 32 bits in signed two’s-complement
    • “type int” = { -231, …, 231 - 1 }
  • Class type (not the same as a class)
    • Any object of class C or a subclass of C
    • “type C” = set of all instances of C or of any transitive subclass of C (“class C” is just a blueprint for objects)
  • Subtypes are subsets: T2 is a subtype of T1 if T2’s set of values is a subset of T1’s set of values

16

17 of 26

Monomorphism vs. Polymorphism

  • Greek:
    • mono = single
    • poly = many
    • morph = form
  • Monomorphism
    • Every computational entity belongs to exactly one type
  • Polymorphism
    • A computational entity can belong to multiple types

17

18 of 26

Types of Polymorphism

parametric

universal

inclusion (subset)

polymorphism

overloading

ad hoc

coercion

18

19 of 26

Types of Polymorphism

parametric

universal

inclusion (subset)

polymorphism

overloading

ad hoc

coercion

19

20 of 26

Coercion

  • Values of one type are silently converted to another type
    • e.g. addition: 3.0 + 4 : converts 4 to 4.0
      • int × int → int or real × real → real
  • In a context where the type of an expression is not appropriate
    • either an automatic coercion (conversion) to another type is performed automatically
    • or if not possible: compile-time error

20

21 of 26

Coercions

  • Widening
    • coercing a value into a “larger” type
    • e.g., int to float, subclass to superclass
  • Narrowing
    • coercing a value into a “smaller” type
    • loses information, e.g., float to int

21

22 of 26

Types of Polymorphism

parametric

universal

inclusion (subset)

polymorphism

overloading

ad hoc

coercion

22

(operators or functions)

23 of 26

Types of Polymorphism

parametric

universal

inclusion (subset)

polymorphism

overloading

ad hoc

coercion

23

24 of 26

Parametric Polymorphism: Generics in Java

package java.util;

public interface Set<E> extends Collection<E> { …

Iterator<E> iterator();

boolean add(E e);

boolean addAll(Collection<? extends E> c); }

class Rectangle { … }

class SwissRectangle extends Rectangle { … }

Set<Rectangle> s = new HashSet<Rectangle>();

s.add(new Rectangle(1.,2.)); s.add(new SwissRectangle(3.,4.,5));

Set<SwissRectangle> s2 = new TreeSet<SwissRectangle>();

s2.add(new SwissRectangle(6.,7.,8)); s.addAll(s2);

24

25 of 26

Types of Polymorphism

parametric

universal

inclusion (subset)

polymorphism

overloading

ad hoc

coercion

25

26 of 26

Inclusion (Subset) Polymorphism

  • Subtype relationships among types
    • Defined by “Y is subset of X” (i.e., set inclusion)
  • A computational entity of a subtype may be used in any context that expects an entity of a supertype
  • Typical examples
    • Imperative languages: record types
    • Object-oriented languages: class types

26