CSCE 434 Lecture 24

« previous | Friday, October 18, 2013 | next »

Begin Exam 2 content

Lecture Slides

Type Checking

A type is a memory blueprint (size, layout, etc.)

Helps identify errors

• incompatible operands for an operator
• correct number of parameters to a function call

Type checking occurs between parsing and intermediate code generation phase

Each operator and expression in a program has a type:

• basic: int, float, char, etc.
• constructed: arrays, sets, pointers, functions, structs

Type system is a collection of rules for assigning type expressions to variables

• e.g. If both operands of an arithmetic function (addition, subtraction, multiplication, etc.) are integers, then the result is of type integer

Type checker implements this type system.

Type Expressions

1. Type of a language construct
2. basic types (with addition of typeError, which signals an error, and void, which denotes untyped statement.
3. type names given to type expressions (think typedef)
4. variables for unknown types (like in Haskell)
5. type constructors:

Type Constructors

Build new types by combining basic types; can be recursive.

arrays

if $T$ is a type expression, then $array(I,T)$ is a type expression denoting the type of an array with elements of type $T$ and an index set $I$ (usually a range).

products

If $T_{1}$ and $T_{2}$ are types, then cartesian product $T_{1}\times T_{2}$ is also a type expression

Denotes "member" types by associating names to types: e.g. $(\mathrm {varName} \times integer)$

records

Similar to product, but internally, records have named fields

Example: $record((\mathrm {address} \times integer)\times (\mathrm {lexeme} \times array(1\ldots 15,char)))$

functions

Maps input types to an output type.

Static vs. Dynamic

Static type-checking occurs at compile-time.

Dynamic type-checking occurs at runtime.

int i;
int[30] xs;

xs[i];  // i cannot be guaranteed to be within [0,30] at runtime

type system is sound if it eliminates need for dynamic type checking since it can be guaranteed statically that these errors cannot occur.

A strongly typed language guarantees compiler will accept only program that executes without type errors (e.g. Java)

Type-Checking Statements

Using AST structure,

1. assign types to leaf nodes (int, string, float, etc.)
2. recursively propagate values up tree.

S
  : id '=' E
    {
      S.type = (id.type == E.type) ? void : typeError;
    }
  | 'if' E 'then' S1
    {
      S.type = (E.type == boolean) ? S1.type : typeError;
    }
  | 'while' E 'do' S1
    {
      S.type = (E.type == boolean) ? S1.type : typeError;
    }
  | S1 ';' S2
    {
      S.type = (S1.type == void) ? void : typeError;
    }
  ;

Type-Checking Functions

Capture arguments and return type:

$T_{1}\to T_{2}$ (function accepting $T_{1}$ and returns $T_{2}$)

applying argument types gives return type

def sequiv s,t
  # basic types
  s == t

  if s == array(s1, s2) and t == array(t1, t2)
    return sequiv(s1,t1) and sequiv(s2,t2)
  else if s == s1 * s2 and t == t1 * t2
    return sequiv(s1, t1) and sequiv(s2, t2)
  end
end

Type Equivalence

• Easy for basic types (int is equivalent to int)
• Structural equivalence for constructors

def sequiv(s,t):
   if same_basic_type(s, t):
      return true
   elif s == "array(s1,s2)" and t == "array(t1,t2)":
      return sequiv(s1,t1) and sequiv(s2,t2)
   elif s == "s1 x s2" and t == "t1 x t2":
      return sequiv(s1,t1) and sequiv(s2,t2)
   # ...
   else:
      return false

Symbol Tables

Associates values or attributes (e.g. types and values) with names

Entries are:

• variables
• functions
• literal constants and strings
• source text labels

Stores information for the compiler

• Name
• Type
• Dimension information
• Declaring procedure
• Lexical level of declaration (scope)
• storage class (base address)
• offset in storage
• if a record, pointer to structure table
• if parameter, by reference or by value
• other aliases
• if function, number and type of arguments

UNIX utility nm will spit out all symbol table information.