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.

The missing diamond of Scala variance

This article is an expanded version of my LambdaConf 2016 talk of the same name (video, slides). The below covers every topic from that talk, and much more on possible extensions to variance polymorphism, but the talk is a gentler introduction to the main concepts here.

As part of its subtyping system, Scala features variance. Using variance lets you lift the subtyping relation into type constructors, just like type equality (~) already does.

type Endo[A] = A => A     // invariant
type Get[+A] = Foo => A   // covariant
type Put[-A] = A => Foo   // contravariant

X ~ Y → Endo[X] ~ Endo[Y] // invariant
X <: Y → Get[X] <: Get[Y] // covariant
X <: Y → Put[Y] <: Put[X] // contravariant
             ↑reversed!↑

Subtyping is incomplete without variance

With simple type equality, you have four properties:

1. Reflexivity: A ~ A
2. Symmetry: A ~ B → B ~ A
3. Transitivity: A ~ B ∧ B ~ C → A ~ C
4. Congruence: A ~ B → F[A] ~ F[B]

Just try to use GADTs without equality congruence! That’s what’s expected in a subtyping system without variance.

1. Reflexivity: A <: A
2. Antisymmetry: A <: B ∧ B <: A → A = B
3. Transitivity: A <: B ∧ B <: C → A <: C
4. Congruence: A <: B → Put[B] <: Put[A]

Completing subtyping: variables

val aCat = Cat("Audrey")
val anAnimal: Animal = aCat

A bare type is in a covariant position. You can’t abstract over something as simple as a value box without variance.

Completing subtyping: the harmony of a function call

def speak(a: Animal): IO[Unit]
speak(aCat)

This is how functions and their arguments form a more perfect union. One way to think of the mechanics here is that Cat upcasts to Animal. But there’s no way to tell that what is really happening isn’t that the function is upcasting from Animal => IO[Unit] to Cat => IO[Unit]! Or that they aren’t meeting in the middle somewhere; maybe Cat upcasts to Mammal, and Animal => IO[Unit] upcasts to Mammal => IO[Unit].

So I don’t think there’s really subtyping without variance; there’s just failing to explicitly model variance that is there anyway. Since you cannot have subtyping without variance, if variance is too complicated, so is subtyping.

What else is there? What else is needed?

There is one advanced feature that fans of higher-kinded types would have found a deal-breaker to live without in Scala, even if they are unaware of its existence.

def same[A, F[_]](fa: F[A]): F[A] = fa
def widen[A, B >: A, F[+_]](fa: F[A]): F[B] = fa

All of Endo, Get, and Put can be passed as the F type parameter to same. However, only Get can be passed as the F type parameter to widen. This works because you can only “use” variance if you know you have it, but don’t need to make any assumptions about your type constructors’ variances if you don’t “use” it.

Variance exhibits a subkinding relation

same takes an invariant type constructor F, but you are free to pass covariant and contravariant type constructors to it. That’s because there is a subtype relationship between these at the type level, or a subkind relationship.

Invariance is the ‘top’ variance, the most abstract, and co- and contravariance are its subvariances. When you pass a covariant or contravariant type constructor as F to same, its variance “widens”.

Because variance is part of the “type of type constructor”, not the specific parameter where the variance annotation appears, it’s an element of the kind of that type constructor, just as arity is. For example, when we talk about the kind of Get , we don’t say that A has a covariant kind, because this variance has nothing to do with A. Instead, we say that Get has kind +* -> *, because this particular variance annotation is all about the behavior of types referring to Get. Moreover, subvariance is just a restricted flavor of subkind.

Flipping variances

I started to find it odd that this order of subclassing was enforced as a result of the subvariance relation.

mutable.Seq[A] extends Seq[+A]

CovCoy[F[+_]] extends Coy[F[_]]

It makes perfect sense empirically, though; you can easily derive unsafeCoerce if you assume this exact ordering isn’t enforced.

Then I found, while working on monad transformers, that this is the only way that makes sense, too.

InvMT[T[_[_]]] extends CovMT[T[_[+_]]]

CovMTT[W[_[_[+_]]]] extends InvMTT[W[_[_[_]]]]

I had seen this before.

Type parameter positions are variance-contravariant

The kinds of type constructors (type-level functions) work like the types of value-level functions. Both sorts of functions are contravariant in the parameter position. So every extra layer of nesting, “flips” the variance, just like with functions. Below is the version of this for value-level functions, akin to the examples above.

type One[-A] = A => Z
type Two[+A] = (A => Z) => Z
type Three[-A] = ((A => Z) => Z) => Z
type Four[+A] = (((A => Z) => Z) => Z) => Z

A bottom variance: the diamond, completed

