News for hackers. Stuff that matters.
Re:Algebraic Effects for the Rest of Us by reikonomusha on Wednesday July 24, 2019 @02:06AM (#20512711)
The author ought to look into and write about the Common Lisp condition system, which allows error handlers to invoke restarts at different parts of the call stack. [1] The long-story-short on them is that they decouple the treatment of exceptional situations (or conditions) into three orthogonal roles: signaling the condition (akin to “throwing”), handling the condition (akin to “catching”), and recovering from the condition (which has no resemblance in popular languages). The signaler, the handler, and the recoverer can be three disjoint bodies of code sitting in different parts of your call stack.

Doesn’t have a cool name like “algebraic effects”, and doesn’t have cool operational semantics written out, but it does something quite similar to what the article describes. Here is a little example I cooked up for a Julia programming audience. The code offers an API for computing roots of functions, and has a DIVERGENCE-ERROR condition and a handful of different restarts which handlers of said error can invoke. [2]

If you want to see what languages will look like in N years, it’s always wise to see what Common Lisp or Scheme are up to.

[1] http://www.gigamonkeys.com/book/beyond-exception-handling-co...

[2] https://github.com/stylewarning/lisp-random/blob/master/talk...

Re:Algebraic Effects for the Rest of Us by Vinnl on Wednesday July 24, 2019 @07:27AM (#20514048)
I think raganwald made the same point here: https://www.reddit.com/r/javascript/comments/cfz8lo/algebrai...

And the author (gaeron, aka Dan Abramov) replied:

> As far as I understand, the difference is that effects are actually typed (as part of your function signature), which I didn't go into — and so you have a lot more guarantees about what a function can or cannot do.

Re:Algebraic Effects for the Rest of Us by riffraff on Wednesday July 24, 2019 @02:14AM (#20512737)
Smalltalk also had resumable exceptions, and I remember implementing then in ruby too, with callcc, but I think algebraic effects are more general and by focusing on exceptions the author has sort of hidden that, even if he kept saying it's just an example.
Re:Algebraic Effects for the Rest of Us by reikonomusha on Wednesday July 24, 2019 @02:18AM (#20512753)
The condition system is also quite general. It’s more of a system for communicating with and passing control to distant (but structured) parts of the call stack. It’s also quite dynamic in nature; the behavior isn’t captured with purely lexical functions. It’s possible to use the condition system purely as a communication mechanism, as a way to implement dynamic bindings, and many other things. It just happens it’s framed in the language of error handling and that’s its most popular use.

With that said, I’m not claiming they’re equivalent to algebraic effects. However, looking at the semantics provided by Pretnar [1], the Common Lisp condition system is quite close to the functionality offered in the purely functional formalism.

[1] https://www.eff-lang.org/handlers-tutorial.pdf

Re:Algebraic Effects for the Rest of Us by nudq on Wednesday July 24, 2019 @06:23AM (#20513754)
> I think algebraic effects are more general

Not an expert on algebraic effects, but I suspect they are both more and less general.

On the one hand, "algebraic" hints at some constraints in the name of static typeability. Such restrictions wouldn't be present in Common Lisp.

On the other hand, Common Lisp only has single-shot downward continuations, so you won't get, e.g. nondeterminism-as-an-effect.

Re:Algebraic Effects for the Rest of Us by TeMPOraL on Wednesday July 24, 2019 @04:02AM (#20513136)
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.

Re:Algebraic Effects for the Rest of Us by TeMPOraL on Wednesday July 24, 2019 @08:34AM (#20514539)
I've expanded on this example and added some further thoughts in a blog post: http://jacek.zlydach.pl/blog/2019-07-24-algebraic-effects-yo....
Re:Algebraic Effects for the Rest of Us by lispm on Wednesday July 24, 2019 @10:20AM (#20515543)
Note also that this mechanism is usually hidden behind a macro. In user code one would just write:

    (with-progress-noted (datum data)
      (process-partial-data datum))
And this then would expand into a machinery like above.

The Lisp Machine OS had a system-wide progress bar at the bottom of the screen, which then would show the progress of some process - usually the front process or something related.

Re:Algebraic Effects for the Rest of Us by tomp on Wednesday July 24, 2019 @06:34AM (#20513798)
Thanks for this example! Reminds me of callbacks in JavaScript or event listeners in OOP, with slightly different (better?) structure!
Re:Algebraic Effects for the Rest of Us by jules on Wednesday July 24, 2019 @11:41AM (#20516332)
The essential feature of algebraic effects is that the restarts can be passed around as first class values resumed multiple times. Can CL do that?
Re:Algebraic Effects for the Rest of Us by dleslie on Wednesday July 24, 2019 @01:00PM (#20517182)
Scheme certainly can, via call/cc
Re:Algebraic Effects for the Rest of Us by dleslie on Wednesday July 24, 2019 @12:59PM (#20517169)
I was thinking throughout reading this: "Isn't this just call/cc?"
Re:Algebraic Effects for the Rest of Us by codebje on Wednesday July 24, 2019 @04:51PM (#20519537)
All monadic computation can be accomplished with continuations, which offer a way to thread the monadic bind between sub-programs. But at some point this is equivalent to saying that all continuations can be implemented with machine language... True, but beside the point.

The main purpose of ideas like algebraic effects is to build on a firm understanding of a model of computation. Implementing algebraic effects (whether with call/cc or otherwise) lets one specify a program's behaviour more precisely.

Whether this seems useful or not is probably closely aligned with whether you think static types and purity are useful or not, perhaps.

Re:Algebraic Effects for the Rest of Us by theaeolist on Wednesday July 24, 2019 @01:59PM (#20517823)
call/cc with handlers i.e. delimited continuations, yes.
Re:Algebraic Effects for the Rest of Us by ww520 on Wednesday July 24, 2019 @04:34AM (#20513270)
Even Visual Basic has a crude variant in the form of:

    On Error { GoTo N | Resume Next }
Re:Algebraic Effects for the Rest of Us by dreamcompiler on Wednesday July 24, 2019 @09:44AM (#20515168)
Yes. I read the article and thought "Wow. Somebody has rediscovered handler-bind from Common Lisp."
Re:Algebraic Effects for the Rest of Us by cultus on Wednesday July 24, 2019 @10:00AM (#20515336)
Algebraic effects can actually be implemented with delimited continuations [0].

Algebraic effects are more aimed towards statically typed languages like Haskell or Ocaml. They can replace most uses of monad transformers, which has both cognitive and performance benefits.

As you showed, there are better ways of solving the problem in lisps.

Tagless final algebras are another much more popular alternative that has been proven very effective in practical software. In tagless final, one writes composable DSLs (which are just records of functions) with the nature and interpretation of effects left abstract.

One then writes interpreters which interpret the DSL, giving meaning to the effects. This achieves the same fundamental goals as algebraic effects, but just using the ordinary language features of static FP languages.

[0] https://docs.racket-lang.org/reference/eval-model.html#%28pa...

[1] http://okmij.org/ftp/tagless-final/index.html

Re:Algebraic Effects for the Rest of Us by dan-robertson on Wednesday July 24, 2019 @06:56PM (#20520917)
Algebraic effects and delimited continuations are strictly more powerful than the Common Lisp condition system which is largely powered by the lexical goto (or return-from) feature. Invoking a restart can only unwind the stack (and the bit which is unwound can never be gotten to again), whereas algebraic effects allow more of a “forking” behaviour.