CS 460 Notes 06

Lecture

For CharAt, the type must be a string type.

PHASE 4 NOTES

S -> E E -> E + F | F F -> id | (E)

Ex:

E ->

LOOK AT CANVAS NOTES FOR MORE DETAILS

Transition terminals are used/useful for shifting

Reductions in states: $I_1$ - accept $I_2$ - $I_3$ - $I_7$ - $I_8$ -

When doing a reduction, if the input that you’re reading is not found in the FOLLOW set,

Readings

Chapter 7 Type Checking

Type checking ensures all operators are compatible w/ their operands.

Two approaches to type checking:

1. static type checking - performs type checking at compile time
2. dynamic type checking - performs type checking at runtime

In statically typed languages, variables and parameters are bounds to types at compile time; their use are also checked at compile time to assure there are no type errors. Statically typed languages also declare variables before they are used–when declared, they are bound to a type.

In dynamically typed languages, there is no binding. A variable’s type is determined by the values assigned to it–which happens at runtime.

Tradeoffs with both approaches typically involve the flexibility and type safety.

Strongly typed - all type errors canbe detected at runtime Weakly typed - expressions w/ pointer arthimetic cannot be type checked at compile time.

NOTE: a variable of superclass type can hold a reference to an object of subclass type.

Type Safe - there are no type errors. If a program is written in a strongly typed language, then it is considered to be type safe; if a program is written in a language that are type safe, then the lagnauge is strongly typed.

No dynamically typed language can be type safe–neither can any useful OOP language.

A type has a set of values $v$ and a set of operations $o$. Operations in $o$ are applicable to the values found in $v$

For example: A type $int$ (32-bit) has a set of possible values ${-2147483648, … , -2, -1, 0, 1, 2, … , 2147483647}$ and has a set of operations ${ +, -, *, /, %, … }$

Type system - collection of types that has a set of rules for associating types w/ expressions, variables, and other entities that can have a type.

Sound - invalid programs are rejected Complete - valid programs are accepted

Page 367 for more info about sound and complete

Equal - Two types $T_1$ and $T_2$ are considered equal if they have the same type

Type Equivalent - Given two types $T_1$ and $T_2$, they are type equivalent if any value of type $T_1$ can be assigned to a variable of type $T_2$, and any value of $T_2$ can be assigned to a variable of $T_1$.

Look at examples on page 368

Atomic Types

Typically referred as a primitive type, it is a type that is not made up of other types–it is built into the language. Examples: integers, doubles, booleans, characters, byte, etc.

Type Constructors

Type Constructor - a mechanism that allows for the creation of new constructed types that is based on the existing atomic/other constructed types. Ex: LL, trees, graphs, struct

NOTE: no two fields in a record can have the same name–it is not a type checking issue.

Arrays

It is an ordered list that is indexable by integral values, starting at $0$ and going to $n-1$ if it contains $n$ elements. Base Type - Each element within an array must have the same type.

By definition, an array is a pair consisting of the base type and index set. $Array(base type, [low..high])$

Array(int, [0..9]) = int a[10]

Refiable type - type whose type information is fully available at runtime. Does not have all its info available at runtime.

Constructed Types

There are two approaches to determine type equivalence for constructed types:

1. Name equivalence - types have the same name
2. Structural equivalence - types have the same structure

Example: Records (structs) A value of a record type is an ordered set of values that are compatible w/ the types of the record.

struct s {
  int a;
  double d;
  char c;
};

Can be initialized as one of the following:

// order does not matter since the fields are named.
struct s myS = { .a = 10, .d = 10.5, .c = 'd' };

// order matters since fields are NOT named
struct s myS = { 10, 10.5, 'd' };

When using typedef, declarations would be of the same type–this is an example of declaration equivalence.

Summary