gistfile1.clj

(require '(clojure [zip :as zip]))

(defn memoize-calls
  "Takes an expression, and replaces calls to func with cache checks, and calls
  if cache is missing."
  ([func cache expr] (memoize-calls func cache expr (zip/seq-zip expr)))
  ([func cache expr pos]
     (if (zip/end? pos) (zip/root pos) ; if at the end, return the tree.
	 (if (and (=  func (zip/node pos))
		  (empty? (zip/lefts pos)))
	   ;; replace function call with if-let cache check expression
	   (let [args (zip/rights pos)
		 call (-> pos zip/up zip/node)
		 retval (gensym)
		 pos ;; write over pos with new expression
		 (-> pos zip/up
		     (zip/replace
		      `(if-let [~retval (get-in (deref ~cache) [~@args])]
			 ~retval
			 (let [~retval (~func ~@args)]
			   (swap! ~cache assoc-in [~@args] ~retval)
			   ~retval))))]
	     (recur func cache expr (zip/next pos))) ; keep traversing
	   ;; if not at a function call, keep traversing (DFS)
	   (recur func cache expr (zip/next pos))))))

(defmacro defn-memo-rec
  "Replaces recursion with memoization checks"
  [name args expr]
  (let [cache (gensym)
	new-expr (memoize-calls name cache expr)]
    `(let [~cache (atom {})]
       (defn ~name ~args
	 ~new-expr))))

(defn-memo-rec
  fib [n]
  (if (<= n 1) 1
      (+ (fib (dec n))
	 (fib (- n 2)))))

(time (fib 1000))
;; "Elapsed time: 52.709875 msecs"