Don’t Fear the Profunctor Optics! (Part 1/3)

Today we start a new series of posts on Profunctor Optics. Since WordPress has some limitations to highlight Haskell snippets, we’ve decided to publish it as a Github repo. You can find the first part here: Optics, Concretely. We hope you like it!

Advertisements
Posted in Uncategorized | Leave a comment

Functional APIs: an OOP approach to FP

In the series of posts about the essence of functional programming, we’ve already seen how we can build purely declarative programs using GADTs. This is a picture of what we got (using more standard cats/scalaz data types):

free-flow-version

This program above has several advantages over an impure one, given that it completely separates the business logic (the WHAT) from the interpretation (the HOW). This gives us full room of possibilities, since we can change the whole deployment infrastructure without having to change the logic in any way. In other words, business logic changes affect only business logic code and infrastructure changes affect only interpreters (provided that neither of these changes affect the DSL, of course). Some changes of interpretation could be, for instance, running the program using Futures in an asynchronous way, or running it as a pure state transformation for testing purposes using State.

Now, you might be wondering, is OOP capable of achieving this level of declarativeness? In this post, we will see that we can indeed do purely functional programming in a purely object-oriented style. However, in order to do so, the conventional techniques that we normally employ when doing OOP (plain abstract interfaces) won’t suffice. What we actually need are more powerful techniques for building Functional APIs, namely type classes!

The issues of conventional OOP

In OOP, the most common way to achieve declarativeness is by using plain abstract interfaces, of course. In a similar way to the GADT approach, we can acknowledge four parts of this design pattern:

  • Interface/API
  • Method/Program over that interface
  • Concrete instances
  • Composition

Here there is a very illustrative diagram of this approach:

oop-interface-design-pattern

However, this is just one step towards declarativeness; it separates a little bit WHAT and HOW, since IO is an abstract interface, but we still have a very limited range of possible HOWs. This is quite easy to prove just by giving a couple of interpretations we can not implement. These are, for instance, asynchronous and pure state transformations. In the former case, we can’t simply implement the IO signature in an asynchronous way, since this signature forces us to return plain values, i.e. a value of type String in the read case, and a value of type Unit in the  write case. If we attempt to implement this API in an asynchronous way, we will eventually get a Future[String] value, and we will have to convert this promise to a plain String by blocking the thread and waiting for the asynchronous computation to complete, thus rendering the interpretation absolutely synchronous.

object asyncInstance extends IO {
  def write(msg: String): Unit =
    Await.result(/* My future computation */, 2 seconds)
  def read: String = /* Idem */
}

Similarly, an state-based interpretation won’t be possible. In sum, if we want an asynchronous or a pure state transformer behaviour for our programs, we would have to change the original interface to reflect those changes and come up with two new APIs:

trait IO { // Async
  def write(msg: String): Future[Unit]
  def read(): Future[String]
}

trait IO { // Pure state transformations
  def write(msg: String): IOState => (IOState, Unit)
  def read(): IOState => (IOState, String)
}

This is clearly not desirable, since these changes in API will force us to rewrite all of our business logic that rests upon the original IO API. Let’s go ahead and start improving our OOP interfaces towards true declarativeness. As we’ve seen in this pattern, we can distinguish between the abstract world (interface and interface-dependent method) and the concrete world (interface instance and composition).

Abstract world: towards Functional APIs

We may notice that there are not many differences among the three interfaces we’ve shown so far. In fact, the only differences are related to the return type embelishment in each case:

find-7-differences

We can factor out these differences and generalize a common solution for all of them; we just need to write our interface in such a way that the instructions (methods) don’t return a plain value, but a value wrapped in a generic type constructor, the so-called embelishment; from now on we will also call those embelishments programs, as they can be considered computations that will eventually return a result value (once the asynchronous computation completes, or when we enact the state transformation).

trait IO[P[_]] {
  def read: P[String]
  def write(msg: String): P[Unit]
}

// Console
type Id[A] = A
type SynchIO = IO[Id]

// Async
type AsyncIO = IO[Future]

// Pure state transformations
type State[A] = IOState => (IOState, A)
type StateIO = IO[State]

Wow! our new interface is a generic interface, and, more specifically, a type class that solves our declarativeness problem: we can now create interpreters (instances) for both asynchronous and state transformers computations, and for any other program you may think of.

We call this type of class-based APIs functional APIs, due to their ability to totally decouple business logic from interpretation. With our traditional interfaces we still had our business logic contaminated with HOW concepts, specifically with the limitation of running always in Id[_]. Now, we are truly free.

Abstract world: programs

Ain’t it easy? Let’s see what we have so far. We have a type class that models IO languages. Those languages consists on two instructions read and write that returns plain abstract programs. What can we do with this type class already?

def hello[P[_]](IO: IO[P]): P[Unit] =
  IO.write("Hello, world!")

def sayWhat[P[_]](IO: IO[P]): P[String] =
  IO.read

Not very impressive, we don’t have any problem to build simple programs, what about composition?

def helloSayWhat[P[_]](IO: IO[P]): P[String] = {
  IO.write("Hello, say something:")
  IO.read()
} // This doesn't work as expected

Houston, we have a problem! The program above just reads the input but it’s not writing anything, the first instruction is just a pure statement in the middle of our program, hence it’s doing nothing. We are missing some mechanism to combine our programs in an imperative way. Luckily for us, that’s exactly what monads do, in fact monads are just another Functional API: 🙂

trait Monad[P[_]] {
  def flatMap[A, B](pa: P[A])(f: A => P[B]): P[B]
  def pure[A](a: A): P[A]
}

Well, you won’t believe it but we can already define every single program we had in our previous post. Emphasis in the word define, as we can just do that: define or declare in a pure way all of our programs; but we’re still in the abstract world, in our safe space, where everything is wonderful, modular and comfy.

def helloSayWhat[P[_]](M: Monad[P], IO: IO[P]): P[String] =
  M.flatMap(IO.write("Hello, say something:")){ _ => 
    IO.read
  }

def echo[P[_]](M: Monad[P], IO: IO[P]): P[Unit] =
  M.flatMap(IO.read){ msg => 
    IO.write(msg)
  }

def echo2[P[_]](M: Monad[P], IO: IO[P]): P[String] =
  M.flatMap(IO.read){ msg => 
    M.flatMap(IO.write(msg)){ _ => 
      M.pure(msg)
    }
  }

Ok, the previous code is pretty modular but isn’t very sweet. But with a little help from our friends (namely, context bounds, for-comprehensions, helper methods and infix operators), we can get closer to the syntactic niceties of the non-declarative implementation:

def helloSayWhat[P[_]: Monad: IO]: P[String] =
  write("Hello, say something:") >>
  read

def echo[P[_]: Monad: IO]: P[Unit] =
  read >>= write[P]

def echo2[P[_]: Monad: IO]: P[String] = for {
  msg <- read
  _ <- write(msg)
} yield msg

You can get the details of this transformation in the accompanying gist of this post.

Concrete world: instances and composition

As we said, these are just pure program definitions, free of interpretation. Time to go to real world! Luckily for us, interpreters of these programs are just instances of our type class. Moreover, our console interpreter will look almost the same as in the OOP version, we just need to specify the type of our programs to be Id[_] (in the OOP approach this was set implicitly):

