Part 3: Working with the abstract F

This is the third of a four-part series on tagless-final effects.

Previously

1. Introduction, motivation, and the core techniques;
2. The role of Monad.

The freedom of erased abstraction

There is something supremely elegant about the way values of the F-type flow between effectful programs and their interpreters.

Consider the pair of copy and the IOFulFSAlg.

1. The first F is created by IOFul; in fact, the copy method cannot create any on its own. It knows that F = Function0, so can use () => ... to create its result.
2. This value flows to copy. But copy doesn’t know that F = Function0; the value is “actually” callable likeSo(), but that will not compile!
3. copy passes it back to the interpreter’s bind. All of a sudden, callability is back, so it can be implemented!

Each time F values cross the boundary between effectful program and interpreter, this knowledge appears and disappears in exactly the way that guides us to keep effectful programs properly abstract, that is, agnostic to the representation of the effects.

The way that representation appears and disappears in just the right places is a hallmark of parametric polymorphism. By contrast, consider “hiding behind a class’s public interface”, a hallmark of the object-oriented polymorphic way of thinking:

1. If the interpreter is embedded directly within the F class, then it can only safely work with exactly one F, the receiver. bind and such must be implemented with casting, which is by definition unsafe.
2. If the interpreter is separate, it must cast every F.

Regardless, the presence of a class implies manual wrapping and unwrapping, to apply the Adapter pattern; in Scala, this is a one-time cost. Even AnyVal subclasses box quite readily.

We can observe that there is no runtime wrapper quite readily in Scala by doing unsafe casting on the results of algebra methods.

def unsafeRead(source: String, alg: FSAlg): String =
  alg.readFile(source)
     .asInstanceOf[() => String]
     .apply()

If we pass our IOFulFSAlg to this function, it will work! The F is really (!) what the interpreter thinks, a Function0.

However, if we pass the test interpreter, it will just crash. Effectful programs can only do this by cheating the interpreter out of its job; honest programs do not do this.

I explained all this to demonstrate that tagless-final relies on a purely type-level form of abstraction. It cannot be meaningfully enforced without a type checker with parametric polymorphism. If you do not have parametric polymorphism, it is difficult to say that abstraction is happening at all; it will certainly be extremely difficult for a programmer unversed in effect algebras to stick to the abstract interface, without the aid of enforcement.

In Scala, there’s a “hole” in this abstraction, demonstrated by the partially-checked cast to () => String above. Scala permits uncontrolled type tests in its pattern matching, not just those useful for ADT pattern matching, so it is also possible to use this to violate the abstraction even further.

def andInATest(alg: FSAlg): Boolean =
  alg.readFile("irrelevant") match {
    case _: Function0[_] => false
    case _: Function1[_, _] => true
  }

Parametricity does not let us determine more about F than that explicitly provided in FSAlg; the alg certainly did not supply information about how to break the abstraction.

This is why “runtime type information” or “reified generics” are neither benign nor harmless. I’ve lost the absolute guarantee that the effectful program isn’t breaking the purely type-level abstraction.

Luckily, the compiler doesn’t encourage this sort of thing either. In the Scalazzi Safe Scala Subset we take it back to a rule, by forbidding use of type tests. Thus, full abstraction is restored.

Is the type parameter really necessary?

The presence of a type parameter on the abstract type F—making F a “higher-kinded type”—gets in the way of implementing this in Java. Perhaps the best way to see why this type parameter is so important is to see a case where it is not.

Java programmers confronted with a constellation of methods that produce substrings will often, “for performance”, pass around a StringBuilder or Writer as an argument, changing all the functions into void-returning mutations.

Tagless-final style offers a far more elegant way to get this runtime optimization.

trait StrAlg {
  type S
  def fromString(str: String): S
  def append(l: S, r: S): S
}

object SBStrAlg extends StrAlg {
  type S = StringBuilder => Unit

  def fromString(str: String) =
    sb => sb.append(str)

  def append(l: S, r: S) =
    sb => {
      l(sb)
      r(sb)
    }
}

def numbers(alg: StrAlg): alg.S =
  (1 to 100).foldLeft(alg.fromString("")){
    (acc, m) => alg.append(acc, alg.fromString(m.toString))
  }

