Table of Contents
What is a Program?
Computational processes are abstract beings that inhabit computers…People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells. — Harold Abelson and Gerald Sussman
I can claim with absolute certainty that if you are reading these notes you have used a computer program before. I can claim with less certainty, although I think there's pretty decent odds considering undergraduates are often American citizens, that you have driven, or have been driven by, a car. I'd say there's a good chance that if that's the case you likely don't know all about the mechanics involved in make a car go: the inner workings of the combustion engine, the way the transmission changes the direction of rotation, how the break fluid transfers pressure from your foot to stop the wheels, etc. This is much the same how you may not have known anything about how when you boot up your laptop that there's an entire world of transistors that begin firing off to let you eventually launch your browser of choice to browse the internet.
It's fine to not know how a car works if you're not in the market to build cars. It's less fine to not know how a computer program works if you're in the market to make computer programs. The point of this course is to get you closer to understanding how a computer program works and to get you on the right track to build up your knowledge in the future.
Why Do We Program?
Computer programming is a practical effort in real-world problem solving. It is primarily an intellectual exercise involving the careful balancing of the rules of computation with the desired outcomes envisioned by the programmer. In the most obvious way, the fact that computers dominate our daily lives implies that they must have some sort of use value, i.e. there must be a reason to program them. When asked, sophomore computer science students often come up with the following points:
- To automate tasks
- To simplify tasks
- To store the results of tasks
Once a computer program has been written and transformed into a runnable state, a human being no longer has to perform the same mental calculus that was needed in order to write it in the first place. They simply run the program and record the results (or maybe the results are recorded for them!). For example, the first computer programs were written to help speed up ballistics calculations for naval warfare—all the user needed to do was provide information about the variables involved and the machine would perform all necesarry computations.
What Are the Components?
Nearly all modern day computers follow a design philosophy which was established in the late 1940s: the Von Neumann Machine. Named after the Hungarian-American mathematician Jon von Neumann, the Von Neumann Machine is a logical abstraction of a computation machine which, in its simplest formulation, is constituded of just four parts:
- Input Unit
- Central Processing Unit
- Memory Unit
- Output Unit
These four "components" are often represented as such:
+-------------+ +---------------------+ +-------------+
| | | | | |
| Input Unit +---->+ Central Processing +---->+ Output Unit |
| (1) | | Unit | | (4) |
| | | (2) | | |
+-------------+ +----------+----------+ +-------------+
|
|
+----------+----------+
| |
| Memory Unit |
| (3) |
+---------------------+
(1) Takes input from the user, without which we would have no way of interacting with the machine. (2) The "brain" of the machine that decodes instructions and carries them out. (3) Provides temoporary storage for larger computations. (4) Displays output to the user, without which we would have no way to get our results.
Real world machines are often more complicated than Listing 1, but more often than not they can still be reduced to the same abstraction from a programmer's point of view1.
What's Special About the Von Neumann Model?
Von Neumann developed his famous abstraction with inspiration derived from another titan of computer science, Alan Turing. Turing in his watershed paper, On Computable Numbers, with an Application to the Entscheidungsproblem, gave the outline for a way to model computation in a pure, formal system. In it he states that "it is possible to invent a single machine which can be used to compute any computable sequence"—this powerful, abstract machine would later be named a Turing Machine. A diagram is shown below:
State Register
+----------+
| q1 |
+----+-----+
|
v
+------+------+
| Control |
| Unit |
+--+------+---+
| |
read | | write + move
v v
<-- L +---+---+---+---+---+---+---+ R -->
infinite | _ | _ | 1 | 0 | 1 | _ | _ | infinite
+---+---+---+---+---+---+---+
^
|
+----+----+
| Head |
+---------+
The machine is quite simple, it takes input from tape and writes output to that tape. Its instruction set, i.e. it's language, dictates how the head will move around the tape. Some instructions move it to the left, others to the right; some instructions skip spaces, others write to spaces; etc. Turing's great insight was that this abstract machine could represent every conceivable computation a human being could think up. There is not a single actionable mathematical computation that can't be represented by a Turing Machine. Taken one step further, a Turing Machine can be constructed which takes as its input other Turing Machines. This "super" Turing Machine is called a Universal Turing Machine and it was what Von Neumann based his computer design on. There are theoretical limitations of the Turing Machine, but that is outside the scope of this class2.
The uniqueness of the Turing Machine is that the tape does not distinguish between instructions and data, i.e. instructions can be manipulated like anything else.
How Do We Get the Instructions?
It should be clear now that in order to program a computer we must provide it with instructions. Here's an example you saw in the previous lecture:
1: #include <stdio.h> 2: int main(){ 3: printf("Hello, World!\n"); 4: }
Listing 3 is a small program that prints "Hello, World!" out to the screen. But how does it print out to the screen? How does this strange, sentence-like structure turn into something the computer can "understand"? This is something we'll learn later in the course.
So, What is a Program?
A program is nothing more than a set of instructions which tells a machine what to do. They can be as complicated as Linux or as simple as a single HALT instruction. By the end of this course you'll be able to write C programs that fall somewhere in-between those two extremes.
Exercises
- Think up more reasons one might program. Does it fall into one or more of the given categories?
- Assume we have a Turing Machine with tape that has letters of the English alphabet as shown in Listing 4, further assume the head will point at A to start. Each time the head moves it will print the character it lands on. Write down the instructions needed to print out your first name.
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
- Think about a computer program you use every day. While doing so, try to think about all of the steps that might be involved in getting that program to actually run on real hardware. (Try not to give yourself a migrane…)
Footnotes:
This, of course, varies depending on the sorts of programming one engages in. A software engineer dealing with high-minded business logic can think the computer "looks like" a few floating rectangles, but a computer engineer working on an embedded device will need an entirely different mental model. For this class, we'll stick to the high-minded abstraction provided by the Von Neumann machine. At least for now…
One such impasse being the "Halting Problem". It is impossible to construct a Universal Turing Machine capable of knowing whether or not an incoming Turing Machine is going to "halt" (stop processing instructions).