Today I'm gonna start an implementation of Lisp in Clojure following the mal - Make a Lisp guide. It is a learning tool, a language with many of the features of Clojure that has been done in 73 languages! It is deeply rooted in the Clojure community, originally inspired by gherkin, a functional programming language and interpreter written in GNU Bash 4. Since this is part of my 100 Days of Clojure challenge, I'm gonna make a Lisp in Clojure.

The first thing that usually comes to mind when doing such a thing is that it somehow feels like cheating. But this has been one of the most famous and beautiful exercises in the Lisp tradition.

The way I see it, the project that I'm taking on is to build a toolbox. And to do it, it just so happens that I have one of the best toolboxes with which to accomplish that, Clojure.

In particular, the following features will make the task relatively easy:

• Sequential compound data structures (lists, vectors, etc)
• Associative compound data structures (hash-maps)
• Function references (first class functions, function pointers, etc)
• Real exception handling (try/catch, raise, throw, etc)
• Variable argument functions (variadic, var args, splats, apply, etc)
• Function closures
• regular expressions
• Dynamic typing / boxed types (specifically, the ability to store different data types in the sequential and associative structures and the language keeps track of the type for you)
• Compound data types support arbitrary runtime "hidden" data (metadata, metatables, dynamic fields attributes)

Here is an illustration of the basic framework of our interpreter:

So we're gonna make a REPL!

We will first take a high-level overview of what the process will be like. We're gonna need 4 functions: READ, EVAL, PRINT, and rep (read-eval-print), which will go in a loop:

(ns lisp.step0-repl
  (:require [lisp.readline :as readline])
  #?(:clj (:gen-class)))
  
(defn READ [& [strng]]
  strng)

(defn EVAL [ast env]
  ast)

(defn PRINT [exp]
  exp)

(defn rep [strng] (PRINT (EVAL (READ strng), {})))

(defn repl-loop []
  (let [line (readline/readline "user> ")]
    (when line
      (when-not (re-seq #"^\s*$|^\s*;.*$" line) ; blank/comment
        (println (rep line)))
      (recur))))

(defn -main [& args]
  (repl-loop))

For our readline library, we can use either GNU readline or editline via the clojure-jna project (Java Native Access) to dynamically load and use native C libs.

(ns lisp.readline
    (:require [clojure.string :refer [split]]
              [clojure.java.io :refer [file]]
              [net.n01se.clojure-jna :as jna]))

(defonce history-loaded (atom nil))
(def HISTORY-FILE (str (System/getProperty "user.home") "/.mal-history"))

;;
;; Uncomment one of the following readline libraries
;;

;; editline (BSD)
#_
(do
  (def readline-call (jna/to-fn String edit/readline))
  (def add-history (jna/to-fn Void edit/add_history))
  (def load-history #(doseq [line (split (slurp %) #"\n")]
                       (jna/invoke Void edit/add_history line))))

;; GNU Readline (GPL)
;; WARNING: distributing your code with GNU readline enabled means you
;; must release your program as GPL
;#_
(do 
  (def readline-call (jna/to-fn String readline/readline))
  (def add-history (jna/to-fn Void readline/add_history))
  (def load-history (jna/to-fn Integer readline/read_history)))

(defn readline [prompt & [lib]]
  (when (not @history-loaded)
    (reset! history-loaded true)
    (when (.canRead (file HISTORY-FILE))
      (load-history HISTORY-FILE)))
  (let [line (readline-call prompt)]
    (when line
      (add-history line)
      (when (.canWrite (file HISTORY-FILE))
        (spit HISTORY-FILE (str line "\n") :append true)))
    line))

We have also added history support. Now we need to read and print:

We'll make a namespace for functions related to the reader:

(ns lisp.reader
    (:refer-clojure :exclude [read-string])
    #?(:clj  (:require [clojure.tools.reader :as r]
                       [clojure.tools.reader.reader-types :as rt]))
    #?(:cljs (:require [cljs.tools.reader :as r]
                       [cljs.tools.reader.reader-types :as rt])))

;; change tools.reader syntax-quote to quasiquote
(defn- wrap [sym]
  (fn [rdr _] (list sym (#'r/read rdr true nil))))

(defn- wrap-with [sym]
  (fn [rdr arg _] (list sym (#'r/read rdr true nil) arg)))

;; Override some tools.reader reader macros so that we can do our own
;; metadata and quasiquote handling
(def new-rmacros
  (fn [f]
    (fn [ch]
      (case ch
        \` (wrap 'quasiquote)
        \~ (fn [rdr comma]
             (if-let [ch (rt/peek-char rdr)]
               (if (identical? \@ ch)
                 ((wrap 'splice-unquote) (doto rdr rt/read-char) \@)
                 ((wrap 'unquote) rdr \~))))
        \^ (fn [rdr comma]
             (let [m (#'r/read rdr)]
               ((wrap-with 'with-meta) rdr m \^)))
        \@ (wrap 'deref)
        (f ch)))))

#?(:clj (alter-var-root #'r/macros new-rmacros)
   :cljs (set! r/macros (new-rmacros r/macros)))

(defn read-string [s]
  (r/read-string s))

And for the printer:

(ns lisp.printer)

#?(:clj (import '(java.io Writer)))

;; TODO Better:
;; (extend-protocol IPrintWithWriter
;;   Atom
;;   ...
;;   PersistentArrayMap
;;   ...
;;   PersistentHashMap
;;   ...)

;; Override atom printer
#?(:clj  (defmethod clojure.core/print-method clojure.lang.Atom [a writer]
           (.write writer "(atom ")
           (.write writer (pr-str @a))
           (.write writer ")"))
   :cljs (extend-type Atom
           IPrintWithWriter
           (-pr-writer [a writer _]
             (-write writer (str "(atom " (pr-str @a) ")")))))


;; Override hash-map printer to remove comma separators
#?(:clj  (defmethod print-method clojure.lang.IPersistentMap [hm ^Writer w]
           (.write w "{")
           (when-let [xs (seq hm)]
             (loop [[[k v] & xs] xs]
               (print-method k w)
               (.write w " ")
               (print-method v w)
               (when xs (.write w " ") (recur xs))))
           (.write w "}"))
   :cljs (extend-type PersistentHashMap
           IPrintWithWriter
           (-pr-writer [hm w _]
             (-write w "{")
             (when-let [xs (seq hm)]
               (loop [[[k v] & xs] xs]
                 (-write w (pr-str k))
                 (-write w " ")
                 (-write w (pr-str v))
                 (when xs (-write w " ") (recur xs))))
             (-write w "}"))))


;; Add a version of str that is the same all the way down (no
;; print-readably and nil printing all the way down)
(defn- pr-
  ([] nil)
  ([x]
     #?(:clj (print-method x *out*)
        :cljs (pr x)))
  ([x & more]
   (pr- x)
   (if-let [nmore (next more)]
     (recur (first more) nmore)
     (apply pr- more))))

(defn _str [& xs]
  (binding [*print-readably* nil]
    (with-out-str (apply pr- xs))))

That's enough to chew on for now, as I said this is just to give us an idea of what's going on. In the upcoming posts we'll go into more detail.