Oct
26th
Sat
permalink
permalink
Feb
5th
Tue
permalink
Sep
17th
Mon
permalink
Sep
5th
Wed
permalink

Applicatives are too restrictive, breaking Applicatives and introducing Functional Builders

This post aims to document a practical design implementation we came up with when designing some APIs in Scala. Of course the concept is not Scala specific and applies to other functional languages.

If you don’t want to go into the full introduction, this post talks about how Applicatives are too restrictive and breaking them into two independent components can be interesting for Contravariant and Invariant Functors. Jump to implementation attached.

We are taking JSON serialization/deserialization as a motivating example.

JsValue is the name of the type that represents the JSON AST. What we need is to be able to read a JsValue and produce an A:

trait Reads[A]{

  def reads(json:JsValue):JsResult[A]

}

Implementing Reads interface provides a way to deserialize a JSON value into an A (and here giving you an opportunity to fail with JsError which is a valid JsResult).

Writing JSON we have its dual:

trait Writes[A]{

  def writes(a:A):JsValue

}

Implementing Writes provides a way to write JSON for a type A.

We have also a type that represents both, being able to read and write a JSON for an A type:

trait Format[A] extends Reads[A] with Writes[A]

Reads happens to be a monad, which is interesting but we are not going to talk about this much more. What we are interested in is having a simple way of combining JSON serializers, meaning if we have

val readAge: Reads[Int]
val readName: Reads[String]

it could be very interesting to have a Reads[(Int,String)] or even better, a Reads[User] having for instance case class User(age:Int, name:String)

This is actually quite easy to achieve with Applicative Functors. To simplify, Applicative Functors are Functors (having the map or fmap function implemented) together with the Applicative part which adds the power we need to achieve the combination we want to do. Explaining Applicative Functors is out of scope and there is a lot of material on the web explaining these.

val readUser: Reads[User] = readAge.and(readName).apply(User)

// or using symbolic methods:

val readUser: Reads[User] = (readAge ~ readName).apply(User)

This composition simply means that if we have two readers of two different types, they could read from the same JSON and provide two values which I can pack into another type (User here).

Now that we solved our problem of combining the Reads with Applicative Functors, wouldn’t it be even more interesting if we could combine similarly the Writes? Having:

val writeAge: Writes[Int]
val writeName: Writes[String]

then we could have a Writes[User], or can we?

Almost. If we have two writers (capable of writing two different JsValue from two different types, Int and String here) then we end up with two JsValues, and there is no way of merging these into one, except if they are both JsObjects.

Let’s do a new type that only writes JsObject

trait OWrites[A] extends Writes[A]{

  def writes(a:A):JsObject

}

Now it makes sense to have one writer out of our two writes above ( writeAge, writeName) by simply merging the resulting objects. So logically it makes sense, except that we can’t use our Applicative based builder since an OWrites is not a Functor at all!

Actually our OWrite is, naturally, the dual of a Functor, a CoFunctor (or Contravariant). Put simply, this means that to change the A type to B in OWrites we should provide a function backwards from B => A. This makes a lot of sense since if we know how to write an A and we know how to transform a B to A then we can write a B. Instead of fmap we got a contramap

def contramap[B](B => A):OWrite[B]

So or status here, we know how to transform the type of OWrites, we know how to merge two OWrites but all of that doesn’t help us to use the builder which based on an Applicative Functor.

What if we split our problem into two components. Let’s introduce a new type that we call FunctionalCanBuild:

trait FunctionalCanBuild[M[_]]{

  def apply[A,B](ma:M[A],mb:M[B]):M[(A,B)]

}

Meaning for a given container M, we can some how compose two instances into one with the tuple of the type parameters. So for Reads it will be:

val fpReads = new FunctionalCanBuild[Reads]{

  // read the same value using the two readers and return a tuple
  def apply[A,B](ra:Reads[A],rb:Reads[B]):Reads[(A,B)] = ...

}

and for the OWrites it will make:

val fpOwrites = new FunctionalCanBuild[OWrites]{

  /* write two objects using the two writers
  and merge the two resulting JsObjects */
  def apply[A,B](oa:OWrites[A],ob:OWrites[B]):OWrites[(A,B)] = ...

}

But that gets us only half way through what we want to achieve. What we want is actually a Reads and OWrites of User and not tuple of Int, String.

