TypesStatic Semantic AnalysisTypes and Static Semantic AnalysisStephen A. EdwardsColumbia UniversityFall 2011Part ITypesData TypesWhat is a type?A restriction on the possible interpretations of a segment of memoryor other program construct.Useful for two reasons:Runtime optimization: earlier binding leads to fewer runtimedecisions. E.g., Addition in C efficient because type of operandsknown.Error avoidance: prevent programmer from putting round peg insquare hole. E.g., In Java, can’t open a complex number, only a file.Are Data Types Necessary?No: many languages operate just fine without them.Assembly languages usually view memory as undifferentiated arrayof bytes. Operators are typed, registers may be, data is not.Basic idea of stored-program computer is that programs beindistinguishable from data.Everything’s a string in Tcl including numbers, lists, etc.C’s Types: Base Types/PointersBase types match typical processorTypical sizes: 8 16 32 64char short int longfloat doublePointers (addresses)int*i; /*i is a pointer to an int*/char**j; /*j is a pointer to a pointer to a char*/C’s Types: Arrays, FunctionsArrayschar c[10]; /*c[0] ... c[9] are chars*/double a[10][3][2]; /*array of 10 arrays of 3 arrays of 2 doubles*/Functions/*function of two arguments returning a char*/char foo(int, double);C’s Types: Structs and UnionsStructures: each field has own storagestruct box {int x, y, h, w;char*name;};Unions: fields share same memoryunion token {int i;double d;char*s;};Composite Types: RecordsA record is an object with a collection of fields, each with apotentially different type. In C,struct rectangle {int n, s, e, w;char*label;color col;struct rectangle*next;};struct rectangle r;r.n = 10;r.label = "Rectangle";Applications of RecordsRecords are the precursors of objects:Group and restrict what can be stored in an object, but not whatoperations they permit.Can fake object-oriented programming:struct poly { ... };struct poly*poly_create();void poly_destroy(struct poly*p);void poly_draw(struct poly*p);void poly_move(struct poly*p, int x, int y);int poly_area(struct poly*p);Composite Types: Variant RecordsA record object holds all of its fields. A variant record holds only oneof its fields at once. In C,union token {int i;float f;char*string;};union token t;t.i = 10;t.f = 3.14159; /*overwrites t.i*/char*s = t.string; /*returns gibberish*/Applications of Variant RecordsA primitive form of polymorphism:struct poly {int x, y;int type;union { int radius;int size;float angle; } d;};If poly.type == CIRCLE, use poly.d.radius.If poly.type == SQUARE, use poly.d.size.If poly.type == LINE, use poly.d.angle.Layout of Records and UnionsModern processors have byte-addressable memory.0123The IBM 360 (c. 1964) helpedto popularizebyte-addressable memory.Many data types (integers, addresses, floating-point numbers) arewider than a byte.16-bit integer:1032-bit integer:32 10Layout of Records and UnionsModern memory systems readdata in 32-, 64-, or 128-bitchunks:32 107 6 541110 98Reading an aligned 32-bit value isfast: a single operation.32 107 6 541110 9 8It is harder to read an unalignedvalue: two reads plus shifting32 107 6 541110 9 86 543SPARC prohibits unalignedaccesses.MIPS has special unalignedload/store instructions.x86, 68k run more slowly withunaligned accesses.PaddingTo avoid unaligned accesses, the C compiler pads the layout ofunions and records.Rules:ÏEach n-byte object must start on a multiple of n bytes (nounaligned accesses).ÏAny object containing an n-byte object must be of size mn forsome integer m (aligned even when arrayed).struct padded {int x; /*4 bytes*/char z; /*1 byte*/short y; /*2 bytes*/char w; /*1 byte*/};x x x xy yzwstruct padded {char a; /*1 byte*/short b; /*2 bytes*/short c; /*2 bytes*/};b bac cC’s Type System: Enumerationsenum weekday {sun, mon, tue, wed,thu, fri, sat};enum weekday day = mon;Enumeration constants in the same scope must be unique:enum days {sun, wed, sat};enum class {mon, wed}; /*error: mon, wed redefined*/C’s Type SystemTypes may be intermixed at will:struct {int i;union {char (*one)(int);char (*two)(int, int);} u;double b[20][10];}*a[10];Array of ten pointers to structures. Each structure contains an int, a2D array of doubles, and a union that contains a pointer to a charfunction of one or two arguments.Strongly-typed LanguagesStrongly-typed: no run-time type clashes.C is definitely not strongly-typed:float g;union { float f; int i } u;u.i = 3;g = u.f + 3.14159; /*u.f is meaningless*/Is Java strongly-typed?Statically-Typed LanguagesStatically-typed: compiler can determine types.Dynamically-typed: types determined at run time.Is Java statically-typed?class Foo {public void x() { ... }}class Bar extends Foo {public void x() { ... }}void baz(Foo f) {f.x();}PolymorphismSay you write a sort routine:void sort(int a[], int n){int i, j;for ( i = 0 ; i < n-1 ; i++ )for ( j = i + 1 ; j < n ; j++ )if (a[j] < a[i]) {int tmp = a[i];a[i] = a[j];a[j] = tmp;}}PolymorphismTo sort doubles, only need to changetwo types:void sort(double a[], int n){int i, j;for ( i = 0 ; i < n-1 ; i++ )for ( j = i + 1 ; j < n ; j++ )if (a[j] < a[i]) {double tmp = a[i];a[i] = a[j];a[j] = tmp;}}C++ Templatestemplate <class T> void sort(T a[], int n){int i, j;for ( i = 0 ; i < n-1 ; i++ )for ( j = i + 1 ; j < n ; j++ )if (a[j] < a[i]) {T tmp = a[i];a[i] = a[j];a[j] = tmp;}}int a[10];sort<int>(a, 10);C++ TemplatesC++ templates are essentially language-aware macros. Eachinstance generates a different refinement of the same code.sort<int>(a, 10);sort<double>(b, 30);sort<char*>(c, 20);Fast code, but lots of it.Faking Polymorphism with Objectsclass Sortable {bool lessthan(Sortable s) = 0;}void sort(Sortable a[], int n) {int i, j;for ( i = 0 ; i < n-1 ; i++ )for ( j = i + 1 ; j < n ; j++ )if ( a[j].lessthan(a[i]) ) {Sortable tmp = a[i];a[i] = a[j];a[j] = tmp;}}Faking Polymorphism with ObjectsThis sort works with any array of objects derived from Sortable.Same code is used for every type of object.Types resolved at run-time (dynamic method dispatch).Does not run as quickly as the C++ template version.ArraysMost languages provide array types:char i[10]; /*C*/character(10) i ! FORTRANi : array (0..9) of character; -- Adavar i : array [0 .. 9] of char; { Pascal }Array Address CalculationIn C,struct foo a[10];a[i] is at a + i ∗ sizeof(struct foo)struct foo a[10][20];a[i][j] is at a + (j + 20 ∗ i) ∗ sizeof(struct foo)⇒ Array bounds must be known to access 2D+ arraysAllocating Arrays in
View Full Document