Handouts csc 441 Compiler Construction Muhammad Bilal Zafar vcomsats learning Management System

The applications of types can be grouped under checking and translation. Type checking uses logical rules to reason about the behavior of a program at run time. Specifically, it ensures that the types of the operands match the type expected by an operator. For example the && operator in Java expects its two operands to be booleans, the result is also of type boolean.

• 
  From the type of a name, a compiler can determine the storage that will be needed for that name at run time.
  
• 
  Type information is also needed to calculate the address denoted by an array reference, to insert explicit type conversions, and to choose the right version of an arithmetic operator, among other things.
  
• 
  The actual storage for a procedure call or an object is allocated at run time, when the procedure is called or the object is created.
  
• 
  Types have structure, which is represented using type expressions.
  

Many type-checking rules have the form if two type expressions are equal then return a certain type else error. Potential ambiguities arise when names are given to type expressions and the names are then used in subsequent type expressions. The key issue is whether a name in a type expression stands for itself or whether it is an abbreviation for another type expression.

When type expressions are represented by graphs, two types are structurally equivalent if and only if one of the following conditions is true:

• 
  They are the same basic type.
  
• 
  They are formed by applying the same constructor to structurally equivalent types.
  
• 
  One is a type name that denotes the other.
  

• 
  The language comes with a type system, i.e., a set of rules saying what types can appear where.
  
• 
  The compiler assigns a type expression to parts of the source program.
  
• 
  The compiler checks that the type usage in the program conforms to the type system for the language.
  

There are two forms of type checking.

• 
  Type synthesis where the types of parts are used to infer the type of the whole. Ex, integer + real = real.
  
• 
  Type inference is very slick. The type of a construct is determined from usage. This permits languages like ML to check types even though names need not be declared.
  

Type conversion rules vary from language to language. The rules for Java distinguish between widening conversions which are intended to preserve information, and narrowing conversions which can lose information.

An overloaded symbol has different meanings depending on its context. Overloading is resolved when a unique meaning is determined for each occurrence of a name. In a DAG representing a type expression, we assign an integer index called a value number, to each node then we construct a signature for a node consisting of its label and the value numbers of its children, in order from left to right. The signature for a function consists of the function name and the types of its arguments. The assumption that we can resolve overloading based on the types of arguments is equivalent to saying that we can resolve overloading based on signatures. It is not always possible to resolve overloading by looking only at the arguments of a function. In Ada, instead of a single type, a sub expression standing alone may have a set of possible types for which the context must provide sufficient information to narrow the choice down to a single type.

Revision