31-10-2012, 04:33 PM
Automata & Compiler Design
Automata.ppt (Size: 144 KB / Downloads: 29)
Recursive Types in C
C Policy: avoid cycles in type graphs by:
Using structural equivalence for all types
Except for records -> name equivalence
Example:
struct cell {int info; struct cell * next;}
Name use: name cell becomes part of the type of the record.
Use the acyclic representation
Names declared before use – except for pointers to records.
Cycles – potential due to pointers in records
Testing for structural equivalence stops when a record constructor is reached ~ same named record type?
Overloading Functions & Operators
Overloaded Symbol: one that has different meanings depending on its context
Example: Addition operator +
Resolving (operator identification): overloading is resolved when a unique meaning is determined.
Context: it is not always possible to resolve overloading by looking only the arguments of a function
Set of possible types
Context (inherited attribute) necessary
Type Variables
Why: variables representing type expressions allow us to talk about unknown types.
Use Greek alphabets α, β, γ …
Application: check consistent usage of identifiers in a language that does not require identifiers to be declared before usage.
A type variable represents the type of an undeclared identifier.
Type Inference Problem: Determine the type of a language constant from the way it is used.
We have to deal with expressions containing variables.
Type Checking Polymorphic Functions
Distinct occurrences of a p.f. in the same expression need not have arguments of the same type.
deref ( deref (q))
Replace α with fresh variable and remove (αi, αo)
The notion of type equivalence changes in the presence of variables.
Use unification: check if s and t can be made structurally equivalent by replacing type vars by the type expression.
We need a mechanism for recording the effect of unifying two expressions.
A type variable may occur in several type expressions.