// Remember, `Id[A]` is just the same as `A`
implicit object ioTerminal extends IO[Id] {
  def print(msg: String) = println(msg)
  def read() = readLine
}

implicit object idMonad extends Monad[Id] {
  def flatMap[A, B](pa: Id[A])(f: A => Id[B]): Id[B] = f(pa)
  def pure[A](a: A): Id[A] = a
}

def helloConsole(): Unit = hello[Id](ioTerminal)

def sayWhatConsole(): String = sayWhat(ioTerminal)

def helloSayWhatConsole() = helloSayWhat(idMonad, ioTerminal)

def echoConsole() = echo[Id]

def echo2Console() = echo2[Id]

So now, we can start talking about the type class design pattern. In the same way we did with the plan abstract interface design pattern, here it is the diagram of this methodology:

tagless-flow-version

Conventional OOP vs. FP (OO Style) vs. FP (GADT style)

Fine, we’ve seen two ways of defining pure, declarative programs (GADTs and Functional APIs), and another one that unsuccessfully aims to do so (plain OOP abstract interfaces), what are the differences? which one is better? Well, let’s answer the first question for now using the following table:

comparison

As you can see, the GADT style for doing functional programming (FP) favours data types (IOEffect and Free), whereas FP in a OO style favours APIs (IO and Monad); declarative functions in the GADT style return programs written in our DSL (IOProgram), whereas declarative functions in FP (OO Style) are ad-hoc polymorphic functions; concerning interpretations, natural transformations used in the GADT style correspond simply to instances of APIs in OO-based FP; last, running our programs in the GADT style using a given interpreter, just means plain old dependency injection in FP OO. As for the conventional OOP approach, you can just see how it can be considered an instance of FP OO for the Id interpretation.

About the question of which alternative is better, GADTs or Functional APIs, there’s not an easy answer, but we can give some tips:

Pros Functional APIs:

  • Cleaner: This approach implies much less boilerplate.
  • Simpler: It’s easier to perform and it should be pretty familiar to any OOP programmer (no need to talk about GADTs or natural transformations).
  • Performance: We don’t have to create lots of intermediate objects like the ADT version does.
  • Flexible: We can go from Functional APIs to GADTs at any time, just giving an instance of the type class for the ADT-based program (e.g., object toADT extends IO[IOProgram]]).

Pros GADTs:

  • More control: In general, ADTs allows for more control over our programs, due to the fact that we have the program represented as a value that we can inspect, modify, refactor, etc.
  • Reification: if you need somehow to pass around your programs, or read programs from a file, then you need to represent programs as values, and for that purpose ADTs come in very handy.
  • Modular interpreters: Arguably, we can write interpreters in a more modular fashion when working with GADTs, as, for instance, with the Eff monad.

Conclusion & next steps

We have seen how we can do purely functional programming in an object-oriented fashion using so-called functional APIs, i.e. using type classes instead of plain abstract interfaces. This little change allowed us to widen the type of interpretations that our OO APIs can handle, and write programs in a purely declarative fashion. And, significantly, all of this was achieved while working in the realm of object-oriented programming! So, this style of doing FP, which is also known as MTL, tagless final and related to object-algebras, is more closely aligned with OO programmers, and don’t require knowledge of alien abstractions to the OO world such as GADTs and natural transformations. But we just scratched the surface, as this is a very large subject to tackle in one post. Some of the topics we may see in the future are:

  • Modular interpreters: How to seamlessly compose interpreters using Functional APIs is another large issue which is currently under investigation. A recent library that aims at this goal is mainecoon.
  • Church encodings: In the GADT approach, declarative functions return programs that will eventually be interpreted, but with Functional APIs, we don’t see any such program value. In our next posts, we will see how the Church encoding allows us to reconcile this two different ways of doing FP.

Last, let us recommend you this presentation where we talk about the issues of this post! All roads lead … to lambda world. Also, you can find the code of this post here.

See ya!

Posted in algebra, functional programming, Scala, Type Class | Leave a comment

From “Hello, world!” to “Hello, monad!” (part III/III)

In the first part of this series, we saw how we can write the business logic of our applications as pure functions that return programs written in a custom domain-specific language (DSL). We also showed in part II that no matter how complex our business logic is, we can always craft a DSL to express our intent. All this was illustrated using the “Fibonacci” example of purely functional programming, namely IO programs. We reproduce bellow the resulting design of the IO DSL and a sample IO program:

  // IO DSL

  sealed trait IOProgram[A]
  case class Single[A](e: IOProgram.Effect[A]) 
    extends IOProgram[A]
  case class Sequence[A, B](p1: IOProgram[A],
    p2: A => IOProgram[B]) extends IOProgram[B]
  case class Value[A](a: A) extends IOProgram[A]

  object IOProgram{
    sealed trait Effect[A]
    case class Write(s: String) extends Effect[Unit]
    case object Read extends Effect[String]
  }

  // Sample IO program

  def echo(): IOProgram[String] =
    Sequence(Single(Read()), (msg: String) =>
      Sequence(Write(msg), (_ : Unit) =>
        Value(msg)))

However, while this design is essentially correct from the point of view of the functional requirements of our little application, and from the point of view of illustrating the essence of functional programming, there are two major flaws concerning two important non-functional guarantees: readability and modularity. Let’s start from the first one!

Note: you can find the code for this post in this repo.

More sugar!

What’s the problem with the little echo function we came up with? Well, this function being pure has an essential advantage: it simply declares what has to be done, and the task of actually executing those programs in any way we want is delegated to another part of the application – the interpreter. Thus, we could run our echo() IO program using the println and readLine methods of the Console; or using an asynchronous library using Future values; or test it without the need of mocking libraries with the help of custom state transformers in a type-safe way. Great, great, great! But … who would ever want to write our pure functions using that syntax? We have to admit that the readability of our little program is poor … to say the least. Let’s fix it!

Smart constructors for atomic programs

We start by adding some lifting methods that allow us to use IO instructions as if they were programs already:

object IOProgram {
  object Syntax{
    val read(): IOProgram[String] = 
      Single(Read)
    def write(msg: String): IOProgram[Unit] = 
      Single(Write(msg))
  }
}

Smart constructors for complex programs

Next, let’s introduce some smart constructors for sequencing programs. We will named them flatMap and map — for reasons that will become clear very soon. As you can see in the following implementation, flatMap simply allow us to write sequential programs using an infix notation; and map allows us to write a special type of sequential program: one which runs some program, transforms its result using a given function, and then simply returns that transformed output.

sealed trait IOProgram[A]{
  def flatMap[B](f: A => IOProgram[B]): IOProgram[B] =
    Sequence(this, f)
  def map[B](f: A => B): IOProgram[B] =
    flatMap(f andThen Value.apply)
}

Using all these smart constructors we can already write our program in a more concise style:

import IOProgram.Syntax._

def echo: IOProgram[String] =
  read() flatMap { msg =>
    write(msg) map { _ => msg }
  }

Using for-comprehensions

We may agree that the above version using smart constructors represents an improvement, but, admittedly, it’s far from the conciseness and readability of the initial impure version:

