Unformatted text preview:

1Introduction to typesAmer DiwanOverview• This topic: what are types, kinds of types,representation of types (1-2 lectures)• Next topic: type checking, relationship betweentypes, information hiding (2 lectures)• Topic after next: polymorphism/OO (2 lectures)2Let’s think about the untyped world• Untyped universe: 1 type– e.g., in machine code, everything is a string of bits– e.g., in smalltalk, everything is an objectBut, ...• Types often arise naturally...– Bit strings in computer memory are organized intointegers, characters, instructions, ...– Objects in smalltalk are organized into rectangles,dictionaries, ...• But organized as sets of pairs, functions, ...• Even untyped universes of objects decomposenaturally into sets with uniform behavior3From untyped to typed worldsObjects naturally fall into groups but code can violate the groupsA type system is a suit of armor that “protects” the groupsintegersvalues between 1 and 10values between-1 and -10Why have types?• Correct use of variables can be checked• Types are valuable documentation• Disambiguation of operators can be done atcompile time• Accuracy control: yields space optimization andgives more information to compiler about legalvalues4A value-centric notion of types• A type is a collection of values...– ...,-100,...,0,...,100,...: integer– -128,...,0,...,128: char– {i=10, f=4.0},...,{i=20, f=5.0}: struct{ int i; float f};– {i=10, f=4.0},...,{i=20,g=‘a’}: ???• Not all sets of values make up meaningful types inprogramming languages• Which set of values make up meaningful types?So, which sets of values make up types?• When values have some commonality• When the type system of the language allows theset of values to be expressed!– Different languages allow different types: more init later!5Organizing types• Primitive types (e.g., int, boolean, ...)• User-defined types– Ordinal types• values in the type are ordered• e.g., int– Composite types• made by applying a type constructor (e.g., record) toone or more types– Others: e.g., Pointer types, procedure typesE.g., ordinal type:enumerations• TYPE Color = {red, green, blue};VAR i: Color;i := Color.green;• Since enumerations are ordinal types, can comparethe order between two values– e.g., ORD(i) < ORD(j)6Why have enumerations?• Instead of: TYPE Color = {red, green, blue}; VAR i: Color;• Could have: CONST red = 1; CONST green = 2; CONST blue = 3; VAR i: INTEGER;E.g. ordinal type:Subranges• TYPE Score = [0..100];VAR s: Score;s = 30;• Why have subranges?7Composite types• Further improve readability by allowing user todefine specialized types– Records– Variant records– Arrays– Sets– Pointers– Classes (later)structs, objects, datatypesC union,...arrays in Modula-3, Java, ...Pascal and Modula-3 setsPointers in C, C++, ...classes in Java, C++, M-3, ...Records• TYPE Point = RECORD x, y: INTEGER;END;• VAR p: Point;• p.x := 10; p.y := 20;p := Point(10, 20); // sometimes!8Representation of recordsx yp: Point32 bit32 bitp.x /* *(&p + 0) */p.y /* *(&p + 4) */sizeof(int) may depend on machine (depends on how the language defines it)Another exampleTYPE R = RECORD ch1: CHAR; v: INTEGER; ch2: CHAR; END;VAR r: R;ch1 vr: R8 bit32 bitch28 bitr.v /* *(&r + 1) */What’s the problem?9Efficiency concerns• On modern machines it is much faster to accessmemory of size w bytes if it is aligned on a wboundaryvr: R32 bitch1 ch2 32 bit32 bitWasteful in space but faster to accessModula-3 compilers will typically use the above representationunless the program specifies “packed”Field order in records• If a language allows a compiler to reorder fieldsthen we can use a good compromisech1 vr: R8 bit 32 bitch28 bitempty16 bitSince reordering interacts with things such as type equality andsubtyping, most languages don’t allow it10Variant records• Provides two or more alternative fields orcollections of fields, only one of which is valid atany given time• e.g.,union U { int i; float f;};U u;u.i = 10; u.f = 20.0;So what does it really look like?i fstruct { int i; float f; }i, funion { int i; float f; }The fields of a union share the same space!11A little problem• union U { int i; float f;};U u;u.i = 10;print(u.f)• What’s the problem?Discriminated union• A discriminated union contains a tag that ischecked on each field access and assignment• u.i = 10;u.tag = “i”;print(check u.tag = “f”, u.f);• Some languages such as Pascal have discriminatedunion12Representation of discriminated unionsi, funion { int i; float f; }tag10u.i = 10;“i”2.0u.f = 2.0;“f”Comparison of discriminated versus non-discriminated unions• Expressiveness• Simplicity• Ease of implementation• Efficiency13Arrays• Two ways of viewing arrays– A sequence of values– A mapping from an index to a value– (Some languages, e.g., Modula-3, emphasize thefirst view)• VAR a: ARRAY [1..100] OF INTEGER;a[5] = 10;...print(a[5]);Some variations in arrays• Are array sizes determined at compile time or atrun time?• Can the array size change dynamically at runtime?• How many dimensions does the array have?• Are array references checked for “out-of-bounds”errors?14When is array size determined, orfixed versus open arrays• Fixed arrays: size is fixed at compile time– e.g., a: ARRAY [1..100] OF INTEGER; or int a[100];– Are the two above arrays the same size?• Open arrays: size is not determined until run time– a := NEW (ARRAY OF INTEGER, n);– a = new int[n];– procedure sort(A:array[lower..upper] of real)Representation of fixed arraysa: ARRAY [1..100] OF INTEGER;1 2 1003..99a[i] => *(&a + (i-1))0 based arrays may be more efficient since they don’t need asubtraction15Representation of open arraysa := NEW (ARRAY OF INTEGER, n);0 1 n-1Does the above representation work for open arrays?A better representation of open arraysa := NEW (ARRAY OF INTEGER, n);0 1 n-1ndopevectorA dope vector contains all the information that one needs about an open arrayat run time16Can open arrays be allocated on thestack?procedure sort(A: array[l..u] of real) { int i, j; ...}What’s the problem here?ijmainsortdope vectorA’s elementsThe fixObservations:•Dope vector has a fixed size; elements have a compile-timeunknown size•Elements are accessed only by going through the dope vector:so we can place them anywhereijmainsortdope vectorA’s elements17Comparision of fixed versus open


View Full Document

CU-Boulder CSCI 3155 - Introduction to types

Download Introduction to types
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to types and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to types 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?