Class 21: Type Equivalence

Held Wednesday, October 16, 2002

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

• Are there more questions on phase 2 of the project?
• As some of you noticed, ssh isn't working well with erdos. Mr. Stone is looking into the problem.

Overview

• Summary of current type knowledge
• Other types
  • Type coercion
• 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)
  • Arrays (might be functions, might be something else)
  • Enumerated types (subrange or explicit list)

Other Types

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

Type Coercion

• At times, as part of the type checking endeavor, we may convert a value of one type to a value of another type.
• The most typical example is to go from integers to floating point numbers.
• This coercion can be done explicitly (with some operation) or implicitly.
• There are different possible meanings to a coerced value:
  • Convert the value, according to some rule.
  • Interpret the bits in the value as the bits of the coerced type.
  • ...
• Side note: Are the standard coercions we do always safe?

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, similar to those you examined in lab yesterday

  type
    t0 = record a: integer; b: integer end;
    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
    v0: t0;
    v1: t1;
    v2: t2;
    v3: t3;
    v4: t4;
    v5: t5;
    v6: t6;
    v7: record a: integer; b: real end;
    v8,v9: record a: integer; b: real end;
  

• Which of v0 ... v0 can we assign to v1? (v1 := vi)
• Which of v0 ... v9 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.