Algebraic Effects for the Rest of Us

The Common Lisp condition system is based on the 'New Error System' in Zetalisp for the Symbolics Lisp Machine operating system. The New Error System is from the early 80s. So we are talking about 35 years old. Well, actually the New Error System was based on ideas from PL/I and the Multics OS from the 60s..

The more interesting thing is not the wheel (aka the technology) itself, but how to make actual use of it...

Near the end of the article:

> Because algebraic effects are coming from statically typed languages, much of the debate about them centers on the ways they can be expressed in types. This is no doubt important but can also make it challenging to grasp the concept. That’s why this article doesn’t talk about types at all.

I'm only remotely familiar with algebraic effects, but I thought the whole point was to have a nice & composable way of dealing with effects in the type system, as an alternative to monads that generally do not mix well.

Also, Daan Leijen's papers on Koka are pretty accessible.

Like reikonomusha said, CL's condition system is pretty general in itself. The naming choice isn't an accident - the thing that's being "raised" is a "condition" (of which "error" is just a subtype), and what you do with a condition is "signal" it. In CL, most of the time it's used for exception handling, but I've seen code using this system for tasks not related to errors.

As a simple example, you can imagine data processing function for use in potentially interactive application, that reports progress and allows for aborting:

  (define-condition progress ()
    ((amount :initarg :amount :reader amount)))
  
  (defun process-partial-data (data)
    "NOOP placeholder"
    (declare (ignore data)))
  
  (defun process-data (data)
    (restart-case
        (loop
           initially
             (signal 'progress :amount 0)
           with total = (length data)
           for datum in data
           for i below total
           do
             (process-partial-data datum)
             (signal 'progress :amount (/ i total))
           ;; Report progress
           finally
             (signal 'progress :amount 1)
             (return :done))
      (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 signalling 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 (you can provide more than one named flow).

Now for the REPL sessions (-> denotes returned value). 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

A progress bar in a GUI usually has a "cancel" button. Let's simulate it by assuming that user clicked "cancel" around the 50% progress mark, 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

You'll note that function code is entirely transparent for how the progress reporting and abort decision work; it's callee-level handlers that are concerned with it. It works in console, it can work with Lisp's interactive debugger, and it could work with a GUI just as well. Hell, it could work with network requests (and I've seen similar code for writing handler response code for multiple protocols, letting you deliver partial results where supported, and transparently buffering them where it isn't.)

N.b. your typical experience with restarts in Common Lisp is the interactive debugger that pops up when an error gets unhandled. This example serves as a reminder that restarts are not just for errors, and that you can invoke them programmatically - building applications that can figure out how to handle their own errors.

I think you can fault the academics that use the "algebraic effects" term for that. Alternatively, you can see it as an extension of the efforts done in Lisp community since the 1960s.

However, neither the linked paper nor the author of this article seem aware of Lisp's prior art in this space, which is a shame. In particular, it's not true that you "can't touch this" - you absolutely can touch a production-ready implementation of this, in Common Lisp, and could for the past 30 years.

Yeah, it's literally a subset of Common Lisp's condition system. With Lisp's closure and continuation, it's easy to implement the feature. When I read the blog, I was wondering is renaming old concepts with exotic names and making them new the trend now?