Abstract

This is a simulator of a simple stack machine. It can be programmed using a language which resembles RPN and RPL. Currently only the following commands are provided:

Operations on the data stack

Command Name Stack Diagram

nnn

Number

( - - n )

+

Add

( x y - - x + y )

-

Subtract

( x y - - x - y )

*

Multiply

( x y - - x * y )

/

Divide

( x y - - x / y )

STO n

Storage

( x - - )

RCL n

Recall

( - - x )

DUP

Dup

( x - - x x )

DROP

Drop

( x - - )

SWAP

Swap

( x y - - y x )

Controll structure

Command Name

LBL n

Label

GTO n

GoTo

x=0?

EqualsZero

x>0?

GreaterZero

GSB n

GoToSubroutine

RTN

Return

But it’s very easy to extend the language with new commands like MOD or OVER.

Code

Processor

The processor has an unlimited stack and 10 registers plus a few functions to manipulate them:

  • push: pushes the value onto the top of the stack

  • pop: pops and returns the last value of the stack

  • peek: reads and returns the last value of the stack

  • storage: stores the value in the register using the index

  • recall: recalls the register using the index 

package Processor;

my @stack = ();
my @register = (0) x 10;

sub push($) {
    my ($value) = @_;
    CORE::push @stack, $value;
}

sub pop() {
    my $value = CORE::pop @stack;
    return $value;
}

sub peek() {
    my $index = $#stack;
    my $value = $stack[$index];
    return $value;
}

sub storage($$) {
    my ($index, $value) = @_;
    $register[$index] = $value;
}

sub recall($) {
    my ($index) = @_;
    my $value = $register[$index];
    return $value;
}

sub toString() {
    return <<EOF;
Register: @register
Stack   : @stack
EOF
}

return 1;

Controller

The controller has an unlimited return stack, a list of labels that keeps track of the corresponding progam line and a program counter pc.

  • label: stores the program line for a label

  • goTo: jumps to the program line registered with that label

  • incPc: increments the program counter by 1

  • enter: pushes the current adress on the return stack and jumps to the label

  • leave: sets the program counter to the last value of the return stack

  • run: executes each command of the program 

package Controller;

my @stack = ();
my @label = ();
my $pc = 0;

sub label($$) {
    my ($index, $value) = @_;
    $label[$index] = $value;
}

sub goTo($) {
    my ($index) = @_;
    $pc = $label[$index];
}

sub incPc() {
    $pc++;
}

sub enter($) {
    my ($index) = @_;
    push @stack, $pc;
    goTo($index);
}

sub leave() {
    $pc = @stack ? pop @stack : 1_000_000_000;
}

sub run(@) {
    my @program = @_;
    @stack = ();
    for ($pc = 0; $pc < @program; $pc++) {
        $program[$pc]->();
    }
}

return 1;

Command

A command is a closure, which is a function together with a referencing environment. It may operate both on the processor and the controller. Part of the environment are the variables name and value which are passed when calling the constructor. The name is used to select the command from an anonymous hash-map. This command is then returned within a wrapper-function that prints the command and both the registers and the stack of the processor.

package Command;

use Processor;
use Controller;

