Effects

Effects

Any program that does anything useful has some side-effect. Well, the whole point of a program is to have some side-effect. Examples of side-effects are reading from console, writing to db, request over the network, etc. A pure function however, does not cause any side-effects. So how do we then make a program that does anything useful pure?

Referential Transparency

The foundation of functional programming is Referential Transparency. By referential transparency we can replace the result of a function with its definition. If we take an effectful function such as,

def addHits(hits: Int): Int // adds 'hits' to counter, returns new value.

val h = addHits(10) 
h + h  

// is not the same as

addHits(10) + addHits(10)

Effects are not referentially transparent by default.

What about Futures?

At present, the most common way of dealing with async computations(including side-effects) is through Futures. However, Futures aren’t pure. Futures are eager and memoize the result.

 
val fut = Future { addHits(10) }

for {
  h1 <- fut
  h2 <- fut
} yield h1 + h2  // will evaluate the `fut` only once

// and is not the same as

for {
  h1 <- Future { addHits(10) }
  h2 <- Future { addHits(10) }
} yield h1 + h2

breaking referential transparency.

The Effect Type

The key technique to convert an impure program to a pure one is to factor out the effectful code from the rest of the program(pure). Then, use pure functions to compute the description of the effectful computation and a separate interpreter to actually perform the side-effects.

trait Effect[A] {
  def run: A // interperter
}

Now, that we have seen how to satify referential transparency, lets look at some of the other requirements that the Effect Type must satisfy.

Sequentiality & Composability

In order to build programs, we should be able to compose the different effectful functions. This essentially means that we need an Effect Monad.

trait Effect[A] {
  def run: A // interperter

  def pure[A](a: A): Effect[A]
  def flatMap[B](eff: Effect[A])(a: A => Effect[B]): Effect[B]
}

Stack Safety

Most of the programs that we run, run indefinitely, however, the stack space is limited. A simple recursive function such as

def forever(effect: Effect[Unit]): Effect[Unit] = 
  flatMap(effect)(_ => forever(effect))

causes the interpreter to run out of stack space in sometime.

In order to ensure stack safety, the control flow of the execution is baked into data types viz.,

case class Pure[A](a: A) extends Effect[A]
// wraps an already available value into an Effect
case class Suspend[A](resume: () => A) extends Effect[A]
// execute an effect to produce a value
case class FlatMap[A](sub: Effect[A], f: A => Effect[B]) extends Effect[B]
// extend an effect by combining with another effect

Now, the interpreter handle these types such that it remains tail recursive.

def run[A](eff: Effect[A]): A = eff match {
  case Pure(a) => a
  case Suspend(s) => s()
  case FlatMap(x, f) => x match {
	case Pure(a) => run(f(a))
	case Suspend(s) => run(f(s()))
	case FlatMap(y, g) => run(y flatMap (a => FlatMap(g(a), f)))
  }
}

In eff.flatMap(f), f is not executed immediately, but instead returns one of Pure, Suspend, FlatMap, returning control back to run. Thus by making the FlatMap a trampolined exection (control jumps into FlatMap and exits immediately to run), the interpreter remains tail-recursive.

Abstracting Over Effects

When you have effectful functions in a program it is possible to abstract over the Effect type and provide only the description of the program while adding the interpretation of those functions using a specific Effect later. This is possible through Free Monads or Tagless Final.

Free Monad approach uses Free structures from Category Theory

case class State(value: AtomicInteger)

sealed trait CalculatorInstruction[A]
case class Add(x: Int) extends CalculatorInstruction[Unit]
case class Get() extends CalculatorInstruction[State]

class Calculator {
  def add(x: Int): CalculatorProgram[Unit] = Free.liftF(Add(x))
  def get: CalculatorProgram[State] = Free.liftF(Get())
}

class CalculatorFutureInterpreter(state: State) {
  val interpreter = new (CalculatorInstruction ~> Future) {
    override def apply[A](fa: CalculatorInstruction[A]): Future[A] = fa match {
      case Add(x) => Future.successful{state.value.addAndGet(x); ()}
      case Get() => Future.successful(state)
    }
  }
}

object FreeMonad extends App {
  type CalculatorProgram[A] = Free[CalculatorInstruction, A]

  val calculator = new Calculator()

  val program: Free[CalculatorInstruction, Int] = for {
    _ <- calculator.add(10)
    result <- calculator.get
  } yield result.value.get()

  val response = program.foldMap(new CalculatorFutureInterpreter(State(new AtomicInteger(0))).interpreter)
}

Tagless Final approach uses plain inheritance to provide a specific side-effect implementation.

 
case class State(value: AtomicInteger)

trait Calculator[F[_]] {
  def add(x: Int): F[Unit]
  def get: F[State]
}

class CalculatorFutureInterpreter(state: State) extends Calculator[Future] {
  override def add(x: Int): Future[Unit] = Future.successful { state.value.addAndGet(x) }
  override def get: Future[State] = Future.successful(state)
}

object TaglessFinal extends App {
  val state = State(new AtomicInteger(0))
  val interpreter = new CalculatorFutureInterpreter(state)

  val program: Future[Int] = for {
    _ <- interpreter.add(10)
    result <- interpreter.get
  } yield result.value.get()
}

In this way it is possible to seperate the description of the program from the interpretation of side-effects. Another key use is that it is possible to provide different interpretation(using different Effect types) for various environments. Eg: for production we can provide the Async Effect intepreter whereas for test we are happy with an Id Effect.

Summary

Pure functions are preferred by everyone because they are much easier to reason. However, it is impossible to write meaninful programs that do not interact with external systems at the least. We have seen how to handle external effects in a purely functional way. There are a couple of libraries that provide ways to deal with Effects, the major ones being Cats and Scalaz. Both provide a lot of typeclasses to encapsulate side-effects. Also there is Monix-Task that provides lazy and asynchronous computation as a pure replacement of Futures.