def echo(): String = {
  val msg: String = readLine
  println(msg)
  msg
}

For one thing at least: in case that our program consists of a long sequence of multiple subprograms, we will be forced to write a long sequence of nested indented flatMaps. But we can avoid this already using so-called for-comprehensions! This is a Scala feature which parallels Haskell’s do notation and F#’s computation expressions. In all of these cases, the purpose is being able to write sequential programs more easily. Our little example can be written now as follows:

import IOProgram.Syntax._

def echo(): IOProgram[String] = for{
  msg <- read()
  _ <- write(msg)
} yield msg

For-comprehensions are desugared by the Scala compiler into a sequence of flatMaps and a last map expression. So, the above program and the flatMap-based program written in the last section are essentially identical.

Hello, Monad!

Let’s deal now with the second of our problems: the one concerning modularity. What’s the problem with the little DSL to write IO programs we came up with? Basically, the problem is that, approximately, half of this data type is not related to input-output at all. Indeed, if we were to write a different DSL to write imperative programs dealing with file system effects (e.g. reading the content from some file, renaming it, etc.), we would almost write line by line half of its definition:

sealed trait FileSystemProgram[A]
case class Single[A](e: FileSystemProgram.Effect[A]) 
  extends FileSystemProgram[A]
case class Sequence[A, B](p1: FileSystemProgram[A], 
  p2: A => FileSystemProgram[B]) extends FileSystemProgram[B]
case class Value[A](a: A) extends FileSystemProgram[A]

object FileSystemProgram{
  sealed abstract class Effect[_]
  case class ReadFile(path: String) extends Effect[String]
  case class DeleteFile(path: String) extends Effect[Unit]
  case class WriteFile(path: String, content: String) 
    extends Effect[Unit]
}

The only remarkable change is related to the kinds of effects we are dealing with now: file system effects instead of IO effects. The definition of the DSL itself simply varies in the reference to the new kind of effect. This amount of redundancy is a clear signal of a lack of modularity. What we need is a generic data type that accounts for the common imperative features of both DSLs. We can try it as follows:

sealed trait ImperativeProgram[Effect[_],A]{
  def flatMap[B](f: A => ImperativeProgram[Effect,B]) =
    Sequence(this, f)
  def map[B](f: A => B) =
    flatMap(f andThen Value.apply)
}
case class Single[Effect[_],A](e: Effect[A]) 
  extends ImperativeProgram[Effect,A]
case class Sequence[Effect[_],A, B](
  p1: ImperativeProgram[Effect,A],
  p2: A => ImperativeProgram[Effect,B]) 
  extends ImperativeProgram[Effect,B]
case class Value[Effect[_],A](a: A) 
  extends ImperativeProgram[Effect,A]

Note how the Single variant of the DSL now refers to a (type constructor) parameter Effect[_]. We can now reuse the ImperativeProgram generic DSL in a modular definition of our DSLs for IO and file system effects:

type IOProgram[A] = 
  ImperativeProgram[IOProgram.Effect, A]

type FileSystemProgram[A] = 
  ImperativeProgram[FileSystemProgram.Effect, A]

This ImperativeProgram generic DSL seems pretty powerful: indeed, it encodes the essence of imperative DSLs, and it is actually commonly known through a much more popular name: Free Monad! The definitions of Free that you will find in professional libraries such as cats, scalaz or eff are not quite the same as the one obtained in this post, which is quite inefficient both in time and space (not to mention further modularity problems when combining different types of effects); but, the essence of free monads, namely, being able to define imperative programs given any type of effects represented by some type constructor is there. This substantially reduces the effort of defining an imperative DSL: first, program definition will collapse into a single type alias; second, we will get the flatMap and map operators for free; and, similarly, although not shown in this post, we will also be able to simplify the definition of monadic interpreters (those that translate the given free program into a specific monadic data type, such as a state transformation, asynchronous computation, etc.), amongst many other goodies.

Conclusion: modularity all the way down!

We may say that the essence of functional programming is modularity. Indeed, the defining feature of functional programming, namely pure functions, is an application of this design principle: they let us compose our application out of two kinds of modules: pure functions themselves that declare what has to be done, and interpreters that specify a particular way of doing it. In particular, interpreters may behave as translators, so that the resulting interpretations are programs written in a lower-level DSL, that also need to be interpreted. Eventually, we will reach the “bare metal” and the interpreters will actually bring the effects into the real world (i.e. something will be written in the screen, a file will be read, a web service will be called, etc.).

But besides pure functions, functional programming is full of many additional modularity techniques: parametric polymorphism, type classes, higher-order functions, lazy evaluation, datatype generics, etc. All these techniques, which were first conceived in the functional programming community, basically aim at allowing us to write programs with extra levels of modularity. We saw an example in this post: instead of defining imperative DSLs for implementing Input/Output and File System programs in a monolithic way, we were able to abstract away their differences and package their common part in a super reusable definition: namely, the generic imperative DSL represented by the Free monad. How did we do that? Basically, using parametric polymorphism (higher-kinds generics, in particular), and generalised algebraic data types (GADTs). But functional programming is so rich in abstractions and modularity techniques, that we may have even achieved a similar modular result using type classes instead of GADTs (in a style known as finally tagless). And this is actually what we will see in our next post. Stay tuned!

Posted in Embedded DSLs, functional programming | Tagged , , | 1 Comment

Algebras for the Masses!

According to Wikipedia, “an Algebraic Structure is a set with one or more finitary operations defined on it that satisfies a list of axioms”. From a programming perspective, that sounds like a bunch of methods defined on a type. In fact, we can find many of those algebras represented as type classes in libraries such as scalaz or cats. This way of representing algebras is pretty related to object algebras. However, it’s quite common to hear about F-algebras as well, an abstraction that arises from the field of Category Theory. Today, we’ll see not only that both representations are isomorphic, but also how to systematically generate conversions between them. To validate those transformations, we’ll scratch the surface of Matryoshka to fold several expressions with the aforementioned algebra representations. So here we go!

Algebras and Their Representations

Undoubtedly, one of the most widespread algebraic structures in the functional programming community is monoid. Despite its simplicity, it turns out to be very powerful. Typically, in Scala type class libraries, monoid is represented as follows:

trait OMonoid[A] {
  def mzero(): A
  def mappend(a1: A, a2: A): A
}

This type class is what is known as the object algebra interface, an interface of an abstract factory to create expressions. It contains two methods: mzero and mappend which correspond with the two operations that describe this particular algebra. Once we have created the algebra interface, we could provide instances for it, that are also known as object algebras. A common monoid instance is sum:

val sumOMonoid: OMonoid[Int] = new OMonoid[Int] {
  def mzero(): Int = 0
  def mappend(a1: Int, a2: Int): Int = a1 + a2
}

Once we have shown object algebra fundamentals, it’s time to focus on F-algebras. This is a really simple abstraction that consists of a Functor F[_], a carrier type A and an algebra structure (the function itself):

type FAlgebra[F[_], A] = F[A] => A

