Stack Based Interpreter In Clojure - Part 3


In part two we we built a stack that we can use to store our operands. The next step for you is to define insstructions taht allow us to perform operations on the operands in the stack.

In case you missed the definitions in part one let's recap what we need to make instructions:

  • name - Technically this is optional, but I'll be damned if I'm going to use a machine where I have to remeber the opcodes of our instructions
  • opcode - A unique number for this instruction. It's important that this doesn't change between interpreter versions otherwise we won't be able to run old code.
  • arity - The number of arguments this instruction takes: that depends on the number of operands it pops from the stack.
  • behavior - The action that our instruction will perform. In a CPU this is made using transistors but in our case we'll use Clojure functions.

With all that in mind, let's build our instruction type.

(ns com.vadelabs.instruction.core)
(defprotocol IInstruction
(get-op-code [this])
(get-name [this])
(arity [this])
(function [this]))
(defrecord Instruction [op-code name arity function]
(get-op-code [this]
(get-in this [:op-code]))
(get-name [this]
(get-in this [:name]))
(arity [this] (get this :arity))
(function [this] (get this :function)))
(defn make-instruction
[op-code name arity func]
(map->Instruction {:op-code op-code
:name name
:arity arity
:function func}))

Next we need an instruction table - a structure which we can store instructions in and look them up by opcode and name. We're going to use a Clojure Map.

(ns com.vadelabs.instruction.table
(:refer-clojure :exclude [empty?])
[com.vadelabs.instruction.core :as instruction]))
(defprotocol ITable
(by-op-code [this op-code])
(by-name [this n])
(insert [this instr])
(empty? [this])
(symbols [this]))
(defrecord Table [table]
(by-op-code [this op-code]
(get-in this [:table op-code]))
(by-name [this n]
(first (filter (fn [item]
(= n (instruction/get-name item)))
(vals (get-in this [:table])))))
(insert [this instr]
(assoc-in this [:table (:op-code instr)] instr))
(empty? [this]
(clojure.core/empty? (:table this)))
(symbols [this]
(let [result (map (fn [k]
(let [instr (get-in this [:table k])]
[(instruction/get-op-code instr) (instruction/get-name instr)]))
(keys table))]
(sort-by first result))))
(defn make-instruction-table
(map->Table {:table {}}))

We've come to the end of today's journey. We now have an operand stack, and a way to collect and use our instructions. In our next post we're going to create the necessary structures to represent a program that our stack machine can execute.

Algorithms & Data Structures In Clojure(Script)