loading...

Algebraic Effects - You Can Touch This!

temporal profile image Jacek Złydach Originally published at jacek.zlydach.pl on ・7 min read

An article by Dan Abramov (of React fame) has been making rounds today on the Internet. It introduces readers to a body of theoretical work called "algebraic effects", providing an overview and a set of examples of how these ideas could be implemented in hypothetical extension to JavaScript.

What jumped at me in this article were two things. First, that the article claims this field of work is still theoretical, "only supported by a few languages that were created specifically to explore that idea" and definitely not production-ready. Second, that I've seen code like the article's examples before - in fact, I write similar code frequently, both in professional and hobby settings. The presented examples are a JavaScript pseudocode version of the Common Lisp's conditions and restarts system.

To be completely honest: I'm not familiar with the body of work under the name of "algebraic effects", though I've learned it has a larger scope than what's described here and in the original article (see remarks at the end of this post). However, Dan's article describes a subset that's in actual, practical use, so this is what this article focuses on.

Conditions and Restarts

Conditions and restarts are kind of like try/throw exception handling you know from more mainstream languages, except much more powerful. It's not meant for just handling errors, but any kind of flow, in which some communication up and down the call stack must occur.

To quote from an excellent introduction in Practical Common Lisp:

The condition system is more flexible than exception systems because instead of providing a two-part division between the code that signals an error and the code that handles it, the condition system splits the responsibilities into three parts--signaling a condition, handling it, and restarting.

(…) you could use the condition system to allow a low-level function to detect a problem while parsing a log file and signal an error, to allow mid-level code to provide several possible ways of recovering from such an error, and to allow code at the highest level of the application to define a policy for choosing which recovery strategy to use.

I won't try to summarize PCL here, but I want to introduce some vocabulary:

  • condition - is an object that represents some "situation" - i.e. something of note that's happened, but not necessarily an error
  • signal - quoting from CLHS, "v. to announce, using a standard protocol, that a particular situation, represented by a condition, has been detected"
  • handler - a function that receives a condition, and can somehow handle it (e.g. by invoking a restart), or decline and just pass the condition on
  • restart - quoting again, "represents a function that can be called to perform some form of recovery action"

Outside of Lisp, conditions are usually known as exception objects, signaling is done by throw, and restarts and handlers are bundled together as catch & finally blocks.

For more details, head on to the PCL chapter I linked above.

Error handling example

I'm not going to repeat the original article here; it's really worth a read anyway. What I'll do instead is show you how the example from would be done in Common Lisp, where it's not pseudocode but a real, fully supported, ANSI-standardized feature.

;;; Bookkeeping, to make the example compile and run.
(define-condition ask-for-name () ()
  (:documentation "A mock condition that means a name needs to be provided."))

(defun name (user)
  "Reader for name of `USER'."
  (car user))

(defun friend-names (user)
  "Reader for a list of names of friends of `USER'."
  (cdr user))

(defun (setf friend-names) (new-value user)
  "Setter for `FRIEND-NAMES'."
  (setf (cdr user) new-value))

