--- Introduction

This chapter walks through some basic programming theory.

Patterns are collections of objects, so to understand patterns,
you need to understand Object-Oriented Programming (OOP).  
Objects are Turing machines, so to understand OOP, you need to
understand Turing machines.   Programming theory is the study 
of Turing machines, so if you really want to understand Patterns
and OOP, it helps to know the underlying theory.


---- So what are Turing machines?

The Turing machine is the conceptual foundation of programming
theory. It's the simplest device that can do anything a computer
can do.

Mathematically, a Turing machine is an ordered 9-tuple:

    M = (Q, Ai, At, _, |, d(), s, a, r)

where:

    Q   is a set of states
    Ai  is the input alphabet
    At  is the tape alphabet
    _   is the blank symbol
    |   is the left end-marker
    d() is a transition function
    s   is the start state

    t   is the accept state
    r   is the reject state

and you don't have to memorize that, we're just laying it out 
for future reference.

Conceptually, a Turing machine has three parts:

    -  a tape that consists of discrete 'cells'
    -  a decision engine called the 'finite control'
    -  and a read/write head that connects them


    ---------------------
      |   |   |   |   |     <--  Tape
    ---------------------
            ^
            |    <-------------  Read/write head
          +---+
          |   |  <-------------  Finite control
          +---+


A Turing machine starts with its read/write head at the tape's
left end.   To program a Turing machine, you fill its tape with
symbols from the input alphabet, put the finite control in the
'start' state, and set the machine to work.

For each cycle of operation, a Turing machine does four things:

    1. it reads the symbol from the cell currently under the head
    2. it puts the finite control in a new state
    3. it writes a new symbol back to the current cell
    4. it moves the head to a new position on the tape   

Then it goes back to step 1 and repeats the cycle on the new
cell.   The cycle continues until the finite control reaches
either the 'accept' state or the 'reject' state.   When (or
rather, if) that happens, we say the machine 'halts'.   The
contents of the tape when the machine halts are considered the
program's output.

Now, that doesn't look much like regular programming, let alone
OOP.   Appearances can be deceptive, though.   The Turing
machine is computationally equivalent to another machine, called
the Random Access Machine, that looks more familiar.


---- The Random Access Machine

The random access machine is the generic abstraction of a digital
computer.   It has a central processing unit with a set of
built-in instructions, a bank of addressed memory, and a bus
that carries data between memory and the CPU:


    +-----+                     +-----+
    | CPU |--- memory bus --+-->|     |
    +-----+                 |   +-----+
                            +-->|     |
                            |   +-----+
                            +-->|     |
                            |   +-----+
                           ...  | ... |


The CPU also contains two special memory locations called
'registers':

    - an accumulator
    - a program counter

that perform special functions while the machine works its way
through a program.

Each of the CPU's built-in instructions has a corresponding
symbol, called an 'opcode' that can be stored in memory.   To
program a random access machine, you load a series of opcodes
into memory, load the address of the first symbol into the
program counter, and set the machine to work.

For each cycle of operation, the random access machine:

    - reads the program counter,
    - fetches the appropriate opcode from memory,
    - executes the corresponding instruction,
    - and advances the program counter

which is similar to the operating cycle of a Turing machine.

In fact, it's tempting to say that the random access machine is
exactly the same as a Turing machine.   The program counter and
bank of addressed memory do the same thing as a tape with a
read/write head, and the symbols that represent instructions
look much like a Turing machine's tape alphabet.   

Unfortunately, it's not quite that simple.

A random access machine's instruction set can do things that a
Turing machine's tape alphabet can't.   A random access machine
could have an instruction that adds two numbers together, for
instance.   A Turing machine can certainly add numbers, but you
can't reduce addition to a simple table that maps symbols A and
B onto symbol C.   Or rather, you can, but you'll need an
infinite number of symbols, and a Turing machine uses a finite
tape alphabet.

That doesn't make a random access machine more powerful than a
Turing machine, though.   It just means that a random access
machine can do more work per cycle of operation than a Turing
machine can.   To show how the random access machine is
equivalent to a Turing machine, we have to dig a little deeper.

