Hands-on lab — Day 2: The CPU: Fetch, Decode, Execute

# add-two-numbers.txt — the demonstration program from the Day 2 lesson.
# Loads 5 and 3 into registers, adds them into R3, prints the sum, stops.
LOAD R1,5
LOAD R2,3
ADD R1,R2->R3
PRINT R3
HALT

# trace-01.txt — worksheet program 1. Predict the output before running.
LOAD R1,4
LOAD R2,7
ADD R1,R2->R3
PRINT R3
HALT

# trace-02.txt — worksheet program 2. A register can be a source and the
# destination of the same instruction. Predict the output before running.
LOAD R1,10
ADD R1,R1->R2
ADD R2,R2->R2
PRINT R2
HALT

# trace-03.txt — worksheet program 3. Two PRINTs: the machine outputs the
# register's value at that moment. Predict both outputs before running.
LOAD R1,6
LOAD R2,2
ADD R1,R2->R1
PRINT R1
ADD R1,R2->R1
PRINT R1
HALT

#!/usr/bin/env bash
# toy_cpu.sh — a four-instruction toy CPU simulator for the Day 2 lab.
#
# It reads a program file (one instruction per line, '#' starts a comment)
# and executes it exactly the way the lesson describes: fetch the
# instruction at the program counter (PC), advance the PC, decode the
# instruction into an opcode and operands, execute it, and show the
# register state after every step.
#
# Instruction set (opcodes must be uppercase):
#   LOAD Rn,value      put an integer into register Rn
#   ADD Ra,Rb->Rc      add registers Ra and Rb, store the sum in Rc
#   PRINT Rn           send the value of register Rn to the output
#   HALT               stop the machine
#
# Registers: R1 R2 R3 R4, all starting at 0.
#
# Usage: bash toy_cpu.sh <program-file>
#
# Exit codes: 0 = program ran to HALT; 1 = bad instruction or no HALT;
#             2 = usage error (missing or unreadable program file).
set -u

if [ $# -ne 1 ]; then
  echo "usage: bash $0 <program-file>" >&2
  exit 2
fi
program_file="$1"
if [ ! -f "${program_file}" ]; then
  echo "error: program file not found: ${program_file}" >&2
  exit 2
fi

# --- machine state -----------------------------------------------------
R1=0; R2=0; R3=0; R4=0
PC=0
executed=0
halted=no

die() {
  # PC has already advanced past the fetched instruction, so report PC-1.
  echo "ERROR at PC=$((PC - 1)): $1" >&2
  exit 1
}

is_reg() {
  case "$1" in
    R1 | R2 | R3 | R4) return 0 ;;
    *) return 1 ;;
  esac
}

reg_value() {
  # Caller must have validated the name with is_reg first.
  eval "printf '%s' \"\$$1\""
}

set_reg() {
  eval "$1=\$2"
}

is_int() {
  case "$1" in
    '' | -) return 1 ;;
    -*) case "${1#-}" in *[!0-9]* | '') return 1 ;; *) return 0 ;; esac ;;
    *[!0-9]*) return 1 ;;
    *) return 0 ;;
  esac
}

