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:

- 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
`mul`

to 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
`mul`

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