At first glance, this looks very different from the object algebra approach for monoids. However, as we will see, the translation is completely natural. Indeed, this representation just packs all the algebra operations into a unique function. Thereby, the major challenge here is to identify the corresponding functor for monoids, which is an Algebraic Data Type with a representative for every operation conforming the algebra. We refer to it as the algebra signature:

sealed trait Σ[A]
case class MZero[A]() extends Σ[A]
case class MAppend[A](a1: A, a2: A) extends Σ[A]

Once the functor is defined, we can modularize Monoid as an F-algebra:

type FMonoid[A] = FAlgebra[Σ, A]

Finally, we could provide a sum instance for the brand new monoid representation, as we did with the previous approach:

val sumFMonoid: FMonoid[Int] = {
  case Mzero() => 0
  case Mappend(a1, a2) => a1 + a2
}

We claim that sumFMonoid is isomorphic to sumOMonoid. In order to provide such an evidence, we show the isomorphism between OMonoid and FMonoid:

val monoidIso = new (OMonoid <~> FMonoid) {

  val to = new (OMonoid ~> FMonoid) {
    def apply[A](omonoid: OMonoid[A]) = {
      case Mzero() => omonoid.mzero
      case Mappend(a1, a2) => omonoid.mappend(a1, a2)
    }
  }

  val from = new (FMonoid ~> Monoid) {
    def apply[A](fmonoid: FAlgebra[Σ, A]) = new FMonoid[A] {
      def mzero = fmonoid(Mzero())
      def mappend(a1: A, a2: A) = fmonoid(Mappend(a1, a2))
    }
  }
}

(*) Notice that we have ignored the monoid laws along the article for simplicity, but keep in mind that they constitute a fundamental part of every algebra.

Given this situation, the question we should be asking is: “What is the best algebra representation for us?” Sadly, there’s no clear answer to this. On the one hand, there is F-algebra. Undoubtedly, this representation is more modular. In fact, it is used in projects such as Matryoshka, a library of recursion-schemes that is able to generate fixed points for any Functor, or define a generic catamorphism (or fold) once and for all, which works for any F-algebra. On the other hand, there is the object algebra representation, closer to the widespread programming interfaces, that we can find in libraries such as scalaz or cats. Although not as modular as F-algebras, this representation is powerful enough to interpret algebra expressions with little effort. See this paper on shallow embedding to get a better intuition on that. Therefore, both representations do appear in prominent libraries of the functional programming community. Wouldn’t it be nice to have them coexisting?

Macro @algebra to Provide Conversions

As we have seen in the previous section, turning object algebras into F-algebras (and viceversa) is straightforward. Besides, we noticed that both algebra representations are used in everyday programming. For all these reasons, we decided to code an experimental macro (@algebra) to make both representations live together. The macro annotation can be applied to an object algebra Interface:

@algebra trait OMonoid[A] {
  def mzero(): A
  def mappend(a1: A, a2: A): A
}

This annotation removes boilerplate by automatically generating some F-algebra encodings. They should enable us to translate object algebras wherever an F-algebra is required. To check that behaviour, we’re going to invoke a Matryoshka catamorphism (cata) that requires an F-algebra as input parameter, but we’ll be implementing object algebras instead. Besides, we’ll be using the tiny language (num literals and multiplications) that is used in Matryoshka’s introduction, so we recommend the reader to glance at it before moving ahead. Then, you should be able to appreciate that Expr leads to the following object algebra interface:

@algebra trait ExprAlg[A] {
  def num(value: Long): A
  def mul(l: A, r: A): A
}

First of all, our macro has to generate the corresponding Expr signature. So, our auto generated companion for ExprAlg will contain:

sealed abstract class Σ[_]
case class Num[A](value: Long) extends Σ[A]
case class Mul[A](l: A, r: A) extends Σ[A]

In this section from Matryoshka’s introduction, we see that it’s required to provide a functor for Expr prior to apply a cata. Our macro is able to derive the Functor instance for Σ, so we don’t have to worry about that. The document shows also an eval F-algebra, that we can translate easily to an object algebra:

implicit def eval = new Expr[Long] {
  def num(value: Long) = value
  def mul(l: Long, r: Long) = l * r
}

Notice that we marked it as implicit, because it will be necessary for the next task, which is invoking the catamorphism over an expression. Firstly, we need to declare the expression to be folded, I mean, evaluated. We can copy someExpr as is, and it will compile smoothly, since the Mul and Num case classes are generated by the macro as well:

def someExpr[T](implicit T: Corecursive.Aux[T, Σ]): T =
  Mul(Num[T](2).embed, Mul(Num[T](3).embed,
    Num[T](4).embed).embed).embed

Finally, we can invoke the cata. As we noted previously, it requires an F-algebra as input. Thereby, we use the FAlgebra summoner, generated by the macro, that detects the implicit eval and turns it into a compatible F-algebra to feed the function.

someExpr[Mu[Σ]].cata(FAlgebra[Long]) // ⇒ 24

To sum up, we applied our macro annotation to ExprAlg to generate some utilities to deal with F-algebras. Then, we defined our eval as an object algebra. As the generated encodings knew how to turn it into a F-algebra, we could invoke Matryoshka’s cata with this algebra safely. Thus, we reach our objective of making both representations coexist nicely.

Future Work

Today, we have seen OMonoid[A] and ExprAlg[A] as algebra examples, both demanding a concrete type parameter. However, there are algebras that are parametrized by a type constructor. Take Monad[F[_]] as an example. In this particular situation, we can’t generate isomorphisms with F-algebras as we know them. Instead, we have to deal with F-algebras for Higher Order Functors. Our macro @algebra is able to detect GADTs and generate the corresponding encodings. This is still very experimental, but you can find an example here.

By now, we have placed @algebra in azucar (spanish word for “sugar”), a library where we plan to deploy more utilities to deal with (co)algebras. If you have some feedback or suggestion to improve it, we’d be very glad to hear from you. Anyway, we hope you’ve enjoyed reading!

Posted in Uncategorized | Leave a comment

From “Hello, world!” to “Hello, monad!” (Part II/III)

In the first part of this series, we set forth the essence of functional programming, namely, being declarative. This was illustrated with the ubiquitous “Hello, world!” example, a ridiculously simple program which, nonetheless, allowed us to introduce the major concepts involved in purely functional programming: declarative functions, languages, and interpreters. It’s time now to show that this approach actually scales up for larger and more complex programs.

In the following paragraphs, you’ll find a series of impure IO programs that represent purification challenges. Compare to the simple “Hello, world!” program, these new programs feature additional IO instructions, and an increasingly complex control flow structure. These extra levels of complexity will force us to enrich the simple IOProgram DSL and interpreter that we created to purify the simple “Hello, world!” program. For easy of reference, we reproduce that initial purification bellow:

object HelloWorld{
  /* Impure program */
  def helloWorld: String =
    println("Hello, world!")

  /* Functional solution */
  object Fun {
    // Language
    type IOProgram = Print
    case class Print(msg: String)

    // Pure function
    def pureHello(): IOProgram =
      Print("Hello, world!")

    // Interpreter
    def run(program: IOProgram): Unit =
      program match {
        case Print(msg) => println(msg)
      }

    // Impure program (modularised)
    def hello() = run(pureHello())
  }
}

