For any that don't know, LMC (little man computer) is a simple model of a computer which is mainly used for teaching students about von Neumann architecture. It only has 10 instructions, 100 memory addresses and only supports direct addressing. These features make it quite limited however provide just enough utility to perform many computational tasks. In this post I will explore a couple of more advanced tasks and how I solved them. You can find the most commonly used LMC emulator here.
A stack is a simple data structure that allows you to add (push) and remove (pop) pieces of data. Many architectures such as x86 have push and pop instructions built in however LMC doesn't have such a convenience. This means we will have to implement it ourselves.
Functions are commonly implemented in low-level languages by simply placing the arguments in predetermined registers and branching to the start of the procedure. This is exactly what we will aim to do: the push function should expect the value to add to the stack in the accumulator and the return address in the memory location labeled ret; the pop instruction should expect the return address in ret and should return the value taken off the stack in the accumulator.
There is one major caveat to our scheme however and that is the fact that as previously mentioned, LMC does not support indirect addressing. This means that to dynamically return from the functions and to change where on the stack we are storing to / retrieving from we will need to modify the future instructions in the program. Luckily enough, LMC is based on the von Neumann architecture meaning that machine code is data and data is machine code which allows us to simply use
STA to modify the program.
ret DAT one DAT 1 store DAT 300 load DAT 500 branch DAT 600 stack-t DAT stack-p DAT stack-p
Here we set up the data locations we will need. Note the
branch constants; these are the base machine code for the
BRA instructions respectively. Also note
stack-p DAT stack-p which is a handy way of getting the stack pointer to point to itself (the bottom of the program from where the stack will grow downwards).
stack-r STA stack-t LDA ret ADD branch STA stack-i LDA stack-t stack-i DAT ...
Next it is important to work out how we are going to return to the address specified in ret. This is the first instance where we need to modify the machine code that is about to be executed. First we store the current value of the accumulator in
stack-t as a measure to make sure we don't lose the contents while doing our memory manipulation. Next we load ret into the accumulator and add our
branch constant (600) to it which essentially builds the instruction to return to the address specified in ret. Now we store this instruction in memory location
stack-i and load
stack-t back into the accumulator. Finally we execute the instruction in
stack-i thus branching to the value of ret.
pop LDA stack-p ADD load STA pop-i SUB load SUB one STA stack-p pop-i DAT BRA stack-r ...
The time to implement the pop function is upon us. First we load
stack-p which holds the address of the most recently added value on the stack and add
load (500). This builds the instruction to load the value at the top of the stack into the accumulator. Now we store this instruction in
pop-i and decrement
stack-p by one. Finally
pop-i is executed and we branch to
stack-r to return to ret.
push STA stack-t LDA stack-p ADD one STA stack-p ADD store STA push-i LDA stack-t push-i DAT BRA stack-r ...
Our push procedure is much like pop but in reverse so I won't explain it in depth. We incriminate
stack-p by one, build the instruction to store the value of the accumulator at the top of the stack, e execute the instruction and branch to
The completed program is about 30 lines long which is over a quarter of available LMC memory and doesn't implement any sort of underflow protection meaning it is perhaps not the most practical data type for LMC programming. You can see the completed program below.
push STA stack-t LDA stack-p ADD one STA stack-p ADD store STA push-i LDA stack-t push-i DAT BRA stack-r pop LDA stack-p ADD load STA pop-i SUB load SUB one STA stack-p pop-i DAT BRA stack-r stack-r STA stack-t LDA ret ADD branch STA stack-i LDA stack-t stack-i DAT ret DAT one DAT 1 store DAT 300 load DAT 500 branch DAT 600 stack-t DAT stack-p DAT stack-p
Calling the functions
Whilst calling push or pop is as simple as
BRA push or
BRA pop it can be tough to get the arguments in the correct registers. Below I will show how I would go about pushing a value to the stack.
LDA ret-p STA ret LDA value BRA push ret-p DAT ret-l ret-l ...
First we load
ret-p which points to our return location (
ret-l) and store it in ret. Next we load the value we want to push into the accumulator. Finally we branch to
In maths $x!=x(x-1)\ldots(2)(1)$. E.g. $5!=5\times4\times3\times2\times1=120$. This is especially difficult in LMC as there is no multiplication instruction meaning we will have to implement that ourselves through repeated addition.
To make things clearer, implementing multiplication as if it were a function. We will say that in memory location a it will expert the first operand, in location b it will expect the second and will return the result in c. We only need to return to one location so we can just directly branch to ret without having to worry about modifying memory.
mul LDA zero STA c mul-l LDA c ADD a STA c LDA b SUB one STA b BRZ ret BRA mul-l zero DAT 0 a DAT b DAT c DAT 1 one DAT 1
This is a fairly simple implementation of multiplication so I won't explain it in depth. We first set c to 0. Now we add a to c and subtract 1 from b and continue to do this until b reaches 0 which means we will have added a to c b times which results in c becoming a times b. Finally we return to memory location ret.
INP STA a SUB one STA d STA b BRA mul ... ret LDA d SUB one BRZ end STA d STA b LDA c STA a BRA mul end LDA c OUT HLT d DAT ...
Okay, this is quite long, in fact it is the entire rest of the program. For this reason I will explain it step by step in an list:
- Accept user input and store it in a, this will be the number we will work out the factorial of.
- Subtract 1 and store that in d and b. This sets up our first multiplication, i.e. input times input - 1.
- Branch to
multo perform the multiplication.
- Load the value of d which acts as our counter to keep track of what we are multiplying next.
- Subtract 1 from d and end the program (outputting the result) if it is 0.
- Store d in b and c in a to set up the next multiplication (the previous result times the counter).
- Branch to
multo perform the next multiplication.
- Loop to 4.
Below I will show the full code with a couple of additions to deal with $1!$ and $0!$ as well as a couple of hacks to reduce the length of the code.
INP STA a BRZ end SUB one STA d STA b BRZ end BRA mul mul LDA zero STA c mul-l LDA c ADD a STA c LDA b SUB one STA b BRZ ret BRA mul-l ret LDA d SUB one BRZ end STA d STA b LDA c STA a BRA mul end LDA c OUT zero HLT a DAT b DAT c DAT 1 d DAT one DAT 1
Thank you for reading.