sub new($$) {
    my ($class, $name, $value) = @_;

    my $command = {
        Number => sub {
            Processor::push($value);
        },
        '+' => sub {
            my $x = Processor::pop();
            my $y = Processor::pop();
            Processor::push($y + $x);
        },
        '-' => sub {
            my $x = Processor::pop();
            my $y = Processor::pop();
            Processor::push($y - $x);
        },
        '*' => sub {
            my $x = Processor::pop();
            my $y = Processor::pop();
            Processor::push($y * $x);
        },
        '/' => sub {
            my $x = Processor::pop();
            my $y = Processor::pop();
            Processor::push($y / $x);
        },
        'MOD' => sub {
            my $x = Processor::pop();
            my $y = Processor::pop();
            Processor::push($y % $x);
        },
        'DUP' => sub {
            my $x = Processor::peek();
            Processor::push($x);
        },
        'DROP' => sub {
            Processor::pop();
        },
        'SWAP' => sub {
            my $x = Processor::pop();
            my $y = Processor::pop();
            Processor::push($x);
            Processor::push($y);
        },
        'OVER' => sub {
            my $x = Processor::pop();
            my $y = Processor::peek();
            Processor::push($x);
            Processor::push($y);
        },
        'STO' => sub {
            my $x = Processor::pop();
            Processor::storage($value, $x);
        },
        'RCL' => sub {
            my $x = Processor::recall($value);
            Processor::push($x);
        },
        'x>0?' => sub {
            my $x = Processor::pop();
            unless ($x > 0) {
                Controller::incPc();
            }
        },
        'x=0?' => sub {
            my $x = Processor::pop();
            unless ($x == 0) {
                Controller::incPc();
            }
        },
        'LBL' => sub {
        },
        'GTO' => sub {
            Controller::goTo($value);
        },
        'GSB' => sub {
            Controller::enter($value);
        },
        'RTN' => sub {
            Controller::leave();
        },
    }->{$name};

    return sub {
        $command->();
        printf <<EOF, Processor::toString();
$name $value
%s
EOF
    }
}

return 1;

Running a program

The simulator reads the DATA line by line and creates a list of commands — the program — which is passed to the controller to run it. Each line is split into a name and its value but the latter may be missing.

There are two cases that have to be considered:

  • numbers: the name "Number" is used

  • labels: a label will register the current program line within the controller

The example program will calculate the sum of the natural numbers from 0 to 10.

#!/usr/bin/perl

use strict;
use Scalar::Util qw(looks_like_number);
use Processor;
use Command;
use Controller;

my @program = ();
while (<DATA>) {
    my ($name, $value) = split;
    if (looks_like_number($name)) {
        ($name, $value) = ('Number', $name);
    }
    elsif ($name eq 'LBL') {
        Controller::label($value, $#program);
    }
    push @program, new Command($name, $value);
}

Processor::push(10);
Controller::run(@program);

__DATA__
STO 0
0
LBL 0
RCL 0
+
RCL 0
1
-
STO 0
RCL 0
x>0?
GTO 0

Recursion

Thank’s to the unlimited return- and data-stack recursion is possible. Here’s a recursive variant of the program above:

LBL 0
DUP
x=0?
RTN
DUP
1
-
GSB 0
+
RTN

Examples

Greatest Common Divisor

LBL 0
SWAP
OVER
MOD
DUP
x>0?
GTO 0
DROP

Factoring Numbers

STO 0
2
STO 1
LBL 0
RCL 1
DUP
*
RCL 0
-
x>0?
GTO 9
RCL 0
RCL 1
MOD
x=0?
GTO 1
RCL 1
1
+
STO 1
GTO 0
LBL 1
RCL 0
RCL 1
/
STO 0
RCL 1
GTO 0
LBL 9
RCL 0

We could add the following commands to make the program above a little shorter:

        'x<y?' => sub {
            my $x = Processor::pop();
            my $y = Processor::pop();
            unless ($x < $y) {
                Controller::incPc();
            }
        },
        'INC' => sub {
            my $x = Processor::recall($value);
            Processor::storage($value, $x + 1);
        },

Feel free to add all the stuff that is still missing.

Download

Just unzip this file in a new directory:

# unzip simulator.zip
Archive:  simulator.zip
  inflating: simulator.pl
  inflating: Command.pm
  inflating: Controller.pm
  inflating: Processor.pm

Here’s how to run the simulator:

# perl simulator.pl
00: STO 0
Register: 10 0 0 0 0 0 0 0 0 0
Stack   :

01: Number 0
Register: 10 0 0 0 0 0 0 0 0 0
Stack   : 0

02: LBL 0
Register: 10 0 0 0 0 0 0 0 0 0
Stack   : 0

(...)

09: RCL 0
Register: 0 0 0 0 0 0 0 0 0 0
Stack   : 55 0

10: x>0?
Register: 0 0 0 0 0 0 0 0 0 0
Stack   : 55