Class 20: Type Equivalence

Held Wednesday, March 7, 2001

Summary

Today we consider issues of type equivalence. That is, when two types can be treated as equivalent for purposes of assignment and function/procedure calls.

Notes

• Sorry about the lack of notes for Monday's class.
• I've updated the syllabus. The biggest change is that there will be no class on the Friday before break. (Alternatively, you could have an hour exam; let me know what you think.)
• Quiz!

Overview

• Summary of current type knowledge
• Other types
• Type equivalence

Status

• Just to keep you posted, here are some of the thigns we've decided about type checking.
• Type checking has many uses, although there are two big ones.
  • Verifying that code is "correct" (e.g., that function calls have the correct number and types of parameters).
  • Deciding which code to generate (e.g., for arithmetic operations).
• We want to do two activities hand-in-hand:
  • Determining the "type" of each expression.
  • Determining whether that expression is used in a type-appropriate way.
• We know about many different types:
  • Basic types: integer, reals, strings, Booleans (in Pascal)
  • Procedure or Function types (from list of types to type)
  • Record types (list of name/type pairs)

Other Types

• Are there other types? Certainly.
  • Arrays
  • Enumerated types
  • Pointers
  • ...
• We'll need to think about what kinds of type checking we do for each. (At least in Pascal.)

Type Equivalence

• One of the key issues in language design is deciding whether two types are ``the same'' for purposes of calls and assignment.
• These questions often have to do with user-defined types.
• Consider the following type and variable declarations

  type
    t1 = record a: integer; b: real end;
    t2 = record a: integer; b: real end;
    t3 = record b: real; a; integer end;
    t4 = record c: integer; b: real end;
    t5 = record a: integer; b: real; c: integer; end;
    t6 = t1;
  var
    v1: t1;
    v2: t2;
    v3: t3;
    v4: t4;
    v5: t5;
    v6: t6;
    v7: record a: integer; b: real end;
    v8: record a: integer; b: real end;
  

• Which of v1 ... v7 can we assign to v1? (v1 := vi)
• Which of v1 ... v7 can we assign v1 to? (vi := v1)
• Can we assign v7 and v8 to each other?
• Pascal gives one set of specifications, but there are others possible (which depend on the language).
• We can ask similar questions about enumerated types, array types, and pointer types.
• Pointer types can introduce some fairly complicated questions, which may lead us to make different decisions about pointer types than we make about record types.