Assembly language: the Little Man Computer

OCR's LMC instruction set: tracing and writing programs with selection and iteration, run in Python.

A9.5Computer architectureA level25 min

Do this lesson in the simulator

Machine code is binary, and nobody wants to write it. Assembly language gives each machine code instruction a short mnemonic such as ADD or LDA, and lets you name addresses with labels. An assembler translates it into machine code, usually one instruction for one instruction. At GCSE (F6.5) you met assembly as a low-level language. At A level, OCR asks you to read, trace and write programs in a real, if tiny, instruction set: the Little Man Computer (LMC).

The model

The LMC imagines a little man in a room with:

  • 100 mailboxes, numbered 00 to 99: the memory, each holding a three-digit number, an instruction or data;
  • an accumulator: the register that holds the current value;
  • a program counter: the number of the mailbox to fetch next;
  • an in tray for input and an out tray for output.

He runs the fetch-decode-execute cycle forever: read the mailbox the program counter points at, add 1 to the counter, and do what the instruction says. The first digit of an instruction is the operation; the last two are the mailbox it uses. That is direct addressing, for every instruction.

The instruction set

Mnemonic Code What it does
ADD 1xx add the contents of mailbox xx to the accumulator
SUB 2xx subtract the contents of mailbox xx from the accumulator
STA 3xx store the accumulator in mailbox xx
LDA 5xx load the contents of mailbox xx into the accumulator
BRA 6xx branch always: set the program counter to xx
BRZ 7xx branch to xx if the accumulator is zero
BRP 8xx branch to xx if the accumulator is zero or positive
INP 901 copy the next input into the accumulator
OUT 902 output the accumulator
HLT 000 stop
DAT not an instruction: reserve a mailbox for data, with an optional starting value

There is no code starting with 4. There is no multiply, no compare and no "branch if negative": everything is built from these.

A first program: add two numbers

        INP             // accumulator = first input
        STA first       // keep it in mailbox "first"
        INP             // accumulator = second input
        ADD first       // add the first number to it
        OUT             // output the total
        HLT
first   DAT             // a mailbox for data

A label at the start of a line names that mailbox. first is mailbox 6, because it is on the seventh line, counting from 0. The assembler replaces each label with its number, so this program becomes the mailboxes 901 306 901 106 902 000 000.

Trace it with inputs 12 and 30:

Instruction PC after ACC first (mailbox 6) Output
INP 1 12 0
STA first 2 12 12
INP 3 30 12
ADD first 4 42 12
OUT 5 42 12 42
HLT 6 42 12

Selection: which is bigger?

The LMC has no "if A > B". Instead, subtract and test the sign. SUB leaves A - B in the accumulator, and BRP branches when that is zero or positive, which is exactly when A ≥ B.

        INP
        STA a
        INP
        STA b
        LDA a
        SUB b           // accumulator = a - b
        BRP abig        // a - b >= 0 means a >= b
        LDA b           // otherwise b was bigger
        OUT
        HLT
abig    LDA a
        OUT
        HLT
a       DAT
b       DAT

To test "equal", subtract and use BRZ. To test "less than", subtract the other way round, or branch past the code when BRP is true.

Iteration: a countdown

A loop is a branch backwards. This outputs the input, then counts down to 0:

        INP
        STA count
loop    LDA count
        OUT
        SUB one
        STA count
        BRP loop        // go round again while count is still >= 0
        HLT
count   DAT
one     DAT 1

With input 3 it outputs 3, 2, 1, 0. The constant 1 lives in a mailbox, because the LMC has no immediate addressing: every operand is a mailbox number.

Running LMC in Python

This is the whole Little Man Computer: an assembler that turns labels into mailbox numbers, and a fetch-decode-execute loop. In this version the accumulator can hold a negative number. In OCR's LMC a subtraction below zero sets a negative flag instead, and BRP tests that flag; the programs behave the same way.

OPCODES = {"ADD": 100, "SUB": 200, "STA": 300, "LDA": 500, "BRA": 600, "BRZ": 700, "BRP": 800,
           "INP": 901, "OUT": 902, "HLT": 0}

def assemble(source):
    lines = [text.split("//")[0].split() for text in source.split("\n")]
    lines = [words for words in lines if words]
    labels = {}
    for address, words in enumerate(lines):
        if words[0] not in OPCODES and words[0] != "DAT":
            labels[words[0]] = address
    mailboxes = [0] * 100
    for address, words in enumerate(lines):
        if words[0] in labels:
            words = words[1:]
        mnemonic = words[0]
        operand = words[1] if len(words) > 1 else "0"
        value = labels[operand] if operand in labels else int(operand)
        if mnemonic == "DAT":
            mailboxes[address] = value
        elif mnemonic in ("INP", "OUT", "HLT"):
            mailboxes[address] = OPCODES[mnemonic]
        else:
            mailboxes[address] = OPCODES[mnemonic] + value
    return mailboxes

