Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
;; an answer to http://kotka.de/blog/2010/03/The_Rule_of_Three.html#summary
;; memoize from core.clj:
(defn memoize
[f]
(let [mem (atom {})]
(fn [& args]
(if-let [e (find @mem args)]
(val e)
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret)))))
(defn f [& xs]
(println "Called with" xs)
xs)
;; parametrized-memoize:
(defn memoize2
([f] (memoize2 f [{} identity assoc]))
([f [init cached assoc]]
(let [mem (atom init)]
(fn [& args]
(if-let [e (find (cached @mem) args)]
(val e)
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret))))))
(defn fifo-strategy [bound]
[[(into clojure.lang.PersistentQueue/EMPTY (repeat bound :dummy)) {}]
peek
(fn [[queue cache] args ret]
[(-> queue pop (conj args))
(-> cache (dissoc (peek queue)) (assoc args ret))])])
(comment
user=> (def g (memoize2 f (fifo-strategy 3)))
#'user/g
user=> (map g (range 3))
(Called with (0)
Called with (1)
Called with (2)
(0) (1) (2))
user=> (g 0)
(0)
user=> (g 3)
Called with (3)
(3)
user=> (g 0)
Called with (0)
(0)
)
;; but alas, no way to implement a lru-strategy
;; 2nd attempt at parametrizing memoize:
(defn memoize3
([f] (memoize3 f [{} identity identity assoc]))
([f [init cached hit assoc]]
(let [mem (atom init)]
(fn [& args]
(if-let [e (find (cached @mem) args)]
(do
(swap! mem hit args)
(val e))
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret))))))
(defn fifo-strategy [bound]
[[(into clojure.lang.PersistentQueue/EMPTY (repeat bound :dummy)) {}]
peek
(fn [mem args] mem)
(fn [[queue cache] args ret]
[(-> queue pop (conj args))
(-> cache (dissoc (peek queue)) (assoc args ret))])])
(defn lru-strategy [bound]
[[bound (into (sorted-map) (for [n (range bound)] [n :dummy])) {} {}]
peek
(fn [[tick lru-map last-uses cache] args]
[(inc tick)
(-> lru-map (dissoc (last-uses args)) (assoc tick args))
(assoc last-uses args tick)
cache])
(fn [[tick lru-map last-uses cache] args ret]
(let [[ltick largs] (first lru-map)]
[(inc tick)
(-> lru-map (dissoc ltick) (assoc tick args))
(-> last-uses (dissoc largs) (assoc args tick))
(-> cache (dissoc largs) (assoc args ret))]))])
(comment
user=> (def g (memoize3 f (lru-strategy 3)))
#'user/g
user=> (map g (range 3))
(Called with (0)
Called with (1)
Called with (2)
(0) (1) (2))
user=> (g 0)
(0)
user=> (g 3)
Called with (3)
(3)
user=> (g 0)
(0)
user=> (g 1)
Called with (1)
(1)
)
;; but, wait, there's at least one bug!
;; if two threads try to concurrently memoize the exact same call
;; the capacity of the cache may definitely decrease!
;; so we have to verify that the entry of interest to us hasn't changed:
(defn memoize4
([f] (memoize4 f [{} identity identity assoc]))
([f [init cached hit assoc]]
(let [mem (atom init)
hit-or-assoc (fn [mem args ret]
(if (find (cached mem) args)
(hit mem args)
(assoc mem args ret)))]
(fn [& args]
(if-let [e (find (cached @mem) args)]
(let [ret (val e)]
(swap! mem hit-or-assoc args ret)
ret)
(let [ret (apply f args)]
(swap! mem hit-or-assoc args ret)
ret))))))
;; wait, there's a repetition! let's refactor:
(defn memoize5
([f] (memoize5 f [{} identity (fn [mem args] mem) assoc]))
([f [init cached hit assoc]]
(let [mem (atom init)
hit-or-assoc (fn [mem args ret]
(if (find (cached mem) args)
(hit mem args)
(assoc mem args ret)))]
(fn [& args]
(let [ret (if-let [e (find (cached @mem) args)] (val e) (apply f args))]
(swap! mem hit-or-assoc args ret)
ret)))))
;; and to be sure that you only compute each entry once,
;; we first change memoize5 so that the returned value *is*
;; the cached value and not another equal value.
(defn memoize6
([f] (memoize6 f [{} identity (fn [mem args] mem) assoc]))
([f [init cached hit assoc]]
(let [mem (atom init)
hit-or-assoc (fn [mem args ret]
(if (find (cached mem) args)
(hit mem args)
(assoc mem args ret)))]
(fn [& args]
(let [ret (if-let [e (find (cached @mem) args)] (val e) (apply f args))
m (swap! mem hit-or-assoc args ret)]
(get (cached m) args))))))
;; then we can build memoize7 on memoize6:
(defn memoize7
([f] (memoize7 f [{} identity (fn [mem args] mem) assoc]))
([f strategy]
(comp deref (memoize6 #(delay (apply f %&)) strategy))))
;; integrating memoize6 and memoize7 (inspired by Eugen Dück memoize7-variant
;; see http://groups.google.com/group/clojure/browse_thread/thread/36a13d150d830683 )
(defn memoize8
([f] (memoize8 f [{} identity (fn [mem args] mem) assoc]))
([f [init cached hit assoc]]
(let [mem (atom init)
hit-or-assoc (fn [mem args]
(if (contains? (cached mem) args)
(hit mem args)
(assoc mem args (delay (apply f args)))))]
(fn [& args]
(let [m (swap! mem hit-or-assoc args)]
(-> (cached m) (get args) deref))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment