Ruff, a more efficient algebraic effects library for Ruby

Satoru Kawahara — Mon, 12 Aug 2019 17:25:03 +0000

I have been developing a more efficient algebraic effects library for Ruby.

There are alredy some effect library for Ruby, dry-effects and affect. So I introduce the merits of our library.

Merit 1: refined syntax

Although which of libraries provides a better syntax is a matter of getting used to it, better syntax sometimes helps avoiding bugs and is thankful for beginners.

Comparing to dry-effects, we have easier syntax to understand.

Here is dry-effects' example from here.

class Operation
  include Dry::Effects.State(:counter)

  def call
    3.times do
      self.counter += 1
    end

    :done
  end
end

class Wrapper
  include Dry::Effects::Handler.State(:counter)

  def initialize
    @operation = Operation.new
  end

  def call
    with_counter(0) { @operation.call }
  end
end

Wrapper.new.call # => [3, :done]

Even being about to compare to the above now, I can't understand what they want to do🤔

We can write state manipulation with effect handler more intuitionisticly.

Put = Ruff.instance
Get = Ruff.instance

def with_counter(init, &task)
  state = init

  Ruff.handler
    .on(Put){|k, s| state = s; k[0] }
    .on(Get){|k| k[state] }
    .run &task
end

puts with_counter(0) {
  3.times{|x|
    Put.perform x
    puts Get.perform
  }

  "returns #{Get.perform}"
}

=begin
# ==>
0
1
2
returns 2
=end

Merit 2: first-class continuation

Algebraic effects and handlers originally take continuation, the rest of handled computation.
Affect says:

Note: Affect does not pretend to be a complete, theoretically correct implementation of algebraic effects. Affect concentrates on the idea of effect contexts. It does not deal with continuations, asynchrony, or any other concurrency constructs.

I see, but I think manipulating continuation is essential ability for algebraic effects and handlers.
Different from Affect, we have first-class continuation.

Defer = Ruff.instance

with_defer = Ruff.handler.on(Defer){|k, f|
    k[]
    f[]
  }

with_defer.run {
  Defer.perform(->(){ puts "world" })
  puts "hello"
}

# ==> hello
# ==> world

Nice! Since we can manipulate continuation, we crush the thunk after calling continuation.

Even we can use continuation outside of handler.

class Coroutine
  Yield = Ruff.instance

  def self.yield v
    Yield.perform v
  end


  def initialize &task
    @th = ->(_) {
      Ruff.handler.on(Yield){|k, v|
        @th = k
        v
      }.run &task
    }
  end

  def resume *v
    @th[*v]
  end
end

co = Coroutine.new {
  puts "hello"
  x = Coroutine.yield 3
  puts "world"
  puts x + 5
}

v = co.resume nil
co.resume v + 4

Limitation and Technical View

We have a limitation that you can run continuation ONLY UP TO ONCE.
The limitation is because of our embedding method.
We use Fiber to realize embedding algebraic effects¹ on Ruby.
In short, in our embedding, continuations correspond to the rest of coroutine thread.
Fiber does not have a method to copy the rest of computation so the limitation occurs.

But you don't have to be disappointed. Even the limitatoin we already write some powerful programs above.
And we can think Affect's implicit continuation as running continuation only at tail position, exactly once.
Multicore OCaml has also algebraic effects and handlers with one shot limitation².

Why doesn't Fiber have the method? I think that, coroutines are thought as lightweight thread, and cloning coroutine is heavy procedure so this doesn't match to the concept lightweight and is rejected.
Or implementers may think there is no need to clone coroutines since the idea of Conway in the early 1960s.
So if you make a patch to something clone a coroutine thread, we can run continuation many times.

Summary

I've been developing an algebraic effects library for Ruby with good points comparing to existing libraries.
Even the limitation about continuation, you can use powerful control abstruction.

Enjoy algebraic effects!

Related works

We've implemented eff.lua, an algebraic effects library for Lua.
It is also based on our embedding method.

we research about embedding one-shot algebraic effects using stackful asymmetric coroutines. See here and here (only japanese). ↩
They have Obj.clone_continuation to clone continuation and run many times, but it is expensive at runtime so they provide explicit cloning. ↩