And so numbers is freed from the admonition not to iteratively concatenate Strings, even if you are too lazy to implement the more efficient interpreter later! We also have this nice fusion property: numbers is fully decoupled from what we do with its results, even if we arrange for fromString to write to an exotic output stream of some sort.

However, any S for a given interpreter is like any other S. There’s no behavioral way to distinguish between different sorts of S in our algebra. This is fine when we want to represent exactly one (stringish) thing, but a typical algebra needs more, and so does a typical effectful program.

Consider FSAlg. It returns two sort of results, F[String] and F[Unit], which is already one too many for the so-called “star-kinded” representation employed by StrAlg. Say we faked it with an empty string for the F[Unit] case.

How would you represent an effectful program that parses a List[Int] out of a file? With FSAlg, it is easy:

def listONums(source: String, alg: FSAlg): alg.F[List[Int]]

How would you get this list, without a type parameter? Well, you’d have to interpret F to a String. But now, this function that returns List[Int] runs the interpreter, so it cannot be used as a component of abstract effectful programs. It does not compose.

Higher-kinded types like FSAlg’s F are the foundation of the appeal and useful applicability of the tagless-final pattern. If we don’t have them, or we stubbornly refuse to use them, we’re doomed from the start.

CanBuildFrom has appeal to higher-kinded skeptics, but if you attempt to integrate something like it into FSAlg, yet still write signatures like listONums, you will never finish writing all the abstract types and map instances required to have a general-purpose algebra.

Is copy a functional program?

Suppose that we wrote a version of copy, or any effectful program, that directly referred to IOFulFSAlg to produce effects, rather than taking an algebra argument and leaving F abstract. It would be hard to argue that it is still a purely functional program. However, the case for its being functional is relatively simple in the abstract case. Since the only difference is taking an argument, why is that?

The usual way in which we make programs more functional is to divide a side-effecting program into two parts: one to make decisions and purely produce a value representing those decisions, and one to “interpret” that value. This forms an obvious, structural abstraction.

To accept copy as a pure function requires you to broaden your acceptance of abstraction to include the type level. Because copy does not only receive functions in an algebra as an argument, it also receives a type, F, as an argument. By means of this abstraction, we form an “effectful shell” of a shape that would not work without the ability to abstract at the type level.

On finally, on tagless

The pure type-level approach is why this is tagless. Other approaches to custom algebras, such as using free monads, require a runtime “tag” to be created and picked up by the interpreter.

In tagless final style, we skip the tag step and just have the interpreter emit the final form of the effect right away.

Drawback: decomposition required

One drawback of the tagless-final style is that it imposes a specific structure on the interpreters you write.

When you interpret a free monad structure, you have a few methods of interpretation available. One is “natural transformation”; this is similar to what you do with tagless-final, but with a chunk of boilerplate. However, you can also write the interpreter as a tail-recursive loop. This loop can conveniently do things like update state variables, notice when certain actions happen after certain other actions, and so on.

By contrast, tagless-final style requires you to take that interpretive logic and encode it in data structures, each returned by a method specific to that action. Each algebra method acts as an isolated component, with no relation to others that may be called in the same effectful program.

Luckily, while tagless-final requires you to have a uniform, functional representation of effects per interpreter, it doesn’t say anything else about what that structure is. So to the extent that you want the extra features of a free monad structure for interpretation power, you can incorporate one. Moreover, this remains invisible to the effectful programs themselves. The underlying style remains tagless; any tags present in the system are as you choose, for your interpreters’ convenience.

This article was tested with Scala 2.12.0.

Part 2: The role of Monad

This is the second of a four-part series on tagless-final effects.

Previously

1. Introduction, motivation, and the core techniques.

The role of Monad

A useful effectful program needs some way of not only producing F effects, but combining and manipulating them. There are no methods on F from the perspective of effectful programs to satisfy this need; the interpreter must provide.

Suppose we have a basic copy method.

def copy(source: String, dest: String, alg: FSAlg)
    : alg.F[Unit] = {
  alg.readFile(source)
  // somehow get the String from F[String]...
  alg.writeFile(dest, contents)
}

