CIS-4050 Homework #4: Type Checking

Reading: Section 4.5 in the text is on symbol tables and their representation. Section 5.4 says more about how nested scopes and related features can be represented. Section 5.5 talks about types and type checking issues.

In this assignment you will implement some type checking logic in the AGC semantic analyzer.

Start by updating your clone of the Augusta project:

Switch to the main branch (if not already on it) using: git switch main.
Update the main branch using: git pull.
Create a new branch for this assignment using: git switch -c homework-04.

Part 1: Complications to Ignore

In Ada (and August), the Boolean data type is an ordinary enumeration type declared like this:

  type Boolean is (False, True);

This declaration is effectively built into the compiler (or in the "root scope" as the AGC symbol table thinks about it).

This means that looking up the type of the boolean literals "False" and "True" should follow, in theory, automatically from AGC's normal lookup behavior for enumeration types. Unfortunately, handling enumerators correctly is complicated and outside the scope of this assignment. To provide a temporary work-around, AGC's grammar uses a BOOLEAN_LITERAL token that can have the text of either "False" or "True." A BOOLEAN_LITERAL is a kind of primary expression alongside other primary expressions like INTEGER_LITERAL and IDENTIFIER. This handling of Boolean is only a temporary fix; once AGC knows how to look up enumerators properly, Boolean literals can be treated as any other IDENTIFIER.

You do not need to implement the symbol table changes necessary to deal with enumerators properly.

Part 2: The Type Checking Algorithm

Because Ada (and Augusta) use named type equivalence, the type checking algorithm, at least for now, is simple. Here are the main points:

BOOLEAN_LITERALS have type Boolean
INTEGER_LITERALS have type Integer (for now). Note that in "real" Ada/August integer literals have the special type "Universal Integer," which is compatible with all integer types. We will try to ignore that for now.
We will ignore REAL_LITERALS and the floating point types.
IDENTIFIERS have the type as declared. Consult the symbol table, but see below about subtypes.
The arithmetic operators PLUS, MINUS, MULTIPLY, DIVIDE, and REM cannot be applied to the Boolean type.
The relational operators EQUAL, NOT_EQUAL, LESS, LESS_EQUAL, GREATER, and GREATER_EQUAL cannot be applied to the Boolean type.
The logical operators AND, OR, and NOT can only be applied to the Boolean type.
For all the binary operators, the types of both operands must match. There are no implicit conversions to worry about.

Subtypes are special because they are not really new types. If a variable is of a subtype, its type is actually the parent of the subtype. However, since subtypes can have other subtypes as parents, it is necessary to unwind that chain to find the actual type. For example:

  subtype A is Integer range 1 .. 100;
  subtype B is A range 10 .. 50;
  X : B;

When looking up the name X it will be returned as having "type" B. The representation of type B (which you also need to look up) will show that it is a subtype of A. It is now necessary to look up the representation of A to see that it is a subtype of Integer. The representation of Integer shows that it is not a subtype of anything else, so the type of X, for purposes of type checking is Integer.

This means all subtypes of a type are compatible and can be mixed in expressions.

Think about writing a method that takes a type name that could actually be a subtype name and returns the type associated with that name. In many cases your method would return the same type it is given, but in other cases it will need to do the "unwinding" I describe above.

Technically, this should be done in the symbol table to avoid weird (and incorrect) behavior such as the following:

  procedure Hello is
     type A is Integer range 1 .. 100;
     subtype B is A range 10 .. 50;
  begin
     declare
        subtype A is Integer range 1 .. 10;
        X : A;
        Y : B;
     begin
        X := Y; -- This should be an error!
                -- X is Integer, but Y has type A which is incompatible.
     end;
  end;

In this example a simple implementation that looks up parent types starting at the same scope as the identifier will find the subtype A as the parent of B, which is wrong. The parent lookup should continue from the scope where the subtype is found. Doing this properly will require implementing the lookup in the symbol table class. That is outside the scope of this assignment.

Part 4: Implementation

All of your changes should be focused on the SemanticAnalyzer class. I don't believe you will need to change any other files.

Proceed as follows:

Implement the visitation methods for all of the expression forms, including left_expression. The implementation of and_expression is already done and can serve as a model for the others.
You will need to write a new (private) method that looks up the type from a subtype as I described above. Subtypes do not participate in type checking, only their parent types do.
Implement visitation functions for the conditional statement and the iteration statement to verify that the conditional expression has type Boolean.
Report all errors via the Reporter.

Submit your SemanticAnalyzer.scala file to Canvas