Name Date Period

← CS Unplugged

CS Unplugged activity

Little Man Computer: tracing a program

About 20 minutesSoloPencil

Every computer, from a phone to a supercomputer, runs the same basic loop: read one instruction, do exactly what it says, move to the next one. The Little Man Computer (LMC) is a paper model of that loop, invented by Stuart Madnick in 1965, small enough to trace with a pencil. If you can trace one of these programs by hand, you understand what a processor actually does.

Meet the model

Picture a little man sitting in a room of 100 numbered mailboxes, each holding one three-digit number. He keeps one number in his hand at a time, the accumulator, along with a calculator that can only add and subtract. He works through a numbered list of instructions one at a time, reading a number from the input tray, doing arithmetic with a mailbox, or sending a number out to the output tray, until an instruction tells him to stop.

How the pieces connect: numbers come in through the input tray, the accumulator does the arithmetic with the mailboxes, and results leave through the output tray.

The instructions

Every instruction is a 3-digit number: the first digit says what to do, the last two say which mailbox to do it to. INP, OUT, and HLT don’t need a mailbox, so they use fixed codes instead.

Code	Mnemonic	What it does
1xx	ADD	Add the mailbox to the accumulator.
2xx	SUB	Subtract the mailbox from the accumulator.
3xx	STA	Store the accumulator into the mailbox.
5xx	LDA	Load the mailbox into the accumulator.
6xx	BRA	Branch (jump) to that instruction, always.
7xx	BRZ	Branch there, but only if the accumulator is exactly zero.
8xx	BRP	Branch there, but only if the accumulator is zero or positive.
901	INP	Take the next number from the input tray.
902	OUT	Send the accumulator to the output tray.
000	HLT	Stop. The program is over.
(none)	DAT	Not an instruction. Just a number sitting in its own mailbox.

This sheet only uses straight-line programs: no BRA, BRZ, or BRP yet. The little man just works down the list, one line at a time, until HLT. Branches are their own idea, on the next sheet.

Worked example

Here’s a program that takes two numbers from the input tray, adds them, and outputs the total. The number in front of each line is its address, which mailbox it lives in, counting from 00. The trace table below it is filled in already: study it before you try one yourself.

Now you trace it

For each program below: start at address 00, follow the program counter one instruction at a time, and fill in every row, in order, exactly the way the worked example did it. The table always has exactly as many rows as the program takes steps, so if you run out of rows, check your last few answers.