Scala wisely included a bottom type, Nothing, to go with its top type Any. That helps complete its subtyping system, but a bottom variance was unfortunately left out of its subkinding system. Here’s something that might work.

type ConstI[👻A] = Int

ConstI[A] ~ ConstI[B] // phantom, or 👻

This is exactly what you’d get if you applied both the covariant and contravariant rules to a type parameter. Therefore, phantom variance or anyvariance is more specific than either, and as the ‘bottom’ variance, completes the diamond. It is the perfect choice, because it is truly a greatest lower bound; it is both more specific than either by itself and no more specific than both together.

Whence monad transformer variance?

There are two competing flavors of the monad transformers, like OptionT.

final case class NewOptionT[F[_],   A](run: F[Option[A]])

final case class OldOptionT[F[+_], +A](run: F[Option[A]])

The first remains invariant over A, but conveniently doesn’t care about the variance of F—its declared variance is the “top” variance. The latter gives the more specific covariance over A, but requires the F to be covariant (or phantom), which can be very inconvenient. These two transformers can’t be practically unified.

If you look at the structure, the variance of A’s position is always of a piece with the variance of F.

Variance variables

final case class OptionT[😕V, F[V😕_], V😕A]

1. The “variance variable” V is declared with the syntactic marker 😕.
2. 😕 appears infix before _ to say “F has the variance V for the type parameter in this position”.
3. 😕 appears infix before A to say “the parameter A has the variance V”.

Therefore, when you specify variance V = +, the remaining parameters have kind F[+_] and +A, and similarly for other variances.

I’ve chosen the confused smiley 😕 to represent likely reactions to this idea, and especially to my complete lack of consideration for elegant syntax, but it’s really just a limited form of a kind variable in PolyKinds—after all, variance is part of the kind of the surrounding type constructor. And, as seen above, we already have subkind-polymorphism with respect to variance, so what’s wrong with parametric kind polymorphism? “Variance variables” are just parametric kind polymorphism, but not as powerful.

Variance bounds

The OptionT example is a simple case; it supports all possible variances, and features a simple relationship: whatever you select for V is exactly the variance used at the various places V appears. It’s easy to break this simple scheme, though.

final case class WrenchT[F[_], A](run: F[Option[A]], wrench: A)

Now the variance of the A position isn’t strictly the variance of F, as it was with OptionT; it can only be covariant or invariant, due to the wrench being in covariant position.

Well, we have variables over something with a conformance relation, let’s add bounds!

final case class WrenchT[😕V >: +, F[V😕_], V😕A]

And these bounds themselves could be determined by other variance variables, &c, but I don’t want to dwell on that because the complications aren’t over yet.

No easy unification

final case class Compose[F[_], G[_], A](run: F[G[A]])

This type complicates things even further! There are numerous possibilities based on the variances of F and G.

F,G	G,F	A
Inv	Inv	Inv
Inv	+	Inv
Inv	-	Inv
Inv	👻	👻
+	+	+
+	-	-
+	👻	👻
-	-	+
-	👻	👻
👻	👻	👻

(The order of F and G doesn’t matter here, so I’ve left out the reverses here.) So the variance of A’s position is the result of multiplying the variance of F and G. The multiplication table is just above. Guess we need a notation for that.

[😕FV, 😕GV, 😕V >: FV × GV, F[FV😕_], G[GV😕_], V😕A]

The bound here only means that V is in variance-covariant position, but bounded by FV × GV.

Another wrench

We can privilege F a little bit to make things more interesting.

final case class ComposeWr[F[_], G[_], A](run: F[G[A]], fa: F[A])

F×G	F	A
	Inv,+,-	Inv
Inv,+,-,👻	Inv	Inv
+,👻	+	+
-	+	Inv
-,👻	-	-
+	-	Inv
👻	👻	👻

Here’s another level to the function that determines the A-position variance: it’s now lub(F×G, F), where lub is the least upper bound, the most specific variance that still holds both arguments as subvariances.

Variance families? Really?

I hope you guessed where I was going when I said “function”: the rules determining the lower bound on the A-position variance can be specified by the programmer with a variance-level function—a mapping where the arguments and results are variances—or a variance family. Again, I don’t think this is terribly novel; it’s just a kind family, but more restricted.

You’d want it closed and total, and I can see the Haskell now.

variance family LUBTimes a b where
  LUBTimes - + = -
  LUBTimes 👻 Inv = 👻
  …

Only because I’m not sure where to begin making up the Scala syntax.

There are four variances

When I started looking for ways to describe the variances of the datatypes I’ve shown you, I noticed the relationship between variance and kinds, converted the problem to a kind-level problem, and started thinking of solutions in terms of PolyKinds. That’s where variance variables come from, and everything else follows from those.

