Virtual Machine implemented as a Domain Specific Language in Ruby

Abstract

Some time ago I created a simple programming language that was compiled to its own assembly language, a file in this assembly language could be executed in a Virtual Machine or be compiled to an executable form. Today I will present an idea how to use Domain Specific Language (DSL) created in Ruby to load and execute the assembly file just as a regular Ruby script.

Implementation

A sample of an assembly file is presented below, it's intuitive except the "int" mnemonic, it means "interruption", int 0 pops element from the stack and prints it on STDOUT. There aren't any registers, everything is done by using a stack.

bar:
    int 0
ret

foo:
    call bar
    ret

main:
    push 13
    call foo
    ret

Some of the syntax isn't valid in Ruby so before the assembly file is loaded, it's parsed by a small preprocessor (DSLPreprocesor class). Parsed assembly file is presented below:

@bar = Proc.new{
    int 0
}

@foo = Proc.new{
    call @bar
}

@main = Proc.new{
    push 13
    call @foo
}

One of cool things in the syntax of Ruby is the possibility to invoke method without parenthesis, it was also used here (e.g. to it enables constructions like "push 0" to be executed directly by Ruby interpreter).

Below is presented a complete source code of the mentioned virtual machine, it can be also cloned from GitHub (DSLInRuby directory).

#!/usr/bin/env ruby 

class DSLVirtualMachine
    def initialize(file_name = String.new)
        @preprocesor = DSLPreprocesor.new file_name
        @stack = Array.new
        @memmory = Array.new
        @stack_ptr = [0]
        @memmory_ptr = [0]
    end

    def run()
        eval @preprocesor.parse()
        @main.call()
    end

    private

    def alu(operation)
        parser = { 'add' => lambda { @stack.pop + @stack.pop },
                   'sub' => lambda { @stack.pop - @stack.pop },
                   'div' => lambda { @stack.pop / @stack.pop },
                   'mul' => lambda { @stack.pop * @stack.pop },
                   'gt'  => lambda { @stack.pop > @stack.pop }, }
        push parser[operation].call()
    end

    def call(function)
        @memmory_ptr.push @memmory.length
        function.call()
        @memmory_ptr.pop
    end

    def push(element)
        @stack.push element
    end

    def load(offset)
        memmory_ptr = @memmory_ptr.last
        @stack.push @memmory[offset+memmory_ptr]
    end

    def store(offset)
        memmory_ptr = @memmory_ptr.last
        @memmory[offset+memmory_ptr] = @stack.pop
    end

    def get_if_condition()
        return @stack.pop
    end

    def int(interrupt)
        parser = [ lambda { p @stack.pop },
                   lambda { push gets.to_i } ]
        parser[interrupt].call()
    end
end


class DSLPreprocesor
    attr_accessor :fname

    def initialize(fname = String.new)
        @fname = fname
        @parser = {
            # remove comments
            /^([^;]*);.*$/  => 
                        lambda { |u| "#{u}" },
            
            /^[\s]*jz ([a-z0-9]*)$/ => 
                        lambda { |u| "if (get_if_condition)" },
            /^a[0-9]:*$/ => 
                        lambda { |u| "end" },

            /^([a-z]*[0-9]*):$/  => 
                        lambda { |u| "@#{u} = Proc.new{" },
            
            /^[\s]*ret$/  => 
                        lambda { |u| "}" },
             
            /^[\s]*call ([a-z0-9]*)$/  =>
                        lambda { |u| "call @#{u}" },

            /^[\s]*(add|sub|mul|div|gt|lt|eq)$/ => 
                        lambda { |u| "alu '#{u}'" },
        }
    end

    def parse()
        file = File.readlines(self.fname)
        return file.map { |l| parse_mnemonic(l) }.join('')
    end

    private
    def parse_mnemonic(mnemonic)
        @parser.map { |k,v| mnemonic.gsub!(k){ v.call($1) } }
        return mnemonic
    end
end

vm = DSLVirtualMachine.new ARGV[0]
vm.run()

Usage presented on mentioned above assembly file:

bash-3.2$ ruby vm.rb sample.asm 
13
bash-3.2$ 

Results

Originally, I made in Python a regular Virtual Machine for this assembly language, later czarodziej made his own version in C. Version in Python has ~250LOC, in C ~600LOC, implementation in Ruby (+DSL) has ~110LOC. I think that it' a really good result. It could be even smaller, if the assembly language would be designed from the beginning to be executed in Virtual Machine

2 comments:

  1. Ruby is great for making a DSL, we use it in our company for this task too.

    ReplyDelete