Programming Languages Implementation of Data Structures

1 Programming Languages Implementation of Data Structures Cao Hoaøng Truï Khoa Coâng Ngheä Thoâng Tin Ñaïi Hoïc Baùch Khoa TP. HCM 2 Contents • Fundamentals • Elementary data types • Structured data types • Subprograms 3 Fundamentals • Data objects • Data types • Type specification and implementation • Declaration • Type checking, compatibility, and conversion • Assignment and initialisation 4 Data Objects • A run-time grouping of one or more pieces of data • A container for data values • Block of storage • Programmer-defined and system-defined • Lifetime • Variables and constants 5 Fundamentals • Data objects • Data types • Type specification and implementation • Declaration • Type checking, compatibility, and conversion • Assignment and initialisation 6 Data Types • A class of objects having the same properties • Primitive data types 7 Fundamentals • Data objects • Data types • Type specification and implementation • Declaration • Type checking, compatibility, and conversion • Assignment and initialisation 8 Specification • Attributes • Values • Operations: op_name: arg_type x arg_type x  result_type x result_type x 9 Examples: Arrays • Attributes:  number of dimensions  subscript range for each dimension  data types of the components • Values: valid values for the components • Operations: subscripting, creating, accessing attributes 10 Implementation • Storage representation • Operation definitions:  hardware operations  subprograms  in-line codes 11 Fundamentals • Data objects • Data types • Type specification and implementation • Declaration • Type checking, compatibility, and conversion • Assignment and initialisation 12 Declaration • To provide information about data objects:  number and type  name and position  lifetime  constant and initialised value 13 Declaration • Data type declaration:  by name var A: integer  by specification var A: array [1..20] of integer 14 Declaration • Operation declaration:  argument number, order, data types  result number, order, data types function FOO(X: integer; Y: real) : real; FOO: integer x real  real 15 Declaration • Purposes:  choice of storage representations  storage management  generic operations  type checking 16 Fundamentals • Data objects • Data types • Type specification and implementation • Declaration • Type checking, compatibility, and conversion • Assignment and initialisation 17 Type Checking • Checking if each operation receives the proper number of arguments of the proper data types • Dynamic (run time) vs. static (compile time) type checking 18 Type Checking • Dynamic type checking:  no declarations required  types of data objects may change as needed  programmers have no concerns about data types  difficult to debug and remove type errors  extra storage required for keeping type information  reduction of execution speed 19 Type Compatibility • T1 and T2 are compatible if data objects of type T1 can occur in the positions of data objects of type T2, and vice versa: name or structural equivalence type VECT1: array [1..10] of real; VECT2: array [1..10] of real; var X, Y: VECT1; Z: VECT2; Y := X; Z := Y; 20 Type Compatibility • Name equivalence:  no anonymous types allowed  global type definitions used var X: array [1..10] of real; 21 Type Compatibility • Structural equivalence:  difficult to define  static type checking compromised  cost to check type METERS = integer; LITERS = integer; var LEN: METERS; VOL: LITERS; LEN + VOL 22 Type Conversion • When types are mismatched:  type error  type conversion (coercion) var A: integer; int I; B, C: real; unsigned U; float F; C := A + B I = - 1; U = 1; F = U * I; /* I = - 1  65535 */ 23 Fundamentals • Data objects • Data types • Type specification and implementation • Declaration • Type checking, compatibility, and conversion • Assignment and initialisation 24 Assignment • Basic operation for changing values of data objects • Specification: := : type1 x type2  void = : type1 x type2  type3 Z := X + Y Z = X + (Y = W * 2) A = B = C 25 Initialisation • To set a value in the storage of an data object • Un-initialised data object • Explicit and implicit initialisation 26 Programming Languages Implementation of Data Structures Cao Hoaøng Truï Khoa Coâng Ngheä Thoâng Tin Ñaïi Hoïc Baùch Khoa TP. HCM 27 Contents • Fundamentals • Elementary data types • Structured data types • Subprograms 28 Elementary Data Types • Numeric data types • Enumerations • Booleans • Characters 29 Numeric Data Types • Integers • Subranges • Floating-point real numbers • Fixed-point real numbers • Complex numbers • Rational numbers 30 Integers 2 bytes 4 bytes -32768  32768 -65536  65536 31 Subranges var A: 1..10 • Smaller storage requirements  fewer bits than a general integer  software-simulated operations • Better type checking 32 Floating-Point Real Numbers exponent mantissa Sign bit for mantissa Sign bit for exponent 6.7510 = 110.112 = 0.110112 x 23 = 0.110112 x 00112 11011 0011 0 0 33 Fixed-Point Real Numbers integer part fractional part Sign bit 6.7510 = 110.112 11 110 0 34 Complex Numbers real part imaginary part 35 Rational Numbers • To avoid roundoff and truncation • Pairs of integers of unbounded length Sign bit numerator denominator 36 Elementary Data Types • Numeric data types • Enumerations • Booleans • Characters 37 Enumerations type DEGREE = (bachelor, master, doctor) 0 1 2 38 Elementary Data Types • Numeric data types • Enumerations • Booleans • Characters 39 Booleans • A particular bit • Zero/non-zero value 1 byte 40 Elementary Data Types • Numeric data types • Enumerations • Booleans • Characters 41 Characters 1 byte 2 byte 42 Contents • Fundamentals • Elementary data types • Structured data types • Subprograms 43 Structured Data Types • Fundamentals • Vectors and arrays • Records • Character strings • Pointers • Sets • Files 44 Fundamentals • Specification • Implementation • Type checking 45 Specification • Attributes:  Number of components  Type of each component  Names for selecting components  Maximum number of components  Organization of components 46 Specification • Operations:  Component selection (random/sequential)  Whole-data-structure operations  Insertion/deletion  Creation/destruction 47 Implementation • Storage representation: Decriptor Component Component Decriptor Component Component Sequential Linked 48 Implementation • Selection operation:  Sequential  base-address-plus-offset  Linked  pointer following 49 Implementation • Storage management: Garbage Dangling References object object 50 Type Checking var A: array [1..10] of real; • Existence of a selected component: A[I] • Type of a selected component: A[2].link.item 51 Structured Data Types • Fundamentals • Vectors and arrays • Records • Character strings • Pointers • Sets • Files 52 Vectors Vector LB UB Integer E Base address a Component size A[LB] A[LB + 1] A[UB] var A: array [1..10] of integer; loc A[I] = a + D + (I - LB) x E packed/unpacked storage 53 Matrix var A: array [1..2, -1..1] of real; 1 2 -1 0 1 -1 0 1 1 2 row-major order column-major order 54 Multidimensional Arrays var A: array [LB1..UB1, LB2..UB2, , LBn..UBn] of real; • Row-major order: var A: array [LB1..UB1] of array [LB2..UB2, , LBn..UBn] of real; • Column-major order: var A: array [LBn..UBn] of array [LB1..UB1, , LBn-1..Ubn-1] of real; 55 Matrix Matrix LB1 UB1 LB2 UB2 Real E Base address a Component size A[1, -1] A[1, 0] var A: array [1..2, -1..1] of real; loc A[I, J] = a + D + (I - LB1) x S + (J - LB2) x E S = (UB2 - LB2 + 1) x E loc A[I, J] = a + K + I x S + J x E K = D - LB1 x S - LB2 x E A[1, 1] A[2, -1] A[2, 0] A[2, 1] 56 Structured Data Types • Fundamentals • Vectors and arrays • Records • Character strings • Pointers • Sets • Files 57 Records • Heterogeneous components • Symbolic names for components var EMPLOYEE: record ID: integer; AGE: integer; DEPT: string; SALARY: real; end 58 Records 22901 2901.10 Base address a ID loc R.I = a + j=1, I-1(size of R.j) 27 “IT” AGE DEPT SALARY computed during compile time 59 Variant Records type PAY_TYPE = (MONTHLY, HOURLY) var EMPLOYEE: record ID: integer; AGE: integer; DEPT: string; case PAY_CLASS: PAY_TYPE of MONTHLY: (MONTH_RATE: real; START_DATE: integer); HOURLY: (HOUR_RATE: real; REG_HOURS: integer; OVERTIME: integer) end 60 Variant Records 22901 ID 27 “IT” AGE DEPT PAY_CLASS HOUR_RATE REG_HOURS OVERTIME ID AGE DEPT PAY_CLASS MONTH_RATE START_DATE Unused 61 Variant Records • Dynamic tag checking • No checking 62 Structured Data Types • Fundamentals • Vectors and arrays • Records • Character strings • Pointers • Sets • Files 63 Character Strings R E L A T I V I T Y • Fixed declared length: 64 Character Strings 12 8 E I N S T E I N • Variable length with declared bound: Maximum length Current length 65 Character Strings • Unbounded length: Current length 8 I E S N E T N I 66 Character Strings • Concatenation • Relational operations • Substring selection (by character-position/pattern matching) • Input-output formatting 67 Structured Data Types • Fundamentals • Vectors and arrays • Records • Character strings • Pointers • Sets • Files 68 Pointers • Referencing data objects of a single type type VECT = array [1..20] of real; var P: VECT; • Referencing data objects of any type 69 Pointers Object d 0 d Object d 0 d Absolute address Relative address 70 Pointers • Absolute address:  fast access  difficult storage management • Relative address:  slower access  simpler storage management 71 Pointers • List: type ELEMENT = record HEAD: integer; TAIL: ELEMENT end var P: ELEMENT P 72 Structured Data Types • Fundamentals • Vectors and arrays • Records • Character strings • Pointers • Sets • Files 73 Sets • Membership test • Element insertion/deletion • Union, intersection, difference 74 Sets var S: set of (mon, tue, wed, thu, fri, sat, sun); • Bit-string representation: mon tue wed thu fri sat sun [mon, wed, fri] 1 0 1 0 1 0 0 [mon, tue, wed] 1 1 1 0 0 0 0 [mon, wed] 1 0 1 0 0 0 0 75 Sets • Hash-coded representation:  for large domain size  each set is represented by a storage block  each element has a hash address in that block 76 Structured Data Types • Fundamentals • Vectors and arrays • Records • Character strings • Pointers • Sets • Files 77 Files • Represented on a secondary storage device (disk/tape) • Much larger than data structures of other types • Lifetime is longer than that of the program creating it 78 Files • Sequential files • Text files • Direct-access files • Indexed sequential files 79 Files • Open • Read • Write • End-of-file test 80 Contents • Fundamentals • Elementary data types • Structured data types • Subprograms 81 Subprograms • Abstract operations:  name  arguments  results  action • Data objects 82 Subprograms function FOO(X: real; Y: integer): real; var A: array [1..10] of real; N: integer; begin N := Y + 1; X := A[N]*2; end; 83 Subprograms • Code segment (static part) • Activation record (dynamic part):  parameters  function results  local variables 84 Subprograms Prologue FOO Code segment Activation record Epilogue Statement executable codes Return point and system data X Y A N 85 Subprograms Code segment Activation record 1 Activation record 2 Activation record N 1st call 2nd call N-th call 86 Exercises • Consider the following piece of program: program P; var A: 1..10; N: integer; begin read(N); A := N + 1; end;  Where is type checking?  Can it be done statically?  Can it be done dynamically and how? 87 Exercises • Illustrate the storage representation of A: array [0..1, 1..2] of integer using the column-major order. Give the accessing formula for computing the location of A[I, J], supposing that the size of an integer is 2 bytes.