Generally speaking, a random access machine does one of four
things in each cycle of operation:

    - it loads the contents of a memory location into the 
      accumulator,
    - it manipulates the contents of the accumulator,
    - it stores the contents of the accumulator to memory,
    - or it sets the program counter explicitly.

And while a Turing machine can't do some of those things in a
single step, it can do them all in multiple steps.   In fact,
you can say that a random access machine is made of one Turing
machine nested within another.   The outer machine uses the bank
of addressed memory as its tape, and the inner one uses the
accumulator.   The outer machine carries information between the
accumulator and memory, and the inner one manipulates values
once they reach the accumulator.

Now you'll have to take this on faith for the moment, but we
can make a single Turing machine do anything a collection of
Turing machines can do.   The single machine will be bigger,
slower, and more complicated, but it will still do everything 
the collection can do.

That means we can program a Turing machine to simulate a random
access machine.   We can write programs to simulate an
accumulator and program counter, addressed memory and a set of
built-in instructions with opcodes.   Therefore a Turing machine
can do anything a random access machine can do.

The opposite is also true.   A random access machine can be
programmed to act like a Turing machine.   Either machine can do
anything the other one can, so the two machines are said to be
'computationally equivalent'.


----  Objects

Objects are random access machines.

If you look back at the description of random access machines,
you'll notice that I carefully avoided saying that the memory is
addressed numerically, or that the memory locations store
fixed-width binary integers.   Those are details that constrain
the theory to a specific implementation, not part of the theory
itself.   A numeric memory address is just a label, an opcode is
just a symbol, and a bank of 8-bit bytes is equivalent to a tape
with an alphabet of 256 arbitrary symbols.

An object's attributes are discrete chunks of addressed memory.
Its methods serve as a built-in instruction set.   Attributes
have human-readable names rather than numerical addresses, and
can hold arbitrary values.   Methods can perform arbitrarily
complex operations, instead of being limited to primitive binary
logic and branching.   As far as programming theory is
concerned, though, none of those distinctions make any
difference.

It would be trivial to create an object that simulates a random
access machine.   The accumulator, program counter and memory
bank would be attributes.   The instruction set would be a
collection of methods, and each method would map to a symbol
that could be stored in the memory array.

By the same token, a random access machine can be programmed to
act like an object.   With suitable programming, it could
translate a set of human-readable names into ranges of memory
that represent values of arbitrary type.   Then it could
simulate methods to set and manipulate those values, or to do
anything else that an object method can do.   And since a Turing
machine can do anything a random access machine can do, an
object is just another kind of Turing machine.

The key to understanding OOP is to realize that each object is a
*distinct* Turing machine.

Each object has its own private set of attributes, which makes
it equivalent to a random access machine with it own private
address space, or to a Turing machine with its own private tape.
By those terms, the central concept of OOP can be summed up in
just three words:

    no shared tape

An Object-Oriented program is a network of objects that,
ideally, share no data storage at all.

Classes, inheritance, access control, and all those other OO
terms are derivative concepts that we'll deal with later.  
Either they involve communication between objects, or they
involve telling a runtime environment how to create new objects.
Before we can make sense out of those, you need to understand
how objects themselves work.


---- Programming theory

Programming theory is pretty much the science of understanding
Turing machines.. what they are, and how they work.   And as
with most sciences, programming theory breaks Turing machines
down into pieces that are smaller, simpler, and easier to
understand.

The simple machines of programming are:

    - Simple expressions
    - Parametric expressions
    - Finite automata
    - Pushdown automata
    - Turing machines

Each one corresponds to a certain kind of information:

    - Simple expressions        ==  values
    - Parametric expressions    ==  enumerable sets
    - Finite automata           ==  regular expressions
    - Pushdown automata         ==  context-free grammars
    - Turing machines           ==  contextual recursive grammars

And each one lets programmers work with certain basic concepts:

    - Simple expressions        ==  representation and
                                    identification
    - Parametric expressions    ==  relation
    - Finite automata           ==  state and behavior
    - Pushdown automata         ==  encapsulation
    - Turing machines           ==  arbitrary data storage

The next few sections will examine those machines, types of
information, and concepts.
[download]