Say what?

Our first challenge consists in purifying the following impure program:

def sayWhat: String =
  readLine

Similarly to the “Hello, world!” program, the “sayWhat” program consists of a single IO instruction. In this case, when the program is run it will immediately block until we type something in the console. Then, it will return the string typed, rather than Unit:

scala> SayWhat.sayWhat
(type "something")
res0: String = "something"

In order to purify any program we have to return pure values that represent a description of the logic we want to accomplish. In order to describe this logic, we use the IOProgram DSL, but the current version of this DSL does only offer a Write instruction, so we have to extend it with a new Read command:

type IOProgram[A] = IOEffect[A]

sealed trait IOEffect[A]
case class Write(msg: String) extends IOEffect[Unit]
case object Read extends IOEffect[String]

There are several things going on here:

  • We chose to use an ADT (Algebraic Data Type) to represent our instructions. We created an effect Language to perform IO operations, composed by two instructions, one to read from and the other to write to the console. And our programs consist of either one of these instructions.
  • The new Read instruction is a case object because it is a singleton instance; there can only exist one and only one instance of Read as it has no arguments.
  • Another thing to point out is that we parameterized our IOEffect and IOProgram ADTs. We did that because we need to store the return type of our instructions somewhere in order to be able to implement the interpreter. So in this case we use a phantom type to carry that information over. Thus, the IOEffect algebraic data type is what is known as a Generalised Algebraic Data type (GADT).

We got it. Now we can express the impure “sayWhat” program in a pure fashion as follows:

def pureSayWhat: IOProgram[String] = Read

As simple as that. But things become more complicated when we try to update our interpreter:

def run(program: IOProgram): ??? = ...

Now our programs are parameterized so we need to change the signature a little bit; remember that the return type is stored in the program type parameter. We can use good old pattern matching to know which instruction we are dealing with (Scala’s support for pattern matching GADTs suffices in this case):

def run[A](program: IOProgram[A]): A =
  program match {
    case Write(msg) => println(msg)
    case Read => readLine
  }

The only thing left to do is reimplementing in a modular fashion our equivalent impure function. I’ll leave the complete example below:

object SayWhat {
  /* Impure program */
  def sayWhat: String = readLine

  /* Functional solution */
  object Fun {
    // Language
    type IOProgram[A] = IOEffect[A]

    sealed trait IOEffect[A]
    case class Write(msg: String) extends IOEffect[Unit]
    case object Read extends IOEffect[String]

    // Pure Program
    def pureSayWhat: IOProgram[String] = Read

    // Interpreter
    def run[A](program: IOProgram[A]): A =
      program match {
        case Write(msg) => println(msg)
        case Read => readLine
      }

    // Composition
    def sayWhat: String = run(pureSayWhat)
  }
}

Say What? (reloaded)

We’ll start now building programs with more than one instruction. In this case we are going to print something to the console and then read the user’s input.

Impure program

def helloSayWhat: String = {
  println("Hello, say something:")
  readLine
}

As you can see, this is a common imperative program which can be read out aloud as follows: “first, do this; next, do this”.

Pure function and language

So far, our program definition has been just a type alias of a single instruction, but now we want our programs to be able to represent two-instructions programs as well. It turns out our program definition must be also an ADT:

sealed trait IOProgram[A]
case class Single[A](e: IOEffect[A]) extends IOProgram[A]
case class Sequence[A, B](e1: IOProgram[A], e2: IOProgram[B]) extends IOProgram[B]

def pureHelloSayWhat: IOProgram[String] =
  Sequence(
    Single(Write("Hello, say something:")),
    Single(Read))

As you can see, our programs can now be made up of just a Single instruction or a Sequence of two programs.

Interpreter

We must now change the interpreter accordingly. In particular, we need two interpreters, one for programs and one for effects:

def run[A](program: IOProgram[A]): A =
  program match {
    case Single(e) => runEffect(e)
    case Sequence(p1, p2) =>
      runProgram(p1) ; runProgram(p2)
  }

def runEffect[A](effect: IOEffect[A]): A =
  effect match {
    case Write(msg) => println(msg)
    case Read => readLine
  }

Composition

The only thing left is to rewrite the impure program in a modular fashion:

def sayWhat: String = run(pureHelloSayWhat)

Echo, echo!

In our next program we’ll complicate the control flow a little bit.

Impure program

def echo: Unit = {
  val read: String = readLine
  println(read)
}

Note that the println instruction is writing the result of the read operation. This is a behaviour we can’t describe with our program representation yet. The problem is that the Sequence case doesn’t allow us to use the result of the first program. We thus need somehow to represent context-dependent programs, i.e. programs that depend on the results of previous ones. Let’s fix that.

Pure function and language

sealed trait IOProgram[A]
case class Single[A](e: IOEffect[A]) extends IOProgram[A]
case class Sequence[A, B](e1: IOProgram[A],
  e2: A => IOProgram[B]) extends IOProgram[B]

def pureEcho: IOProgram[Unit] =
  Sequence(
    Single(Read), read =>
    Single(Write(read)) )

As simple as that, the new version of Sequence carries as its second parameter a program that is allowed to depend on a value of type A, i.e. the type of values returned when the first program is interpreted. Of course, the intention is that the interpreter will apply this function to that precise value, as will be shown in the next section. By the way, does the signature of the new version of Sequence ring a bell?

Interpreter

As commented previously, the new version of the interpreter will simply need to modify the way in which sequenced programs are executed:

def runProgram[A](program: IOProgram[A]): A =
  program match {
    case Single(e) => runEffect(e)
    case Sequence(p, next) =>
      val res = runProgram(p)
      runProgram(next(res))
  }

Composition

The last thing to do is to reimplement the impure function in a modular way by applying the interpreter to the result of the pure function.

def echo: Unit = runProgram(pureEcho)

On pure values

There are still some impure IO programs we can’t represent with our current IOProgram ADT. In particular, think of imperative programs structured as follows: “Do this program; then, do this other program, possible taking into account the result of the last program; etc.; finally, return this value, possible taking into account the results of the last steps.”. It’s the last step which can’t be represented. For instance, let’s consider the following program.

Impure program

def echo(): String = {
  val read: String = readLine
  println(read)
  read
}

This program is similar to the last one, but this time we return the String read, i.e., a pure value. So let’s add this new functionality to our ADT.

Pure function and language

sealed trait IOProgram[A]
case class Single[A](e: IOEffect[A]) extends IOProgram[A]
case class Sequence[A, B](e1: IOProgram[A],
  e2: A => IOProgram[B]) extends IOProgram[B]
case class Value[A](a: A) extends IOProgram[A]

def pureEcho: IOProgram[String] =
  Sequence(
    Single(Read), read =>
      Sequence(
        Write(read), _ =>
          Value(read)))

This is the final form of our ADT, whereby a program can be one of three:

  • Single: A single instruction.
  • Sequence: A sequence of context-dependent programs.
  • Value: A pure value (e.g. a String, Int, MyFancyClass, etc.)

Interpreter

In order to update the interpreter, we just have to deal with our new type of IO programs.

