Programs as Values, Part IV: Algebras

In the previous instalments of this series, we’ve introduced two core components of the programs as values paradigm: datatypes that represent effects, and functions that combine instances of those datatypes in order to construct programs by describing control flow explicitly.

Today we will formalise and clarify this structure, by introducing the concept of an algebra.

Note: In an unfortunate abuse of notation, the word “algebra” is used with a few different meanings in the FP world. See the Appendix for more details on the terminology.

An algebra is a structure consisting of four components:

1. A single, concrete type T, which is sometimes called the carrier of the algebra. Depending on the algebra, it can have different shapes: V, F[A], G[E, R], etc. The carrier type is the datatype that represents the particular effect its algebra encodes.

2. A set of functions which return values of the carrier type T, called introduction forms. These functions can all take different inputs, but what characterises them as introduction forms is that none of their inputs is of the carrier type T, i.e. they construct or introduce T. Introduction forms are the primitive programs of their algebra, the starting points from which we can build more complex logic.

3. A set of functions which return values of the carrier type T, called combinators. These functions can all take different inputs, but at least one of those inputs needs to be of the carrier type T. In other words, a combinator takes one or more programs in T, and returns another program in T.
   Combinators are the essential building blocks of programs as values we’ve been talking about so far, they take smaller programs and construct bigger programs, often by explicitly describing some form of control flow. Most of the logic in your code will be expressed through combinators.

4. A set of functions called elimination forms. They can all take different inputs, but one of those inputs needs to be of the carrier type T. Furthermore, their output needs to be a different type from T, i.e. they eliminate T.
   Informally, elimination forms encode the concept of “running” a program written in a specific algebra after we’re done constructing it. The concept of running is however expressed as a translation from the carrier type T to another type.

In some cases, algebras also have a fifth component: laws, i.e. equalities between programs written in the algebra. We won’t be talking much about laws in this post, but they will be more prominent later.

So to recap, to build a program in a given algebra we start from the introduction forms, and use combinators to express all the logic we need. Once we’re done, we run it by translating it to another type via one of the elimination forms. Another way to look at it is that each algebra describes a mini language: we write programs in that language, and then translate them to another language, all the way to the most general language of all, which is, as we will see, IO.

We’re now ready to look at some concrete examples.

The Doc algebra

For our first example, we’re going to look at paiges, a pretty printing library that lets you generate text that needs to be well formatted, with paragraph wrapping at different line lengths. The entire library is centred around a document algebra, so let’s look at its components in more detail.

The carrier type of the algebra is called Doc, which means we represent documents as programs of type Doc, like val myDoc: Doc. It might sound strange that we’re referring to a static artifact such as a document as a “program”, but you will see that the mindset we’re working in doesn’t change that much once we move to dynamic behavior with types such as cats.effect.IO or cats.parse.Parser.

The introduction forms are the initial building blocks, as per their definition they create values of type Doc without requiring any value of type Doc as input. Here are a few:

Doc.text: String => Doc
Doc.char: Char => Doc
Doc.spaces: Int => Doc
Doc.comma: Doc
Doc.line: Doc
... // and more

Note that I’m showing them as functions to make the types clearer, but they are generally methods in Scala, so:

val char: Char => Doc
// is more typically written as
def char(c: Char): Doc

also, they tend to appear in the companion object of the carrier type, but don’t use that as a strict rule, sometimes combinators are there too.

Introduction forms have shape (A, B, ..) => Doc, so you might be wondering where do primitive values such as comma or line fit. You can think of them as introduction forms from Unit to the carrier:

val comma: Doc
// can be thought as
val comma: () => Doc

Let’s now look at combinators, functions that take one or more values of type Doc and return a value of type Doc. Combinators will express the lion’s share of our logic, so much so that libraries based on algebras are often called combinator libraries. Here are a few:

indent: (Doc, Int) => Doc
line: (Doc, Doc) => Doc
bracketBy: (Doc, Doc, Doc, Int) => Doc
aligned: Doc => Doc
stack: Iterable[Doc] => Doc
... // and more

Again, I wrote them as standalone functions to make the types clearer, in reality they are written as instance methods, which obscures the fact that at least one of their inputs (this) is of type Doc:

