CS 345 slide 201 Spring 200522 March 2005The infinite recursion is eliminated by using explicitpointers:type Expr = recordcase kind: ExpKind ofLit:(value: integer)Add:(op1,op2: Expr)Sub:(op1,op2: Expr)endendNow the record size is finite, because the size ofExpr is independent of the size of Expr.A matching evaluation function:function eval( exp : Expr ) : integerbegincase exp.kind ofLit: eval := exp.value;Add: eval := eval( exp.op1) + eval( exp.op2);Sub: eval := eval( exp.op1) – eval( exp.op2);endendThe C example:struct tree { int label; tree* left; tree* right; };Allowing pointers to be null enables trees to be finite.CS 345 slide 202 Spring 200522 March 2005Sequence data typesPascal Arraystype constructor:array index-type of element-type whereindex-type (enumerations  subranges  { char }examples:array [0..99] of chararray [ 'a'.. 'z' ] of integerarray (north, east, south, west) of real An array’s index-type is part of the array’s type.Hencearray [0..9] of realarray [1..10] of realarray [–3..3] of realare different types, and cannot be usedinterchangeably as procedure arguments.value construction:1. allocate storage (at compile time)2. assign values to individual elementsselector:array-name ‘[’ index-value ‘]’Indexing includes bounds checks (which can beturned off).CS 345 slide 203 Spring 200522 March 2005Modula–2 arraysModula–2’s array types resemble Pascal’s exceptfor procedures’ parameters.Modula–2 allows ordinary array parameters PROCEDURE P( VAR x: ARRAY [1..12] OF INTEGER );In any call of P, the argument type is ARRAY [1..12] OF INTEGER.But Modula–2 also allows open array parameters: PROCEDURE Q( VAR y : ARRAY OF INTEGER );In any call of Q, the argument type isARRAY [i..j ] OF INTEGERwhere i and j can be any integers.Within Q, y’s index range is 0..HIGH(y), regardlessof the corresponding argument’s declaration.VAR a: ARRAY [1..12] OF INTEGER ,b: ARRAY [10..99] OF INTEGER;…Q(a); (* within Q, y’s index range is 0..11 *)Q(b); (* within Q, y’s index range is 0..89 *)CS 345 slide 204 Spring 200522 March 2005C/C++: Arraystype constructor:element-type‘[’ ‘]’example:double[]variable declaration: element-type name‘[’ integer-constant ‘]’example: Pascal equivalentdouble x[12] x : array [0..11] of real Array indexing begins at 0 (an array’s size isits smallest invalid index). Array size is a compile-time constant.value constructor:double a[7] = { 4,7,1,9,5,2,5 }selector: array-name ‘[’ index-value ‘]’ Indexing includes no bounds check. An array’s size is not part of the array’s type.Hencedouble y[3]; double z[300];are the same type and can be used inter-changeably as procedure arguments.A procedure, however, cannot discover anarray argument’s size (which must thereforebe declared as a separate argument).CS 345 slide 205 Spring 200522 March 2005Java arraystype constructor:element-type‘[’ ‘]’example:double[]variable declaration: element-type ‘[’ ‘]’ namevalue constructor:new element-type ‘[’ integer-expression ‘]’ example:double[] x = new double[size_of_x]; Array size is a run-time value.selector: array-name ‘[’ index-value ‘]’ Indexing includes bounds check(IndexOutOfBounds exception)CS 345 slide 206 Spring 200522 March 2005Haskell: liststype constructor: []if a is a type, then [a] is the type list of a.value constructors:• list enumeration: [3,4,2,1]• list construction:if x::a and xs::[a], then x:xs ::[a]value selectors:• patternsif xs is a non-empty list theny:ys = xs  binds y to the first element of xs  binds ys to the rest of xs.• indexing: xs!!n> (!!) :: [t] -> Int -> t> (b:bs)!!0 = b> (b:bs)!!(n+1) = bs!!nComparing arrays and lists:size access timeinsert/deletetimeArrays fixed (–) constant (+) linear (–)Lists variable (+) linear (–) constant (+)CS 345 slide 207 Spring 200522 March 2005Array indexingThe key feature of arrays is O(1)-time access to anyarray element.Hence the time to compute the l-value of A[k] must beindependent of k.Suppose A is declared byA : array [low..high] of TAn array is implemented by a block of contiguousmemory locations. For array A, let these locations’addresses bem0, m1, …, m(high–low+1)*size(T ) – 1Then A[k]’s address is computed bym0 + (k – low)*size(T )In a statically typed language, size(T ) is a compile-time constant; assuming that m0 is available, the costof computing A[k] is clearly independent of k.Computing A[k]’s address with bounds check:if lowk highthen m0 + (k – low)*size(T )else errorThe check adds a constant to the access time.Is it worth the cost?CS 345 slide 208 Spring 200522 March 2005StringsIn Pascal, C, and C++, a (character) string is asequence of characters stored in an array —but it isnot the same as an array of characters.A variable of type string needs to be able to storestrings of varying lengths, but in these languagesarray variables’ sizes are fixed at compile time.Pascal solution: str255 = array of 256 characters; firstcharacter is a one-byte integer specifying the string‘slength, i.e., how many array elements are valid.Calif ronai10012552C solution: string = char array of arbitrary length;string’s last character is followed by '\0'.Calif ronai\0012C++ libraries (STL and others), Java, and Haskellprovide much more convenient character-stringtypes:• In C++/STL and Java, a string’s properties includeits length, and no termination character isnecessary• in Haskell, a string is just a list of characters,manipulable by all polymorphic list functions—length, (!!), map, filter, …What makes this possible is that in these languagesvariables’ sizes are not fixed at compile