def runProgram[A](program: IOProgram[A]): A =
  program match {
    case Single(e) => runEffect(e)
    case Sequence(p, next) =>
      val res = runProgram(p)
      runProgram(next(res))
    case Value(a) => a
  }

As you can see, this interpretation is fairly easy: a program Value(a) just means “returns a”, which is what our interpreter does.

Composition

Last, we compose interpreter and pure function as usual to obtain a modular version of the original impure program:

def echo: String = runProgram(pureEcho)

Conclusion

This post aimed at showing that no matter how complex you impure programs are, you can always design a DSL to represent those programs in a purely declarative way. In our case, the DSL for building IO programs we ended up with is pretty expressive. In fact, we can represent any kind of imperative control flow with it. Try it!

There are, however, two major flaws we have still to deal with. First, we have to admit that the readability of programs written in the final IOProgram DSL is … poor, to say the least. Second, there is a lot of boilerplate involved in the design of the IOProgram type. Indeed, no matter the type of DSL we are dealing with (based on IO instructions, File system operations, Web service calls, etc.), if we need imperative features, we will need to copy & paste the same Sequence and Value cases. We leave the solution to these problems for the next and last post of this series!

Edit: All code from this post can be found here.

Posted in Embedded DSLs, functional programming, Scala | 1 Comment

Lens, State Is Your Father

In our last post, we introduced IOCoalgebras as an alternative way of representing coalgebras from an algebraic viewpoint, where Lens was used as a guiding example. In fact, lens is an abstraction that belongs to the group of Optics, a great source of fascinating machines. We encourage you to watch this nice introduction to optics because we’ll show more optic examples under the IOCoalgebra perspective. While doing so, we’ll find out that this new representation let us identify and clarify some connections between optics and State. Finally, those connections will be analyzed in a real-world setting, specifically, in the state module from Monocle. Let us not waste time, there is plenty of work to do!

(*) All the encodings associated to this post have been collected here, where the same sectioning structure is followed.

Optics as Coalgebras

First of all, let’s recall the IOCoalgebra type constructor:

type IOCoalgebra[IOAlg[_[_]], Step[_, _], S] = IOAlg[Step[S, ?]]

As you can see, it receives three type arguments: the object algebra interface, the state-based action or step, and the state type. Once provided, coalgebras are defined as a state-based interpretation of the specified algebra. Take Lens as an example of IOCoalgebra:

trait LensAlg[A, P[_]] {
  def get: P[A]
  def set(a: A): P[Unit]
}

type IOLens[S, A] = IOCoalgebra[LensAlg[A, ?[_]], State, S]

(*) This is a simple Lens, in opposition to a polymorphic one. We will only consider simple optics for the rest of the article.

If we expand IOLens[S, A], we get LensAlg[A, State[S, ?]], which is a perfectly valid representation for lenses as demonstrated by the following isomorphism:

def lensIso[S, A] = new (Lens[S, A] <=> IOLens[S, A]) {

  def from: IOLens[S, A] => Lens[S, A] =
    ioln => Lens[S, A](ioln.get.eval)(a => ioln.set(a).exec)

  def to: Lens[S, A] => IOLens[S, A] = ln => new IOLens[S, A] {
    def get: State[S, A] = State.gets(ln.get)
    def set(a: A): State[S, Unit] = State.modify(ln.set(a))
  }
}

We’ll see more details about lenses in later sections but, for now let’s keep diving through other optics, starting with Optional:

trait OptionalAlg[A, P[_]] {
  def getOption: P[Option[A]]
  def set(a: A): P[Unit]
}

type IOOptional[S, A] = IOCoalgebra[OptionalAlg[A, ?[_]], State, S]

This optic just replaces IOLens’ get with getOption, stating that it’s not always possible to return the inner value, and thence the resulting Option[A]. As far as we are concerned, there aren’t more significant changes, given that State is used as step as well. Thereby, we can move on to Setters:

trait SetterAlg[A, P[_]] {
  def modify(f: A => A): P[Unit]
}

type IOSetter[S, A] = IOCoalgebra[SetterAlg[A, ?[_]], State, S]

In fact, this is a kind of relaxed lens that has lost the ability to “get” the focus, but is still able to update it. Notice that set can be automatically derived in terms of modify. Again, State is perfectly fine to model the step associated to this optic. Finally, there is Getter:

trait GetterAlg[A, P[_]] {
  def get: P[A]
}

type IOGetter[S, A] = IOCoalgebra[GetterAlg[A, ?[_]], Reader, S]

This new optic is pretty much like a lens where the set method has been taken off, and it only remains get. Although we could use State to represent the state-based action, we’ll take another path here. Since there isn’t a real state in the background that we need to thread, ie. we can only “get” the inner value, Reader could be used as step instead. As an additional observation, realize that LensAlg could have been implemented as a combination of GetterAlg and SetterAlg.

There are still more optics in the wild, such as Fold and Traversal, but we’re currently working on their corresponding IOCoalgebra representation. However, the ones that have already been shown are good enough to establish some relations between optics and the state monad.

Optics and State Connections

Dealing with lenses and dealing with state feels like doing very similar things. In both settings there is a state that could be queried and updated. However, if we want to go deeper with this connection, we need to compare apples to apples. So, what’s the algebra for State? Indeed, this algebra is very well known, it’s named MonadState:

trait MonadState[F[_], S] extends Monad[F] {
  def get: F[S]
  def put(s: S): F[Unit]

  def gets[A](f: S => A): F[A] = 
    map(get)(f)

  def modify(f: S => S): F[Unit] = 
    bind(get)(f andThen put)
}

This MonadState version is a simplification of what we may find in a library such as scalaz or cats. The algebra is parametrized with two types: the state-based action F and the state S itself. If we look inside the typeclass, we find two abstract methods: get to obtain the current state and put to overwrite it, given a new one passed as argument. Those abstract methods, in combination with the fact that MonadState inherits Monad, let us implement gets and modify as derived methods. This sounds familiar, doesn’t it? It’s just the lens algebra along with the program examples that we used in our last post! Putting it all together:

trait LensAlg[A, P[_]] {
  def get: P[A]
  def set(a: A): P[Unit]

  def gets[B](
      f: A => B)(implicit
      F: Functor[P]): P[B] =
    get map f

  def modify(
      f: A => A)(implicit
      M: Monad[P]): P[Unit] =
    get >>= (f andThen set)
}

(*) Notice that we could have had LensAlg extending Monad as well, but this decoupling seems nicer to us, since each program requires only the exact level of power to proceed. For instance, Functor is powerful enough to implement gets, so no Monad evidence is needed.

Apparently, the only difference among LensAlg and MonadState lies in the way we use the additional type parameter. On the one hand, LensAlg has a type parameter A, which we understand as the focus or inner state contextualized within an outer state. On the other hand, we tend to think of MonadState‘s S parameter as the unique global state where focus is put. Thereby, types instantiating this typeclass usually make reference to that type parameter, as one could appreciate in the State instance for MonadState. However, we could avoid that common practice and use a different type as companion. In fact, by applying this idea in the previous instance, we get a new lens representation:

type MSLens[S, A] = MonadState[State[S, ?], A]

(*) The isomorphism between IOLens and MSLens is almost trivial, given the similarities among their algebras. Indeed, you can check it here.