# --- load the program into "memory" (a bash array) ---------------------
program=()
while IFS= read -r raw || [ -n "${raw}" ]; do
  line="${raw%%#*}"                              # strip comments
  line="${line#"${line%%[![:space:]]*}"}"        # trim leading whitespace
  line="${line%"${line##*[![:space:]]}"}"        # trim trailing whitespace
  [ -z "${line}" ] && continue
  program[${#program[@]}]="${line}"
done < "${program_file}"

if [ "${#program[@]}" -eq 0 ]; then
  echo "error: ${program_file} contains no instructions" >&2
  exit 2
fi

echo "=== Toy CPU ==="
echo "Program: ${program_file} (${#program[@]} instructions in memory)"
echo "Registers start at: R1=0 R2=0 R3=0 R4=0"
echo

# --- the fetch-decode-execute loop --------------------------------------
while [ "${PC}" -lt "${#program[@]}" ]; do
  instr="${program[${PC}]}"
  printf 'PC=%s  FETCH    %s\n' "${PC}" "${instr}"
  PC=$((PC + 1))                                 # PC advances right after fetch

  case "${instr}" in
    *' '*) op="${instr%% *}"; args="${instr#* }" ;;
    *) op="${instr}"; args="" ;;
  esac
  args="$(printf '%s' "${args}" | tr -d '[:space:]')"

  case "${op}" in
    LOAD)
      dest="${args%%,*}"
      value="${args#*,}"
      [ "${dest}" = "${args}" ] && die "LOAD needs the form: LOAD Rn,value"
      is_reg "${dest}" || die "unknown register '${dest}' (valid: R1 R2 R3 R4)"
      is_int "${value}" || die "'${value}' is not an integer"
      printf '      DECODE   opcode=LOAD  dest=%s  value=%s\n' "${dest}" "${value}"
      set_reg "${dest}" "${value}"
      printf '      EXECUTE  %s <- %s\n' "${dest}" "${value}"
      ;;
    ADD)
      case "${args}" in
        *,*'->'*) ;;
        *) die "ADD needs the form: ADD Ra,Rb->Rc" ;;
      esac
      src1="${args%%,*}"
      rest="${args#*,}"
      src2="${rest%%->*}"
      dest="${rest#*->}"
      is_reg "${src1}" || die "unknown register '${src1}' (valid: R1 R2 R3 R4)"
      is_reg "${src2}" || die "unknown register '${src2}' (valid: R1 R2 R3 R4)"
      is_reg "${dest}" || die "unknown register '${dest}' (valid: R1 R2 R3 R4)"
      v1="$(reg_value "${src1}")"
      v2="$(reg_value "${src2}")"
      sum=$((v1 + v2))
      printf '      DECODE   opcode=ADD  src1=%s  src2=%s  dest=%s\n' "${src1}" "${src2}" "${dest}"
      set_reg "${dest}" "${sum}"
      printf '      EXECUTE  %s <- %s + %s = %s + %s = %s\n' "${dest}" "${src1}" "${src2}" "${v1}" "${v2}" "${sum}"
      ;;
    PRINT)
      reg="${args}"
      [ -n "${reg}" ] || die "PRINT needs the form: PRINT Rn"
      is_reg "${reg}" || die "unknown register '${reg}' (valid: R1 R2 R3 R4)"
      printf '      DECODE   opcode=PRINT  reg=%s\n' "${reg}"
      printf '      EXECUTE  send %s to the output\n' "${reg}"
      printf 'OUTPUT: %s\n' "$(reg_value "${reg}")"
      ;;
    HALT)
      printf '      DECODE   opcode=HALT\n'
      printf '      EXECUTE  stop the clock\n'
      executed=$((executed + 1))
      halted=yes
      break
      ;;
    *)
      die "unknown opcode '${op}' (valid: LOAD ADD PRINT HALT)"
      ;;
  esac

  executed=$((executed + 1))
  printf '      REGS     R1=%s R2=%s R3=%s R4=%s\n\n' "${R1}" "${R2}" "${R3}" "${R4}"
done

echo
if [ "${halted}" = yes ]; then
  echo "HALT reached after ${executed} instructions."
  echo "Final registers: R1=${R1} R2=${R2} R3=${R3} R4=${R4}"
else
  echo "ERROR: the program ended without HALT — a real CPU would keep fetching whatever bits sit in the next memory cells and try to execute them." >&2
  exit 1
fi

lesson_id: D002
day: 2
kind: process-simulation
languages: [bash]
setup_commands:
  - cd labs/sections/computing-foundations/day-002-the-cpu-fetch-decode-execute