For the Reads[(Int,String)] we can solve this problem easily using the fmap function of Functor. But even for OWrites[(Int,String)] it is easy, OWrites is a CoFunctor (or ContraVariant) and we can use contramap to get back from (Int,String) to User.

So it seems that separating the problem into two sub problems is working for us. But what about format? Format is not a Functor and a Contra, it is actually Invariant. This means that it need functions in both directions, A => B and B => A to transform the A type to B.

Like the OWrites we will use OFormat:

trait OFormat[A] extends OWrites[A] with Reads[A]

Now we can implement FunctionalCanBuild[OFormat] :

val fbf: FunctionalCanBuild[OFormat] = new FunctionalCanBuild[OFormat]{

  // merge reads and writes
  def apply[A,B](fa: OFormat[A], fb: OFormat[B]): OFormat[(A,B)] = ...

}

and once we have the OFormat[(Int,String)] we can transform it to a User by using inmap and passing (Int,String) => User and User => (Int,String).

This led us to an API that is capable of building compositions for Functors (Reads), CoFunctors (Writes) and Invariant (Format). Using the FunctionBuilder type class and the correct Variance we can offer a nice unified API for composing different abstractions.

Bottom Line: By breaking Applicatives into two independent components (FunctionalCanBuild and Variance we could use them for more than Functors, ie Covariant and Invariant Functors.

ps: FunctionalCanBuild[M[_]] may look like a monoid but it is not exactly one.

ps2: This is a work I did together with @mandubian and other Zenexity guys

ps3: The Format,Reads and Writes approach is copied and adapted from @debasishg on sjson

ps4: This work is integrated into Play’s included JSON library

ps5: A potentially more readable version as a gist

Jul
9th
Mon
permalink
Jul
8th
Sun
permalink

Is socket.push(bytes) all what you need to program Realtime Web apps?

One of the goals of Play2 architecture is to provide a programming model for what is called Realtime Web Applications.

Realtime Web Applications

Realtime Web Applications are applications making use of Websockets, Server Sent Events, Comet or other protocols offering/simulating an open socket between the browser and the server for continuous communication. Basically, these applications offer to users delivery of information as it is published without having the user periodically pinging the service.

There are quite a few web frameworks that target the development of this type of applications. Mostly, however, the solution is by providing an API that allows developers to push/receive messages from/to an open channel, something like:

channel.push(message)
//and
channel.onMessage { ... }

Though this kind of API offers an opportunity to get started doing Realtime Web, it doesn’t offer a programming model for dealing with the challenges encountered when programming with streams of data, including creating, adapting, manipulating, filtering and merging streams of data and all of the synchronization involved.

A Programming Model

Since development of Realtime Web Apps is mostly built around manipulation of streams of data, it is crucial to have a programming model which identifies clearly what a stream of data is and defines composable components to deal with it.

It is obvious that the above channel api falls short when manipulating a rich set of streams of data, but even the classic InputStream/OutputStreams interfaces are not sufficient. Forgetting about their inefficient blocking runtime properties, they don’t carry enough signals/information to allow building rich stream manipulation api.

Play2 uses Iteratees together with Futures for dealing with streams of data, providing a very rich model for programming rich Realtime Web Applications.

A sample Realtime Web App

The goal of this text isn’t to provide a detailed description of what Iteratees and pals are. Nevertheless I will go into a fast introduction and then move into an example illustrating few aspects of how powerful this approach is.

  • An Iteratee[E,A] is an immutable interface that represents a consumer, it consumes chunks of data each of type E and eventually produces a computed value of type A. Iteratee[String,Int] is an iteratee that consumes chunks of strings and eventually produces an Int (that could be for instance number of charecters in the passed chunks)

    An iteratee can choose to terminate before the EOF sent from the stream, or could wait for EOF before it terminates, returning the computed A value.

    You can compose different Iteratees together and this can be an opportunity for partitioning consuming logic into different parts.

  • An Enumerator[E] represents a stream that is pushing chunks of data of type E. An Enumerator[String] is a stream of strings. Enumerators can be composed one after the other, or interleaved concurrently providing means of streams management.

  • An Enumeratee[From,To] is an adapter from a stream of Froms to a stream of Tos. Note that an Enumeratee can rechunk differently, add or remove chunks or parts of them. Enumeratees as we will see are instrumental for stream manipulation.

  • There are convenient methods for creating different kinds of Enumerators Iteratees and Enumeratees for different scenarios.

Our sample application features two streams, one is a stream of financial operations:

val operations: Enumerator[Event] = Enumerator.generateM[Event] {
  Promise.timeout(
    Some(Operation( if(Random.nextBoolean) "public" else "private",
    Random.nextInt(1000))), Random.nextInt(500))
}

Here we are generating random values at random distances (of maximum 500ms). In the real world this stream could be coming from a datastore or an open socket with another server.

An Operation is private or public and curries an amount of type Int:

case class Operation(level: String, amout: Int) extends Event

The other stream we have is a stream of system messages, messages that talk about the status of the system:

case class SystemStatus(message: String) extends Event

val noise: Enumerator[Event] = Enumerator.generateM[Event] {
  Promise.timeout(
    Some(SystemStatus("System message")),
    Random.nextInt(5000)
  )
}

This stream can be coming from another server or datastore. With these two streams at hand, we can prooduce one single stream that contains messages of both by interleaving them:

val events: Enumerator[Event] = operations >- noise

Actually those not comfortable using symbolic operators can use interleave method:

val events: Enumerator[Event] = operations.interleave(noise)

Now the model part of our application looks like:

Our sample Realtime Web App features:

Our application will publish this stream of Event as Server Sent Event or Comet (both are protocols for uni-directional socket from the server to the browser) and will be providing two simple features:

Authorization:

You can only see Events that are allowed for your role. Managers can see private operations and system status whereas normal users can see only public operations, for this purpose we create an Enumeratee which collects appropriate messages:

def feed(role: String) = Action {

  val secure: Enumeratee[Event, Event] = 
    Enumeratee.collect[Event] {
      case e@SystemStatus(_) if role == "MANAGER" => e
      case e@Operation("private", _) if role == "MANAGER" => e
      case e@Operation("public", _) => e
    }

Filtering:

You can filter the stream by range of interest in the amount of the operation. By providing an upper and lower bounds you get only corresponding operations, for this we create another Enumeratee collecting appropriate operations:

def feed(role: String, lowerBound: Int, higherBound: Int) = Action {

  val secure: Enumeratee[Event, Event] = ...

  val inBounds: Enumeratee[Event, Event] =
    Enumeratee.collect[Event] {
      case e@Operation(_, amout) 
        if amout > lowerBound && amout < higherBound => e
      case e@SystemStatus(_) => e
    }

}

JSON:

Our App will be pushing JSON messages to the browser, that’s why we need one more Enumeratee for transforming Events to JSON values, ie, Enumeratee[Event,JsValue]:

val asJson: Enumeratee[Event, JsValue] =
  Enumeratee.map[Event] { 
    case Operation(visibility, amount) =>
      toJson(Map("type" -> toJson("operation"),
                        "amount" -> toJson(amount),
                        "visibility" -> toJson(visibility)))

    case SystemStatus(msg) =>
      toJson(Map("type" -> "status", "message" -> msg))
}

For convenience, let’s produce one single adapter out of the three we got, for that we can use the compose method or its symbolic equivalent ><>:

val finalAdpater = secure ><> inBounds ><> asJson

We’re almost done. Now all what we need is to respond to the browser with an Ok status wrapping each message into the Server Sent Event (EventSource) protocol. Actually there is already an Enumeratee which adapts a stream and wraps its chunks into the SSE protocol:

Ok.feed(Stream.events &> finalAdpater ><> EventSource())
    .as("text/event-stream")

Here we pass our stream through the finalAdapter and then through the EventSource adapter, applying then the appropriate header to the response.

Our application now looks like:

All what we need now from the client side is to connect to the stream using the following javascript:

feed = new EventSource(‘/feed?role=@role&lower=’ + min + ‘&higher=’ + max)

Snapshots of our Realtime Web App:

/manager /

Bottom Line

Realtime Web involves dealing with different streams of data from different sources. It is hard to do any non-trivial application without having a programming model that contains an appropriate representation of a stream and necessary API for creating, adapting, filtering and consuming streams of data. Play2 uses Iteratees to offer a programming model and a rich API.

Note: Full working application source was created by me @sadache and @guillaumebort for one of our talks

Note2: Probably a more readable version of this post

Note3: Examples of Realtime Web Apps using Play2 Typesafe Console lichess.org

Jul
3rd
Tue
permalink
Jul
1st
Sun
permalink
permalink

New York

(Source: flickr.com)