lilac.town

Notes & opinions of Will Acton

Algebraic Effects(-ish Things) in Clojure

Posted at — Jan 25, 2019

*UPDATE*: Some great discussion about this post taught me how these ideas have been explored in dynamic languages before under some other names: conditions.

The most notable language with a condition system is Common Lisp, which popularized the term.

In Clojure, there's a library called Special which is a port of these ideas. It has some gotchas: your conditions code must be eager, and does not support resumeability like this blog post talks about.

Just goes to show, there's never anything new under the sun! 😁

--------

Algebraic effects and handlers provide a modular abstraction for expressing

effectful computation, allowing the programmer to separate the expression of an

effectful computation from its implementation.

-- Effective Concurrency with Algebraic Effects

Algebraic effects are a way of executing an operation in code that lets the surrounding context define how it should be performed. Effects can be used to model many different kinds of things in our programs, from control-flow to mutability and async operations.

Effect systems have been an active area of research since 2003. The most popular implementations live in an extension to OCaml and the Eff language. As a research topic, the main interest is in the ability to model side effects in a sufficiently advanced static type system. However, I think that there could be a lot of value in a formalized pattern of this kind of controlled indirection in dynamic languages.

In fact, there are many parts of Clojure that we use every day that bear striking similarities to aspects of algebraic effects. In this post, I'd like to try and reimagine how a effects could be used to implement each one.

A typical example in many lanaguages are caught exceptions:

(defn throws! [] 
  (println "Raising the exception!")
  (throw (Exception. "Oh no!")))

;; ...elsewhere
(try (throws!)
     (catch Exception _e
       (println "Handling the exception!")))

throw is a form that takes an exception. When executed, it will cause the program to perform a lookup of the nearest enclosing catch form to handle the exception.

This is the essence of an algebraic effect: you perform an effect, and it will then look up a handler for that in the enclosing context.

Using exceptions to model things like IO, mutable state, or other things would be quite nasty. Other than performance, the reason why we can't use exceptions as a general effect system is that there's not an easy way to continue executing code at the site of the raise form. Once you've raised an exception, it aborts whatever it was doing.

Since we want to explore how we could implement this generally, let's imagine a new way of throwing and catching exceptions in Clojure:

(defn throws! []
  (println! "Throwing the exception!")
  (perform :throw
           (Exception. "Oh no!")))

  ;; ...elsewhere
(handle
 ;; handlers for this context
 {:throw (fn [_resume _e] (println "Handling the exception!"))}
 ;; run the function with the context
 (throws!))

The perform function is given a keyword and any number of values. It will then dynamically look up the nearest enclosing handle form that implements an effect handler function for the keyword, and pass those values to the function to be executed.

In this imaginary library, the _resume binding in the function above would be the function to call if we wanted to continue to execute the call site of the effect. Suffice to say, it is outside of the scope of this post to explore how we might implement that! More about it later.

The only important thing about the resume binding above is that we don't call it in the case of exceptions. Elsewhere, we'll find it useful to be able to resume execution of the place where we started to perform an effect.

Let's see where else we might find these effect-ish patterns.

Printing

Clojure's printing utilities have built in support for redirecting output to any output stream you choose using dynamic variables. Per the docs of the print function:

Prints the object(s) to the output stream that is the current value

of *out*. print and println produce output for human consumption.

So we can re-bind the *out* var in a given context, and the =print= function will use whatever the nearest binding of that variable is.

(defn greet [name]
  (print "Hello, " name))

(defn greet-str [name]
  (binding [*out* (java.io.StringWriter.)]
    (greet name)
    (str *out*)))

(greet-str "String!")
;; => "Hello, String!"

In this case, we re-bind *out* to actually be a StringWriter and return the string, instead of outputting to stdout.

This is very similar to performing an effect! Re-binding a var ends up being a way for us to re-define the behavior of a callsite without modifying any of the code within.

The same in our psuedo-effect system:

(defn greet [name]
  (perform :out "Hello, " name))

(defn greet-str [name]
  (let [out-str (java.io.StringWriter.)]
    (handle
     {:out (fn [resume & xs] 
             ;; imaginary convert and append o to out-str
             (.append out-str (obj->chars xs))
             (resume))}
     (greet name))
    (str out-str)))

This seems far more verbose than the above! The price we pay for generality. We can wrap this up into a similar API as Clojure provides with =with-out-str=:

(defn print [& xs]
  (apply perform :out xs))

