What are objects really all about? The data stupid. We don't give data enough credit for it role in programming. Perhaps we shouldn't call it coding but datering or something. The relationship between data and code is deep and it is the real reason we invented object oriented programming.

What Programmers Know

Contents

1. The Computer - What's The Big Idea?*
2. The Memory Principle - Computer Memory and Pigeonholes*
3. Principles of Execution - The CPU
4. Assemblers and assembly language*
5. The Essence Of Programming
6. Variables - Scope, Lifetime And More*
7. Binary Arithmetic
8. Hexadecimal*
9. Binary - Negative Numbers*
10. Floating Point Numbers*
11. Inside the Computer - Addressing
12. The Mod Function
13. Recursion
14. The Lost Art Of The Storage Mapping Function *
15. Hashing - The Greatest Idea In Programming
16. Advanced Hashing
17. XOR - The Magic Swap*
18. Programmer's Introduction to XML
19. From Data To Objects*
20. What Exactly Is A First Class Function - And Why You Should Care*
21. Stacks And Trees*
22. The LIFO Stack - A Gentle Guide*
23. Data Structures - Trees
24. Inside Random Numbers
25. The Monte Carlo Method
26. Cache Memory And The Caching Principle
27. Data Compression The Dictionary Way
28. Dates Are Difficult*
29. Sequential Storage*
30. Magic of Merging*
31. Power of Operators
32. The Heart Of A Compiler*
33. The Fundamentals of Pointers
34. Functional And Dysfunctional Programming*

* Recently revised

This is an informal beginners introduction to the role that data has in programming and the way that it eventually leads to the idea of object oriented programming. If you think that you know what object oriented programming is about you might have to reconsider a little.

Personally I think that Niklaus Wirth said it well in the title of his classic text on computer science:

Algorithms + Data structures = Programs

Here I am going to deal with two fundamental  data structures- the array and the record.

The array leads on to other more interesting data structures - mainly based on the associative array or dictionary.

The record on the other hand leads on to one of the nicest ideas in programming - the object.

If you already know about objects then you might find it surprising that they spring out of not some deep theory about code but from a generalization of a simple data structure.

The Array

The most basic of data abstractions is the variable. It's an area of memory that you can store one item of data in.

Of course exactly what you mean by "one item" of data varies according to what you are doing. An integer is clearly one item of data but a string of characters?

The key idea is that for the current purpose a variable stores a chunk of data that has no structure of its own i.e. it is what is stored in the variable and what is retrieved when you use the variable.

Variables are all very well but you quickly discover that they aren’t enough.

For example if you want to store a table of numbers then you really do need something more than a single variable. The most common way of storing tables of data is to use an “array”.

This is an “indexed” collection of variables and the meaning of “indexed” will become apparent in a moment.

For example, in Basic or a similar language you might write:

Dim A(10)


This creates an array with ten “elements” - A(1), A(2), A(3) and so on to A(10).  Let's ignore the issue of whether array elements start at 0 or 1.

Each element is a variable in its own right and you can store a single item of data in it. For example:

A(3)=15

stores 15 in A(3).

An array of variables

Why bother with an array?

Why not just use 10 distinct variables?

The answer is this index business.

The power of an array comes from being able to pick out which element of the array you are interested in using by way of a variable.

For example:

I=3
A(I)=15

again stores 15 in element 3 of the array.

In this case I is called the “index” and using this sort of idea you can write programs that lookup information in arrays such as “give me the 56th element” or process the entire array by changing the index as part of the working of the program. Notice that the key idea is the ability to select which variable you are referring to at run time.

That is you can write A1 or even A(1) and this will always refer to the same variable and which one id defined at compile time. In more general terms when you write A(1) in a program you can deduce which variable is being referred to at once. However A(I) is anything you like depending on the value that I has at the time.

Consider the pseudo code:

I=RND(0,100)
Print A(I)

You cannot know which element of A is printed and what is more it is different each time you run the code. 

Arrays bring dynamic to data.

Index and Enumerator

Today there is a concept that is very similar to the indexed array but not quite the same - the enumeration. Often indexed arrays are used in a very simply and restrictive way. They are in principle fully "random" access. That is you can get any element ot the array any time you want it and you can get the entire set of elements in any order. However if you look at the way arrays are commonly used you find that they are accessed sequentially a lot of the time:

For I from 1 to 100
 Print A(I)
Next I

This is so common that it is useful to generalize it to other sequential access data types called enumerations. All you need for an enumeration is a function that retrieves the next item, usually called the enumerator and you can write things like:

For item In A 
 Print item
Next

Some times enumerations are just indexed arrays that give you an enumerator as well as an index. Sometimes they are pure enumerations that don't allow indexed access. 

Enumerations make writing loops that scan though the data very easy because you can forget about the value of the index. However they do have some limitations. For example it is, depending on the language, difficult to arrange to scan though two enumerations at the same time. That is the enumeration equivalent of

For I from 1 to 100
 Print A(I),B(I)
Next I

Is often difficult to write. 

Enumerations are sequential arrays and indexed arrays are random access. 

<ASIN:0521880378>
<ASIN:0072253592>

<ASIN:0131997467>