Lastly, we can’t forget about one of the most essential elements conforming an algebra: its laws. MonadState laws are fairly known in the functional programming community. However, the laws associated to our LensAlg aren’t clear. Luckily, we don’t have to start this work from scratch, since lens laws are a good starting point. Despite the similarity between both packages of laws (look at their names!) we have still to formalize this connection. Probably, this task will shed even more light on this section.

Monocle and State

Connections between optics and state have already been identified. Proof of this can be found in Monocle, the most popular Scala optic library nowadays, which includes a state module containing facilities to combine some optics with State. What follows is a simplification (removes polymorphic stuff) of the class that provides conversions from lens actions to state ones:

class StateLensOps[S, A](lens: Lens[S, A]) {
  def toState: State[S, A] = ...
  def mod(f: A => A): State[S, A] = ...
  def assign(a: A): State[S, A] = ...
  ...
}

For instance, mod is a shortcut for applying lens.modify over the standing outer state and returning the resulting inner value. The next snippet, extracted from Monocle (type annotations were added for clarity), shows this method in action:

case class Person(name: String, age: Int)
val _age: Lens[Person, Int] = GenLens[Person](_.age)
val p: Person = Person("John", 30)

test("mod") {
  val increment: State[Person, Int] = _age mod (_ + 1)

  increment.run(p) shouldEqual ((Person("John", 31), 31))
}

That said, how can we harness from our optic representation to analyze this module? Well, first of all, it would be nice to carry out the same exercise from the IOLens perspective:

case class Person(name: String, age: Int)
val _ioage: IOLens[Person, Int] =
  IOLens(_.age)(age => _.copy(age = age))
val p: Person = Person("John", 30)

test("mod") {
  val increment: State[Person, Int] = 
    (_ioage modify (_ + 1)) >> (_ioage get)

  increment.run(p) shouldEqual ((Person("John", 31), 31))
}

Leaving aside the different types returned by _age mod (_ + 1) and _ioage modify (_ + 1), we could say that both instructions are pretty much the same. However, mod is an action located in an external state module while modify is just a primitive belonging to IOLens. Is this a mere coincidence? To answer this question, we have formalized this kind of connections in a table:

Monocle State-Lens Action IOLens Action Return Type
toState get State[S, A]
? set(a: A) State[S, Unit]
? gets(f: A ⇒ B) State[S, B]
? modify(f: A ⇒ A) State[S, Unit]
mod(f: A ⇒ A) ? State[S, A]
modo(f: A ⇒ A) ? State[S, A]
assign(a: A) ? State[S, A]
assigno(a: A) ? State[S, A]

What this table tells us is how the actions correspond to each other. For instance, the first raw shows that toState (from Monocle) corresponds directly with get (from our IOLens), both generating a program whose type is State[S, A]. The second raw contains a new element ?, which informs us that there’s no corresponding action for set in Monocle. Given the multitude of gaps in the table, we could determine that we’re dealing with such different stuff, but if you squint your eyes, it’s not hard to appreciate that mod(o) and assign(o) are very close to modify and set, respectively. In fact, as we saw while defining increment, mod is just a combination of get and modify. So, it seems to exist a strong connection between the IOLens primitives and the actions that could be placed in the state module for lenses. The obvious question to be asked now is: Is there such a connection between the state module and other optics? In fact, Monocle also provides facilities to combine State and Optionals, so we can create the same table for it:

Monocle State-Optional Action IOOptional Action Return Type
toState getOption State[S, Option[A]]
? set(a: A) State[S, Unit]
? gets(f: A ⇒ B) State[S, Option[B]]
? modify(f: A ⇒ A) State[S, Unit]
modo(f: A ⇒ A) ? State[S, Option[A]]
assigno(a: A) ? State[S, Option[A]]

Again, the results are very similar to the ones we extracted from IOLens. In fact, we claim that any IOCoalgebra-based optic which can be interpreted into State may contain a representative in the state module, and the actions that the module may include for each of them are just its associated primitives and derived methods. But, what about Getters, where both State and Reader are suitable instances? Well, the State part is clear, we can add a new representative for Getter in the state module. However, the interesting insight comes with Reader: identifying new interpretations means identifying new modules. In this sense, we could consider including a new module reader in the library. Obviously, we could fulfill that module by following the same ideas that we showed for state.

To sum up, by following this approach, we have obtained a framework to systematically determine:

  • The appropriateness of including a new module.
  • The optics that it may support.
  • The methods it may contain for every optic.

This is a nice help, isn’t it?

Discussion and Ongoing Work

Today, we have seen that IOCoalgebras served us two purposes, both of them involving understandability. First of all, we have identified an unexpected connection between Lens and the State Monad. In fact, we have defined Lens in terms of MonadState, so we had to explain Lens who was his biological father, and that was tough for her! Secondly, we have described a systematic process to create and fulfill Monocle’s peripheral modules, such as state. In this sense, if we go one step further, we could think of those peripheral modules as particular interpretations of our optic algebras. This perspective makes the aforementioned process entirely dispensable, since optic instances would replace the module itself. As a result, logic wouldn’t end up being contaminated with new names such as assign or mod, when all they really mean is set and modify, respectively.

As we mentioned before, we still have to translate other optics into their corresponding IOCoalgebra representation and identify the laws associated to the algebras. Besides, we focused on simple optics, but we should contemplate the polymorphic nature of optics to analyze its implications in the global picture. Anyway, optics are just a source of very low-level machines that conform one of the first steps in the pursue of our general objective, which is programming larger machines, ie. reactive systems, by combining smaller ones. It’s precisely within this context where our optics, in combination with many other machines from here and there, should shine. In this sense, there’s still a lot of work to do, but at least we could see that isolating algebras from state concerns has turned out to be a nice design pattern.

Posted in algebra, coalgebra, Lens, Optics, State, Type Class | Leave a comment

Yo Dawg, We Put an Algebra in Your Coalgebra

As Dan Piponi suggested in Cofree Meets Free, we may think of coalgebraic things as machines with buttons. In this post, we take this metaphor seriously and show how we can use algebras to model the Input/Output interface of the machine, i.e. its buttons. Prior to that, we’ll make a brief introduction on coalgebras as they are usually shown, namely as F-coalgebras.

What are F-coalgebras?

F-coalgebra (or functor-coalgebra) is just a reversed version of the more popular concept of F-algebra, both of them belonging to the mystical world of Category Theory. The most widespread representation of an F-algebra is

type Algebra[F[_], X] = F[X] => X

(using Scala here) Paraphrasing Bartosz Milewski, “It always amazes me how much you can do with so little”. I believe that its dual counterpart

type Coalgebra[F[_], X] = X => F[X]

deserves the very same amazingness, so today we’ll put focus on them.

Given the previous representation, we notice that F-coalgebras are composed of a carrier X, a functor F[_] and a structure X => F[X] itself. What can we do with such a thing? Since we are just software developer muggles (vs matemagicians), we need familiar abstractions to deal with coalgebras. Therefore, we like to think of them as machines with buttons, which know how to forward a particular state (maybe requiring some input) to the next one (maybe attaching some output along) by pressing the aforementioned buttons. Now, let’s find out some examples of mainstream machines that we, as functional programmers, already know:

