This lesson is on putting data into computer memory in ways that we can perform interesting operations on the data either with one processor or with many processors, each following its own instructions but in some way contributing to a global result.
Every computer is built out of one or more processors that perform calculations and a memory where the data that the processors use are stored. Both processors and memory can be very complicated in some computers, but we can learn a lot about how computers operate if we think of processors and memory in very simple terms, which is what we shall do.
We won't say much about processors for now. As we talk about them, we will just assume that they can do certain simple things, and these assumptions will be both correct and easy to understand.
Memory is basically simple. Memory is composed of locations, which are places where a number or a few characters of text can be stored. Each location has an address which we can use when getting or putting things there. In fact, we can store addresses in locations, so one location can talk about another rather than about a number or some characters of text. So, the memory is a bunch of locations with addresses. These addresses are numbered in the simplest possible manner, 0, 1, 2, and so on.
Memory locations aren't big enough to hold many numbers or more than a few characters of text, so larger objects are built in computer memory using many locations. If, for example, each location could hold just one character of text, we could store a sentence such as, "This is a computer." in nineteen consecutive locations. We could describe the sentence by the location of the first character, the `T', and by the number of characters. Or we could simply give the address, and in the twentieth location we could put a character that means end and which we never want to use as a character. Since characters are numbered from 0 through 255, we use the 0 itself for this terminator.
The example of representing the sentence, "This is a computer." in twenty consecutive locations is an example of an array, the name we use for consecutive memory locations we have agreed upon will be used to store some object with a simple, consecutive structure, where each datum is of the same type.
We could store the sentence another way. We could decide that we will have many arrays of size two. It the first of the two locations in the array, we will store a character, and in the second we will store the address of where the 2-location array holding the next character is located. Here is what the sentence might look like.
Now, all of this seems like a clumsy idea. But now let's change the sentence to read, "This is a new computer." With our "clumsy" scheme we can add the new characters without moving the old ones.
There are two things to be said now. First, we will give some better and more realistic examples a little later. And, second, what we have called a "2-location array" isn't an array by our definition, since the character and the address are not of the same type. When we have consecutive locations that are to hold data of different types, we will call this grouping a structure.
In the course of writing programs for computers, programmers use many different structures as well as arrays. The particular structure we have just described, which is composed of a datum together with the address of the "next" datum, deserves a special name. It is called a list element , and the whole representation, say of the sentence "This is a new computer.", is called a list . There is one handy detail that we can mention right off. We no longer need the end or "zero" character. We can simply end the list by putting no address at all in the last element. By no address at all we mean the address called NULL .
In our pictures of lists we usually won't use the real addresses in the address field. We will use arrows because they are easier for us to read. The computer, of course, will use numbers that refer to addresses in memory.
Author: Donald Johnson, approximately 1993. Converted to HTML by David Kotz.
Back to DAPPLE.