Sunday, January 13, 2013

From imperative to data flow to functional style

Functional style makes code more maintainable. How? One way makes processing into a flow of data with discrete steps. Another way separates flow from context, making the context swappable. This post illustrates both.

We'll go from an imperative style to a more and more functional style. Scala is a good language for this illustration, since it supports both. If you want to run this, grab the code from github and :load it in the Scala REPL.

Example: Given a filename, we extract the message from its first line:
The secret message is '...'
Watch out for files that don't exist, are empty, or don't follow the format. In any of these cases, return None. If everything looks good, we get a SecretMessage containing the quoted text from the file.
case class SecretMessage(meaning: String) 
The type of the function is:
String => Option[SecretMessage]
Note: In good old-fashioned style, this function could return null if it can't provide a result. I may be starting out imperatively, but not that dirty. Option is better: None represents no result, or Some contains a value. Either way, we get a valid object reference and no NullPointerExceptions.

Note: Since the SecretMessage is input and output as a string, we could encode it as a String. This isn't specific enough for my taste. I like my types to tell me what the thing is, not just how it is read in or output. 


Imperative

The imperative implementation is straightforward IF you like to play compiler in your head. Open the file, check whether it exists. If it does, read it; check whether it's empty. If it isn't, read the first line and then use a regex to check its format and extract the secret message. Nothing weird there, but you have to step through every line to know what the method is doing.

def imperativeStyle(filename : String)
  : Option[SecretMessage]
= {
  val file = new java.io.File(filename)
  if(!file.exists)
    None
  else {
    val source = io.Source.fromFile(file)
    if (!source.hasNext) {
      source.close
      None
    }
    else {
      val firstLine = source.getLines.next
      source.close
      val ExpectedFormat = "The secret message is '(.*)'".r
      firstLine match {
        case ExpectedFormat(secretMessage) =>
          Some(SecretMessage(secretMessage))
        case _ => None
} } } }


Data Flow

Think about what this function is trying to do. Take a filename, get a file (that exists), get its first line (if it isn't empty), extract a message (if it's in a certain format). These are three transformations, and each of them might not work. These become three methods:
def openFile(n: String) : Option[java.io.File]
def readFirstLine (f : java.io.File) : Option[String]
def parseLine(line : String) : Option[SecretMessage]
If any of these return None, then our function will return None. A Some return means processing continues.
This makes two pipelines: one where processing continues, and one where the None value is just passed along; only the type parameter changes to meet the required output of the function. This is like the gutter in a bowling alley.

Now, to implement this. The three transformation functions I've stuck in a module called transformers; it's the form of the surrounding function that's interesting. We'll walk through four refactors that make it more and more readable.

Minimally, we can change the if statements to call the transforming functions.

def useTransforms(filename: String)
  : Option[SecretMessage]
= {
  import transformers._
  val fileOption = openFile(filename)
  if (fileOption.isEmpty)
    None
  else {
    val lineOption = readFirstLine(fileOption.get)
    if (lineOption.isEmpty)
      None
    else {
      parseLine(lineOption.get)
} } }

This is a little cleaner than the original. The transforming function names call out what each is accomplishing. The separation of these pieces of functionality leads to more lines of code, but now each piece can be tested individually. That's always good!


Moar functional

Checking isDefined on options is ugly. The more idiomatic way to branch on Option is to use pattern matching.

def patternMatching(filename:String)
  : Option[SecretMessage]
= {
  import transformers._
  openFile(filename) match {
    case None => None
    case Some(file) =>
      readFirstLine(file) match {
        case None => None
        case Some(line) =>
          parseLine(line)
} } }

This is shorter, but it still has a repetitive pattern. With each transformation step, we're manually coding that gutter flow.

The next trick is to recognize that Option is a collection. It's a special collection, containing either one or zero items. Then notice that each transformation operates on the single item in the collection returned by the previous step. What method applies a function to items in a collection? map! Except that is not quite right, because map transforms a collection element into another element. Each of our transformers return another collection of zero or one items. What method applies a function to items in a collection and turns each into another collection? flatMap!

def chainOfMaps(filename:String)
  : Option[SecretMessage]
= {
  import transformers._
  openFile(filename).
    flatMap(readFirstLine).
    flatMap(parseLine)
}

