broomy-broom.clj

;; A simple mark-and-sweep implementation over a toy VM

(ns broom.core
  (:clojure-refer :exclude [pop]))

;; Maximum stack size
(def ^:const STACK-MAX 256)

;; Virtual Machine global ref
(def ^:private vm (ref {:max-objs 10
                        :num-objs 0
                        :stack []
                        :stack-size 0}))

;; Object model
(def ^:const OBJ {:type nil :val nil :marked? false})

(defn push [v]
  (dosync
    (assert (< (:stack-size @vm) STACK-MAX) "Stack overflow")
    (alter vm update-in [:stack] (fn [s] (conj s v)))
    (alter vm update-in [:stack-size] inc)))

(defn pop []
  (dosync
    (assert (> (:stack-size @vm) 0) "Stack underflow")
    (let [v  (-> @vm :stack last)
          ss (:stack-size @vm)]
      (alter vm update-in [:stack] (fn [s] (subvec s 0 (dec ss))))
      (alter vm update-in [:stack-size] dec)
      v)))

(defn new-obj [type]
  (dosync
    (when (> (:num-objs @vm) (:max-objs @vm))
      ;; Garbage Collection!
      (marky-mark-sweepy-sweep))

    (let [obj (assoc OBJ :type type)]
      (alter vm update-in [:num-objs] inc)
      obj)))

(defn push-int [n]
  (let [int-obj (assoc (new-obj :int) :val n)]
    (push int-obj)))

(defn push-pair []
  (let [pair-obj (-> (new-obj :pair)
                     (update-in [:val :head] (fn [_] (pop)))
                     (update-in [:val :tail] (fn [_] (pop))))]
    (push pair-obj)))

(defn mark [obj]
  (if-not (:marked? obj)
    (if (-> obj :type (= :pair))
        (-> obj
            (assoc :marked? true)
            (update-in [:val :head] mark)
            (update-in [:val :tail] mark))
        (assoc obj :marked? true))
    obj))

(defn mark-all []
  (dosync (alter vm update-in [:stack] #(into [] (map mark %)))))

(defn sweep []
  ;; TODO... :)
  )

(defn marky-mark-sweepy-sweep []
  (dosync
    (let [num-objs (:num-objs @vm)]
      (mark-all)
      (sweep)
      (alter vm update-in [:num-objects] (partial * 2)))))