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

Introduction

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.

Let's start!

The code

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 store, load and branch constants; these are the base machine code for the STA, LDA, and 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 stack-r.

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 push.

Factorials

Introduction

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.

The code

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:

  1. Accept user input and store it in a, this will be the number we will work out the factorial of.
  2. Subtract 1 and store that in d and b. This sets up our first multiplication, i.e. input times input - 1.
  3. Branch to mul to perform the multiplication.
  4. Load the value of d which acts as our counter to keep track of what we are multiplying next.
  5. Subtract 1 from d and end the program (outputting the result) if it is 0.
  6. Store d in b and c in a to set up the next multiplication (the previous result times the counter).
  7. Branch to mul to perform the next multiplication.
  8. 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.