Now this is about as short as it gets. The gutter pipeline is encoded in flatMap itself, because a flatMap on None will return another None. How can it get cleaner than this?

There's another way to process collections in Scala: the for comprehension. it lets us line things up in a more readable fashion, and then it calls flatMap and map. Here, we give names to intermediate values in the pipeline.

def forComprehension(filename:String) : Option[SecretMessage] = {
  import transformers._
  for( file <- openFile(filename);
       line <- readFirstLine(file);
       secretMessage <- parseLine(line))
  yield { secretMessage }
}

In IntelliJ, it lets me hover over these variables names to see their types. In my experience, this style is drastically easier to get right, to debug, and to follow when reading. These benefits are worth a few extra lines and curly braces.


What have we accomplished?

We turned a step-by-step imperative function into a very concise concatenation of three transformations. We removed all manual handling of the gutter pipeline. We broke out the transformations into testable bits.


Now for the cool part.

Here, we're using the Option class as a context for our data. It is a context that says, "I might have a result, and I might not. If I don't, roll the ball down the gutter and ignore future transformations."

Requirements change! The caller of our function wants to know why no secret message was found. Instead of None, return a failure type with a message. Implement this by changing the context the work is done in. The work for this is in another file, if you want to run it yourself.

That context is either a Failure or a Success. It is a generic context, but at the end of our function a Success will contain a SecretMessage, while a Failure contains only an error message.[1]

Change each transformer to output Result instead of Option. They each include a descriptive message upon Failure.

One more step is needed to make Result operate as a context the same way Option does. Scala's for comprehension will work with any type that implements map and flatMap. Add the declarations to the common Result trait, and then the implementations to each concrete class.

sealed trait Result[A] {
  def flatMap[B](f : A => Result[B]) : Result[B]
  def map[B](f : A => B): Result[B]
}
case class Success[A](value : A) extends Result[A] {
  def flatMap[B](f : A => Result[B]) = f(value)
  def map[B](f : A => B) = Success(f(value))
}

case class Failure[A](message: String) extends Result[A] {
  def flatMap[B](f : A => Result[B] ) = Failure(message)
  def map[B](f : A => B) = Failure(message)
}

Success applies the passed-in functions to the value inside it. Failure always returns another Failure, with the same message but a different type parameter. This is the gutter where errors flow.

Here's the interesting bit: when it comes to changing our function, we almost don't. The return type changes. The pipeline is identical!

def forComprehension(filename:String) : Result[SecretMessage] = {
  import transformers._
  for( file <- openFile(filename);
       line <- readFirstLine(file);
       result <- parseLine(line))
  yield { result }
}

This is a key concept of functional programming: separating out context. Sometimes that context contains state, other times isolated side effects (I/O), other times order of execution (synchronous, asynchronous, parallel). We can abstract things that used to be inherent. An imperative style cements mutable state and step-by-step order of execution; changing this is a huge amount of work and easy to get wrong. Functional style, once you get used to it, gives us more degrees of freedom.

Next time you write a method longer than a few lines, look for a path of data transformation. It might lead you someplace elegant.


[1] Sure, this sounds like an Either. If only Either implemented flatMap, it would completely work for this.

9 comments:

  1. Great post. I like that you approached the problem from the top down, rather than starting with the monadic laws and the bind/return definitions, and THEN showing the use-case. Makes it much easier to grasp for new people.

    ReplyDelete
  2. Great post! One nitpick: None does not take type parameters.

    ReplyDelete
  3. For real-world code, I'd ask why Failure doesn't simply extend Result[Nothing]. As a tutorial, though, this works fine if you haven't introduced Nothing yet.

    ReplyDelete
  4. Imperative style doesn't mean that you code one long function/method! Moreover, in your example if statements are coded in an unreadable way. All in all, an anti-pattern of what the imperative style should look alike.

    ReplyDelete
  5. What all you have to do is just visit lender’s website offering such loan service and complete their online application form that is quite easy to fulfill. Make sure that you mention only right and up to date information so that lenders could easily approve you at the very first time. There is no need to make loads of hassles during the application process.http://6monthloansfirst.co.uk/

    ReplyDelete
  6. The Buddhist way to all of this is quite genuine, really. Buddhism understands of that from the perspective of ego the opportunities of lack of way of life is generally difficult. The ego cannot think about being deceased. TUBE

    ReplyDelete