An identifier (e.g.
+) has several meanings depending on the type at which it is used (polymorphic?). The entry in the symbol table for this identifier must contain attribute records for all meanings in the scope.
In previous lectures we have discussed static (otherwise known as lexical) scoping, which is where the scope of a declaration is determined by the physical structure of the program.
However, some languages support dynamic scoping which is where the scope of a declaration is determined by the control flow (current declaration is last declaration encountered during execution). Based on the slides it sounds like this isn’t a great idea as it makes programs hard to understand. But is ‘sometimes useful’ because it allows implicit arguments. Implicit arguments are useful in Haskell so that you don’t have to pass all variables to auxiliary functions; but I think that’s a fringe case.
Identification – a summary
- Identification involves checking scope rules and connecting identifiers in abstract syntax trees to attribute records.
- Most modern programming languages use static scoping, with nested scopes (e.g. not just a global namespace!).
- Symbol table is a dictionary used during identification.
- A standard symbol table is a stack of tables to allow scope.
- Efficiency of the symbol table data structure is directly proportional to efficiency of compiler.
- Language features (classes, modules) often make scoping complicated.
Type checking checks rules about types against expressions. At their simplest types are sets of values. The main purpose of having a type checking is to prevent errors at run time by noticing programming errors at compile time. You have strong and weakly typed languages. Strongly typed languages have certain ‘guarantees’ that a specified set of errors cannot occur.
Static vs. Dynamic type systems
A static type system:
- Part of the language syntax
- Compile time checks
- Some run time checks
A dynamic type system:
- Values carry type information at run time
- All type checks are performed at run time
Static is better because..
- You can generate better code that takes less space and is more specific at compile time.
- You can find errors at compile time.
- Types can be used to describe interfaces between modules (imagine Ada’s packages).
No doubt there is also ‘Dynamic is better because..’ somewhere…
A language is polymorpgic if it allows language constructs to have more than one type; overloading or subtyping. If you did FUN then you know a lot about polymorphism and why it is handy. Allows for generic data structures and functions.
Basic type checking
- Fill in type attribute(s) for identifier.
- Recursively type check components.
- Recursively type check components.
- Check that types of expression components meet type rules. e.g. the
if exp then a else bis of type
Infer the type of the expression bottom-up:
- Recursively type check subexpressions and check that these meet type rules
- The type rule and types of subexpressions then determine the type of the expression
e.g. a literal
idcan be inferred from the attribute record connected to
id(exp1, ... ,expn)is more complicated. It involves type checking all expressions then obtaining the types of the parameters of
idand checking that they are equivalent to the expressions’ types. Then the type of the whole expression is the result of type
id. This makes more sense if you just think about it intuitively.
New types are usually either distinct or synonymous. Most languages use a mixture.
Obviously you can have recursive types. Bear in mind in C it only is permitted if you use pointers. Other languages do this too, apparently it’s t stop infinite comparison (e.g. if you went
a == b it would loop).
Type conversions and subtyping
Some types may be able to convert into other types based on a set of rules. For example adding an
int and a
float together. Usually the type checker inserts the transformation at compile time. You can also do explicit conversion e.g.
Already discussed this briefly, pretty obvious what overloading is, the slides are a bit confusing looking.
Type checking – a summary
- Types are sets of values
- Static v.s. dynamic type systems
- Why have a static type system?
- Type checking, bottom-up type inference
- Type equivalence
- Polymorphism, subtyping, and overloading