It is tempting to include an evaluator in the algebra, but resist! Don’t include the runner in the algebra!

The appeal of this temptation lies with its similarity to an imperative style. You write

val contents = alg.run(alg.readFile(source))
alg.writeFile(dest, contents)

However, not only is this no longer functional programming, it is very, very hard to think about when this readFile side effect happens in relation to the other side effects in a side-effecting interpreter.

1. It could happen before all of the F-controlled side effects.
2. It could happen before one or more of the side effects you expect to happen first.
3. it could happen after one or more of the side effects you expect to happen later.
4. Any mix of the above can happen in the same interpreter.

Instead, we can supply combinators in the algebra to allow effects to be sequenced. Here’s a combinator for FSAlg that will allow copy to be written.

def bind[A, B](first: F[A])(next: A => F[B]): F[B]

This is called monadic bind, and can be written for both FSAlg interpreters.

// IOFul
def bind[A, B](first: () => A)(next: A => () => B): () => B =
  () => next(first())() // we can't call `first` now; that would
                        // break the delay of its side-effects

// TestMap
def bind[A, B](first: Directory => (Either[Err, A], Directory))
              (next: A => Directory => (Either[Err, B], Directory))
    : Directory => (Either[Err, B], Directory) =
  dir => {
    val (ea, dir2) = first(dir)
    ea match {
      case Left(err) => (Left(err), dir2)
      case Right(a) => next(a)(dir2)
    }
  }

With this function in the algebra, we can implement an effectful copy in a functional way.

def copy(source: String, dest: String, alg: FSAlg)
    : alg.F[Unit] =
  alg.bind(alg.readFile(source)){
    contents =>
      alg.writeFile(dest, contents)
  }

The broad applicability of this pattern to sequential effect problems—of both the pure and side sort, as exemplified by our two interpreters—is why Monad is so commonly used for problems like this.

Chances are that your effectful programs will need to perform F effects in this sequential way, where later effects (e.g. writeFile) need to be calculated based on the resulting values (e.g. contents) of earlier effects (e.g. readFile). So, as a design shortcut, you ought to incorporate Monad into your algebra.

Don’t reinvent the Monad wheel

It may be tempting to avoid incorporating a library of functional abstractions such as Scalaz or Cats into your program. This is a mistake; these libraries incorporate a large number of functions that are useful for working with abstract effects, as well as a large number of pre-built and tested implementations of bind and many similar combinators, ready for reuse in your interpreter.

These libraries are foundational because they cover so many common tasks for algebraic abstractions. For example, take a pure effectful program that reads a list of files.

def readFiles(names: List[String], alg: FSAlg)
    : alg.F[List[String]] =
  names.map(alg.readFile(_))
  //       ↑
  // [error] type mismatch;
  //  found   : List[alg.F[String]]
  //  required: alg.F[List[String]]

This doesn’t work because the Fs must be sequenced and returned from the method, not dropped on the floor. (foreach is completely useless in these programs for a similar reason.) An author of a pure effectful program can solve this problem herself, presuming the algebra includes the other essential monad function point.

// in algebra
def point[A](a: A): F[A]

// readFiles
  names.foldRight(alg.point(List.empty[String])){
    (name, rightF) =>
      alg.bind(alg.readFile(name)){hContents =>
      alg.bind(rightF){rest =>
        alg.point(hContents :: rest)
      }}}

With Scalaz, not only does abstract monad syntax give you a nicer way to write this fold and list reconstitution:

names.foldRight(List.empty[String].point[alg.F]){
  (name, rightF) =>
    for {
      hContents <- alg.readFile(name)
      rest <- rightF
    } yield hContents :: rest
}

But you wouldn’t bother, because the library already includes this function, for List and several other types.

names.traverse(alg.readFile(_))

Now all we did was change map to traverse.

Using a good foundational functional library is especially important for newcomers to monadic abstraction, because it contains in so many common patterns a demonstration of the proper way to work with F.

Monad reuse in FSAlg

Let’s rewrite what we have so far to incorporate a standard Monad into FSAlg.