;;; A helper macro wrapping an idiom allowing to do a test and request a new value if test fails.
(defmacro ensure (test place condition)
  "If the `TEST' fails, signal a `CONDITION', with a restart `USE-VALUE' ready for a new value."
  `(restart-case
       (unless ,test
         (signal ,condition))
     (use-value (new-value)
       (setf ,place new-value))))

;;; Implementation of the first example from the original article
(defun get-name (user)
  (let ((name (name user)))
    (ensure (not (null name)) ;Just NAME would suffice, but spelling it out for clarity.
      name
      'ask-for-name)
    name))

(defun make-friends (user-1 user-2)
  (push (get-name user-2) (friend-names user-1))
  (push (get-name user-1) (friend-names user-2)))

(let ((ricky (cons nil nil))
      (bubbles (cons "Bubbles" nil)))
  (handler-bind ((ask-for-name (lambda (c) (use-value "Ricky" c))))
    (make-friends ricky bubbles)
    ;; Let's return the two objects for the sake of REPL output.
    (list ricky bubbles)))

    ;;; REPL output:
    ((NIL "Bubbles") ("Bubbles" "Ricky"))

The part:

if (name === null) { name = perform 'ask name'; }

is implemented by the ensure form, which performs the test and ensures a restart named use-value is in place to externally set the value of a passed place (e.g. variable). This small utility essentially works as a simplified Common Lisp's assert macro, except the latter forces you to specify the new value(s) interactively (in fact, you could rewrite this code to work with Lisp's interactive debugger by changing ensure to assert, and (use-value "Ricky" c) to (continue c).

The handle (effect) { ... } part is entirely handled by handler-bind Common Lisp form - its job is to bind functions to handle particular signals coming from the code it encloses. You can see it matches ask-for-name condition we've defined earlier, and to handle it, it calls use-value. use-value is a Common Lisp built-in for invoking a restart named use-value (it's not an uncommon thing to do), but if such a built-in wasn't provided, you'd rewrite the handler-bind as follows:

(handler-bind ((ask-for-name (lambda (c)
                               (let ((restart (find-restart 'use-value c)))
                                 (when restart
                                   (invoke-restart restart "Ricky"))))))
  (make-friends ricky bubbles)
  ;; Let's return the two objects for the sake of REPL output.
  (list ricky bubbles))

That is, you can find and invoke programmatically any restart that was installed when the condition was signaled. Common Lisp just provides a shorthand, functional interface to common restarts abort, continue, muffle-warning, store-value, and use-value.

Beyond errors

As said before, conditions/restarts system can be used for more than just an error handling. The second example from the article demonstrates something that's essentially dynamic binding for function names, which can be done in Common Lisp in a different way (and arguably should), albeit with some work. Clojure - another Lisp - provides a nice built-in tool for that: with-redefs-fn.

So instead, let me describe an example I initially posted on HN, of how you can use conditions and restarts to implement progress reporting and aborting of a long-running calculation, possibly in interactive / GUI context.

(define-condition progress ()
  ((amount :initarg :amount
           :reader amount
           :documentation "How done is the operation, [0..1]."))
  (:documentation "A condition signaled by long operations that report progress."))

(defun process-partial-data (data)
  (declare (ignore data))
  ;; Some data processing here.
  )

(defun process-data (data)
  (restart-case
      ;; Main flow
      (loop
         ;; Report that we've started
         initially
           (signal 'progress :amount 0)

         ;; Perform the data processing
         with total = (length data)
         for datum in data
         for i below total
         do
           (process-partial-data datum)
           (signal 'progress :amount (/ i total))

         ;; Report that we're done
         finally
           (signal 'progress :amount 1)
           (return :done))
    ;; Restart flow
    (abort-work ()
      (format *trace-output* "Aborting work!")
      :failed)))

The "business meat" of our function is the loop form. You'll notice it reports its progress by signaling a progress condition which, without installed handlers, is essentially a no-op (unlike throwing an exception). The "meat" is wrapped in restart-case form, in order to provide an alternative flow called abort-work.

Let's look at some REPL session logs (-> denotes returned result, to differentiate it from printed output). First, regular use:

CL-USER> (process-data '(1 2 3 4 5 6))
-> :DONE

Let's simulate a GUI progress bar, by actually listening to the progress condition:

CL-USER> (handler-bind ((progress (lambda (p) (format *trace-output* "~&Progress: ~F~%" (amount p)))))
           (process-data '(1 2 3 4 5 6)))

Progress: 0.0
Progress: 0.0
Progress: 0.16666667
Progress: 0.33333334
Progress: 0.5
Progress: 0.6666667
Progress: 0.8333333
Progress: 1.0
-> :DONE

Let's simulate user pressing a "Cancel" button by assuming that it was clicked around the 50% progress mark. We can do that through invoking the abort-work restart programmatically:

CL-USER> (handler-bind ((progress (lambda (p) (format *trace-output* "~&Progress: ~F~%" (amount p))
                                                (when (>= (amount p) 0.5)
                                                  (invoke-restart 'abort-work)))))
             (process-data '(1 2 3 4 5 6)))
Progress: 0.0
Progress: 0.0
Progress: 0.16666667
Progress: 0.33333334
Progress: 0.5
Aborting work!
-> :FAILED

As pointed out under my original example, in real use you'd want to hide this mechanism under a macro. It's fairy easy to write one, for instance:

(defmacro dolist-with-progress-noted ((datum data return) (&key on-abort) &body body)
  (alexandria:once-only (data)
    (alexandria:with-gensyms (total i)
      `(restart-case
           (loop
              initially
                (signal 'progress :amount 0)

              with ,total = (length ,data)
              for ,datum in ,data
              for ,i below ,total
              do
                ,@body
                (signal 'progress :amount (/ ,i ,total))

              finally
                (signal 'progress :amount 1)
                (return ,return))
         (abort-work ()
           ,on-abort)))))

Now the following code expands to the original example above:

(defun process-data (data)
  (dolist-with-progress-noted (datum data :done)
      (:on-abort (progn (format *trace-output* "Aborting work!") :failed))
    (process-partial-data datum)))

Parting thoughts

On HN thread it's been pointed out that algebraic effects as a concept is larger than what Common Lisp can support. So it might be; I don't know much about the scope of the theoretical work there. The missing ingredient is implied to be "continuations", which are not supported in Common Lisp. However, Scheme family of Lisps has continuations. And apparently conditions. In the highest of Lisp traditions, they should be able to incorporate whatever other clever ideas come out of algebraic effects work.

So, it turns out, you absolutely can touch this, and could for the past 30+ years (or more), in a production-ready environment. I'm happy to see the JavaScript community rediscovering forgotten techniques of the programming art, but before people jump to writing their own DSLs for the JS transpilers, I implore you - please at least take a look at how it has all been done successfully in practical languages, and heed the lessons their communities learned.

(Originally published on my blog. Who do I ask to get dev.to to enable syntax highlighting for Common Lisp code?)

Posted on by:

temporal profile

Jacek Złydach

@temporal

Just a programmer with dreams of space.

Discussion

markdown guide