run_commands:
  - bash examples/toy_cpu.sh examples/programs/add-two-numbers.txt
  - bash examples/toy_cpu.sh examples/programs/trace-01.txt
  - bash examples/toy_cpu.sh examples/programs/trace-02.txt
  - bash examples/toy_cpu.sh examples/programs/trace-03.txt
  - bash examples/toy_cpu.sh starter/my_program.txt
test_commands:
  - bash tests/run_tests.sh
cleanup_commands:
  - 'git checkout -- starter/my_program.txt starter/trace-worksheet.md  # optional: reset your work'
requires_network: false
requires_api_key: false
estimated_minutes: 30
last_executed: '2026-07-12'
executed_on: 'macOS (Apple Silicon), bash tests/run_tests.sh → 27 checks, 0 failure(s).'

# Dependencies — Day 002 lab

**None beyond a POSIX shell.** This lab intentionally has zero installable
dependencies:

- `bash` ≥ 3.2 (preinstalled on macOS and every mainstream Linux
  distribution; on Windows, use WSL).
- Standard utilities the scripts call: `tr`, `grep`, `sed`, `mktemp`,
  `dirname` — all part of the base system on macOS and Linux.

There is deliberately no `requirements.txt`/`package.json` here: the toy
CPU is a single readable shell script, because the point of the lab is
that you can see every moving part. Later labs declare their Python or
Node dependencies in this directory.

# my_program.txt — your own program for the toy CPU.
#
# It already works. From the lab directory, run:
#
#   bash examples/toy_cpu.sh starter/my_program.txt
#
# Then extend it. Rules of the machine:
#   - four registers: R1 R2 R3 R4, all starting at 0
#   - LOAD Rn,value   / ADD Ra,Rb->Rc / PRINT Rn / HALT
#   - opcodes in uppercase, one instruction per line, '#' starts a comment
#
# Ideas: double a number three times, sum three different values into R4,
# or print a register before and after changing it. Keep HALT last —
# remove it and watch what the simulator says.
LOAD R1,2
PRINT R1
HALT

# Trace worksheet — be the CPU before you run the CPU

Work through all three programs **by hand, on this sheet, before running
anything**. That order matters: predicting first and checking second is how
you find out whether your mental model of fetch-decode-execute is right.
The programs live in `../examples/programs/`.

Rules of the machine (same as the lesson):

- Four registers — R1, R2, R3, R4 — all start at 0.
- The PC starts at 0 and moves to the next line after each fetch.
- `LOAD Rn,value` puts a number in a register. `ADD Ra,Rb->Rc` adds two
  registers into a third (which may be one of the sources). `PRINT Rn`
  emits `OUTPUT: <value>`. `HALT` stops the machine.

Fill every empty cell. The first row of program 1 is done for you.

## Program 1 — `trace-01.txt`

```text
LOAD R1,4
LOAD R2,7
ADD R1,R2->R3
PRINT R3
HALT
```

| PC | Instruction | What the execute step does | R1 | R2 | R3 | R4 |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | `LOAD R1,4` | R1 gets the value 4 | 4 | 0 | 0 | 0 |
| 1 | `LOAD R2,7` |  |  |  |  |  |
| 2 | `ADD R1,R2->R3` |  |  |  |  |  |
| 3 | `PRINT R3` |  |  |  |  |  |
| 4 | `HALT` |  |  |  |  |  |

- Predicted `OUTPUT:` line(s): `OUTPUT: ____`
- Predicted final line: `Final registers: R1=__ R2=__ R3=__ R4=__`
- Predicted instruction count in `HALT reached after __ instructions.`

## Program 2 — `trace-02.txt`

```text
LOAD R1,10
ADD R1,R1->R2
ADD R2,R2->R2
PRINT R2
HALT
```

Watch the third line closely: R2 is both a source and the destination. The
ALU reads the old value, computes, and only then does the write-back
replace it.

| PC | Instruction | What the execute step does | R1 | R2 | R3 | R4 |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | `LOAD R1,10` |  |  |  |  |  |
| 1 | `ADD R1,R1->R2` |  |  |  |  |  |
| 2 | `ADD R2,R2->R2` |  |  |  |  |  |
| 3 | `PRINT R2` |  |  |  |  |  |
| 4 | `HALT` |  |  |  |  |  |

