Clojure peg memoization example

clojure_peg_memoization_example.clj

(ns clojure-peg-memoization-example
  "A followup to Sean Cribbs' presentation on packrat parsers:

  https://github.com/seancribbs/pwl-chicago-1/

  The goal is to show that in an impure language like Clojure we can
  bolt on memoization after the fact and get the same performance
  advantage as the Haskell implementation without bending over
  backwards -- i.e., we maintain the same algorithm structure as a
  recursive descent parser.

  There are a few practical-performance and style issues with this
  code -- I was aiming to merely demonstrate the point in the previous
  paragraph and nothing more.

  All the parsing functions in this namespace take a single string
  argument and return a pair [val remaining-string], where val is
  an integer, as in the Haskell code, or nil if the string does 
  not match.")

(declare p-additive)

(defn p-decimal
  [s]
  (when (<= (int \0) (int (first s)) (int \9))
    [(Long/parseLong (subs s 0 1))
     (subs s 1)]))

(defn p-primary
  [s]
  (if (= \( (first s))
    (if-let [[val s'] (p-additive (subs s 1))]
      (if (= \) (first s'))
        [val (subs s' 1)]
        (p-decimal s))
      (p-decimal s))
    (p-decimal s)))

(defn p-multitive
  [s]
  (if-let [[val1 s'] (p-primary s)]
    (if (= \* (first s'))
      (if-let [[val2 s''] (p-multitive (subs s' 1))]
        [(* val1 val2) s'']
        (p-primary s))
      (p-primary s))
    (p-primary s)))

(defn p-additive
  [s]
  (if-let [[val1 s'] (p-multitive s)]
    (if (= \+ (first s'))
      (if-let [[val2 s''] (p-additive (subs s' 1))]
        [(+ val1 val2) s'']
        (p-multitive s))
      (p-multitive s))
    (p-multitive s)))

;; add tracing logs
(doseq [v [#'p-decimal #'p-primary #'p-multitive #'p-additive]
        :let [name (-> v meta :name)]]
  (alter-var-root v (fn [f]
                      (fn [& args]
                        (let [ret (apply f args)]
                          (printf "%s   ==>  %s\n"
                                  (pr-str (list* name args))
                                  (pr-str ret))
                          ret)))))

;; Try it without memoization:
;;
;; user> (p-additive "2*(3+4)")
;; (p-decimal "2*(3+4)")   ==>  [2 "*(3+4)"]
;; (p-primary "2*(3+4)")   ==>  [2 "*(3+4)"]
;; (p-decimal "3+4)")   ==>  [3 "+4)"]
;; (p-primary "3+4)")   ==>  [3 "+4)"]
;; (p-decimal "3+4)")   ==>  [3 "+4)"]
;; (p-primary "3+4)")   ==>  [3 "+4)"]
;; (p-multitive "3+4)")   ==>  [3 "+4)"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-multitive "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-multitive "4)")   ==>  [4 ")"]
;; (p-additive "4)")   ==>  [4 ")"]
;; (p-additive "3+4)")   ==>  [7 ")"]
;; (p-primary "(3+4)")   ==>  [7 ""]
;; (p-decimal "3+4)")   ==>  [3 "+4)"]
;; (p-primary "3+4)")   ==>  [3 "+4)"]
;; (p-decimal "3+4)")   ==>  [3 "+4)"]
;; (p-primary "3+4)")   ==>  [3 "+4)"]
;; (p-multitive "3+4)")   ==>  [3 "+4)"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-multitive "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-multitive "4)")   ==>  [4 ")"]
;; (p-additive "4)")   ==>  [4 ")"]
;; (p-additive "3+4)")   ==>  [7 ")"]
;; (p-primary "(3+4)")   ==>  [7 ""]
;; (p-multitive "(3+4)")   ==>  [7 ""]
;; (p-multitive "2*(3+4)")   ==>  [14 ""]
;; (p-decimal "2*(3+4)")   ==>  [2 "*(3+4)"]
;; (p-primary "2*(3+4)")   ==>  [2 "*(3+4)"]
;; (p-decimal "3+4)")   ==>  [3 "+4)"]
;; (p-primary "3+4)")   ==>  [3 "+4)"]
;; (p-decimal "3+4)")   ==>  [3 "+4)"]
;; (p-primary "3+4)")   ==>  [3 "+4)"]
;; (p-multitive "3+4)")   ==>  [3 "+4)"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-multitive "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-multitive "4)")   ==>  [4 ")"]
;; (p-additive "4)")   ==>  [4 ")"]
;; (p-additive "3+4)")   ==>  [7 ")"]
;; (p-primary "(3+4)")   ==>  [7 ""]
;; (p-decimal "3+4)")   ==>  [3 "+4)"]
;; (p-primary "3+4)")   ==>  [3 "+4)"]
;; (p-decimal "3+4)")   ==>  [3 "+4)"]
;; (p-primary "3+4)")   ==>  [3 "+4)"]
;; (p-multitive "3+4)")   ==>  [3 "+4)"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-multitive "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-multitive "4)")   ==>  [4 ")"]
;; (p-additive "4)")   ==>  [4 ")"]
;; (p-additive "3+4)")   ==>  [7 ")"]
;; (p-primary "(3+4)")   ==>  [7 ""]
;; (p-multitive "(3+4)")   ==>  [7 ""]
;; (p-multitive "2*(3+4)")   ==>  [14 ""]
;; (p-additive "2*(3+4)")   ==>  [14 ""]
;; [14 ""]


;; memoize everything
(doseq [v [#'p-decimal #'p-primary #'p-multitive #'p-additive]]
  (alter-var-root v memoize))

;; Run it again with memoization:
;;
;; user> (p-additive "2*(3+4)")
;; (p-decimal "2*(3+4)")   ==>  [2 "*(3+4)"]
;; (p-primary "2*(3+4)")   ==>  [2 "*(3+4)"]
;; (p-decimal "3+4)")   ==>  [3 "+4)"]
;; (p-primary "3+4)")   ==>  [3 "+4)"]
;; (p-multitive "3+4)")   ==>  [3 "+4)"]
;; (p-decimal "4)")   ==>  [4 ")"]
;; (p-primary "4)")   ==>  [4 ")"]
;; (p-multitive "4)")   ==>  [4 ")"]
;; (p-additive "4)")   ==>  [4 ")"]
;; (p-additive "3+4)")   ==>  [7 ")"]
;; (p-primary "(3+4)")   ==>  [7 ""]
;; (p-multitive "(3+4)")   ==>  [7 ""]
;; (p-multitive "2*(3+4)")   ==>  [14 ""]
;; (p-additive "2*(3+4)")   ==>  [14 ""]
;; [14 ""]

Or maybe just using the memoized-fn macro repeatedly would work.