Last active
August 29, 2015 14:18
-
-
Save divs1210/be0037ec737ebf8572dc to your computer and use it in GitHub Desktop.
One Instruction Set Computer (http://en.wikipedia.org/wiki/One_instruction_set_computer)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(ns impala) | |
;; =============== | |
;; IMPALA | |
;; -subleq oisc- | |
;; --------------- | |
;; github/divs1210 | |
;; =============== | |
;; Primitives | |
;; ========== | |
(defn GET | |
" Get value of a " | |
[env a] | |
(-> @env :vars a)) | |
(defn SET | |
" a <= val " | |
[env a val] | |
(swap! env update-in [:vars] assoc a val)) | |
(defn DEL | |
" Delete variable (free memory) " | |
[env a] | |
(swap! env update-in [:vars] dissoc a)) | |
(defn SUB* | |
" b <= b - a " | |
[env a b] | |
(SET env b (- (or (GET env b) 0) | |
(GET env a)))) | |
(defn GOTO | |
" Move IP to given index " | |
[env inst#] | |
(swap! env assoc :IP inst#)) | |
(defn SUBLEQ | |
" Turing Equivalent instruction " | |
[env a b & [c]] | |
(SUB* env a b) | |
(if (and (-> c nil? not) | |
(neg? (GET env b))) | |
(GOTO env c) | |
env)) | |
;; Helpers | |
;; ======= | |
(defn temp | |
" Returns a randomly generated | |
variable name. " | |
[] | |
(keyword (gensym))) | |
(defn mk-env | |
" Returns a fresh environment | |
with the given program ready | |
to be executed. " | |
[prog] | |
(atom {:instr-q (vec prog) | |
:IP 0 | |
:vars {}})) | |
;; Interpreter | |
;; =========== | |
(defn step | |
" Executes the instruction pointed | |
at by the IP. Returns env." | |
[env] | |
(let [ instr-q (:instr-q @env) | |
IP (:IP @env) | |
[op & args] (instr-q IP)] | |
(apply op env args) | |
env)) | |
(defn run | |
" Runs the given program in a new | |
environment. Prints state at | |
each step to stdout. Returns env. " | |
[prog] | |
(let [env (mk-env prog)] | |
(println "\n=== start ===") | |
(while (< (-> @env :IP) (-> @env :instr-q count)) | |
(step env) | |
(swap! env update-in [:IP] inc) | |
(println (dissoc @env :instr-q))) | |
(println "==== end ====") | |
env)) | |
;; STDLIB | |
;; ====== | |
(defn SUB | |
" b <= b - a " | |
[env a b] | |
(SUBLEQ env a b)) | |
(defn ADD | |
" b <= b + a " | |
[env a b] | |
(let [Z (temp)] | |
(SET env Z 0) | |
(SUB env a Z) | |
(SUB env Z b) | |
(DEL env Z))) | |
(defn MOV | |
" b <= a " | |
[env a b] | |
(let [Z (temp)] | |
(SUB env b b) | |
(SUB env a Z) | |
(SUB env Z b) | |
(DEL env Z))) | |
;; Test | |
;; ==== | |
(def prog | |
[[SET :a 5] | |
[SET :b 3] | |
[ADD :a :b] | |
[SUB :a :b] | |
[MOV :a :b]]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
A simple register-based bytecode-interpreting VM in Clojure.
$ lein repl