def run_lmc(mailboxes, inputs):
    pc, acc = 0, 0
    while True:
        instruction = mailboxes[pc]                      # fetch
        pc = pc + 1
        opcode, xx = instruction // 100, instruction % 100   # decode
        if instruction == 0:   return                    # execute
        elif opcode == 1:      acc = acc + mailboxes[xx]
        elif opcode == 2:      acc = acc - mailboxes[xx]
        elif opcode == 3:      mailboxes[xx] = acc
        elif opcode == 5:      acc = mailboxes[xx]
        elif opcode == 6:      pc = xx
        elif opcode == 7:      pc = xx if acc == 0 else pc
        elif opcode == 8:      pc = xx if acc >= 0 else pc
        elif instruction == 901: acc = inputs.pop(0)
        elif instruction == 902: print("OUT", acc)

countdown = """
        INP
        STA count
loop    LDA count
        OUT
        SUB one
        STA count
        BRP loop
        HLT
count   DAT
one     DAT 1
"""
mailboxes = assemble(countdown)
print(mailboxes[:10])
run_lmc(mailboxes, [3])

Run this in the simulator

How to write LMC in an exam

  1. Write the algorithm in pseudocode first: inputs, the decision or loop, outputs.
  2. Give every variable a DAT line at the end, after HLT, so it is never executed as an instruction.
  3. Turn each comparison into a subtraction followed by BRZ or BRP.
  4. Trace your program with a small test, including the boundary where the two values are equal.

Task: the larger of each pair

Write an LMC program in the string program. It repeatedly inputs a pair of numbers, first and second, and outputs the larger of the two (either one if they are equal). If the first number of a pair is 0, it stops at once without reading a second number.

The inputs are whole numbers from 0 to 999. The task's inputs are 58, 23, 7, 19, 30, 30, 0, so the program must output OUT 58, OUT 19 and OUT 30, and nothing else. The folded helpers assemble and run_lmc are given: run_lmc prints each output as OUT and the value, and reads each input with input(). The robot does not move.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

OPCODES = {"ADD": 100, "SUB": 200, "STA": 300, "LDA": 500, "BRA": 600, "BRZ": 700, "BRP": 800,
           "INP": 901, "OUT": 902, "HLT": 0}

def assemble(source):
    lines = [text.split("//")[0].split() for text in source.split("\n")]
    lines = [words for words in lines if words]
    labels = {}
    for address, words in enumerate(lines):
        if words[0] not in OPCODES and words[0] != "DAT":
            labels[words[0]] = address
    mailboxes = [0] * 100
    for address, words in enumerate(lines):
        if words[0] in labels:
            words = words[1:]
        mnemonic = words[0]
        operand = words[1] if len(words) > 1 else "0"
        value = labels[operand] if operand in labels else int(operand)
        if mnemonic == "DAT":
            mailboxes[address] = value
        elif mnemonic in ("INP", "OUT", "HLT"):
            mailboxes[address] = OPCODES[mnemonic]
        else:
            mailboxes[address] = OPCODES[mnemonic] + value
    return mailboxes

def run_lmc(mailboxes, max_cycles=5000):
    pc, acc = 0, 0
    for cycle in range(max_cycles):
        instruction = mailboxes[pc]
        pc = pc + 1
        opcode, xx = instruction // 100, instruction % 100
        if instruction == 0:   return
        elif opcode == 1:      acc = acc + mailboxes[xx]
        elif opcode == 2:      acc = acc - mailboxes[xx]
        elif opcode == 3:      mailboxes[xx] = acc
        elif opcode == 5:      acc = mailboxes[xx]
        elif opcode == 6:      pc = xx
        elif opcode == 7:      pc = xx if acc == 0 else pc
        elif opcode == 8:      pc = xx if acc >= 0 else pc
        elif instruction == 901: acc = int(input("INP? "))
        elif instruction == 902: print("OUT", acc)
    print("stopped after", max_cycles, "cycles: a loop that never ends?")

program = """
        HLT
"""

run_lmc(assemble(program))

Challenges

  1. Write an LMC program that inputs two numbers and outputs their product, by repeated addition.
  2. Change the countdown so it stops at 1 instead of 0.
  3. What would happen if the DAT lines were put at the start of the program instead of the end?