Overthunk

Complex Interactions - A Tale of Concurrency Pt 2 (Macros contd.)

Jun 28, 2020

Contents

Summary of Week 1

Here’s what I was able to do this week -

Expectations

Today was a beautiful Sunday and I spent a wonderful day outside far away from everyone. My goal for today was to go back to chapter 5 (Macros, Control Flow) and read the part about Macros. I skipped it the first time I was reading, since I didn’t really know if I needed to know about macros but since one of the chapter 6 questions asks you to create a macro, I figured I should know about it.

Besides reading ch5, I also wanted to write what I learned about Atoms, Refs in Chapter 6 and also talk about my solutions to the Chapter 6 Exercises.

What I learned

Strap in, because this is going to be a long one.

Macros

First, we’re going to talk about macros. Macros are a way of writing code that writes other code. This is commonly known as metaprogramming. Many languages across different programming models have ways of doing this. C has preprocessor macros (written using a different language than C), Scala has syntactic macros, Rust has declarative and procedural macros.

Clojure uses a procedural macro system, where the metalanguage for writing macros is Clojure itself. Not just that, but in Clojure, macros operate on expressions. This brings us full circle to chapter 1 where we learned that code in Clojure is expressed in lists which naturally form an AST structure. This makes it easier to reason about macros since the data structure we operate on is the tree of expressions.

Now that we know about the existence of macros and that they can write their own code, we need to think about when macros would be evaluated. When Clojure is evaluating an expression, it does something called macro-expansion, ie, when it sees a macro, it replaces it with the output of the macro. Once all macros in an expression have been evaluated, the final and restructured expressions can be evaluated.

A simple macro which reverses the arguments to a function:

(defmacro rev [fun & args]
    (cons fun (reverse args)))

So if we call (rev str "hi" (+ 1 2)), it gets macro-expanded to (str (+ 1 2) "hi"). This is the expression that gets evaluated.

Macros are particularly useful for defining new syntax or reducing boilerplate code. Especially when the syntax we’re trying to express is normally quite tedious or hard to express.

In the event that our macro uses some kind of local state like let bindings in it’s final expanded form, we need a way for the macro to return code that isn’t locally evaluated inside the body of the macro. We can do this by using ``` syntax-quote operator. It allows us to prevent evaluation of the following list. We can also substitute in regularly evaluated expressions using the unquote () and unquote-splice (@) operators.

A syntax-quoted expression is like a code template where we can fill in evaluated expressions as needed.

user> (let [x 2] `(inc x))
(clojure.core/inc user/x)

