Types and Static Semantic Analysis COMS W4115 Data Types Are Data Types Necessary What is a type No many languages operate just fine without them A restriction on the possible interpretations of a segment of memory or other program construct Assembly languages usually view memory as undifferentiated array of bytes Operators are typed registers may be data is not Useful for two reasons Prof Stephen A Edwards Fall 2003 Columbia University Department of Computer Science Runtime optimization earlier binding leads to fewer runtime decisions E g Addition in C efficient because type of operands known Basic idea of stored program computer is that programs be indistinguishable from data Everything s a string in Tcl including numbers lists etc Error avoidance prevent programmer from putting round peg in square hole E g In Java can t open a complex number only a file C s Types Base Types Pointers C s Types Arrays Functions C s Types Structs and Unions Base types match typical processor Arrays Structures each field has own storage char c 10 c 0 c 9 are chars double a 10 3 2 array of 10 arrays of 3 arrays of 2 doubles struct box int x y h w char name Functions Unions fields share same memory function of two arguments returning a char char foo int double union token int i double d char s Composite Types Records Applications of Records Composite Types Variant Records A record is an object with a collection of fields each with a potentially different type In C Records are the precursors of objects A record object holds all of its fields A variant record holds only one of its fields at once In C Typical sizes 8 16 char short 32 64 int long float double Pointers addresses int i i is a pointer to an int char j j is a pointer to a pointer to a char struct rectangle int n s e w char label color col struct rectangle next struct rectangle r r n 10 r label Rectangle Group and restrict what can be stored in an object but not what 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 union token int i float f char string union token t t i 10 t f 3 14159 char s t string overwrites t i returns gibberish Applications of Variant Records Layout of Records and Unions Layout of Records and Unions A primitive form of polymorphism Modern processors have byte addressable memory Modern memory systems read data in 32 64 or 128 bit chunks struct poly int x y int type union int radius int size float angle d 0 1 3 2 1 0 2 7 6 5 4 11 10 9 8 3 Reading an aligned 32 bit value is fast a single operation 4 3 2 1 If poly type CIRCLE use poly d radius Many data types integers addresses floating point numbers are wider than a byte 7 6 5 4 If poly type SQUARE use poly d size 16 bit integer 11 10 9 8 If poly type LINE use poly d angle 32 bit integer 3 Layout of Records and Unions Layout of Records and Unions C s Type System Enumerations Slower to read an unaligned value two reads plus shift Most languages pad the layout of records to ensure alignment restrictions enum weekday sun mon tue wed thu fri sat 3 2 1 0 7 6 5 4 11 10 9 8 6 5 4 3 struct padded int x char z short y char w SPARC prohibits unaligned accesses x x MIPS has special unaligned load store instructions y y x86 68k run more slowly with unaligned accesses x 2 4 1 2 1 1 0 1 0 enum weekday day mon bytes byte bytes byte Enumeration constants in the same scope must be unique enum days sun wed sat x z 0 enum class mon wed Added padding error mon wed redefined w C s Type System Strongly typed Languages Statically Typed Languages Types may be intermixed at will Strongly typed no run time type clashes Statically typed compiler can determine types struct int i union char one int char two int int u double b 20 10 a 10 C is definitely not strongly typed Array of ten pointers to structures Each structure contains an int a 2D array of doubles and a union that contains a pointer to a char function of one or two arguments float g union float f int i u u i 3 g u f 3 14159 u f is meaningless Is Java strongly typed 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 Polymorphism Polymorphism C Templates Say you write a sort routine To sort doubles only need to change a few types 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 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 template 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 Templates Faking Polymorphism with Objects Faking Polymorphism with Objects C templates are essentially language aware macros Each instance generates a different refinement of the same code class 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 This sort works with any array of objects derived from Sortable Array Address Calculation Allocating Arrays In C int a 10 static void foo int n int b 15 int c n int d vector int e sort int a 10 sort double b 30 sort char c 20 Fast code but lots of it Arrays Most languages provide array types struct foo a 10 char i 10 C character 10 i FORTRAN i array 0 9 of character Ada 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 arrays 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 …
View Full Document
Unlocking...