🙋 The Little Man Stack Machine

Introduction

The Little Man Stack Machine (LMSM) is a backwards-compatible extension of the venerable and excellent Little Man Computer (LMC) teaching computer model. It is designed to be a teaching aid, to show people how various aspects of computing work in an easy and approachable manner:

• The operations of a basic Von Neumann style computer
• How assembly works
• How assembly can be converted to machine code
• How function calls can be implemented using basic hardware
• How recursive function calls work
• How stack-based languages work
• How a high-level programming language can be compiled to assembly

The LMSM is simple enough that someone interested should be able to build an LMSM emulator, an assembler and a compiler from a high-level language to assembly in a short amount of time, such as within a single quarter or semester.

Like the LMC, the LMSM models a simple Von Neumann computing machine and the execution cycle is identical to the LMC. In order to better support more computational topics that the LMC did, the LMSM adds the following functionality:

• The memory space of the LMSM is doubled from 100 slots to 200 slots.
• Two new registers are available:
  • The stack_pointer register that points to the top of the value stack.
  • The return_address_pointer register that points to the top of the return address stack.
• A new LDI "immediate" instruction is added for loading immediate values directly into the accumulator.
• A new set of stack-related instructions are available for working with the two stacks available on the LMSM.
• Two "virtual" assembly instructions are available to make assembly coding on the LMSM a bit more pleasant.

System Diagram

Below is a system diagram of the LMSM:

Overall System Description

Like the LMC, the LMSM works only in terms of integers between the values -999 and 999. These integers can be interpreted as either data or as instructions, depending on the context they are used in. The LMSM follows a simple Von Neumann style Instruction Cycle: it loads an instruction from memory, bumps the program counter, executes the instruction and then repeats.

More detail on the execution cycle can be found on the Assembly & Execution page.

Registers

The LMSM has a total of five registers (two more than the LMC). The registers are as follows:

• The program_counter register - a register that points to memory location of the next instruction to execute. This register starts with the value 0.
• The accumulator register - a register that is used to "accumulate" values by, for example, an instruction adding a value in memory to the value already in the accumulator. This register starts at value 0.
• The current_instruction register - a register that holds the currently executing instruction. This register starts at value 0.
• The stack_pointer register - a register that points to the memory location at the "top" of the value stack. This pointer starts at value 200 (meaning that the value stack is empty) and is decremented as the value stack grows.
• The return_address_pointer register - a register that points to the memory location at the "top" of the return address stack. This pointer starts at value 99 (meaning that the return address stack is empty) and it is incremented as the return address stack grows.

Memory

The LMSM has a total of 200 memory slots, double that of the LCM. The memory is split into two sections: "lower" and "upper" segments. Traditional LMC instructions such as ADD operate on the lower memory segment, while the new stack instructions of the LMSM operate on the upper section of memory.

The Stacks & Function Calls

A major goal of the LMSM is to provide hardware infrastructure for implementing function calls so that students can see how the function call abstraction can be implemented on top of raw registers and memory. This is a crucial concept in computer science, allowing us to build far more sophisticated pieces of software than raw assembly does.

The function invocation mechanism in the LMSM is very simple when compared with real-world computers, but it demonstrates the core concepts of using stacks to hold function-call related values and recursive function calls.

See Functions for a detailed look at function calls on the LMSM.

Firth

While the LMC is great for introducing students to assembly and how low level computation works, it does not provide enough infrastructure for easily creating a high-level programming language.

By offering a slightly more sophisticated CPU model the LMSM makes it possible to create a simple Forth-inspired language in a relatively short amount of time. This "high-level" language can then be compiled down to LSMS assembly code fairly easily.

The language includes functions, loops, conditionals and so, er, forth: the basics of higher-level programming.

See Firth for more information on this language.