5
\$\begingroup\$

Since I want to try writing my own language at some point, I wanted to have some experience writing an interpreter. BrainFuck is the simplest language I (kind of) know, so I decided to try writing an interpreter for it.

Going in, I decided to use a parsing concept I never fully learned when I used to write Haskell. Basically, each character of BrainFuck acts as a transformation of the internal state. The plan was to essentially translate each character to a function that carries out the transformation, then just fold the state over the commands. It didn't end up being quite that simple since looping requires "backtracking" to earlier commands, but I'm still quite happy with how it turned out.

Features/Limitations:

  • The standard number of cells the interpreter uses is 30,000; which seems to be an agreed upon standard number. The number of cells can be changed, but it's a hardcoded constant.

  • The number of cells doesn't change at runtime. It doesn't expand if the cell-pointer goes past the last cell. Instead, it wraps back to the start.

  • Each cell can hold a value from 0 to 255. I originally had it so each cell could hold any integer value, but some programs rely on the wrapping behavior of 0 to 255, so I limited it to that range.

  • Trying to end a loop before one's been started causes a runtime exception. It isn't, however, an error to have unended loops at the end of the program.

Main points I want advice on:

  • Since I kind-of forgot about loops going in (whoops), I didn't have any plan on how I was going to implement them. After fiddling for a bit, I settled on an "anchor" system. Each time a loop is started, the ['s position is saved to a loop-anchors vector. When a ] is encountered, if the conditions are right to loop again, the instruction pointer is set back to the position of the last [. If the conditions are right for the loop to end, the last added anchor is popped, and execution continues. It works well, but I was wondering if there's a simpler way of going about it.

  • The inclusion of the instruction-pointer field of the state was an unfortunate afterthought to implement looping. I'm not very happy with how it works. Basically, the instruction-pointer keeps track of what part of the code is being executed. As mentioned above, my original plan was just to fold over the commands. When I realized I needed to be able to jump to earlier parts of the code, I added the instruction-pointer, and had the loop constructs read and write to it. The pointer is also auto-advanced after any command is run. My problem with the design is that for the code to be read, the loop that reads the code need to constantly query the instruction-pointer to know what command to execute. In interpret, the loop checks instruction-pointer after every command. It would really be nice if interpret just needed to do something like call a advance function instead of worrying about the position of the instruction-pointer.

  • Is there a better way of handeling command arguments? It seems like I'm using a lot of preprocessing to decide if the program should be run in debug mode or not.

What I don't want advice on:

  • The fact that my program hardcodes some data like cell array size doesn't concern me right now. It's fairly trivial to implement passing that as a command argument later. My main concern is the logic of the interpreter.

  • Since loop-anchors is acting as a stack, an actual stack implementaton would be more appropriate. I'm using a vector here just for simplicity.


state.clj

(ns brain-fuck.state
  "A Brain-Fuck interpreter implementation.
  Cells values are limited to the range 0-255.
  The cell-pointer wraps if instructed to go left of 0, or right of the max cell.wsaq"
  (:require [helpers.general-helpers :as g]
            [clojure.string :as s]))

(defrecord Program-State [instruction-pointer cell-pointer loop-anchors cells]
  Object
  (toString [self] (str "<" (s/join " " (vals self)) ">")))

(defn new-state [n-cells]
  (->Program-State
    0
    0
    []
    (vec (repeat n-cells 0))))

(def standard-new-state (new-state 30000))

(defn syntax-error [^String cause]
  (RuntimeException.
    (str "Syntax Error: " cause)))

(defn check-anchors-non-empty [state]
  (when (empty? (:loop-anchors state))
    (throw (syntax-error "Unmatched ]."))))

; ----- Instruction Pointer

(defn inc-instruction-pointer [state]
  (update state :instruction-pointer inc))

; ----- Inc / Dec

(defn- effect-cell-at-pointer [state f]
  (let [i (:cell-pointer state)]
    (update-in state [:cells i]
      #(g/wrap (f %) 0 255))))

(defn inc-cell-at-pointer [state]
  (effect-cell-at-pointer state inc))

(defn dec-cell-at-pointer [state]
  (effect-cell-at-pointer state dec))

; ----- Pointer Left / Right

(defn- effect-pointer [state f]
  (let [cells (:cells state)
        n-cells (count cells)]
    (update state :cell-pointer
      #(g/wrap (f %) 0 (dec n-cells)))))

(defn move-pointer-left [state]
  (effect-pointer state dec))

(defn move-pointer-right [state]
  (effect-pointer state inc))

; ----- Input/Output

(defn output-cell-at-pointer
  "Assumes the current cell value is a valid character code."
  [state]
  (let [{cells :cells cp :cell-pointer} state
        raw-output (cells cp)
        output-char (char raw-output)]

    (print output-char)
    (flush)

    state))

(defn buffered-input-to-cell-at-pointer
  "Reads in a string, and sets the current cell value to the ASCII code of the first letter.
  Must enter a newline after the input."
  [state]
  (effect-cell-at-pointer state
    (constantly
      (-> (read-line)
          (first)
          (int)))))

; ----- Loop

(defn- current-loop-anchor-index [state]
  (-> state
      (:loop-anchors)
      (last)))

(defn start-loop [state]
  (update state :loop-anchors
    #(conj % (:instruction-pointer state))))

(defn- unchecked-loop-jump [state]
  (assoc state :instruction-pointer
               (current-loop-anchor-index state)))

(defn checked-loop-jump [state]
  (check-anchors-non-empty state)

  (unchecked-loop-jump state))

(defn- unchecked-loop-end [state]
  (update state :loop-anchors
    #(vec (drop-last %))))

(defn checked-loop-end [state]
  (check-anchors-non-empty state)

  (unchecked-loop-end state))

(defn close-loop [state]
  (let [{cp :cell-pointer cs :cells} state]
    (if (zero? (cs cp))
      (checked-loop-end state)
      (checked-loop-jump state))))

; ---- Run

(defn run-command
  ([state command debug-mode?]
   (let [state' (-> state
                  (command)
                  (inc-instruction-pointer))]

     (when debug-mode?
       (println (str state')))

     state'))

  ([state command]
   (run-command state command false)))

interpreter.clj

(ns brain-fuck.interpreter
  (:require [brain-fuck.state :as s]))

(def interpreter-state s/standard-new-state)

(def debug-state (s/new-state 10))

(def char-bindings {\+ s/inc-cell-at-pointer
                    \- s/dec-cell-at-pointer

                    \< s/move-pointer-left
                    \> s/move-pointer-right

                    \[ s/start-loop
                    \] s/close-loop

                    \, s/buffered-input-to-cell-at-pointer
                    \. s/output-cell-at-pointer})

(defn interpret
  "Interprets a string of Brain-Fuck code.
  Any invalid command characters are ignored."
  ([^String code debug-mode?]
   (let [filtered-code (map char-bindings code)
         commands (filterv some? filtered-code)
         initial-state (if debug-mode? debug-state interpreter-state)]

     (loop [state initial-state]
       (let [{ip :instruction-pointer} state
             command (get commands ip nil)]

         (when (some? command)
           (recur (s/run-command state command debug-mode?)))))))

  ([^String code]
   (interpret code false)))

main.clj

(ns brain-fuck.main
  (:require [clojure.string :as s]
            [brain-fuck.interpreter :as i])

  (:gen-class))

(defn -main [& [^String path debug?]]
  (if path
    (let [code (slurp path)
          debug-str? (str debug?) ; So it can be run from the REPL using boolean constants
          debug-char? (when debug? (Character/toLowerCase ^Character (first debug-str?)))
          debug-mode? (and debug? (= debug-char? \t))]

      (i/interpret code debug-mode?))

    (println "Enter a path to read from.")))

general-helpers.clj

(defn wrap "Returns a number with the given range, wrapped if necessary."
  [n min max]
  (let [r (- max min)]
    (cond
      (< n min) (inc (- max (rem (- min n) r)))
      (> n max) (dec (+ min (rem (- n max) r)))
      :else n)))

Note: Because I've had some free time since posting this code, I've updated it to include a REPL. Because it shares some functionality with interpret, I moved the bulk of the interpreting logic to a run-commands function that deals with the instruction pointer. That should deal with the second point I wanted help with, but I'd still love to see alternate ways!

Updated Repository: https://github.com/carcigenicate/brainfuck

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.