Simple Stack Machine

written by Teresa Carrigan


Top

WHAT IS IT?

This is a model of a generic zero-address computer, also known as a stack machine. This model does not show the numeric output of a program, but rather the standard infix expression for that output. This allows students to test their stack machine programs to see if the programs correctly implement the assigned expression.

Top

HOW IT WORKS

A generic stack machine assembly language has only six operations: Push, Pop, Add, Sub, Mul, and Div. Push adds an item to the top of the stack, then increments the stack pointer. Pop removes the item on the top of the stack. The items on the stack do not operate by themselves in this model; everything happens because of button clicks. This is inherent in any stack model, because only the top of the stack is allowed to be processed.

Top

HOW TO USE IT

First press the Setup button, which builds the base of the stack. Now push at least two items onto the stack, and then try pressing one of the operation buttons. If you have written a Stack Machine program that you wish to test, then for each line of the program simply press the appropriate button. To see a demonstration of a random program, repeatedly press the "Random command" button.

Setup - Initializes variables and builds the base of the stack.

Push - Adds an item to the top of the stack. This requires the user to input the item to be added.

Pop - Removes the top item from the stack, storing it somewhere. In this simulation, it is simply displayed in the console.

Add - Removes the top two items from the stack, adds them, and then pushes their sum onto the stack.

Sub - Removes the top two items from the stack, subtracts them, and then pushes their difference onto the stack.

Mul - Removes the top two items from the stack, multiplies them, and then pushes their product onto the stack.

Div - Removes the top two items from the stack, divides them, and then pushes their quotient onto the stack.

Random command - Generates a single random line of a stack machine program, and then executes it. This is handy for demonstrating how the stack machine works when you do not have a program written yet.

Reset - Clears the command center window and also the graphics window. You must press Setup to build the stack again.

Top

THINGS TO NOTICE

Every time you Push an item, the stack gets one more item on top. For every time you Pop, Add, Sub, Mul, or Div, the stack loses one item.

What happens when you try to Pop and the stack is empty? What happens when you have a single item on the stack, and you try to Add? When you press Sub, how does the stack determine which item is subtracted?

Top

THINGS TO TRY

Convert an arithmetic expression to Reverse Polish Notation (also known as postfix). Enter this RPN expression as a series of stack commands. The final result popped will be the normal infix equivalent of the expression. For example,

C 4 + 3 A - *

would be entered as Push C, Push 4, Add, Push 3, Push A, Sub, Mul, Pop. What is popped should be (C + 4) * (3 – A).

Top

EXTENDING THE MODEL

Add another operator to the stack, such as exponentiation, or sin.

Add a memory bank, where variables may be pushed from, or popped to.

Change the stack machine so that instead of simply changing the label of an item, items always have numeric values and the expressions are evaluated.

Modify push to limit the number of items that can be pushed on the stack (to prevent wrapping).

Top

NETLOGO FEATURES

Several interesting NetLogo features were used in this model. The oper-random procedure uses random-one-of to select the name of a procedure to run, and then uses the run command to call the procedure. This is much cleaner than a series of nested ifelse statements to call the procedure chosen.

Each procedure that removes an item from the stack uses "ifelse any? node-at x y" to check that there is a node (the name of the breed used for items) at position x y.

Top

CREDITS AND REFERENCES

This model was written by Teresa W. Carrigan, April 2004.

Permission to use, modify or redistribute this model is hereby granted, provided that both of the following requirements are followed:

  1. this copyright notice is included.
  2. this model will not be redistributed for profit without permission from Teresa Carrigan.
Contact Teresa Carrigan for appropriate licenses for redistribution for profit.

To refer to this model in academic publications, please use: Carrigan, T. (2004). Simple Stack Machine model. Blackburn College, Carlinville, IL.

In other publications, please use: Copyright 2004 by Teresa W. Carrigan. All rights reserved.

Home

Applets on this website were written by Teresa Carrigan in 2004, for use in computer science courses at Blackburn College, with the exception of the Fireworks applet. The applets made with NetLogo require Java 1.4.1 or higher to run. The applets made with NetBeans require Java 1.4.2 or higher to run. Applets might not run on Windows 95 or Mac OS 8 or 9. You may obtain the latest Java plugin from Sun's Java site.