user> (let [x 2] `(inc ~x))
(clojure.core/inc 2)

One last thing we need to know. Since macros are going to rewrite code into more code, we need to make sure that our macro does not overwrite any local variables. So when we need to make use of a new variable in a macro, we use the gensym function to generate a new symbol. This can be simplified to symbol# in a syntax-quoted expression. If we do want to overwrite a local variable with a macro, we can use the form ~`foo instead of foo#. This makes our macro, unhygienic since it could potentially interfere with code beyond what was restructured.

Atoms & Refs

Now let’s move onto the final bits of Chapter 6 - Atoms and Refs. Yesterday, we talked about different ways of deferring computation with delay, future and promise. This did introduce the problem of handling concurrent updates to a mutable var. Since normally, a mutable var expects that updates to it are consecutive (read - single threaded), updates that flow in from multiple threads with future could be incredibly malformed.

user> (def xs #{})
user> (dotimes [i 10] (future (def xs (conj xs i))))
#'user/xs
nil
user> xs
#{0 7 1 4 6 2 9 5}

xs is missing 3 and 8. Since we tried to (conj xs i) in 10 threads in parallel, it is conceivable that somewhere, a few updates weren’t performed.

We need a mechanism for safely updating state in a concurrent-safe way. This is where atoms come in. An Atom, unlike a mutable var, is not transparent. This means that evaluating an atom does not return it’s internal value. We have to use deref.

We can set the value of an atom with - reset!. We can safely update an atomw with swap!. Any update to an atom is linearizable - updates appear to be completed in a single consecutive order, the effect cannot happen before a swap! call, once swap! returns, the effect is visible.

Now we can use update state safely and easily!

Despite all these cool features, atoms are primarily effective when we need to update it individually. If we want to update more than one atom at once, we could run into issues with updates happening out of order or perhaps not at all.

When we want to group a set of updates, we use ref. We use a dosync transaction to update groups of refs.

user=> (def x (ref 0))
user=> (def y (ref 0))
user=> (dosync
         (ref-set x 1)
         (ref-set y 2))
2
user=> [@x @y]
[1 2]

ref is good when we need to update multiple pieces of state independently (there is some overlap between the different pieces). If there is no overlap between the updates, use atoms. ref are powerful and help us achieve safety with its ordering guarantees and strong consistency but all this comes at significant overhead compared to atom.

Chapter 6 Exercises

  1. Use delay to compute this sum lazily. Show it takes no time to return the delay, but roughly 1 second to deref

Non-lazy sum

(defn sum [start end] (reduce + (range start end)))
(time (sum 0 1e7))

user> (time (sum 0 1e7))
"Elapsed time: 909.802143 msecs"
49999995000000

Lazy eval using delay

(def lazysum (delay (sum 0 1e7)))

user> (time lazysum)
"Elapsed time: 0.016645 msecs"
#<Delay@5764fdf1: :not-delivered>

user> (time @lazysum)
"Elapsed time: 881.947225 msecs"
49999995000000
  1. We can do the computation in a new thread directly, using (.start (Thread. (fn [] (sum 0 1e7)))–but this simply runs the (sum) function and discards the results. Use a promise to hand the result back out of the thread. Use this technique to write your own version of the future macro.
(def computedsum (promise))

(.start (Thread. (fn [] (deliver computedsum (sum 0 1e7)))))

@computedsum

@computedsum contains the delivered sum from Thread.

We use our macro writing skills to create a macro.

(defmacro new-future
  [f & args]
  `(let [p# (promise)]
     (do
       (.start (Thread. (fn [] (deliver p# (~f ~@args)))))
       )
     (fn [] (deref p#))))

user> (clojure.pprint/pprint (macroexpand '(new-future inc 1)))
(let*
 [p__7877__auto__ (clojure.core/promise)]
 (do
  (.start
   (java.lang.Thread.
    (clojure.core/fn
     []
     (clojure.core/deliver p__7877__auto__ (inc 1))))))
 (clojure.core/fn [] @p__7877__auto__))

Now we can use this macro to automagically return a promise that we can extract the value from at will.

(def computedsum (new-future sum 0 1e7))
(computedsum)

;; 49999995000000
  1. If your computer has two cores, you can do this expensive computation twice as fast by splitting it into two parts: (sum 0 (/ 1e7 2)), and (sum (/ 1e7 2) 1e7), then adding those parts together. Use future to do both parts at once, and show that this strategy gets the same answer as the single-threaded version, but takes roughly half the time.
(defn sum [start end] (reduce + (range start end)))
(time (let [a (sum 0 (/ 1e7 2)) b (sum (/ 1e7 2) 1e7)]
        (+ a b)))
;; Elapsed time: 946.990875 msecs

(time (let
          [a (future (sum 0 (/ 1e7 2)))
           b (future (sum (/ 1e7 2) 1e7))]
        (+ @a @b)))

;; Elapsed time: 508.677673 msecs

We can see that the version using future does indeed take roughly half the time to execute.

  1. Instead of using reduce, store the sum in an atom and use two futures to add each number from the lower and upper range to that atom. Wait for both futures to complete using deref, then check that the atom contains the right number. Is this technique faster or slower than reduce? Why do you think that might be
(defn atomicsum [start end]
  (let [s (atom 0)
        a (let [firsthalf (future (dotimes [i (/ end 2)] (swap! s + i)))]
            @firsthalf)
        b (let [secondhalf (future (dotimes [i (/ end 2)] (swap! s + (+ i (/ end 2)))))]
            @secondhalf)]
    @s))

(time (atomicsum 0 1e7))

;; 4.9999995E13
;; "Elapsed time: 1459.157893 msecs"

Clearly using an atom to hold the value and then updating it with futures is more time consuming than just using reduce.

  1. Instead of using a lazy list, imagine two threads are removing tasks from a pile of work. Our work pile will be the list of all integers from 0 to 10000:

;; user=> (def work (ref (apply list (range 1e5)))) ;; user=> (take 10 @work) ;; (0 1 2 3 4 5 6 7 8 9)

(def work (ref (apply list (range 1e5))))
(def sum (ref 0))

(defn refsum []
  (dosync
   (alter sum + (first @work))
   (alter work rest)
   ))

(while (first @work)
  (let [a (let [fh (future (refsum))]
            @fh)
        b (let [sh (future (refsum))]
            @sh)]
    (when
        (= (rem @sum 10000) 0)
      (prn @sum)
      )))

Dereferencing sum does indeed return the right value.

Takeaways

Whew, that was a lot! Not only did we see how cool and powerful macros can be, we also checked out how to use future, delay and promise to solve some interesting exercises.

Despite all the time I spent on this, concurrency and parallel programming is a topic I generally tend to be weak in. So I think this is a chapter that I might be coming back to over time to crystallize the insights. I might also be better served writing more complicated programs to test my understanding of this.

Let me close this week by saying that I really enjoyed engaging in this process of publicly learning and being more vocal about the process.

Fin Week 1 of #ClojureFam. Onto Week 2!