// Generator Machine (Streams)
type GeneratorF[A, S] = (A, S)
type Generator[A, S]  = Coalgebra[GeneratorF[A, ?], S]

// Mealy Automata Machine
type AutomataF[I, S] = I => (Boolean, S)
type Automata[I, S]  = Coalgebra[AutomataF[I, ?], S]

// Lens Machine
type LensF[A, S] = (A, A => S)
type Lens[A, S]  = Coalgebra[LensF[A, ?], S]

Firstly, let’s expand Generator[A, S] into S => (A, S) which is something easier to deal with. Indeed, it’s just a function that, given an initial state S, it returns both the head A and the tail S associated to that original state. It’s the simplest specification of a generator machine that one could find! Given a concrete specification and once provided an initial state, we could build a standard Stream of As.

Secondly, we showed a Mealy Automata. Again, let’s turn Automata[I, S] into S => I => (Boolean, S) to see it clearer: given the current state S and any input I we can determine both the finality Boolean condition and the new state S.

Finally, we saw Lens. Notice that the type parameters are reversed if we compare this lens with the “official” representation (eg. lens, Monocle, etc.). This is just to provide homogeneity with the rest of machines, where the state S is kept as the last parameter. As usual, let’s expand Lens[A, S] to obtain S => (A, A => S). This tell us that given an initial state S, we could either get the smaller piece A or set the whole state with a brand new A.

So far, we have seen the typical representation for some prominent coalgebras. On the other hand, we claimed that we like to think of those coalgebras as machines with buttons that let us make them work. That machine abstraction seems nice, but I agree it’s difficult to see those buttons right now. So, let’s find them!

Coalgebras as machines? Then, show me the buttons!

As promised, we’ll dive into F-coalgebras to find some buttons. I anticipate that those buttons are kind of special, since they could require some input in order to be pressed and they could return some output after that action. We’re going to use Lens as a guiding example but we’ll show the final derivation for our three machines at the end as well. So, we start from this representation:

type Lens[A, S] = S => (A, (A => S))

If we apply basic math, we can split this representation into a tuple, getting an isomorphic one:

type Lens[A, S] = (S => A, S => A => S)

Trust me when I say that every element in this tuple corresponds with an input-output button, but we still have to make them uniform. First of all, we’re going to flip the function at the second position, so the input for that button stays in the left hand side:

type Lens[A, S] = (S => A, A => S => S)

Our button at the first position has no input, but we can create an artificial one to make the input slot uniform:

type Lens[A, S] = (Unit => S => A, A => S => S)

Once provided the input for the buttons, we reach different situations. On the first button there is S => A which is a kind of observation where the state remains as is. However, in the second button, there is S => S which is clearly a state transformation with no output attached to it. If we return the original state along with the observed output in the first button and provide an artificial output for the second one, we get our uniform buttons, both with an input, an output and the resulting state.

type Lens[A, S] = (Unit => S => (S, A), A => S => (S, Unit))

If we squint a bit, we can find an old good friend hidden in the right hand side of our buttons, the State monad, leading us to a new representation where both tuple elements are Kleisli arrows:

type Lens[A, S] = (Unit => State[S, A], A => State[S, Unit])

Finally, we can achieve a final step, aiming at both naming the buttons and being closer to an object-oriented mindset:

trait Lens[A, S] {
  def get(): State[S, A]
  def set(a: A): State[S, Unit]
}

So here we are! We have turned an F-coalgebra into a trait that represents a machine where buttons (get & set) are certainly determined. Obviously, pressing a button is synonym for invoking a method belonging to that machine. The returning value represents the state transformation that we must apply over the current state to make it advance. If we apply the same derivation to streams and automata we get similar representations:

trait Generator[A, S] {
  def head(): State[S, A]
  def tail(): State[S, Unit]
}

trait Automata[I, S] {
  def next(i: I): State[S, Boolean]
}

We’re glad we found our buttons, so we can reinforce the machine intuition, but stranger things have happened along the way… The coalgebraic Upside Down world is not quite far from the algebraic one.

Buttons are Algebras

In the previous section we made a derivation from the Lens F-coalgebra to a trait Lens where buttons are made explicit. However, that representation was mixing state and input-output concerns. If we go a step further, we can decouple both aspects by abstracting the state away from the specification, to obtain:

trait LensAlg[A, P[_]] {
  def get(): P[A]
  def set(a: A): P[Unit]
}

type Lens[A, S] = LensAlg[A, State[S, ?]]

So, lenses can be understood as a state-based interpretation of a particular Input/Output algebra. We can distinguish in this kind of specification between two components: the IO interface and the state transition component. Why would we want to define our lenses, or any other coalgebra, in this way? One advantage is that, once we get this representation, where input-output buttons are completely isolated, we can make machine programs that are completely decoupled from the state component, and just depend on the input-output interface. Take modify, a standard lens method, as an example:

def modify[A, P[_]](
    f: A => A)(implicit
    P: LensAlg[A, P],
    M: Monad[P]): P[Unit] =
  P.get >>= (P.set compose f)

Notice that although modify constrains P to be monadic, this restriction could be different in other scenarios, as we can see with gets, where Functor is powerful enough to fulfil the programmer needs:

def gets[A, B, P[_]](
    f: A => B)(implicit
    P: LensAlg[A, P],
    F: Functor[P]): P[B] =
  P.get map f

These programs are absolutely declarative since nothing has been said about P[_] yet, except for the fundamental constraints. Indeed, this way of programming should be pretty familiar for a functional programmer: the step that abstracted the state away led us to a (Higher Kinded) object-algebra interface, which is just an alternative way of representing algebras (as F-algebras are).

Ongoing Work

We started this post talking about F-coalgebras, type Coalgebra[F[_], X] = X => F[X], and then we turned our lens coalgebra example into a new representation where buttons and state transformation concerns are clearly identified (rather than being hidden into the functor ‘F’). Indeed, we may tentatively put forward IO-coalgebras as a particular class of coalgebras, and define lenses as follows:

type IOCoalgebra[IOAlg[_[_]], Step[_, _], S] = IOAlg[Step[S, ?]]
type Lens[A, S] = IOCoalgebra[LensAlg[A, ?], State, S]

As we said in the previous section, this representation empowers us to use the existing algebraic knowledge to deal with coalgebras. So, although we started our journey aiming at the specification of machines, we were brought back to the algebraic world! So, which is the connection between both worlds? In principle, what we suggest is that coalgebras might be viewed as state-based interpretations of algebras. Now, whether any F-Coalgebra can be represented as an IO-Coalgebra is something that has to be shown. And, additionally, we should also identify the constraints in the IOCoalgebra definition that allows us to prove that the resulting formula is actually a coalgebra.

On future posts, we’ll be talking about cofree coalgebras as universal machines. As we will see, those cofree machines exploit the button intuition to simulate any other machine in different contexts. By now, we’d be really grateful to receive any kind of feedback to discuss the proposed connection between languages and machines. Hope you enjoyed reading!

Posted in algebra, coalgebra, Embedded DSLs, machine, Scala, Type Class | 2 Comments