Types and Static Semantic AnalysisCOMS W4115Prof. Stephen A. EdwardsFall 2003Columbia UniversityDepartment of Computer ScienceData TypesWhat is a type?A restriction on the possible interpretations of a segmentof memory or other program construct.Useful for two reasons:Runtime optimization: earlier binding leads to fewerruntime decisions. E.g., Addition in C efficient becausetype of operands known.Error avoidance: prevent programmer from putting roundpeg in square hole. E.g., In Java, can’t open a complexnumber, only a file.Are Data Types Necessary?No: many languages operate just fine without them.Assembly languages usually view memory asundifferentiated array of bytes. Operators are typed,registers may be, data is not.Basic idea of stored-program computer is that programsbe indistinguishable 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 toa pointer to a char */C’s Types: Arrays, FunctionsArrayschar c[10]; /* c[0] ... c[9] are chars */double a[10][3][2]; /* array of 10arrays of 3 arraysof 2 doubles */Functions/* function of two argumentsreturning 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 notwhat operations 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 recordholds only one of 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.01234Many data types (integers, addresses, floating-pointnumbers) are wider than a byte.16-bit integer:1 032-bit integer: 3 2 1 0Layout of Records and UnionsModern memory systems read data in 32-, 64-, or 128-bitchunks:3 2 1 07 6 5 411 10 9 8Reading an aligned 32-bit value is fast: a single operation.3 2 1 07 6 5 411 10 9 8Layout of Records and UnionsSlower to read an unaligned value: two reads plus shift.3 2 1 07 6 5 411 10 9 86 5 4 3SPARC prohibits unaligned accesses.MIPS has special unaligned load/store instructions.x86, 68k run more slowly with unaligned accesses.Layout of Records and UnionsMost languages “pad” the layout of records to ensurealignment restrictions.struct padded {int x; /* 4 bytes */char z; /* 1 byte */short y; /* 2 bytes */char w; /* 1 byte */};x x x xy y zw: Added paddingC’s Type System: Enumerationsenum weekday {sun, mon, tue, wed,thu, fri, sat};enum weekday day = mon;Enumeration constants in the same scope must beunique:enum days {sun, wed, sat};enum class {mon, wed}; /* error: mon, wedredefined */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 containsan int, a 2D array of doubles, and a union that contains apointer to a char function 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 change a few 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.Each instance generates a different refinement of thesame 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 fromSortable.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 Arraysint a[10]; /* static */void foo(int n){int b[15]; /* stacked */int c[n]; /* stacked: tricky */int d[]; /* on heap */vector<int> e; /* on heap */d = new int[n*2]; /* fixes size */e.append(1); /* may resize */e.append(2); /*
View Full Document
Unlocking...