CSE 130 Lecture Notes, May 22, 2002

CSE130 LECTURE NOTES

May 22, 2002

LECTURE GIVEN BY PROF. GARY COTTRELL

WHY TYPES ARE IMPORTANT

Now we know what the range of possibilities is for types in programming languages. In all programming languages, every value has a certain type, and the compiler and/or the runtime system knows what the type is.

Why is it so important to give each value a type? There are several answers to this question.

(1) The implementation of operations like addition is different depending on the types of the operands.

(2) If the programmer gives operands of the wrong type, this is an error that should be reported to her or him.

(3) The type of a variable is important documentation about the software. For example, it is very useful to know whether <2.5,3.7> is of type rectangular or polar, where

type rectangular = record x, y: real end;
type polar = record r, theta: real end;

THE ISSUE OF TYPE EQUIVALENCE

When doing type-checking, one big issue arises: how to decide whether one type is a legal substitute for another. Let's look at two cases.

Case 1: Think of the rectangular and polar types above, and consider a procedure that displays a point on the screen:

procedure plot (p: rectangular);
begin
(* code *)
end;

Should it be legal to call plot(q) where q is a variable of type polar? Intuitively, the plot procedure will probably do the wrong thing with q.

Case 2: Consider a procedure that just writes out a tuple for debugging purposes:

procedure debugwrite (v: record x,y: real end);
begin
writeln(x,y);
end;

Intuitively, this procedure should be a legal operation to perform on variables of type rectangular and also of type polar.

STRUCTURAL VERSUS NAME TYPE EQUIVALENCE

Every programming language has to choose between satisfying case 1 or case 2 behavior.

Satisfying the first case is called name equivalence for types. Two variables are defined to have equivalent types if and only if they have literally the same type, i.e. the names of their types are the same.

Example: Consider

type alpha = array [1..10] of real;
var a,b: alpha;
c,d: array [1..10] of real;

Here a and b have equivalent types, and so do c and d, but alpha is not equivalent to the type of c and d.

Satisfying the second case is called structural equivalence for types. Two variables are defined to have equivalent types if their types are constructed in similar ways.

The definition of structural equivalence needs to be made more concrete. It is actually a recursive definition:

each primitive type is structurally equivalent to itself
if the component types of two composite types are equivalent, and combined in the same way, then the composite types are equivalent.

When Pascal was first designed by Prof. Niklaus Wirth, he failed to say what type equivalence policy the language should follow. Early implementations of the language were therefore incompatible.

FIRST SPECIAL CASE OF TYPE EQUIVALENCE: COERCION

Every programming language also has some ad hoc type equivalence rules that cover special cases.

The most common rule is that values of type integer can be converted to values of type real when necessary. This is called coercion.

This rule can be ambiguous: consider <missing example>

Note that coercion is different from overloading, where the same name is used for different operations. For example the minus sign is usually overloaded to mean four different operations: integer and real negation (a unary operation) and subtraction (a binary operation).

A programming language can have overloading without having coercion!

SECOND SPECIAL CASE OF TYPE EQUIVALENCE: SUBTYPES

In many languages, the sets of values of some types are subsets of the sets of values of other types. These types can be called subtypes. Typically every operation that is legal for the bigger type is legal for the subtype. (This property of these operations is called inclusion polymorphism--see later.)

For example in Pascal, consider

type smallint = -256 .. 255;
var x: smallint;

Here smallint is a subtype of integer, so despite name equivalence, all integer operations can be used on x.

TYPE EQUIVALENCE AND OBJECT-ORIENTED PROGRAMMING

An abstract data types (ADT) should clearly have name equivalence, because its implementation (i.e. the structure of its concrete type) is invisible to its users.

Similarly, an object-oriented class should have name equivalence. But by default a class method should also be available for objects of a child class. This is a form of overloading.

In many OO PLs the programmer can choose the visibility of methods, i.e. choose which overloading is allowed. This really allows the programmer to choose the exact notion of type equivalence to use for each class, which makes some language mechanisms (subtypes for example) redundant. A subtype is really just a derived class.

EXPRESSIONS

Reminder: Traditional programming languages have three big categories of program fragments: definitions, expressions, and commands. For example x[2*j+1] := sqrt(u+v) is a command with two expressions embedded in it, namely 2*j+1 and sqrt(u+v).

Definitions:

An expression is a program fragment that gives a value when evaluated.
A value is a member of a type.
Evaluation is the process of computing the value denoted by an expression.

Expressions involve operators, literal constants (which are also called literals), and identifiers.

An identifier is a name that denotes a value which is obtained by "looking up" the declaration of the identifier. Typically identifiers can be either constants or variables. Parameter identifiers can be either also.

LITERALS

A literal expression is one that directly denotes a value. Conceptually, there is only one, immediate, step of evaluation. Some examples of literals of various types are:

2.5E2
'!'
"prompt?"

Depending on the language, strings may or may not be legal literals, and may or may not be written differently from characters.