[Second try; I don't know what happened to the first one.
Cc'ed to the OP, just in case Usenet eats this one too.
F-up to comp.programming.]
I posted a newsgroup question here a few weeks back, asking some
questions that related to my 10 year quest (so far) to understand
pointers.
Someone
Richard Heathfield. It would be nice if you'd take the time to
look up your quotes. Google Groups might help.
suggested I write a simple emulator. Part of his post is
below. I would have emailed him directly but a valid email wasn't
included.
I'm sure its quite simple for him, but I don't get it! I understand
his suggestion conceptually, but don't have a clue where to start. How
will these 'programs' run? How will the instructions be executed? What
do I do with the instructions? Just print them on the screen? Jeez,
maybe if I was a hardware engineer I might have a clue.
Basically, Richard is suggesting that you create an "imaginary
computer" from scratch -- you can even do this on paper. Once you
have got the basic idea, you can write a C program to emulate the
imaginary machine in software.
Personally, I think this is a bad way to learn pointers, although
it's a nice exercise for general understanding of how computers
work. See below.
[Richard Heathfield wrote:]
If you want to understand pointers, write a computer. Or rather,
write an emulator for the non-existent computer of your choice.
Start off simple. A 1-bit computer with 2 1-bit "bytes" of memory, a
1-bit instruction register (it holds the address in memory of the
next instruction to be executed), and one 1-bit register. Decide on
an instruction set for it (it'll have just two different instructions),
and then write it.
Okay. Let's make a computer! But first we need to get a few
terms straight. Most modern computers have "registers" and "memory."
Memory is the big open space where data is stored; there's a lot of
it, and it can be addressed sequentially. Memory is where the computer
stores programs and other data. Registers are by comparison very small
areas of storage; there are only a few of them, but most CPU operations,
or "opcodes," operate directly on them, so they're fast and useful.
Computer A is our first attempt at making a computer. It's the
1-bit computer Richard describes above.
Computer A has one 1-bit instruction register, IP ("Instruction
Pointer"). IP holds the memory address of the next instruction to
be executed by the CPU. After executing each instruction, the CPU
automatically increments IP by 1.
Exercise 0: How many different memory addresses does Computer A
have, in all?
Answer: Notice that IP is only one bit wide. That means that
Computer A can address only 2 memory addresses in all: address 0 and
address 1 ("M0" and "M1", in our notation).
Computer A also has a general-purpose register, R0. It's one bit
long, too.
Note that the registers IP and R0 don't have memory addresses;
M0 and M1 are distinct from the register set.
Notice also that the state of Computer A can be completely described
by only four numbers -- four bits, really. For example, one state of
Computer A is
IP: 0 R0: 1 M0: 1 M0: 0
These four numbers determine absolutely everything about the state
of the machine.
Now let's add some CPU opcodes, so that the computer can actually
start processing programs. First, we are always going to need a
"halt" opcode to terminate the program. Let opcode '0' be HALT.
Whenever IP ends up pointing to a memory address containing a HALT
opcode, the computer will stop executing the program (the program
will "terminate" successfully).
Let opcode '1' be the operation of printing "Hello world" to the
screen. (These imaginary opcodes can do whatever you like, really
-- but this is a nice user-friendly opcode that will make programming
Computer A a little more fun.)
Exercise 1: Suppose the state of the Computer A is
IP: 0 R0: 1 M0: 1 M0: 0
What happens if we let the computer run from this point? Does
the program terminate succesfully? Does anything get printed?
Answer: IP is 0. The instruction at memory address 0 is '1',
so we print "Hello world." IP is incremented by one. Now IP
is 1. The instruction at M1 is '0', HALT, so the program
terminates. So the effect of the total program is to print
"Hello world" and then halt -- the classic beginners' program!
Exercise 2: Suppose the state of the machine is
IP: 1 R0: 0 M0: 1 M0: 1
What happens if we let the computer run from this point?
Assume that all arithmetic on IP is done modulo 2, so that
the value of IP "wraps around" on overflow.
Answer: The opcode at M1 is '1', so we print "Hello world."
IP is incremented; we execute M0, which is '1', and print
"Hello world" again. IP is incremented to 1, and we print
"Hello world" again. And again. And so on. This program,
in short, is an infinite loop that never terminates.
Exercise 3: Draw on a piece of paper the 16 possible states of
Computer A. (16 is two to the fourth power.) Draw one more state,
and label it "Program Terminated."
Draw an arrow from each state to its "successor" state, the state
reached by executing the current instruction. Along each arrow,
write the output of the program at that stage (i.e., either "Hello
world" or nothing). What do you see?
Answer: This state diagram is pretty boring, isn't it? You should
have noticed by now that the R0 register isn't being used for
anything; you also might have noticed that all programs are either
infinite loops, or stop after one or two "instruction cycles." We'll
remedy this shortly.
/Then/ write programs for it. (These are easy: 00, 01, 10, 11. All done.)
I'm way ahead of you, Richard. ;-)
Exercise 4: Let the program AB (for any values A, B) be the state
IP: 0 R0: 0 M0: A M0: B
Describe the effects of the four programs 00, 01, 10, and 11.
This can be done in around 300 lines of C code. Less if you're a terse
coder, but mine is 300 lines (excluding a few printfs and comments),
and it even includes a rudimentary disassembler.
I must be a very terse coder, then.
Cut and paste this C program into another file, compile and run it.
Try out all four of the programs from Exercise 4. Do they do what
you thought they would? (Note that program 11, the infinite loop,
will require you to know how to break out of a program in your [real]
operating system -- try Ctrl-C for Windows or Linux.)
==cut here==
#include <stdio.h>
struct MemoryCell_1bit {
unsigned value: 1;
};
struct ComputerA {
unsigned R0: 1; /* 1 bit register */
unsigned IP: 1; /* 1 bit IP */
struct MemoryCell_1bit M[2]; /* (2 to the 1) memory cells */
};
#define OPCODE_HALT 0 /* stop the program */
#define OPCODE_HELW 1 /* print "Hello world" */
int main()
{
struct ComputerA a;
int t1, t2, t3, t4;
int running;
puts("Please input the initial values of R0, IP, M0 and M1,");
puts("in the following format: (1 1) (0 1) .");
printf("Input now. >");
fflush(stdout);
if (4 != scanf(" (%d%d ) (%d%d )", &t1, &t2, &t3, &t4)) {
puts("Something fouled up -- please run the program again.");
return 0;
}
a.R0 = t1;
a.IP = t2;
a.M[0].value = t3;
a.M[1].value = t4;
for (running = 1; running; a.IP++) {
switch (a.M[a.IP].value)
{
case OPCODE_HALT:
running = 0; /* halt program */
break;
case OPCODE_HELW:
puts("Hello world");
break;
}
}
puts("Program terminated.");
return 0;
}
==cut here==
Then write a 2-bit computer. That'll have four 2-bit "bytes" of
memory, a 2-bit instruction register, and perhaps you can be daring
and give it two 2-bit registers. The instruction set can have a
massive FOUR instructions.
All right, here's where it gets slightly more interesting. Let's
design Computer B, our 2-bit successor to Computer A. This time, I'm
going to describe it only using C, so take a moment to study the
implementation of Computer A before plunging ahead.
struct MemoryCell_2bit {
unsigned value: 2;
};
struct ComputerB {
unsigned R0: 2; /* 2 bit register */
unsigned IP: 2; /* 2 bit IP */
struct MemoryCell_2bit M[4]; /* (2 to the 2) memory cells */
};
#define OPCODE_HALT 0
#define OPCODE_LOAD 1 /* takes a memory address */
#define OPCODE_INCR 2 /* increment R0 */
#define OPCODE_STOR 3 /* takes a memory address */
You can see that Computer B has still only the one register, R0,
but that R0 and IP are now 2-bit registers, and so are the memory
cells (and now there are four of them). OPCODE_HALT still exists,
but I've taken away the HELW opcode and replaced it with three
more cryptic instructions: LOAD, INCR, and STOR.
LOAD takes the "byte" immediately following the opcode in memory
and uses those two bits as an address. It loads the value stored
at that address in memory into R0. (E.g., the two-byte instruction
sequence '1 3' loads the contents of M3 into R0.)
STOR does the reverse, storing the value currently in R0 back
into the specified memory location.
INCR simply increments R0.
Here is the rest of the code for my implementation of Computer B.
Notice that I've added the "print_machine_state" function, and that
the machine prints its state before executing each instruction.
This way we can keep track of what it's doing with our code.
You should also note that I didn't put any screen-output opcodes
in Computer B, so the "print_machine_state" output is the only
output we're going to get. While Computer B can do some pretty
neat things by modifying its own programs during execution, it
can't print "Hello world" anymore. (But wait a bit...)
#include <stdio.h>
#define NELEM(x) ((int)(sizeof (x) / sizeof *(x)))
void print_machine_state(struct ComputerB *p);
int main()
{
struct ComputerB b;
int t1, t2;
int i;
int running;
puts("Please input the initial values of R0, IP, and M0..M3,");
puts("in the following format: (3 0) (1 2 3 0) .");
printf("Input now. >");
fflush(stdout);
if (2 != scanf(" (%d%d ) (", &t1, &t2)) {
puts("Something fouled up -- please run the program again.");
return 0;
}
b.R0 = t1;
b.IP = t2;
for (i=0; i < NELEM(b.M); ++i) {
if (1 != scanf("%d", &t1)) {
puts("Something fouled up -- please run the program again.");
return 0;
}
b.M
.value = t1;
}
for (running = 1; running; b.IP++) {
print_machine_state(&b);
switch (b.M[b.IP].value)
{
case OPCODE_HALT:
running = 0; /* halt program */
break;
case OPCODE_LOAD:
b.IP++;
b.R0 = b.M[b.M[b.IP].value].value;
break;
case OPCODE_INCR:
b.R0++;
break;
case OPCODE_STOR:
b.IP++;
b.M[b.M[b.IP].value].value = b.R0;
break;
}
}
puts("Program terminated.");
puts("The final state of the machine was:");
print_machine_state(&b);
return 0;
}
void print_machine_state(struct ComputerB *p)
{
int i;
printf(" IP: %d R0: %d\n", (int)p->IP, (int)p->R0);
for (i=0; i < NELEM(p->M); ++i)
printf(" M%d: %d", i, (int)p->M.value);
printf("\n");
}
Exercise 5: Repeat Exercise 3 with a subset of 20 or 30 states
from Computer B. (How many states does Computer B have in total?)
Draw arrows as before. What do you notice?
Answer: Computer B has 4096 (=4**6) states in total. That's much
too many to draw at once. But even with a small subset of the states,
you should see that the diagram is more interesting and complex than
that of Computer A.
My version takes about 350 lines. And the 3-bit version is about 400
lines. It's not difficult, believe me. And by the time you get up
to 8 bits, you /will/ understand pointers.
Hmm. In my opinion, Richard speaks the truth, but only because
you won't ever make it to eight bits without an understanding of
pointers -- I don't see the C implementation of these computers
really using too many pointers (and when they do, as in the LOAD
and STOR instructions, we have double indirection).
But try anyway.
Exercise 6: Design and implement Computer C, a 3-bit version of
Computer B. It will have 8 three-bit "bytes" of memory, and eight
opcodes. Add some opcodes at least that do the following: Print
a message to the screen. Print the value of R0. A "jump" opcode
that directly changes the value of IP.
HTH, and please follow up to comp.programming with any questions
not directly related to the C implementations,
-Arthur