(defmacro with-out-str [& body]
  `(let [out-str# (java.io.StringWriter.)]
     (handle
      {:out (fn [resume & xs] 
              ;; imaginary convert and append o to out-str
              (.append out-str (obj->chars xs))
              (resume))}
      (let [res# ~@body]
        {:result res#
         :str (str out-str#)}))))

(defn greet [name]
  (print "Hello, " name))

(defn greet-str [name]
  (:str
   (with-out-str
     (greet name))))

Anytime that we use dynamic vars + binding or with-redefs, we can think of this as an effect that always resumes.

Here, we call (resume) to simply continue executing without passing anything back to the call site. print is only used for side-effects, so it's expected to return nil. Next, we'll explore an example where we would =(resume some-val)= if we wanted to return something from the perform call.

State

(let [state (atom 0)]
  (println state)
  (reset! state 1)
  (println state)
  (reset! state "abc")
  (println state))
;; Prints:
;;  0
;;  1
;;  "abc"

Here, we've created an atom that we're storing some sort of state in. We then update that state and perform an operation based on it (print it).

Previously, we've looked at how indirection can help us re-define the control flow of our program (catching an exception) and also re-define the effects our program might have on the outside world. In this case, we can also re-define how our application behaves locally by modelling this as an effect.

Here's how this might look in an effect system:

(let [state (atom 0)]
  (handle {:state/put (fn [resume n]
                        (resume (reset! state n)))
           :state/get (fn [resume]
                        (resume @state))}
          (println (perform :state/get))
          (perform :state/put 1)
          (println (perform :state/get))
          (perform :state/put "abc")
          (println (perform :state/get))))
;; Prints:
;;  0
;;  1
;;  "abc"

It's true again that this seems overly verbose compared to using deref / =swap!= and referencing the atom directly. However, what we gain is composability: we can now easily move this stateful code outside of the definition of our local state without modification:

(defn app []
  (println (perform :state/get))
  (perform :state/put 1)
  (println (perform :state/get))
  (perform :state/put "abc")
  (println (perform :state/get)))

(let [state (atom 0)]
  (handle {:state/put (fn [resume n]
                        (resume (reset! state n)))
           :state/get (fn [resume]
                        (resume @state))}
          (app)))
;; Prints:
;;  0
;;  1
;;  "abc"

The example might seem contrived, but this is quite similar to the patterns of indirection that have emerged in application frameworks like component, integrant and duct.

The implementation here is not bound to the atom protocol, but could be used for any kind of stateful resource that we'd want to read and write values to.

One problem that many application frameworks end up working around is that there isn't a great way to propagate these contexts across async barriers (e.g. threads), since there isn't anything like resume in Clojure. We can't just replace our state effect-handlers with a binding and dynamic var with a context map, since any async function that tries to get something out of the context map will find that it is not bound.

with-redefs runs into the issue where it wouldn't be possible to have two running systems at the same time, and all state in the context map would have to be global. Race conditions and thread problems abound.

What most frameworks do is they invert the way dependencies are introduced to the system, where instead of pulling in a dependency via some form like =(perform :state/get)=, they pass the dependency in explicitly as an argument to the component and notate it for constructing the dependency graph to ensure ordering.

Personally, I think that application frameworks are ripe for this kind of abstraction and could be attained through some sort of DSL that implemented its own notion of effects and continuations to build more composable systems.

Reagent Reactions

One of the most motivating use cases for effects is handling potentially async operations. Reagent's Reaction abstraction is an interesting implementation of an effect where a function's inner data dependencies causes an outer context to call the function anytime those dependencies are updated, for instance in response to a button click or network request.

The way a reagent's Reaction works is by tracking calls to Clojure's =deref= on reagent's special atoms. This way, it can record which atoms a particular function depends on, and call them when they're updated.

(def state-a (r/atom 0))

(def state-b (r/atom 0))

(defn app []
  [:div 
   [:div
    [:button {:on-click #(swap! state-a inc)} "+ a"]
    [:button {:on-click #(swap! state-b inc)} "+ b"]]
   [:div "Total: " (+ @state-a @state-b)]])

(r/render [app] (. js/document getElementById "app"))

The machinery of reagent is quite complex. Their custom "ratom" uses a dynamic var *ratom-context* that it binds within each component. When reagent parses the hiccup body of your function, it walks the tree of elements you passed and creates a new React component for each function it finds. When it creates the component, it wraps the function you gave it in a =*ratom-context*=.

When a deref happens to a ratom, the ratom updates the context to add the component to a list of listeners. This way, when the ratom is changed, it knows which components are listening to it so it can force each one to update.

This is why a component called with parens (render) doesn't reactively re-render inside of an application, but [render] will: when you call it with square brackets, the function is not invoked immediately. This gives reagent time to wrap the component in its *ratom-context* so that the derefs are captured and setup to re-render the component on updates. When you call it with parens, it does not have a *ratom-context* and so will just return the current value of the ratoms without adding a new reaction.

We can try and boil it down to a sort of naive version, with the intent of exploring how we might do this with effects and plain atoms:

(def state-a (atom 0))

(def state-b (atom 0))

(defn app []
  [:div 
   [:div
    [:button {:on-click #(swap! state-a inc)} "+ a"]
    [:button {:on-click #(swap! state-b inc)} "+ b"]]
   [:div "Total: " (+ (perform :deref state-a) 
                      (perform :deref state-b))]])

(let [-render #(r/render [app] (. js/document getElementById "app"))]
  (handle {:deref (fn [resume a]
                    (add-watch 
                     a :rerender-app
                     (fn []
                       (-render)))
                    (resume @a))}
          (-render)))

Here, we work at the top render level rather than the component level for the sake of brevity. Each time a :deref effect is performed, the handler adds a watch to the atom that will re-run the render function and update the screen with our new state.

Creating an entire implementation with all of the plumbing and performance tuning that reagent has implemented over the years is far outside of the scope of this post. However, I hope that it makes sense how we could use a generalized effect system to implement the reactive :deref handler for front-end components.

Others

There are many other examples of these effect-ish constructs in most modern programming languages. core.async is one that I didn't go over here but is essentially another implementation of a specialized effect system.

I think a generalized algebraic effects system in Clojure would be awesome, but nothing that I am holding my breath for. The missing piece AFAICT is the =resume= function that we handwaved in these examples: this requires a featured called continuations which allow us to granularly pause and resume a function context.

Passing a function is one of the simpler ways to do it, and was done for it's easy-to-understand nature (everyone uses callbacks). Modern wisdom is to use what are called delimited continuations which represent the call site as a value, rather than a function.

There have been several implementations of various kinds of continuations over the years at the library level, but none have caught on; the ergonomics have proved not to be so nice and settling on one external implmentation to use for something so fundamental carries with it risks. Continuation systems are ultimately not meant for humans, but as a lower-level construct that a language is built on. As a lisp, Clojure gets more flexibility for defining our own language constructs than most, but for every day work these domain specific systems we looked at compose better with the rest of the Clojure ecosystem today.

If you have any questions, comments or corrections, please e-mail me: will AT will acton DOT com.