DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Simple Stack Machine Interpreter Written In Scala

03.04.2007
| 4150 views |
  • submit to reddit
        I wanted to implement a simple stack machine, and I wanted some practice with Scala. The two seemed to combine well.

I'll write up a description of the instruction set when I can be bothered, but it's hopefully pretty self explanatory.

package StackMachine;

import scala.collection.mutable._
import java.io.File;
import java.io.File._;
import java.io.BufferedReader;
import java.io.BufferedReader._ 
import java.io.InputStreamReader;
import java.io.InputStreamReader._;
import java.io.FileInputStream; 
import java.io.FileInputStream._;
import scala.collection.jcl.ArrayList;

class Memory(size : int) {
    private val internalMemory = new Array[int](size);
    
    override def toString : String = internalMemory.toString;    

    def load( location : int) = internalMemory(location % size);
    def store( location : int, value : int) { 
        internalMemory(location % size) = value; }
}

abstract class Instruction;

case class push (value : int) extends Instruction;
case class pop extends Instruction;
case class plus extends Instruction;
case class print extends Instruction;
case class break extends Instruction;
case class dup extends Instruction;
case class goto(instruction : int) extends Instruction;
case class noop extends Instruction;
case class ifCurrent(instruction : int) extends Instruction;
case class minus extends Instruction;
case class store(register : int) extends Instruction;
case class load(register : int) extends Instruction;
case class loadCurrent extends Instruction;
case class storeCurrent extends Instruction;
case class ifEmpty(instruction : int) extends Instruction;

object Instruction{
    def parse (value : String) = {
        if (value.startsWith("#")) noop()
        else {
        val split = splitString(value);
        val instruction = split._1.toLowerCase;
        val args = split._2;

        instruction match {
            case "pop"          => pop()
            case "plus"         => plus()
            case "print"        => print()
            case "push"         => push(args(0)) 
            case "break"        => break()
            case "dup"          => dup()
            case "goto"         => goto(args(0))
            case "ifstack"      => ifCurrent(args(0))
            case "store"        => store(args(0))
            case "load"         => load(args(0))
            case ""             => noop()
            case "minus"        => minus()
            case "ifempty"      => ifEmpty(args(0))
            case "loadcurrent"  => loadCurrent()
            case "storecurrent" => storeCurrent()
            case  _             => throw new Exception("Couldn't parse " + value)}}}

    private def splitString (value : String) = {
        val strings = value.split("\\s");
        
        Tuple2[String, List[int]](strings(0), 
            for {
                val i <- List.range(1, strings.length);
                strings(i) != ""}
            yield Integer.parseInt(strings(i)))
    }
}

class Machine(memorySize : int, states : Array[Instruction]) {
    val stack = new Stack[int]();
    val memory = new Memory(memorySize);
    var position = 0;
    
    private def advance { position = position + 1; }
    private def goto (instruction : int) { position = instruction - 1};    

    private def execute (instruction : Instruction) = 
        instruction match {
            // Stack manipulation
            case push(value)            => { stack += value; 
                                             advance; }
            case pop()                  => { stack.pop; 
                                             advance; }
            case dup()                  => { stack += stack.top; 
                                             advance; }
            
            // Arithmetic
            case plus()                 => { stack += (stack.pop + stack.pop); 
                                             advance; }
            
            case minus()                => { val second = stack.pop;
                                             val first = stack.pop;
                                             stack.push(if (second > first) 0 else (first - second));
                                             advance; }
            // Control flow
            // Our instructions are labelled from 1. Why? Laziness - vim does it that way.
            case goto(instruction)      => goto(instruction);
            case noop()                 => { advance; }
            
            case ifCurrent(instruction)   => { if (stack.pop == 0) goto(instruction); 
                                             else advance; }
            case ifEmpty(instruction)   => { if (stack.isEmpty) goto(instruction);
                                             else advance; }

            // Memory manipulation
            case load(register)         => { stack.push(memory.load(register));      
                                             advance; }                                   
            case store(register)        => { memory.store(register, stack.pop); 
                                             advance; }                                         
            case loadCurrent()          => { stack.push(memory.load(stack.pop)); 
                                             advance;}
            case storeCurrent()         => { val value = stack.pop;
                                             val register = stack.pop;
                                             memory.store(register, value);
                                             advance;}
            
            // IO instructions
            case print()                => { Console.println(stack.top); 
                                             advance; }
        };

    def run(){
        while (position < states.length){
            execute(states(position));
        }
    } 

    def execute (instructions : Iterable[Instruction]) : Unit = { 
        for (val instruction <- instructions)
        yield execute(instruction : Instruction);
        ();}
}

object Main{
    def main (args : Array[String]){
        if (args.length > 0){
            val file = new File(args(0));
            val reader = new BufferedReader(new InputStreamReader(new FileInputStream(file)));    

            var line = reader.readLine();
            
            val instructions = new ArrayList[Instruction]();

            while (line != null) {
                val instruction = Instruction.parse(line);
                instructions.add(instruction); 
                 
                
                line = reader.readLine();
                }

            val machine = new Machine(32, instructions.toArray);
            
            for (val i <- List.range(1, args.length))
            yield { machine.stack.push(Integer.parseInt(args(i))); }
            
            machine.run();
            
            Console.print("\n\n");
            Console.println("Machine terminated with:");
            Console.println("     Memory: " + machine.memory);
            Console.println("     Stack: " + machine.stack);
            Console.print("\n\n");
        }
        else Console.println("Please supply a file name");                
    }    
}

    

Comments

Snippets Manager replied on Wed, 2007/02/14 - 2:44pm

Thanks. This should not however be taken as examples of literate Scala! I've done very little Scala, and at the moment I'm mostly treating it by comparison with languages I already know, context switching between thinking of it as Java with shiny bits and ML with shiny bits and worse syntax. :-)

Sébastien Pierre replied on Wed, 2007/02/14 - 1:39pm

This is really interesting code. I never used scala, but got recently very interested in it... your examples give a good insight into Scala's features.