Variables/Data Types in Imperative Programming

• Basic data types (first class or primary types)
• integer, real, character, boolean (some languages such as Pascal, Java)
• Find out the application based interpretation of an object, such as a day. For example, January 31.
• Determine how you are going to represent that in your program. For example a day in a year can be represented by a number between 1 to 366
• We don't consider machine level representation
• We assume that all the data types will be represented using the basic data types
• You can construct new data types for the object using the basic data types. We saw a simple representation of date using an integer.
• How do we construct other data types
• Arrays (section 4.3, page 111)
• Arrays have subscripts in a given range
  • C allows lower bound of zero and upper bound equal to size-1
  • Pascal allows size from a given lower bound to upper bound
  • Array access is efficient
  • If you want ith element, you don't have to sequentially go down until you reach ith element. You calculate the address of the ith element and use random access to get the contents
  • How is the address calculated?
  • Page 114 gives you the formula
  • i*w + (base-low*w)
  • where base is the address of the first element in the array and w is the width (number of bytes) required to store one element
  • If an array A of integers in C started at location 1000 and if the integer took 4 bytes then A[28] element will be at location1000+28*4=1112
  • If an array A of integers in Pascal with lower bound equal to -20 started at location 1000 and if the integer took 4 bytes then A[28] element will be at location1000+28*4-(-20*4)=1000+48*4=1192
  • In general, you don't know the base address. So your calaculations really should use base address as a variable.
  • Multidimensional arrays: row-major versus column major
  • Let us use two dim arrays as examples in our discussion
  • Row major: Row1 followed by Row 2, Row 3, ......
  • Column major: Column 1 followed by column 2, column 3, .........
  • equation 4.3 gives you the offset for A[i][j]
  • i*wi+j*wj+(base-lowi*wi-lowj*wj)
  • Here wi is the width of the row and wj is the width of an element
    • wi=wj*number of elements in a row
  • suppose you have a matrix that is large enough that only one row or column fits in a page
  • for(i=0; i<n; i++)
  • for(j=0;j<m;j++)
  • a[i][j]=0;
  • what will happen if a was row-major and what will happen if a was column major.
  • row-major works just fine. bring in one row stored of the page and finish all the elements before bringing in the next page.
  • column major for every execuation of a[i][j] we have to bring in a different page a lot of swapping
  • for(i=0; i<n; i++)
  • for(j=0;j<m;j++)
  • a[j][i]=0;
  • the above is a better code if the matrix a were stored column major
  • generally, programming languages make sure that the program is translated efficiently. but in situations like this it helps to know the underlying allocation
  • Some languages like Pascal go beyond using integers for subscripts. They allow any ordinal data type
  • Ordinal means we can define a mapping from the ordinal type values to a range of integers
  • 'a'..'z' characters or enumerated types defined by programmer such as (Sunday, Monday, Tuesday, ....,, Saturday). Use of the ordinal types makes your programmes more readable
  • Total_cost[Sunday] = 20; as opposed to saying Total_cost[0] = 20;
  • In C, there is no explicit provision for ordinal types, but weak typing provides the facility. For example, enumerated type such as (Sunday, Monday, Tuesday, ....,, Saturday) is also interchangeable to the integer 0 to 6.