DOC PREVIEW
Columbia COMS W4115 - Types and Static Semantic Analysis

This preview shows page 1-2-3-22-23-24-45-46-47 out of 47 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Columbia COMS W4115 - Types and Static Semantic Analysis

Documents in this Course
YOLT

YOLT

13 pages

Lattakia

Lattakia

15 pages

EasyQL

EasyQL

14 pages

Photogram

Photogram

163 pages

Espresso

Espresso

27 pages

NumLang

NumLang

6 pages

EMPATH

EMPATH

14 pages

La Mesa

La Mesa

9 pages

JTemplate

JTemplate

238 pages

MATVEC

MATVEC

4 pages

TONEDEF

TONEDEF

14 pages

SASSi

SASSi

16 pages

JTemplate

JTemplate

39 pages

BATS

BATS

10 pages

Synapse

Synapse

11 pages

c.def

c.def

116 pages

TweaXML

TweaXML

108 pages

Load more
Download Types and Static Semantic Analysis
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 Types and Static Semantic Analysis 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 Types and Static Semantic Analysis 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?