First, we eliminate bind and point, substituting a Monad typeclass instance into FSAlg.

import scalaz.Monad

implicit val M: Monad[F]

For IOFulFSAlg, Scalaz already includes an implementation, which we can find by importing.

val M = {
  import scalaz.std.function._
  Monad[F]
}

Scalaz does have a Monad for the test algebra’s F, but using it will require some rewriting of our existing interpreter functions, so let’s just port over the previous bind implementation.

val M = new Monad[F] {
  // bind as above under TestMap
}

[error] object creation impossible, since method point in
 trait Applicative of type [A](a: => A)tfe.TestMapAlg.F[A]
 is not defined
  val M = new Monad[F] {
              ^

We didn’t get around to implementing point, the “effect-free” combinator, and the compiler asks for that now.

def point[A](a: => A): F[A] =
  d => (Right(a), d)

copy can be written in a method-calling style.

def copy(source: String, dest: String, alg: FSAlg)
    : alg.F[Unit] = {
  import alg.M.monadSyntax._
  alg.readFile(source).flatMap{
    contents => alg.writeFile(dest, contents)
  }
}

But it could also be written by calling alg.M.bind directly. Implementers’ choice.

For the traverse method, we need two imports, using the “à la carte” import style, and to pass along the Monad.

import scalaz.syntax.traverse._
import scalaz.std.list._

// and in the method
  names.traverse(alg.readFile(_))(alg.M)

(Use the type-parameter style for algebra definition to avoid this unfortunate failure of implicit resolution.)

Finding more functional combinators, like catching errors

In the type signatures for FSAlg, we haven’t really accounted for the fact that these functions can fail in real-world interpreters, and even in the test interpreter. Well, we have, in the design of the F choices, but that just delays any error until the caller runs the F.

1. For IOFulFSAlg, calling the F function will throw, effectively halting the sequence.
2. For TestDir, errors are represented with Left; reading the bind implementation, you can see that the Left case means that next is not called, effectively short-circuiting the program just like our IOFul does with exceptions.

This isn’t part of the tagless-final pattern; it’s a design choice. When we didn’t include error reporting in the return type of functions like writeFile that certainly can fail in practice, we implied that every interpreter’s F would account for errors. That’s not a convention, it’s an unavoidable outcome of this design decision.

If we want to write effectful programs that can handle errors, which is also a choice itself, we have a couple options.

1. The “explicit” strategy

For functions that can fail, include a representation of error cases inside the F. So FSAlg might have a different signature for readFile:

def readFile(name: String): F[Either[Err, String]]

This is the “explicit” strategy, and has a few major advantages:

1. F can be simpler, because it need not model errors.
2. The algebra can have a mix of failing and non-failing functions. The user of the algebra can tell which is which by looking at the return types.
3. Effectful program authors can delineate which parts of their program may have unhandled errors.

2. The “implicit” strategy

Incorporate an error-recovery function to convert an error into something that can be handled. Choose an error type, such as E, and add such a function as this:

def catchError[A](mayFail: F[A], recover: E => F[A]): F[A]

Assuming that you have incorporated Monad or at least its weaker relative Functor into your algebra, as we have, this is precisely equivalent in power to

def catchError[A](mayFail: F[A]): F[Either[E, A]]

except that its similarity to the try/catch form is more obvious. Alternatively, you might provide for some kind of filtering, so you drop some errors but not others; perhaps recover might be a PartialFunction, or you might take an additional argument that somehow explains to the interpreter which errors you want to handle or let go.

You may also wish to include the equivalent of try/finally, bracket:

def bracket[A](first: F[A], cleanup: F[Unit]): F[A]

This “implicit” strategy has its own set of advantages:

1. The potential for failure need not be noted on each algebra method; it is assumed.
2. Effectful programs can allow errors to percolate up “automatically”, so to speak. (Doing this with the “explicit” variant is possible, but a little tricky.

Unfortunately, there is no way to type-check that an effectful program in the “implicit” style has handled all errors, because F, no matter what, represents a program that might fail in this design.

3. The “someone else’s problem” strategy

As with #2, but don’t provide any means of recovery.

This is a question of delineated responsibility. For many effectful programs, it simply isn’t meaningful to recover from errors originating in the interpreter, and it’s always more appropriate for them to be handled by the invoker of the program, as an “early termination”.

In such a situation, you can communicate this by leaving error-catching out of the interpreter. Though you might want to at least document that you intended to leave the functionality out, and didn’t simply forget it!

None of these strategies is more or less pure; they all preserve the purity of effectful programs.

There is a broader problem here, though: how can you find type signatures like catchError, that convert concepts that seem to require side effects or special support, into plain algebra calls that work for pure FP programs? One great resource is the Haskell base library. Haskell requires all programs, even effectful ones, to be written using only pure constructs and ordinary functions, so many such problems have been solved there. catchError comes from the MonadError typeclass, which supplies a mini-algebra much like FSAlg, but specifically for throwing and catching errors.

1. Break an “effectful” idea down into a primitive concept you’d like to support.
2. Research how this is handled in the IO algebra for Haskell.
3. Replace IO with F and incorporate into your algebra.

Here are the implementations of catchError and bracket for our two interpreters. One test for your choice of effectful API is whether interpreters can implement it. I’ve chosen the Err type to represent errors to effectful programs, but the choice is yours.

import scala.util.control.NonFatal

// IOFulFSAlg
def catchError[A](mayFail: F[A],        // () => A
                  recover: Err => F[A]) // Err => () => A
    : F[A] =
  () => try mayFail() catch {
    case NonFatal(e) => recover(Err(e.getMessage))()
  }

// TestDirFSAlg
def catchError[A](mayFail: F[A],
                  recover: Err => F[A]): F[A] =
  dir => {
    val (result, dir2) = mayFail(dir)
    result match {
      case Left(err) => recover(err)(dir2)
      case Right(a) => (Right(a), dir2)
    }
  }

// IOFul
def bracket[A](first: F[A], cleanup: F[Unit]): F[A] =
  () => try first() finally cleanup()

// TestDir
def bracket[A](first: F[A], cleanup: F[Unit]): F[A] =
  dir => {
    val (result, dir2) = first(dir)
    val (_, dir3) = cleanup(dir2)
    (result, dir3)
  }

When should I take an F argument?

The functions so far follow a pattern that is common for algebra that include Monad. Specifically, our algebra API comes in two flavors:

1. Specific functions like readFile that carry out some task specific to this domain; these return an F but do not take an F as an argument.
2. Abstract effect combinators like map, bind, catchError that likewise return an F but also take one or more as arguments.

This pattern arises because for functions like readFile, this is the most useful signature in the presence of Monad.

With Monad in place, we can easily implement copy’s writing step in terms of flatMap or bind. Without it, we might be tempted to solve the problem of calling writeFile by adding an F argument.

// don't do this
def writeFileBad(filename: String, contents: F[String]): F[Unit]

Now we can call writeFileBad directly with the result of readFile. But what about these?

1. Suppose we want to process the contents of the source file before writing them. Maybe we want to split in two lines and filter some out (like grep), or sort them?
2. Suppose we want to read two or more files, writing all of their contents to the target file?
3. Suppose we wanted to read a file that contains, itself, a list of filenames, and we want to concatenate all of the contents of those files and put them into the target file?

The redesigned writeFileBad is good for only one sort of thing: things like copy. Monad is so ubiquitous partly because it is flexible enough to solve all these combination problems, and many more besides.

Effectful programs can all split their demands on their algebras into wanting to call these two sorts of primitive algebra functions; a program calling writeFileBad can call writeFile and flatMap instead, and will be better for it. Learning to recognize when you’ve accidentally given a specific function the job of a generic combinator is a highly useful skill for the design of abstract APIs.

Bending the mind the right way

The most difficult part of learning to use this pattern is learning how to design usable function types for your effect algebras. I suggested earlier looking at IO in Haskell, because they’ve encountered and solved such problems many times, because they had to.

So this is an attitude worth adopting. Demand a purely-functional approach in your effectful programs. That so many purely functional effect types are widely known is a testament to the unwillingness to compromise the integrity of the Haskell model or abandon the reasoning power that comes with referential transparency.

It’s a good idea to have two interpreters, one like IOFul and one like TestMap, or at least to imagine both. When adding a new function, think

1. Will using this function in effectful programs cause effects before “running” the returned F?
2. If I use this with a side-effect-free interpreter, will running F have side effects?

If the answer to either of these is “yes”, change the type signature.

Still to come

1. Working with the abstract F;
2. How much is this “dependency injection”?

This article was tested with Scala 2.12.0 and Scalaz 7.2.8.

Tagless final effects à la Ermine Writers

This is the first of a four-part series on tagless-final effects.

“Finally tagless” notation is a nice way to get many of the benefits of free monads without paying so dearly in allocation of steps.

Watching John DeGoes’s 2015 presentation of free applicatives, it struck me that I didn’t quite like the notation of “finally tagless” demonstrated therein. To me, threading an algebra compares unfavorably to having an algebra in the program’s scope. The latter is the approach taken by the implementation of the Ermine Writers.

I think the style of effectful programs written like this will be appealing to programmers transitioning from out-of-control side effects to functional programming. By avoiding the sequence of intermediate command data structures that characterizes free monad effects, it saves significant runtime cost; the implementation of the interpreter should also be more obvious to the newcomer. On the other hand, it preserves the idea of multiple interpreter-dependent output types, and with it the testability benefit.

While this style does away with the abstract command structures, it preserves the limitations on available effects provided by good effect libraries. It does this by means of type-level abstraction rather than by means of a specific effect structure. This means that the abstraction is enforced, but erased; the concrete structures are the same as the interpreter output, though the code choosing effects can’t tell what that is.

There’s no library for me to mandate, or that you have to adopt. I recommend that you have a library like Scalaz or Cats with Monad, IO (for interpreters), and related functionality available, but it’s not a requirement. The code involved in adopting this style is specific to your use case.

While this is a good alternative to free monads, eff, and the like, it integrates well with them, too. You can combine these effects with other systems as convenient, either to implement interpreters or to produce effects within effect-abstract code, especially if you incorporate Monad.

How can this all be accomplished? With higher-kinded types, that is, abstraction over type constructors.

Declaring an algebra

As with other designs for constrained effects, you need to declare the various effects you’re going to support. For the sake of a little exoticism, I’m going to declare a simple filesystem interface.

trait FSAlg {
  // I'm using an abstract type constructor (i.e. FSAlg
  // is higher-kinded) for the effect type, but this
  // converts readily to a type parameter F[_] on FSAlg,
  // like Scanner in Ermine
  type F[A]

  def listDirectory(pathname: String): F[List[String]]

  def readFile(pathname: String): F[String]

  def writeFile(pathname: String, contents: String): F[Unit]
}

Writing an effectful program

Instances of FSAlg supply concrete operations for the F type constructor, and so must choose a concrete F as well. Concrete programs that choose which effects to perform should be abstract in F under this design approach.

Instances of FSAlg can be defined in typeclass style (in which case you should use a type parameter for F instead of a type member), or passed as normal arguments.

The other thing ‘effectful programs’ do in this style is return an F; specifically, the F associated with the algebra instance being passed in. In this way, this style radically departs from “dependency injection” or “the strategy pattern”—the “dependency” has a concrete influence on the public return type.

Organizing the program as a set of standalone methods makes it easy to use path-dependent style to return the correct type of effect, when using a type member.

def write42(alg: FSAlg)(pathname: String): alg.F[Unit] =
  alg.writeFile(pathname, "42")

A typeclass version would look more like

def write42[F[_]](pathname: String)(implicit alg: FSAlg[F]): F[Unit] =
  alg.writeFile(pathname, "42")

To avoid passing around the alg everywhere, you might put a whole group of methods under a class, and have the class take the algebra as a constructor parameter. This is a straightforward translation for the typeclass or simple type parameter approach.

class MyProg[F[_]](implicit alg: FSAlg[F]) {
  // several methods using F and alg
}

This is the organization style of Ermine Writers; each individual Writer class (e.g. HTMLWriter) is similar to MyProg.

Doing this with a type member is a little trickier; if you simple put a alg: FSAlg argument in the constructor, you’ll “forget” the F, existential-style. You can either put a bounded type parameter on the class for the alg:

class MyProg[Alg <: FSAlg](alg: Alg)

or a higher-kinded parameter, via the Aux pattern.

// object FSAlg
  type Aux[F0[_]] = FSAlg {type F[X] = F0[X]}

// replacing MyProg
class MyProg[F[_]](alg: FSAlg.Aux[F])

I think the latter yields easier-to-understand method types and type errors, but all of the above alternatives have equal power. So choose whatever seems nice, and change it later if you like.

Writing an interpreter

When writing the effectful program, you’re condemned to be free: you have to choose the effects to perform. The “interpreter”, which “executes” the effect, is more of a guided exercise. You must extend the algebra trait, FSAlg, implementing all of the abstract members.

object IOFulFSAlg extends FSAlg {
  import java.io.File, java.nio.file.{Files, Paths}

  type F[A] = () => A  // your choice!

  def listDirectory(pathname: String): () => List[String] =
    () => new File(pathname).list().toList

  def readFile(pathname: String): () => String =
    () => new String(Files readAllBytes (Paths get pathname))

  def writeFile(pathname: String, contents: String): () => Unit =
    () => Files write (Paths get pathname, contents.getBytes)
}

The key is to choose an F type—you can almost consider it an implementation detail of the class—that will allow you to implement the methods without side-effecting when they are called. I’ve made a good starter choice above, but the real magic happens when I choose more interesting Fs.

A test interpreter

With F abstract in “real” programs, we can choose different ones for different interpreters. Here we use one that allows simulation of the algebra methods without performing any side effects or mutation.

final case class Directory(
  listing: Map[String, Either[String, Directory]])

final case class Err(msg: String)

object TestMapAlg extends FSAlg {
  type F[A] = Directory => (Either[Err, A], Directory)

  private def splitPath(p: String) =
    p.split('/').toList

  private def readLocation(dir: Directory, p: List[String])
      : Option[Either[String, Directory]] =
    p match {
      case List() => Some(Right(dir))
      case k +: ks =>
        dir.listing get k flatMap {
          case r@Left(_) =>
            if (ks.isEmpty) None else Some(r)
          case Right(subd) => readLocation(subd, ks)
        }
    }

  def listDirectory(p: String): F[List[String]] =
    dir => (readLocation(dir, splitPath(p)) match {
              case None => Left(Err(s"No such file or directory $p"))
              case Some(Left(_)) =>
                Left(Err(s"$p is not a directory"))
              case Some(Right(Directory(m))) => Right(m.keys.toList)
            }, dir)

  def readFile(pathname: String): F[String] =
    dir => (readLocation(dir, splitPath(pathname)) match {
              case None => Left(Err(s"No such file or directory $pathname"))
              case Some(Right(_)) =>
                Left(Err(s"$pathname is a directory"))
              case Some(Left(c)) => Right(c)
            }, dir)

  def writeFile(pathname: String, contents: String): F[Unit] =
    dir => {
      def rec(subdir: Directory, path: List[String]): Either[Err, Directory] = 
        path match {
          case List(filename) => 
            Right(Directory(subdir.listing + ((filename, Left(contents)))))
          case dirname +: subpath =>
            val subsubdir = subdir.listing get dirname
            subsubdir match {
              case Some(Left(_)) =>
                Left(Err(s"$dirname is not a directory"))
              case Some(Right(d)) =>
                rec(d, subpath)
              case None =>
                rec(Directory(Map()), subpath)
            }
        }
      rec(dir, splitPath(pathname)) match {
        case Left(e) => (Left(e), dir)
        case Right(newdir) => (Right(()), newdir)
      }
    }
}

Executing the effects

The implementations of effectful programs in this scheme can’t tell what F is. But the code that chooses the interpreter and passes it to that abstract program does know. Accordingly, the type returned by invoking the program will change according to the F type of the interpreter you pass in.

scala> write42(IOFulFSAlg)("hello.txt")
res1: IOFulFSAlg.F[Unit] = <function0>

scala> res1()
// hello.txt appears on my disk. Guess what's in it?

scala> write42(TestMapAlg)("hello.txt")
res2: TestMapAlg.F[Unit] = <function1>

scala> res2(Directory(Map()))
res4: (Either[Err,Unit], Directory) =
  (Right(()),Directory(Map(hello.txt -> Left(42))))

As the invoker of the interpreter, this very concrete level—the first truly concrete segments of code I’ve shown in this post—is responsible for supplying the “execution environment”. It’s here that side effects—if any!—happen. For the first example, we can invoke the zero-argument function and watch the side effects happen. In the second case, we can make up a test Directory and inspect the resulting tuple for the final Directory state, and error if any.

Otherwise, the usual rules of the interpreter pattern apply; by inventing new instances of FSAlg, we can choose different things that should happen in the effects of the various algebra methods.

Effects must be delayed

You may be tempted to use an F like this:

type F[A] = A

and then do something like the IOFul implementation without the leading () =>. This will seem to work, but effectively prevent effectful programs from doing functional programming.

We can see why via a simple counterexample. Consider this simple program,

readFile("hello.txt")
// ...
writeFile("hello.txt", "33")

According to the rules of FP, the below program must always do the same thing as the above program.

val wf = writeFile("hello.txt", "33")
readFile("hello.txt")
// ...
wf

If calling writeFile performs a side effect right away, this will not hold true.

For a similar reason, naive memoization of the side effects’ results will also break FP. Consider this program:

readFile("hello.txt")
// ...
writeFile("hello.txt", "33")
// ...
readFile("hello.txt")

In FP, I can factor these two readFile calls to a val. If readFile memoizes with a local variable, though, the second use of that val gives the wrong file contents. (Of course, if you don’t have any effects in your algebra that can change the results of later effects, this is no problem!)

Otherwise, you don’t have to be wildly principled about the purity of your interpreters’ F choices, while still granting the benefits of pure FP to your effectful programs. Ermine writers’ interpreters use something like

type F[A] = java.sql.Connection => A

and it’s perfectly fine.

Relaxed rules in the interpreter from abstraction in the program

“Local mutation” is a broadly accepted way to implement pure functions. Even Haskell supports it, still without breaking the rules of the language, via the ST abstraction (covered in chapter 14 of Functional Programming in Scala). This is usually taken to refer strictly to mutation local to a certain dynamic scope, though; the universal quantification trick in ST is precisely meant to enforce the dynamic scope of mutable variables.

The Ermine Writers show us a different story, though. When using a concrete type for hiding side effects, like IO, you must be very careful to hide the runner, lest the side-effect be exposed.

Type-level abstraction such as in tagless-final changes both of these parts of the typical ‘local mutation’ method of design.

1. Instead of being dynamically scoped, control over side effects is statically, or lexically scoped, to the code in the interpreter. This lends a new dimension to the idea of a side-effecting “shell” for a pure program—the “shell” is syntactic, not based on the patterns of function calls at runtime.
2. The only care required to not break a type-level abstraction is to not pass something that would break it in the algebra, and to follow the Scalazzi Safe Scala Subset and avoid use of reified type information. (This will be discussed in more detail in part 3, “Working with the abstract F”.)

The degree to which you can “break the rules” in your interpreter is directly proportional to the degree to which you enforce abstraction in effectful programs. Following the approach of examples in this article, there remains a great deal of freedom to experiment with interpreters that exploit your favorite mutation techniques to speed up interpretation. For example, a less naive memoization of readFile and listDirectory is admissible under the current algebra.

By contrast, if you expose too much detail about the F functor to effectful programs, then your interpreter becomes severely constrained. Suppose you define in the abstract algebra

def asReader[A](fa: F[A]): () => A

This may be expedient, but effectively demands that every interpreter works like IOFul; others cannot be safely implemented.

Still to come

1. The role of Monad;
2. Working with the abstract F;
3. How much is this “dependency injection”?

Also, Adelbert Chang is covering “Monadic EDSLs in Scala” in a series over on Typelevel blog; he’s taking a different route to many of the same ideas as this series. I suggest checking out both his series and this one to find the most comfortable route for you.

This article was tested with Scala 2.12.0.