- Predicted `OUTPUT:` line(s): `OUTPUT: ____`
- Predicted final line: `Final registers: R1=__ R2=__ R3=__ R4=__`
- Predicted instruction count in `HALT reached after __ instructions.`

## Program 3 — `trace-03.txt`

```text
LOAD R1,6
LOAD R2,2
ADD R1,R2->R1
PRINT R1
ADD R1,R2->R1
PRINT R1
HALT
```

Two `PRINT`s: each one emits the register's value *at that moment*, so the
two output lines will differ.

| PC | Instruction | What the execute step does | R1 | R2 | R3 | R4 |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | `LOAD R1,6` |  |  |  |  |  |
| 1 | `LOAD R2,2` |  |  |  |  |  |
| 2 | `ADD R1,R2->R1` |  |  |  |  |  |
| 3 | `PRINT R1` |  |  |  |  |  |
| 4 | `ADD R1,R2->R1` |  |  |  |  |  |
| 5 | `PRINT R1` |  |  |  |  |  |
| 6 | `HALT` |  |  |  |  |  |

- Predicted `OUTPUT:` line(s): `OUTPUT: ____` and `OUTPUT: ____`
- Predicted final line: `Final registers: R1=__ R2=__ R3=__ R4=__`
- Predicted instruction count in `HALT reached after __ instructions.`

## Check yourself

Only now, run each program and compare every prediction:

```bash
bash ../examples/toy_cpu.sh ../examples/programs/trace-01.txt
bash ../examples/toy_cpu.sh ../examples/programs/trace-02.txt
bash ../examples/toy_cpu.sh ../examples/programs/trace-03.txt
```

For any cell you got wrong, write one sentence below it about *why* — the
mistake is more valuable than the correction. The most common ones: using
a register's new value one step too early (program 2), and forgetting that
`PRINT` reports the value at that instant, not the final value (program 3).

#!/usr/bin/env bash
# Tests for the Day 002 lab. Run from the lab directory:
#   bash tests/run_tests.sh
#
# Verifies that the toy CPU simulator produces exactly the outputs, step
# counts, and final register states the lesson and worksheet promise, that
# the learner's program in starter/my_program.txt runs to HALT, and that
# the simulator rejects bad programs with a non-zero exit code.
set -u

lab_dir="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." && pwd)"
cpu="${lab_dir}/examples/toy_cpu.sh"
failures=0
checks=0

check() {
  local label="$1" ok="$2"
  checks=$((checks + 1))
  if [ "${ok}" = "yes" ]; then
    echo "  ok: ${label}"
  else
    echo "  FAIL: ${label}"
    failures=$((failures + 1))
  fi
}

contains() {
  # contains <haystack> <needle-regex-free-fixed-string>
  case "$1" in *"$2"*) return 0 ;; *) return 1 ;; esac
}

run_program_checks() {
  # run_program_checks <program> <label> <steps> <final-regs> <output-values...>
  local program="$1" label="$2" steps="$3" regs="$4"
  shift 4
  local output
  echo "Testing ${label} ..."
  if ! output="$(bash "${cpu}" "${program}" 2>&1)"; then
    check "${label}: simulator exits 0" "no"
    echo "${output}" | sed 's/^/    /'
    return
  fi
  check "${label}: simulator exits 0" "yes"

  local fetches
  fetches="$(printf '%s\n' "${output}" | grep -c '^PC=[0-9]*  FETCH')"
  if [ "${fetches}" = "${steps}" ]; then
    check "${label}: ${steps} instructions fetched" "yes"
  else
    check "${label}: ${steps} instructions fetched (got ${fetches})" "no"
  fi

  if contains "${output}" "HALT reached after ${steps} instructions."; then
    check "${label}: halts after ${steps} instructions" "yes"
  else
    check "${label}: halts after ${steps} instructions" "no"
  fi

  if contains "${output}" "Final registers: ${regs}"; then
    check "${label}: final registers are '${regs}'" "yes"
  else
    check "${label}: final registers are '${regs}'" "no"
  fi

  local expected_outputs actual_outputs
  expected_outputs=""
  for v in "$@"; do
    expected_outputs="${expected_outputs}OUTPUT: ${v}
"
  done
  actual_outputs="$(printf '%s\n' "${output}" | grep '^OUTPUT: ' || true)
"
  if [ "${actual_outputs}" = "${expected_outputs}" ]; then
    check "${label}: output lines are exactly [$*]" "yes"
  else
    check "${label}: output lines are exactly [$*]" "no"
  fi
}

