Building a Simple Stack-Based Abstract Machine in Java

1. Background

This project was completed as part of a school assignment focused on understanding how low-level program execution works. The goal was to simulate an abstract machine that interprets a set of simplified machine instructions.

Instead of executing real CPU instructions, the system operates on a predefined instruction set that includes:

Stack manipulation
Control flow
Arithmetic operations
Logical operations
Relational operations

The idea behind this project is similar to how many virtual machines (such as JVM or stack-based interpreters) execute instructions using a stack-oriented architecture.

The abstract machine reads instructions sequentially and executes them using a stack as its primary data storage.

2. Implementation Details

The project was implemented using Java, with the core data structure being a stack.

Stack-Based Execution Model

All operations work by pushing and popping values from a stack.

Typical workflow:

Push values or addresses onto the stack.
Perform operations using the top values.
Store or manipulate results back onto the stack.

Example stack instructions include:

Instruction	Description
`push c`	Push constant `c` onto the stack
`rvalue l`	Push value stored at location `l`
`lvalue l`	Push address of location `l`
`pop`	Remove top value from the stack
`copy`	Duplicate the top value

Control Flow

The machine also supports basic branching instructions:

Instruction	Description
`label l`	Define a jump label
`goto l`	Jump to label `l`
`gofalse l`	Jump if top of stack is `0`
`gotrue l`	Jump if top of stack is non-zero
`halt`	Stop execution

These instructions allow the abstract machine to implement conditional logic and loops.

Arithmetic Operations

Arithmetic instructions operate on the top two stack values.

Operator	Function
`+`	Addition
`-`	Subtraction
`*`	Multiplication
`/`	Integer division
`div`	Remainder

Example:
push 5
push 3
+
Stack result:
8

Logical Operations

Logical instructions allow boolean-style evaluation.

Operator	Function
`&`	Logical AND
`!`	Logical NOT
`	`

These are particularly useful when evaluating conditions in control flow instructions.

Java Structure

The system was implemented with the following components:

Stack structure
- Implemented using java.util.Stack
Instruction parser
- Reads instructions line-by-line
Execution engine
- Interprets instructions and manipulates the stack
Memory store
- Simulates variable storage using a map or array

3. What I Learned

This project helped me understand several important concepts in computer science and software engineering.

How Stack-Based Machines Work

Before this project, I mainly interacted with high-level languages like Java. Implementing a stack machine gave me insight into how programs execute at a lower level.

Many virtual machines use stack-based execution because it simplifies instruction formats and memory management.

Interpreter Design

Building the instruction execution loop helped me understand:

instruction parsing
program counters
jump control
execution flow

These are fundamental ideas behind compilers, interpreters, and virtual machines.

Data Structure Application

Although stacks are simple, this project showed how powerful they can be. Almost all operations—including arithmetic, logic, and control flow—can be built on top of a stack structure.

Debugging Execution State

When implementing instruction execution, debugging required carefully tracking:

stack contents
program counter position
memory values

This improved my ability to reason about program state and execution flow.

Conclusion

This project provided a practical introduction to how programming languages and virtual machines execute instructions internally. By implementing a stack-based abstract machine in Java, I gained a deeper understanding of: