Typsystem och typkontroll

Kursen Kompilatorer och interpretatorer | Föreläsningar: 1 2 3 4 5 6 7 8 9 10 11 12


Det här är ungefär vad jag tänker säga på föreläsningen. Använd det för förberedelser, repetition och ledning. Det är inte en definition av kursinnehållet, och det ersätter inte kursboken.

Idag: Datatyper. Typsystem. Typkontroll.

Statiska och dynamiska kontroller

Some static checks: Examples:
int main() {
  int i;

  *i = 2; // invalid type argument of `unary *'
  break;  // break statement not within loop or switch
 e:
 e:       // duplicate label `e'
  return 0;
}

6.3 Type systems

Each expression is of a certain type. Examples from C: Basic types (int, char, etc.)
"Constructed" types (pointer to ... , array ... of ... , struct { ... })

Type expressions

A type expression is:
  1. A basic type (int, char, etc.)
  2. A type name (such as T after typedef int T;)
  3. A type variable (can be used directly in some languages: type XT = typeof(x); XT y;)
  4. A type constructor applied to one or more type expressions:
Representation. ASU-86 fig 6.2.
char x char -> pointer(integer)
C: int* f(char, char);

Type tree:

        ->
      /   \
     x     pointer
    / \       \
char   char  integer
Type DAG:
        ->
      /   \
     x     pointer
    ||        \
   char      integer

If you haven't seen it before: cdecl

cdecl> declare a as pointer to int
int *a
cdecl> declare a as array 10 of pointer to function returning double
double (*a[10])()
cdecl> explain int *(*foo)[8]
declare foo as pointer to array 8 of pointer to int

Type systems

Type system = a set of rules for assigning type expressions to the various parts of a program.

Static and dynamic checking of types

Everything can be checked dynamically. There are some things that can't be checked statically. Example:
class Djur { public: int x; virtual void f() { } };
class Hund : public Djur { public: int y; };
class Katt : public Djur { public: int z; };

void f(Djur* djur) {
  Hund* hund = dynamic_cast<Hund*>(djur);
  if (hund != 0)
    hund->y = 4711;
}

int main() {
  f(new Djur());
  f(new Hund());
  f(new Katt());
}

Strong and weak typing

Sound type system = allows us to determine statically (that is, at compile time) that type errors can't occur

Strongly typed language = the compiler can guarantee that the program will execute without type errors.

Specification of a simple type checker

A type checker implemented as a translation scheme that synthesizes the type of each expression, from the types of its subexpressions.

A simple language

Four basic types: integer, char, type_error, void
Arrays and pointers
Addition

Grammar (slighly modified from the one on ASU-86 page 349):

Program --> Declarations ; Expr
Declarations --> Declarations ; Declarations | id : Type
Type --> char | integer | array [ num ] of Type | *Type
Expr --> literal | num | id | Expr + Expr | Expr [ Expr ] | *Expr
A literal is a character constant, for example 'a'.

Example program (with a type error?):

n : integer;
i : integer;
a : array [256] of char;
n + a[i] + 7
Idea: Add an attribute type to each node in the parse tree!

A translation scheme, with semantic actions, can be used for type checking. This part of the translation scheme saves the type of a variable in the symbol table (ASU-86 Fig 6.4):

Type --> char { Type.type := char; }
Type --> integer { Type.type := integer; }
Type --> *Type1 { Type.type := pointer(Type1.type); }
Type --> array [ num ] of Type1 { Type.type := array(1..num.val, Type1.type); }
Declarations --> id : Type { addtype(id.entry, T.type); }
Program --> Declarations ; Expr
Declarations --> Declarations ; Declarations

Type checking of expressions

Explicit numbers are integers, etc:
Expr --> num { Expr.type := integer; }
Expr --> literal { Expr.type := char; }
Variables have the type they were declared as:
Expr --> id { Expr.type := lookup(id.entry); }
Adding two integers gives an integer, anything else is a type error:
Expr --> Expr1 + Expr2
  { if (Expr1.type == integer and Expr2.type == integer)
      Expr.type = integer;
    else
      Expr.type = type_error;
  }
Indexing into an array:
Expr --> Expr1 [ Expr2 ]
  { if (Expr2.type == integer and Expr1.type == array(s, t))
      Expr.type = t;
    else
      Expr.type = type_error;
  }

Type checking of statements

A statement has no value, so its type is void.

The while statement:

Stmt --> while ( Expr ) Stmt1
  { if (Expr.type == integer and Stmt1.type == void)
      Stmt.type == void;
    else
      Stmt.type == type_error;
  }
The expression statement from C:
Stmt --> Expr ;
  { if (Expr.type != type_error)
      Stmt.type == void;
    else
      Stmt.type == type_error;
  }

Type checking of functions

Grammar for function call:
Expr --> Expr1 ( Expr2 )
Add function declarations to the declaration part, for example with the type syntax int -> int:
f : int -> int;
f(7) + 3;
Grammar for the function type:
Type --> Type1 "->" Type2
Translation scheme for the function type:
Type --> Type1 "->" Type2
  { Type.type = function(Type1.type, Type2.type); }
Translation scheme for type checking a function call:
Expr --> Expr1 ( Expr2 )
  { if (Expr1.type == function(s, t) and Expr2.type == s)
      Expr.type == t;
    else
      Expr.type == type_error;
  }

6.3.2 Equivalence of type expressions

Learn the difference between: More structural equivalence in C -- m1 and m2 have the same type:
double m1[14][17];
double m2[14][17];
More structural equivalence in C:
typedef int A[10];
typedef int B[10];
typedef int C[11];

int main() {
  A a;
  B b;
  C c;
  A* ap;
  B* bp;
  C* cp;

  ap = &a;
  ap = &b;
  ap = bp;

  ap = cp; /* warning: assignment from incompatible pointer type */
  ap = &c; /* warning: assignment from incompatible pointer type */

  return 0;
}
Checking type equivalence:

C uses structural equivalence for all types except records ("structs"):

struct A { int foo; double fum; };
struct B { int blaj; double urko; };

struct A a;
struct B b;

a = b; /* error: incompatible types in assignment */
This is to aviod cycles in the type representation:
struct L {
  int foo;
  struct L* next;
};
But note that TA1 and TA2 are the same type (since both are A):
typedef struct A TA1;
typedef struct A TA2;

TA1 ta1;
TA2 ta2;

ta1 = ta2; // ok

Kursen Kompilatorer och interpretatorer | Föreläsningar: 1 2 3 4 5 6 7 8 9 10 11 12


Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se) 5 oktober 2007