More on Scoping. Type Checking

29th January 2010 (Absent)

These are lecture notes from my Computer Science course, not a general reference for "More on Scoping. Type Checking"

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.

Dynamic Scoping

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

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…

Polymorphism

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

A declaration

Fill in type attribute(s) for identifier.
Recursively type check components.

A statement

Recursively type check components.
Check that types of expression components meet type rules. e.g. the exp in if exp then a else b is of type bool.

An expression

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 32 or "hello" is obvious.
an id can be inferred from the attribute record connected to id.
an id(exp1, ... ,expn) is more complicated. It involves type checking all expressions then obtaining the types of the parameters of id and 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

New types are usually either distinct or synonymous. Most languages use a mixture.

Recursive Types

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. float(3).

Overloading

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