Programming Languages (CS302 2005S)

Gries, Chapter 5: Notations and Conventions for Arrays

Gries, David (1998). The Science of Programming. New York, NY: Springer-Verlag. ISBN: 0-387-96480-0. Chapter 4: Notations and Conventions for Arrays (pp. 88-98).

Excellent Questions from: Brantley, Edwards, Yilma

Questions from: Barnes, Erickson, Fletcher, French, Guha, Nyombayire, Ramdial, Schmitz, Shireman, Smith, Tansey (guest question),

Questions missing from: Kasidhi, Kuo, Petersen, Rosenbluh,

Contents


Pascal Arrays

Can you explain the following Pascal declaration?

var a  : array[1:3] of integer

The var indicates a variable declaration. The a is the name of the variable. The first colon separates variable (or variables) from type. The array declares an array. The 1:3 indicates that the valid indices are 1, 2, and 3 (the range from 1 to 3).

Is this a variant of the normal Pascal syntax?

Yes, Gries uses a variant syntax. Where Wirth uses ellipses (well, two dots) as the range operator, Gries uses a colon.

What about two-dimensional arrays, either in standard syntax Why does the array start at 1 and not 0?

Pascal, unliked C and Java, allows programmers to choose the starting indices of their arrays. I hypothesize that Wirth's experience suggested that (a) programmers often intended to use different indices and had to write code to convert to 0-based indicing, so making the compiler do it led to more efficient code and more correct code and (b) choosing the range was clearer for beginning programmers.

var a2 : array[1..2,1..3] of char

or Gries syntax

var a3: array[1:2,1:3] of char

As you've surmmised, these are two-dimensional arrays. Valid indices for the first dimension are 1 and 2 (at least in this case) and valid indices for the second dimennsion are 1, 2, and 3 (againn, in this case).

On page 97, why does Gries use b[0:1][1:3], thereby starting the inner array at 0 and the outer at 1?

I would caution against using the terms inner and outer. Think of them as dimensions. He uses different starting points simply because he considers it interesting to do so.

Notational Questions

For the implementation of arrays using partial function, when given (b; i:e)[j], what is the purpose of making i=j imply e? That is, why not always replace the value of b[j] with e regardless of whether i and j are equal.

Because we may want to allow the array (function) take on more than one value. For example, it may be that b[1] is 2 and b[2] is 3. We also want to verify that the index used (j) is valid.

On page 94, equation 5.2.1, Gries notes that perm((b; k:x),B) holds. However, if b and B are originally equal, Ei:i\in domain(b): b[i]=x and (b; k:x) only alters the value at position k, so we end up having an extra copy of x in b. Don't we need to swap elements (instead of altering only one position) for perm((b; k:x),B) to hold?

Don't think of the operations as acting on the arrays; think of them as statements of what we want to have happen. We want the x to appear in position k. Note that if x also appears elsewhere in b, then (b; k:x) won't be a permutation of B. Hence, we've subtlely said that x must be in position k.

Why would I find it necessary to refer to an empty section of an array? Was the point just that if the two indicies are equal there are no array elements being referred to, or did Gries intend to provide us with a way of referring to empty sections because this is useful to us?

At times, in the base case of recursive analysis, we may need to talk about times when the indices are equal. (At least that will often be easiest as a base case.)

Arrays as Functions

What are the particle and wave theories of light? (p 91)

Light sometimes acts like individual particles (which we tend to call photons) and sometimes like a wave. For example, you can get interference between two light beams that acts very much like the way two waves (think sine waves) interact. However, we can also see evidence of individual particles striking collectors. At least that's how I understand it. Our physicists may have other answer.

Neither a purely particle view, or a purely wave view can tell us the whole story on light. Is the same true, for the different array notations (meaning, to fully utilize arrays, do we truly need both notations)?

I think we need both understandings, if not both notations.

On p.91, Gries discusses the advantages and disadvantages of the functional view and collection-of-independent variables view of arrays. Are there other advantages/disadvantages of these two views?

More than I care to discuss here.

Why must arrays be considered as partial functions? Is it because the domain of an array is a finite subset of the naturals (hence is undefined for infinitely many naturals) or because we allow uninitialized/partially initialized arrays?

Primarily that their domain is only a subset of the naturals. However, the other reason isn't bad, either.

Is it possible to use Gries functional view of one-dimensional arrays to an n-dimensional array?

Certainly. You can consider an n-dimensional array to be a function for an n-tuple to a single value or a function from a value (the first dimension) to an (n-1)-dimensional array.

I notice Gries focuses on the functional view of arrays. Will the programming languages we look at later in the class also focus on the functional view?

Just as Gries tends to switch notations and perspectives (see comments above), so will many languages switch between the two. My experiences is that it's easiest to think of arrays as implementations of functions from a limited range of values to a specified type. It is primarily when we worry about implementation that we think of them more in terms of a sequence of storage cells.

Just Plain Strange Questions

Why are computer so dumb?

Because it's really hard to program them to be smart. (Many would argue that we don't yet have enough understanding of intelligence to make them smart.)

Miscellaneous

Is the picture representation of array assertions a Gries specific thing, or does it appear in other literature?

It's a notation that Gries seems to have designed or adopted.

How do you formally define perm?

It's hard.

What do we do if we are using a non array data structure such as Scheme lists? Do we generate new rules and notations with every new data structure?

Scheme lists are essentially two-element arrays plus pointers, so we can use the rules and notations for those two things. Note, however that pointers are a pain. Most data structures are built from records, arrays, and pointers.

On page 90 in examples 1 and 2, how was Gries able to come up with the values that he got for the array?

The values are given by the meaning assigned to the notation. The initial values he chose.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed Mar 2 11:39:32 2005.
The source to the document was last modified on Tue Mar 1 23:08:08 2005.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS302/2005S/Readings/gries5.html.

You may wish to validate this document's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu