Yield for Effects

The functional programming communities have largely settled on monad interpreters as a basis for modeling effects. However, monadic effects are synchronous by default, which is a disadvantage in many contexts. I would like to encourage exploration of an even simpler effects model in a purely functional context: shared memory.

There has been a recent movement towards “free” monads, which enable separation of the interpreter. The ability to interpret free monads in many different contexts results in more compositional, extensible programs. Also, in my subjective opinion, free monads just feel right – simple, clean, less entangled with their environment, a better fit for the functional programming experience than the opaque monads of the past. In any given step, a free monad either:

  • yields with a requested effect and continuation
  • returns with a final result

That is, free monads are variants of the following:

data Free eff a 
  = forall x . Yield (eff x) (x -> Free eff a) 
  | Return a

Aside: The above representation has horrible performance properties for left-associative monadic binding, fmap, etc.. Fortunately, this is is a solved problem. We need only change our representation of continuations to a tree-structured queue or similar. See Oleg Kiselyov’s code for an example.

A natural consequence is that monadic effects are synchronous by default. Our interpreter must acquire a response of type `x` before continuing. Further, fine grained effects tend to require yielding frequently. This hinders efficient parallelism and batch processing. Of course, we can explicitly model asynchronous effects.

A simple alternative is to model a shared memory as a basis for effects. As a refinement of our free monad:

data Prog shm a
  = Yield shm (shm -> Prog shm a) 
  | Return shm a

Shared memory is a general, securable approach to effects. Our shared memory may consist of stream buffers, message queues, publish-subscribe topic lists, tuple spaces, databases, component entity systems, or something application specific. Upon yielding, our interpreter has opportunity to fill input buffers, flush output buffers, etc.. Buffering is common and explicit within the `shm` type.

Subprograms are easily constrained to operate on fragments of the shared memory. Subprograms that operate on different `shm` types can frequently be integrated with simple lensing techniques. (Adapting monadic effects, which are more eventful in nature, is more challenging in general.) In any case, a lot of the nice properties of free monads are still accessible with shared memory effects.

Shared memory effects are asynchronous by nature, and amenable to efficient batch processing. Yielding introduces an opportunity for effects, not a requirement for them.

Of course, we can explicitly model synchronous effects, where our interpreter knows to wait for certain data to become available before continuing. We can also mix, match, and layer our effects models, e.g. representing Free within Prog or vice versa. So, this isn’t a committed choice.

Some readers might assume shared memory effects are similar to `World -> World` functions, e.g. as used in Racket’s How to Design Programs. However, `World -> World` functions are driven externally, whereas yielding for effects on shared memory gives much greater control to the program.

I have enjoyed use of publish subscribe models, tuple spaces, blackboard metaphor, content addressable networking, explicit message queues, and otherwise more REST-ful approaches to effects common in procedural programming. I haven’t thoroughly explored this idea in context of purely functional programming, where we have constraints against aliasing and greater control over the sharing of memory… but I believe those properties will only improve the experience. I will continue to explore this idea in Awelon project.

This entry was posted in Language Design. Bookmark the permalink.

2 Responses to Yield for Effects

  1. brandonbloom says:

    I’m not sure I followed past the `data Prog shm a` type. Maybe an example of a program using a concrete shm type would help.

    • dmbarbour says:

      I agree the article could benefit from more concrete examples. Maybe I’ll try in a follow up article, when I have something concrete in mind as an actual use case in practice.

      As a simplistic use case, we could model `stdin, stdout, stderr` as a tuple of buffers. A program could process inputs and generate outputs, then yield. A subprogram could be constrained to just use `stdin, stdout` with no access to stderr – i.e. controlling effects. We could also model pipelines, e.g. moving the `stdout` buffer from one subprogram to `stdin` in another.

      Free Monadic IO tends to favor sum types (e.g. Out ByteString a | In (ByteString → a)), which requires we yield synchronously to our interpreter for every individual effect. The shared memory model, instead, favors product types – an output buffer and input buffer – to combine multiple effects, and is asynchronous by default. I think the qualitative difference has some pretty profound (and frequently useful) effects in overall program architecture.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s