Class 19: Type checking, continued

Held Monday, October 12, 1998

Notes

• I believe that some of you took the exam over the weekend, but I heard no questions. I'll take that as a good sign.
• Some of you working on the next homework assignment were having trouble getting the number of the character in the input text. You should be able to get that value from the lexer (I believe it's yychar).
• The weekend evaporated, so I don't have homeworks graded. If you'd like to go over your assignments with me, I'd be happy to do so in a one-on-one format.
• In case you hadn't noted it already, int and string are simply identifiers and not keywords.

Environments, Revisited

• Recall that environments map identifiers to information about variables, functions, and types.
• In the previous class, I made some odd suggestions as to the interpretation of environment declarations. Did anyone confirm or reject them?
  • The section on ``Scope Rules'' in the Tiger book gives the details I used.

Implementing Environments

• How do we implement environments in our compiler? Note that an environment is a form of table as it maps keys (identifiers) to values (their type).
• In designing an implementation, we need to be careful to consider the ways in which we use environments. In particular, we extend environments when we enter a new scope and we then ``undo'' those extensions when we leave a scope.
• We may decide that it's best to be ``pure'' in our use and implementation of tables (so that an extension to a table does not affect the underlying table) or impure.
• For impure representations, we'll need to be careful about undoing extensions. For pure representations, the old version still exists, and can be easily restored.
• In impure representations, we typically use a hash table.
• In pure representations, we use a search tree.

Type checking, revisited

• Recall that our goal is to type check the abstract syntax tree. This means that we want to verify that all of the assignments, function calls, and related things are valid.

Some details

• How do we type check? It depends on the particular structure we're checking.
• For assignment statements, we can look up the type of the variable being assigned to and compute the type of the expression being assigned.
  • Note that this means that we need to be able to compute a type for any expression.
• For variable declarations, we need to check the explicit type (if given), as well as the type of the expression being assigned.
• For function declarations, we need to check the explicit return type (if given), as well as the implicit return type (given by return statements). We also need to gather the types of the parameters.
• Note that some things have ``no type'' (or at least no value).

Examples

• For each of the following, we'll summarize the expected check that is done.
• Done today
  • Variable expressions
  • Integer constants
  • String constants
  • Assignments
• To do next class
  • Nil
  • Function calls
  • Operator application
  • Record constants
  • Sequences
  • Conditionals
  • Loops
  • Breaks
  • For loops
  • Let expressions
  • Array constants

History

• Created Monday, October 12, 1998, primarily from notes from the previous class.
• On Wednesday, October 14, 1998, I moved some uncovered topics to the next outline.