# --- 1. the reference programs, against the values on the worksheet -----
run_program_checks "${lab_dir}/examples/programs/add-two-numbers.txt" \
  "add-two-numbers" 5 "R1=5 R2=3 R3=8 R4=0" 8
run_program_checks "${lab_dir}/examples/programs/trace-01.txt" \
  "trace-01" 5 "R1=4 R2=7 R3=11 R4=0" 11
run_program_checks "${lab_dir}/examples/programs/trace-02.txt" \
  "trace-02" 5 "R1=10 R2=40 R3=0 R4=0" 40
run_program_checks "${lab_dir}/examples/programs/trace-03.txt" \
  "trace-03" 7 "R1=10 R2=2 R3=0 R4=0" 8 10

# --- 2. the learner's own program ---------------------------------------
echo "Testing starter/my_program.txt ..."
if my_out="$(bash "${cpu}" "${lab_dir}/starter/my_program.txt" 2>&1)"; then
  check "my_program: runs to completion (exit 0)" "yes"
else
  check "my_program: runs to completion (exit 0)" "no"
  echo "${my_out}" | sed 's/^/    /'
  my_out=""
fi
if printf '%s\n' "${my_out}" | grep -q '^OUTPUT: '; then
  check "my_program: produces at least one OUTPUT line" "yes"
else
  check "my_program: produces at least one OUTPUT line" "no"
fi
if contains "${my_out}" "HALT reached after"; then
  check "my_program: ends with HALT" "yes"
else
  check "my_program: ends with HALT" "no"
fi

# --- 3. the simulator must reject broken programs ------------------------
echo "Testing error handling ..."
tmp_dir="$(mktemp -d)"
trap 'rm -rf "${tmp_dir}"' EXIT

printf 'FLY R1,3\nHALT\n' > "${tmp_dir}/bad-opcode.txt"
if bash "${cpu}" "${tmp_dir}/bad-opcode.txt" >/dev/null 2>&1; then
  check "unknown opcode is rejected (non-zero exit)" "no"
else
  check "unknown opcode is rejected (non-zero exit)" "yes"
fi

printf 'LOAD R9,1\nHALT\n' > "${tmp_dir}/bad-register.txt"
if bash "${cpu}" "${tmp_dir}/bad-register.txt" >/dev/null 2>&1; then
  check "unknown register is rejected (non-zero exit)" "no"
else
  check "unknown register is rejected (non-zero exit)" "yes"
fi

printf 'LOAD R1,1\nPRINT R1\n' > "${tmp_dir}/no-halt.txt"
if bash "${cpu}" "${tmp_dir}/no-halt.txt" >/dev/null 2>&1; then
  check "program without HALT is rejected (non-zero exit)" "no"
else
  check "program without HALT is rejected (non-zero exit)" "yes"
fi

if bash "${cpu}" "${tmp_dir}/does-not-exist.txt" >/dev/null 2>&1; then
  check "missing program file is rejected (non-zero exit)" "no"
else
  check "missing program file is rejected (non-zero exit)" "yes"
fi

echo
echo "${checks} checks, ${failures} failure(s)."
[ "${failures}" -eq 0 ]