clojure laziness explaination

lazy.clj

(ns lazy
  (:require
   [clojure.pprint :as p]))

;; First, make a simple lazy calculation data type

(defrecord Lazy [content]
  clojure.lang.IDeref
  (deref [_]
    (:result
     (swap! content
            (fn [{:keys [computed? f] :as content}]
              (if computed?
                content
                {:computed? true
                 :result (f)}))))))

(defmacro lazy [captures & body]
  `(->Lazy (atom {:computed? false
                  :f (fn [] ~@body)
                  :captures ~captures})))

;; (printing stuff)

(defmethod print-method Lazy
  [lazy-val writer]
  (.write writer "Lazy<")
  (print-method @(:content lazy-val) writer)
  (.write writer ">"))

(defmethod p/simple-dispatch Lazy
  [lazy-val]
  (.write *out* "Lazy<")
  (p/simple-dispatch @(:content lazy-val))
  (.write *out* ">"))

;; It is similar to clojure.core/delay.
(def x (lazy [] (+ 4 5)))
x  ;; => Lazy<{:captures [], :computed? false, :f #function[lazy/fn--14457]}>
@x ;; => 9
x  ;; => Lazy<{:computed? true, :result 9}> 

;; The main difference is the :captures, which is just there to
;; illustrate the values that are required in order to do the lazy
;; calculation. For example:

(def y (let [numbers [1 2 3 9]]
         (lazy [numbers] (count numbers))))
y
;; => Lazy<{:captures [[1 2 3 9]],
;;          :computed? false,
;;          :f #function[lazy/fn--14461/fn--14462]}>

;; Here, I passed `[numbers]` as the first argument to the `lazy`
;; macro to tell it that it will need to capture `numbers` in the
;; function closure - it can't garbage collect it since it will be
;; needed to calculate `(count numbers)`, but we wouldn't be able to
;; see that without me explicitly putting it there for illustration
;; purposes.

;; Now on to the actual memory leak stuff!

;; Take this example of taking some numbers and calculating some stats
;; about them:

(defn number-stats-eager
  [numbers]
  (reduce
   (fn [acc x]
     {:count (inc (:count acc))
      :sum (+ (:sum acc) x)})
   {:count 0 :sum 0}
   numbers))

(def nums [10 5 2 49])
(number-stats-eager nums) ;; => {:count 4, :sum 66}

;; If similar code to this were written in haskell, it would make
;; everything lazy: under the hood it would be more like this:

(defn number-stats-lazy
  [numbers]
  (reduce
   (fn [acc x]
     (lazy []
           {:count (lazy [acc] (inc @(:count @acc)))
            :sum (lazy [acc x] (+ @(:sum @acc) x))}))
   (lazy [] {:count (lazy [] 0) :sum (lazy [] 0)})
   numbers))

(def stats (number-stats-lazy nums))

stats
;; => Lazy<{:captures [],
;;          :computed? false,
;;          :f #function[lazy/number-stats-lazy/fn--14500/fn--14501]}>

(str "average: " (float (/ @(:sum @stats) @(:count @stats))))
;; => "average: 16.5"

stats
;; => Lazy<{:computed? true,
;;          :result
;;          {:count Lazy<{:computed? true, :result 4}>,
;;           :sum Lazy<{:computed? true, :result 66}>}}>

;; Everything looks fine, right? We saved work by not computing the result until it was needed!

;; But what happens what we only use the count and not the sum
(def stats2 (number-stats-lazy nums))
@(:count @stats2) ;; => 4
stats2
;; => Lazy<{:computed? true,
;;          :result
;;          {:count Lazy<{:computed? true, :result 4}>,
;;           :sum
;;           Lazy<{:captures
;;                 [Lazy<{:computed? true,
;;                        :result
;;                        {:count Lazy<{:computed? true, :result 3}>,
;;                         :sum
;;                         Lazy<{:captures
;;                               [Lazy<{:computed? true,
;;                                      :result
;;                                      {:count
;;                                       Lazy<{:computed? true,
;;                                             :result 2}>,
;;                                       :sum
;;                                       Lazy<{:captures
;;                                             [Lazy<{:computed? true,
;;                                                    :result
;;                                                    {:count
;;                                                     Lazy<{:computed?
;;                                                           true,
;;                                                           :result 1}>,
;;                                                     :sum
;;                                                     Lazy<{:captures
;;                                                           [Lazy<{:computed?
;;                                                                  true,
;;                                                                  :result
;;                                                                  {:count
;;                                                                   Lazy<{:computed?
;;                                                                         true,
;;                                                                         :result
;;                                                                         0}>,
;;                                                                   :sum
;;                                                                   Lazy<{:captures
;;                                                                         [],
;;                                                                         :computed?
;;                                                                         false,
;;                                                                         :f
;;                                                                         #function[lazy/number-stats-lazy/fn--14508/fn--14511]}>}}>
;;                                                            10],
;;                                                           :computed?
;;                                                           false,
;;                                                           :f
;;                                                           #function[lazy/number-stats-lazy/fn--14500/fn--14501/fn--14504]}>}}>
;;                                              5],
;;                                             :computed? false,
;;                                             :f
;;                                             #function[lazy/number-stats-lazy/fn--14500/fn--14501/fn--14504]}>}}>
;;                                2],
;;                               :computed? false,
;;                               :f
;;                               #function[lazy/number-stats-lazy/fn--14500/fn--14501/fn--14504]}>}}>
;;                  49],
;;                 :computed? false,
;;                 :f
;;                 #function[lazy/number-stats-lazy/fn--14500/fn--14501/fn--14504]}>}}>


;; We get a monster! This is because in order to compute the :count,
;; the result map has been evaluated, but the :sum is still an
;; unevaluated lazy value, which needs the previous value of `acc` in
;; order to be evaluated. That previous value of `acc` has been evaluated, but its :sum is also an unevaluated lazy value that depends on the previous `acc`, etc.

;; So we have all of this stored in memory until we evaluate the `:sum`:

@(:sum @stats2) ;; => 66
stats2
;; => Lazy<{:computed? true,
;;          :result
;;          {:count Lazy<{:computed? true, :result 4}>,
;;           :sum Lazy<{:computed? true, :result 66}>}}>


;; But imagine if we had a lot more items and never evaluated `@(:sum @stats2)`!

;; Of course haskell programs aren't constantly leaking memory and
;; crashing - they have ways of making sure that things are strictly
;; evaluated when they need to be, although it is very easy to make a
;; mistake...