However, I think I’ve made a mistake. Not with variance variables themselves, mind you, nor the variance-conformance already built in to Scala. But, to deal with the problems that arise with only these, I’ve hypothesized tools—described above—that are way too powerful. They work on open domains of unbounded complexity—the kinds of types—and there are only four variances.

There are two reasons I think there must be a better approach.

First, there are finitely many variance families for a given sort.

Second, there are only so many ways to put variables in positions of variance. You get argument and result position of methods, within other type constructors, and that’s it. Things are simple enough that, discounting desire for working GADTs (which will be discussed in a later post, “Choosing variance for a phantom type”), it is always possible to infer which of the four variances a type parameter ought to have, in a first-order variance situation.

A “good” polyvariance constraint system

Since there are only four variances, and only so many ways to combine them, it might be possible to design something more refined and suited for the task than the too-powerful variance families.

It might be that there are only a few useful variance relations, like × and lub, and a good solution would be to supply these relations along with an expression model to combine them. Or maybe not. Instead, I’ll stop hypothesizing and instead say what a I think a “good” system would look like.

1. It must be writable. Just as it is desirable to write a stronger type role than the inferred one in GHC Haskell ≥ 7.8, there are very common reasons to want a more general variance than the one that would be inferred. So the convenience of writing out the rule explicitly matters a great deal.
2. It must be checkable. For variance variables, that means every possible variance you can choose puts every type parameter only in positions consistent with its variance. For example, our fully generalized OptionT always places A only in positions matching the variance of the F type constructor.

   We can just check every possible variance—up to four for each variable—but I think this is the wrong way to go. We don’t just enumerate over every possible type to check type parameters—that would take forever—we have a systematic way to check exactly one time, with skolemization. Variance is simpler—it should be an easier problem.

3. Not a requirement—but it ought to be inferrable. In the same way that skolemization gives us a path to automatic generalization, if there is a similar way to do quantified variance checking, it should be possible to use the output of that decision procedure to determine the relationships between and bounds on variance variables.

   How that decision is expressed is another question.

Variance & GHC type roles

It might seem that Haskell, with no subtyping, might not care about this problem. But GHC 7.8 type roles are similar enough to variances; the main difference is that Scala variance is about the congruence/liftability of the strong conformance relation, while type roles are about the congruence/liftability of the weak type equality/“coercibility” relation.

nominal:          a ~ b → f a ~ f b
representational: a ~w b → f a ~w f b
phantom:          f a ~w f b

This is pretty useful from a practical, performance-minded perspective, but the problem is

newtype MaybeT m a = MaybeT (m (Maybe a))

there is no way to describe the role of the a parameter in the most general way. It’s stuck at nominal, even if m’s parameter is representational.

Just as the integration of variance and higher kinds in Scala is incomplete without something like the polyvariance system I’ve been describing, Haskell’s type roles are not fully integrated with higher kinds.

I hope if one of these language communities finds a good solution, it is adopted by the other posthaste. The Haskell community is attempting to tackle these problems with roles; perhaps Scala can profit from its innovations. Much of the prose on the GHC matter can be profitably read by replacing “role” with “variance” where it appears. For example, this should sound familiar.

This design incorporates roles into kinds. It solves the exact problems here, but at great cost: because roles are attached to kinds, we have to choose a types roles in the wrong place. For example, consider the Monad class. Should the parameter m have type */R -> *, requiring all monads to take representational arguments, or should it have type */N -> *, disallowing GND if join is in the Monad class? We’re stuck with a different set of problems.

Subtyping or higher kinds?

As things stand, you will have a little trouble combining heavy use of subtyping and of higher kinds in the same system.

I’m not saying for certain that it comes down to one or the other. In Scalaz, we weakened support for subtyping to have better support for higher kinds, because its users typically do not want to use subtyping. However, this preference doesn’t generalize to the Scala community at large. This was only a real concern for monad transformers; most Scalaz constructs, for now, have fine subtyping support.

My suggestion is that you should favor higher kinds; they’re a more powerful abstraction mechanism, and ultimately easier to understand, than subtyping; they also happen to be less buggy in Scala. If you must use subtyping, be warned: it’s much more complex than it first seems.

Further reading

• “Choosing variance for a phantom type” builds upon this post to connect variance and pattern matching
• “Of variance and functors” by Adelbert Chang, provides some foundational intuition for variance
• SI-2066 “Unsoundness in overriding methods with higher‐order type parameters”, easily the most important surfacing of the interaction of higher kinds and variance, revealing the existence of subvariance
• The Liskov type, which builds every other subtyping property on reflexivity and contravariance