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.