Implementing a stack machine

TL;DR

This is a tutorial on programming classes and methods with a stack machine example

Implementing a stack machine

A stack machine is a simple model of a computer in which operations are performed on a stack.

We would like to implement a simple stack machine in Smalltalk.

Creating a class

Let's create a class called StackMachine.

We'll create it from the Playground as a subclass of CollectionValueHolder NewValueHolder subclass: #CollectionValueHolder instanceVariableNames: '' classVariableNames: '' package: 'NewValueHolder-Core-Base' .

This is just a wrapper around a collection that allows us to view live updates (it turns it into a model with a view as in MVC).

StackMachine new
  

NB: For each of the code changes we will make, we can either implement them directly, or we can load the change snippets, such as the following one, by clicking on the checkmark.

CollectionValueHolder subclass: #StackMachine
	instanceVariableNames: ''
	classVariableNames: ''
	package: 'StackMachine'.

StackMachine class
	instanceVariableNames: ''
  

Let's try creating an instance again:

StackMachine new 
  

The object exists now, but the value slot has not been initialized. (See the Raw tab.)

Implementing the initialize method

Let's browse the class and initialize the slot to an OrderedCollection SequenceableCollection subclass: #OrderedCollection instanceVariableNames: 'array firstIndex lastIndex' classVariableNames: '' package: 'Collections-Sequenceable-Ordered' . (Click on the Meta tab.)

"protocol: #accessing"

StackMachine >> initialize
	value := OrderedCollection new
  

Now we can view the machine, but its state is empty. (Go back to the Boxes tab.)

StackMachine new 
  

Testing with example methods

To test our code as we write it, we also write example methods . These are just like test methods, except they also return an example, an object that we can explore, or reuse in further example method.

Let's create an example for an empty stack machine, including some tests.

StackMachine new empty 
  

"protocol: #accessing"

StackMachine >> empty
	<gtExample>
	| result |
	result := StackMachine new.
	self assert: result value isEmpty.
	^ result
  

Push, top and pop

Now let's implement a push: method. First let's define an example with a value pushed.

StackMachine new pushed1  
  

"protocol: #accessing"

StackMachine >> push: anObject
	self addLast: anObject

"protocol: #accessing"

StackMachine >> pushed1
	<gtExample>
	| result |
	result := self empty.
	result push: 1.
	self assert: result size equals: 1.
	self assert: result top equals: 1.
	^ result 

"protocol: #accessing"

StackMachine >> top
	self assert: value isNotEmpty description: 'stack is empty'.
	^ value last
  

NB: push: must send addLast: to self and not the value slot, so the MVC announcements will work.

We'll need top to test the result of push:. We'll also check the precondition that the stack is not empty when we perform top. (Same for pop.)

We have push and top; now we need pop.

StackMachine new push1andPop 
  

"protocol: #accessing"

StackMachine >> pop
	self assert: value isNotEmpty description: 'stack is empty'.
	^ self removeLast

"protocol: #accessing"

StackMachine >> push1andPop
	<gtExample>
	| result popped |
	result := self pushed1.
	popped := result pop.
	self assert: popped equals: 1.
	self assert: result isEmpty.
	^ result 
  

Interacting with live objects in the Inspector

Now we can inspect a StackMachine and interact with the live object. Inspect the following snippet, and directly send it push: and pop messages. (Pull up the playground view at the bottom of the Inspector.)

StackMachine new
  

Implementing stack machine operations

Let's push another value on the stack.

StackMachine new pushed1and2 
  

"protocol: #accessing"

StackMachine >> pushed1and2
	<gtExample>
	| result |
	result := self pushed1.
	result push: 2.
	self assert: result value size equals: 2.
	self assert: result top equals: 2.
	^ result 
  

Now we're ready to implement an add operation.

StackMachine new add1and2 
  

"protocol: #accessing"

StackMachine >> add1and2
	<gtExample>
	| result |
	result := self pushed1and2.
	result add.
	self assert: result value size equals: 1.
	self assert: result top equals: 3.
	^ result

"protocol: #accessing"

StackMachine >> add
	self assert: value size >= 2 description: 'operation needs two arguments on the stack'.
	self push: self pop + self pop
  

More operations

We can add other arithmetic operations, as well as dedicated stack operations, like dup (push a copy of the top value) and swap (swap the top two values).

NB: swap makes it easier to implement operators like sub (subtract) and div (integer divide).