sealed trait Doc {
  def indent(i: Int): Doc
  def line(that: Doc): Doc
  def bracketBy(left: Doc, right: Doc, indent: Int = 2): Doc
  def aligned: Doc
  ... 
  
object Doc {
  def stack(ds: Iterable[Doc]): Doc
  ... 

Doc.stack is a notable exception, it cannot be an instance method on Doc because it operates on a collection of docs. The same intuition about combinators applies though: stack combines programs in the Doc algebra into a bigger program in the Doc algebra.

Finally, eliminations forms translate Doc programs to another type:

isEmpty: Doc => Boolean
maxWidth: Doc => Int
render: (Doc, Int) => String

with the usual caveat that they are defined as instance methods:

sealed trait Doc {
  def isEmpty: Boolean
  def maxWidth: Int
  def render(width: Int): String

Equipped with this knowledge, we can now write Doc programs:

import org.typelevel.paiges.Doc

val openBracket: Doc = Doc.char('[')
val closeBracket: Doc = Doc.char(']')

val north: Doc = Doc.text("NORTH")
val east: Doc = Doc.text("EAST")
val south: Doc = Doc.text("SOUTH")
val west: Doc = Doc.text("WEST")

val directions: Doc = 
  Doc
    .stack(List(north, east, south, west))
    .bracketBy(openBracket, closeBracket)

In the above, I’ve separated usages of introductions forms from combinators for extra clarity, but remember that referential transparency holds, so you can inline definitions or abstract them out freely. We can keep composing to build more complex programs:

val output: Doc = 
  Doc
    .text("Directions:")
    .line(directions.indent(2))
    .bracketBy(Doc.space, Doc.space)

and once we’re done, we can “run” our Doc program by translating it to String via the render elimination form:

output.render(width = 30)
// res0: String = """ 
//   Directions:
//     [ NORTH EAST SOUTH WEST ]
//  """
output.render(width = 15)
// res1: String = """ 
//   Directions:
//     [
//       NORTH
//       EAST
//       SOUTH
//       WEST
//     ]
//  """

The Out algebra

Let’s now look at a made up algebra we’re going to call Out, whose only capability is to print Strings to stdout. It should provide a first, simple example of encoding behaviour, which is more in line with how we think about the word “program”.

Here’s how it looks like:

// Carrier type
Out
// Introduction forms
print: String => Out
// Combinators
andThen: (Out, Out) => Out
// Elimination forms
run: Out => IO[Unit]

except we’re going to assume it’s written idiomatically, with andThen as an instance method and print as a method in the companion object of Out.

Let’s write a program with it:

object Logic {
  val printNewline: Out = Out.print("\n")
  
  val helloWorld: Out = 
    Out
      .print("Hello, world!")
      .andThen(printNewLine)
      .andThen(Out.print("I'm a program!"))
}

object Main extends IOApp.Simple {
  def run: IO[Unit] = Logic.helloWorld.run
}

Main.main(Array())

// Hello, world!
// I'm a program!

So the Out algebra lets us create simple imperative programs that are akin to:

print("tea")
print("coffee")

except we’re in programs as values, so we can easily write compositional code as programs that manipulate other programs. Here’s a basic example, we will see much more interesting ones once we work with algebras that encode complex control flow:

def repeat(p: Out, n: Int): Out =
  if n <= 0 Out.print("")
  else p.andThen(repeat(p, n - 1))

It’s significant that we can write Out programs without any knowledge of its internal structure: we didn’t do any pattern matching on the concrete case classes that form Out, but only used the operations defined on it, or, in other words, its algebra. This style of algebraic thinking is very valuable, because it scales from datatypes with very simple internal structure, such as Option, all the way to highly sophisticated datatypes such as IO or fs2.Stream.

Finally, note that there really is no difference in mechanics nor mindset between imperative-looking algebras such as Out, and algebras that encode static data such as Doc. In fact, we can literally implement Out with Doc:

type Out = Doc
def print(s: String): Out = Doc.text(s)
def andThen(this: Out, that: Out): Out = this + that
def run(p: Out): IO[Unit] = IO.println(p.render(Int.MaxValue))

Conclusion

In this article, we’ve talked about algebras, the fundamental structure at the heart of programs as values. Next time is when things really get interesting, as we’re going to enrich our algebras with the ability to handle outputs. See you then!

---

Appendix on terminology

Terminology can be a source of confusion, since it’s used loosely and inconsistently and mostly reflects historical connections between fields and communities.

“Algebra” is a particularly overloaded term: the meaning we used in the article, which also appears in “Boolean algebra” and “Algebraic Data Types”, originates from a branch of Maths called Universal Algebra. It’s defined as:

• A set A, called the carrier.
• Some finitary operations on A: functions that take tuples of elements of A and return an element of A.

which we called “carrier” and “combinators” respectively. The terms “introduction forms” and “elimination forms” come from logic via type theory instead.

Universal Algebra also introduces the concept of a signature, which defines the set of typed operation symbols without specifying the functions that would be the actual operations. Signatures correspond roughly to the notion of “interface” in programming, and are often encoded in Scala via typeclasses.

The issue is that FP terminology uses the word “algebra” to also mean “signature”, for example in the phrase “algebras and interpreters” which roughly corresponds to “abstractions and implementations” (the usage of the word “interpreter” comes from the theory of embedded domain specific languages, or eDSLs).

---