lisp.clj

;; Because using clojure.core.read-string feels like cheating!
(ns fizzbuzz.lisp
  (require [clojure.test :as t]
           [clojure.string :as s]))

(defn trim [expr]
"Trims parens and whitepsace from a combination"
  (-> expr (s/trim) (subs 1 (dec (count expr)))))

(defn combination? [expr]
"Returns true if the string is a combination"
  (= \( (first expr)))

(defn literal-split [expr]
"Splits a string with a leading literal into that literal
and the remaining expression."
  (s/split expr #"\s" 2))

(defn combo-split
"Splits a string with a leading combination into that combination
and the remaining expression by counting parens. Messes up some
corner cases with strings."
  ([expr] (combo-split [\(] (rest expr) 1))
  ([in-combo out-combo count] 
   (if (zero? count) 
     [(apply str in-combo) (s/trim (apply str out-combo))]
     (let [peek (first out-combo)
           next-count (cond 
                       (= \) peek) (dec count)
                       (= \( peek) (inc count)
                       :else count)]
       (combo-split (conj in-combo peek) 
                    (rest out-combo)
                    next-count)))))

(defn split-expression [expr]
"Reads a string with a lisp expression. If it is empty or nil it returns
an empty list. Otherwise, it breaks out the leading expression and
recurses on itself until the string is exhausted."
(if-not (or (empty? expr) (nil? expr)) 
    (let [[in out] (if (combination? expr) 
                     (combo-split expr) 
                     (literal-split expr))]
      (cons in (split-expression out)))
    ()))

(defn tokenize-literal [token]
"Turns a string into the appropriate literal. Only implemented for ints
and symbols at the moment."
  (if (re-matches #"\d+" token)
    (Integer. token)
    (symbol token)))

(defn build-ast [expr]
  (if (combination? expr)
    (->> expr trim split-expression (map build-ast))
    (tokenize-literal expr)))

(defn parse [expr]
"Converts lisp code into an AST"
  (-> expr (s/trim) (build-ast)))

(t/deftest combo-split-test
  (t/is (= ["(+ 1 2)" "a b c"] (combo-split "(+ 1 2) a b c")))
;; Infinite loop! Teach algorithm to account for unbalanced parens
;; inside of strings!
  #_(t/is (= ["\"(\""] (combo-split "(\"(\")"))))

(t/deftest literal-split-test
  (t/is (= ["42" "(+ 1 2) A B"] (literal-split "42 (+ 1 2) A B"))))

(t/deftest split-expression-test
  (t/is (= ["42"] (split-expression "42")))
  (t/is (= ["42" "34" "12" "12"] (split-expression "42 34 12 12")))
  (t/is (= ["42" "(+ 1 2)" "12"] (split-expression "42 (+ 1 2) 12")))
  (t/is (= ["(+ 1 2)" "(+ 3 2)"] (split-expression "(+ 1 2) (+ 3 2)")))
  (t/is (= ["(+ 1 2 (+ 2 3))"] (split-expression "(+ 1 2 (+ 2 3))")))
  (t/is (= ["+" "1" "2"] (split-expression "+ 1 2"))))

(t/deftest tokenize-literal-test
  (t/is (= 'symbol (tokenize-literal "symbol")))
  (t/is (= 42 (tokenize-literal "42")))
  ;; Our lisp only has symbols, lists, and ints so far...
)

(t/deftest trim-test
  (t/is (= "42" (trim "(42)")))
  (t/is (= "+ 42 1" (trim "(+ 42 1)"))))

(t/deftest parse-test
  (t/is (= 42 (parse "42")))
  (t/is (= 42 (parse "42    \n\t\t")))
  (t/is (= [42] (parse "(42)")))
  (t/is (= ['+ 1 2] (parse "(+ 1 2)")))
  (t/is (= ['+ ['+ 1 2] ['inc 1]] (parse "(+ (+ 1 2) (inc 1))")))
  (t/is (= ['first ['list 1 ['+ 2 3] 9]] 
           (parse "(first (list 1 (+ 2 3) 9))"))))