When OO and FP meet: returning the same type

In the left corner, we have Functional Programming. FP says, “Classes shall be immutable!”

In the right corner, we have Object-Oriented programming. It says, “Classes shall be extendable!”

The battlefield: define a method on the abstract class such that, when you call it, you get the same concrete class back. In Scala.
Fight!

Here comes the sample problem —

We have some insurance policies, auto policies and home policies. On any policy, you can adjust by a discount and receive a policy of the same type. Here is the test:

case class Discount(name: String)

  def test() {
    def adjust[P <: Policy](d: Discount, p: P): P = p.adjustBy(d)
    val p = new AutoPolicy
    val d = Discount(“good driver”)
    val adjustedP: AutoPolicy = adjust(d, p)
    println(“if that compiles, we’re good”)
  }

OO says, no problem!

abstract class Policy {
   protected def changeCost(d: Discount)

   def adjustBy(d: Discount) : this.type = {
       changeCost(d:Discount)
       return this
   }
}

class AutoPolicy extends Policy {
  protected def changeCost(d: Discount) { /* MUTATE */ }
}

FP punches OO in the head and says, “Mutation is not allowed! We must return a new version of the policy and leave the old one be!”[1] The easiest way is to move the adjust method into an ordinary function, with a type parameter:

object Policy {
   def adjust[<: Policy](p: P, d: Discount): P = {
     case ap: AutoPolicy => new AutoPolicy
     … all the other cases for all other policies …
   }
}

But no no no, we’d have to change this code (and every method like it) every time we add a Policy subclass. This puts us on the wrong side of the Expression Problem.[2]

If we step back from this fight, we can find a better way. Where we declare adjustBy, we have access to two types: the superclass (Policy) and this.type, which is the special-snowflake type of that particular instance. The type we’re trying to return is somewhere in between:

How can we specify this intermediate type? It seems obvious to us as humans. “It’s the class that extends Policy!” but an instance of AutoPolicy has any number of types — it could include lots of traits. Somewhere we need to specify “This is the type it makes sense to return,” and then in Policy say “adjustBy returns the type that makes sense.” Abstract types do this cleanly:

abstract class Policy {
  type Self <: Policy
   protected def changeCost(d: Discount): Self

   def adjustBy(d: Discount) : Self = {
       changeCost(d:Discount)
   }
}

class AutoPolicy extends Policy {
  type Self = AutoPolicy
  protected def changeCost(d: Discount) = 
    { /* copy self */ new AutoPolicy }
}

I like this because it expresses cleanly “There will be a type, a subclass of this one, that methods can return.”
There’s one problem:

error: type mismatch;
 found   : p.Self
 required: P
           def adjust[P <: Policy](d: Discount, p:P):P = p.adjustBy(d)

The adjust method doesn’t return P; it returns the inner type P#Self. You and I know that’s the same as P, but the compiler doesn’t. OO punches FP in the head!

Wheeeet! The Scala compiler steps in as the referee. Scala offers us a way to say to the compiler, “P#Self is the same as P.” Check this version out:

def adjust[P <: Policy](d: Discount, p: P)
               (implicit ev: P#Self =:= P): P = p.adjustBy(d)

This says, “Look Scala, these two things are the same, see?” And Scala says, “Oh you’re right, they are.” The compiler comes up with the implicit value by itself.
The cool part is, if we define a new Policy poorly, we get a compile error:
class BadPolicy extends Policy {
  type Self = AutoPolicy
  protected def changeCost(d: Discount) = { new AutoPolicy }
}
adjust(d, new BadPolicy)
error: Cannot prove that FunctionalVersion.BadPolicy#Self =:= FunctionalVersion.BadPolicy.
           adjust(d, new BadPolicy)

Yeah, bad Policy, bad.

This method isn’t quite ideal, but it’s close. The positive is: the abstract type is expressive of the intent. The negative is: any function that wants to work polymorphically with Policy subtypes must require the implicit evidence. If you don’t like this, there’s an alternative using type parameters, called F-bounded polymorphism. It’s not quite as ugly as that sounds.

Scala is a language of many options. Something as tricky as combining OO and FP certainly demands it. See the footnotes for further discussion on this particular game.

The referee declares that FP can have its immutability, OO can have its extension. A few function declarations suffer, but only a little.

————–
[1] FP prefers to simply return a Policy from adjustBy; all instances of an ADT have the same interface, so why not return the supertype? But we’re not playing the Algebraic Data Type game. OO insists that AutoPolicy has additional methods (like penalizeForTicket) that we might call after adjustBy. The game is to combine immutability with extendible superclasses, and Scala is playing this game.
[2] The solution to the expression problem here — if we want to be able to add both functions and new subclasses — is typeclasses. I was totally gonna go there, until I found this solution. For the case where we don’t plan to add functions, only subclasses, abstract types are easier.

More references:
F-bounded type polymorphism (“Give Up Now”)
MyType problem
Abstract self types

Data Exposure and Encapsulation

TL;DR – Scala lets you expose internal data, then later change underpinnings while maintaining the same interface.

The functional Way is an open Way. Internal data is available to anyone who wishes to extract it.

“But what about encapsulation??” – horrified OO programmer
“We do not fear your code, for you cannot screw up our immutable data.” – calm FP programmer
“But what about change? If you expose internal structure, then you can never change internal structure. You’ll break all my code!” – OO
“The surface is resilient. The essence is fluid. We can keep client code happy while expanding underneath.” – FP

One of the ways that Scala achieves “scalability” is: make the code easy to write now, and still flexible to change later. An example is simple data structures: the case class. By default, anyone can pattern match to extract all the values from a case class. For instance:

case class PersonName(first: String, last: String)
val me = PersonName(“Jessica”, “Kerr”)

val greeting = me match {
  case PersonName(first, last) => s”Hello, $first $last”
}

This is handy – it makes building and using simple datatypes painless. Fields are public, which is not frightening because they’re final, safe from alteration.

The danger of this easy syntax is rigidity: if I add a middle-name field to PersonName, then all the code that pattern matched on it is broken. Construction, too.

case class PersonName(first: String, 
                      last: String, 
                      middle: Option[String])
val me = PersonName(“Jessica”, “Kerr”) // broken!

me match {
  case PersonName(first, last) => s”Hello, $first $last” // broken!
}

We want to change the PersonName without breaking backwards compatibility. In Scala, all the handiness of the case class (construction, extractors) is syntax sugar. That means we can pull it apart and do whatever we want with it behind the scenes.

In Scala, the constructor that works without “new” in front of it is really function application on the PersonName companion object. [1] And function application on anything is really a call to its apply method. Case class syntax sugar provides an apply method that accepts all the fields, like:

object PersonName {
     def apply(first: String, 
               last:String, 
               middle: Option[String]) : PersonName =
            new PersonName(first, last, middle)
   …
}

PersonName(“first”, “last”, Some(“middle”)) expands to PersonName.apply(“first”, “last”, Some(“middle”)) .
Since that’s all the case class constructor really is, we can re-enable the old syntax by adding a bonus apply method to the PersonName object:

object PersonName {
    def apply(first: String, last: String): PersonName = 
       new PersonName(first,last, None)
}
val me = PersonName(“Jessica”, “Kerr”) // fixed!

There’s another secret method name behind the pattern match syntax. When Scala sees:

(p : PersonName) match {
   case PersonName(a : String,b : String) =>
}

Scala looks for a method called unapply on the PersonName object; unapply should accept a PersonName and return an optional tuple of two strings.

object PersonName {

  def unapply(pn: PersonName): Option[(String, String)] = 
       Some((pn.first, pn.last))
}


It’s like the case statement is switching around the return value and the arguments of the unapply method. If calling unapply with the matched-against value (p) returns Some(tuple), then the match succeeds and the identifiers (a and b) get the values in the tuple.

Retaining support for the pattern match is harder than the constructor. We can’t add another unapply extractor to the PersonName object; it conflicts with the generated one that comes with the case class.

Here’s a solution that abstracts PersonName into a trait, then backs it with a different case class of our choice. Now the constructors and extractors are ours to control and manipulate.

trait PersonName {
    val first:String
    val last:String
  }

case class FullPersonName(first: String, 
              last: String,
              middle: Option[String]) extends PersonName

object PersonName {
  def apply(first: String, last: String): PersonName = 
          FullPersonName(first,last, None)
  def unapply(pn: PersonName): Option[(String, String)] = 
          Some((pn.first, pn.last))
}

This compatibility could also be met by changing PersonName from a case class into a regular class, and supplying apply and unapply methods as we like. What matters is not how we do it, but that we can.

In this way Scala makes the obvious thing easy, and custom behavior possible. Backwards compatibility enables reuse. In OO we encapsulate everything up front to make later change possible, with indirection and lots of boilerplate. In Scala we don’t have to complicate our code to accommodate possible imagined future change. Stick with YAGNI now, without paying for it later. Reduced suffering for everyone! The world is a better place with FP.

————–
[1] We could fix the broken constructor by supplying a default value for middle name.

case class PersonName(first: String, 
                      last: String,
                      middle: Option[String] = None)

That’s simpler but less flexible.

What FP taught me about OO: Liskov Substitution Principle explained

TL;DR – functional programming taught me that LSP is a special case of PLS: Principle of Least Surprise.

One thing that bugs me while reading Java: I’m reading along, come to a method call, ctrl-click on the method name, and get a list of implementations of the interface. IntelliJ can’t tell me exactly what will run at this point in the code. Java has dynamic dispatch: it decides at runtime which implementation to run.

Functional style has a different concept to offer instead of Java’s interface. It’s called “typeclass,” which is incredibly confusing. Please accept that this idea has little to do with “type” or “class.”

While an interface says, “This class can perform this method,” a typeclass says, “There exists something that can perform this method on this class.” (using ‘class’ loosely) An interface is baked into a class, while a typeclass instance is provided separately.

With typeclasses, the method implementation isn’t attached to the runtime class. Instead, the compiler digs up the typeclass instance, based on a declared type instead of a concrete runtime type. This isn’t flexible in the same way as OO’s dynamic dispatch, but it has the advantage that we can tell by looking at the code exactly which implementation of the method will execute.

This gives us better ability to read the code and figure out what will happen in all circumstances, without using the debugger. Functional programmers call this “reasoning about code.”

In Java, how can we make statements about what the code will do when we don’t know exactly what code will run? One answer is: Liskov Substitution Principle. This OO design principle says, If you inherit from some other class or implement an interface, then be sure your class meets all expectations people have of the superclass or interface. The compiler enforces that our methods have the right signatures, while LSP demands that our implementation have the same invariants, postconditions, and other properties implied the documentation of the superclass or interface.

For instance, if you create an implementation of List with a .length() method that sometimes returns -1, you violate the expectations people have for Lists. This surprises people. Surprises are bad. Surprises stop us from accurately predicting how code will execute.

Therefore, the Liskov Substition Principle says, “Don’t surprise people.” If the documentation of List implies that length() will return a nonnegative integer, always do that. Also make sure that your List is 0-indexed like everyone else’s. To implement an interface is to take on all the implicit and explicit promises made by that interface. That’s LSP.

In Haskell or Scala, we can use typeclasses and be certain what the code will do at runtime. In Java, we can have the flexibility of dynamic dispatch and still have some knowledge of what will happen at runtime as long as we respect the Liskov Substitution Principle.

Functors: What the funk for?

For all the programmers who don’t deeply grok the lambda calculus terminology —

Say you are about to call a method on a container, and that container can give you something back of type Tweet. What you really want isn’t a Tweet, but some part of it, say Tweet.getId(). What if, instead of getting the Tweet back from the container and then calling getId() on it, you prefer to tell the container to get the id for you, and return only what you wanted? Then you need a functor.

So you make a quick function literal (tweet => tweet.getId()) that pulls the id out of a Tweet, and pass that in to the functor. The output is the same kind of container, only it holds IDs instead of Tweets. A functor isn’t a special type; it’s a function with a particular purpose.

Why would you want to do this? I used to think that too. Then…

I have an Iterable tweets, and I want to get the ID of the first element. In this example, I’m using Java with the Guava library. The function to call is Iterables.getFirst, which requires a default value in case the iterable is empty. As it happens, I have a default value for the ID, but no Tweet that contains this default ID. Short of constructing a stupid dummy Tweet that holds my default ID, I’m stuck with:

Tweet firstTweet = Iterables.getFirst(tweets, null) 
return firstTweet == null ? defaultId : firstTweet.getId() 

I have to create an identifier and then check stuff on it. This is not declarative enough or simple enough for my taste. I’d rather do this (using Java 8 lambda syntax for brevity):

return Iterables.getFirst(tweets, t => t.getId(), defaultId)

In this hypothetical example, I’m telling that getFirst function to run my function on the tweet before returning. If tweets is empty, then the function can return defaultId. So I’m supplying a default that is meaningful to me, the function is going to return the same type whether there’s a tweet or not, and everyone is happy.

But, that method doesn’t exist. And it would be a pain to an optional function argument to the interface of all the functions in Iterables. Thinking in terms of functors, I can solve this problem with functions that do exist in Iterables:

Iterables.getFirst(Iterables.transform(tweets, t => t.getId()), defaultId)

Here, transform is a functor: it applies the supplied function to the elements inside the iterable, returning an iterable of the function-output type. This means a tweet gets turned into a tweetId before getFirst sees it.

To a long-time Java dev like me, this looks inefficient. Do work on every tweet in tweets just to get the first one out differently? Ahhh, but Guava iterables are lazy! That function is not applied until somebody calls next() on the iterable returned by transform(tweetst => t.getId()). Iterables.getFirst calls next() at most once, so only the first tweet is transformed. Therefore, I have exactly what I wanted: turn that first tweet (if there is one) into an id before giving it back to me. The type of defaultId matches the element type of transform(tweetst => t.getId()).

The lesson of functors is: you don’t have to take something out of a container in order to operate on it.

In OO design, there’s a principle of “Tell, don’t ask.” Classes are supposed to tell each other what to do, rather than asking for internal data. This is an example of that — the Iterable has tweets, and I want the ID of the first one. Using the functor, I tell it “give me the result of this function applied to your tweet.” This is better encapsulation than pulling out the whole tweet and operating on it.

In this example, a functor is a function that does a transformation on data inside a context. In this example the context is an Iterable and its contents are Tweets. The transformation is a functor from Tweet -> ID. This way, an Iterable can give me back an ID, exactly what I wanted in the first place, without me ever having to see its Tweet.

Look! A functional trick can make my Java more OO than ever.


Caveat: there are many definitions for Functor out there, and different types of functors. This is one.

Abstraction goes both ways

Abstraction is critical to programming. It is the core activity we use to make more interesting and complex programs.

Most of us understand abstraction as finding commonalities between different concepts, and modeling these as an inheritance hierarchy. If you are a retail store, then toy cars, trash cans, and pillows are all sellable items.  Thus, abstraction is finding similarities in disparate things. Identifying patterns.

But there is another side: breaking concepts down into components. While the trash cans and toy cars are the same at the cash register, they are different when stocked on shelves. That GUI button has a view, a model, and some event triggers. Thus, abstraction is also finding differences in what appears to be same. Breaking what appears to be an indivisible whole into disparate components. Design is the process of breaking things apart.

This second application of abstraction is important in analyzing cause and effect. We started an agile process, and then a bug made it into production. Agile is a failure! But really, did our process changes have anything to do with it? Perhaps the two events were unrelated. Or perhaps the same frustrations led to both. As humans we get overexcited about X happened, and then Y happened; therefore X led to Y. We are too quick to form patterns where none exit. Laurie won both poker nights, therefore Laurie is skilled at poker. It is challenging to break Laurie’s play into components of luck and skill – skill we can control, so it’s a much more appealing cause. Breaking a cause or effect into multiple components requires abstraction, and if we use it, we will be better at programming and at life.

Choices with def and val in Scala

In Scala, one can define class properties with either “def” or “val.” Using “def“, one can define the property with or without parentheses, and with or without the equal sign. Why is this? What are the consequences?

For illustrative purposes, we’ll use a block of code that printing to the console, then returns an int. This shows when the code runs.

carrot.scala:

import System.out._
class Carrot {
   val helloTen = { println “hello“; 10 }
}

When a val is initialized to a block of code, the code runs at construction, and the property contains 10. The block only runs once. You can see this in the REPL:

scala> :load carrot.scala

scala> val c = new Carrot()
hello
c: Carrot = Carrot@5fe2b9d1
scala> c.helloTen
res5: Int = 10

If you change val to def, that block of code instead becomes a method. It prints and returns 10 every time it is accessed.

carrot.scala:

import System.out._
class Carrot {
   def helloTen = { println “hello“; 10 }
}

Use the REPL to observe that the code runs at every access:

scala> :load carrot.scala

scala> val c = new Carrot()
c: Carrot = Carrot@5689a400
scala> c.helloTen
hello
res7: Int = 10
scala> c.helloTen
hello
res8: Int = 10

Now I’m going to stop showing you what the REPL prints out, because that’s boring to read. Try it for yourself.

So “def” or “val” determines whether the block of code runs only at construction, or at every access. There’s another consequence: in a subclass, you can override a def with a val or a def, but you can only override a val with a val. When Scala has a val, it knows the value of that expression will never change. This is not true with def; therefore declaring something as val says more than declaring a def.

Let’s move on with “def” because it’s more flexible for extension. Next decision: use parentheses or not? We can choose between
def helloTen = { println “hello“; 10 }
and
def helloTen() = { println “hello“; 10 }

The consequences of this decision are: if you include the parentheses in the definition, then the property can be accessed with or without parentheses. If you do not include parentheses in the definition, then the property must be accessed without parentheses.

Here’s a summary of our options:
th { border-bottom: 2px black solid; } td { padding: 5px; }

With () No ()
val n/a runs at construction;
override with val;
access with no ()
def runs at every access;
override with val or def;
access with or without ()
runs at every access;
override with val or def;
access with no ()


The idiomatic rule of thumb is: use parentheses if the method changes state; otherwise don’t.

Now here’s a subtlety. If we use def with or without parentheses, the property can be overridden in a subclass by a def with or without parentheses (or a val without parentheses). This has strange consequences: If I subclass Carrot and override the property, but change whether parentheses follow the property declaration, then the interface of the subclass does not match the superclass.

carrot.scala:

import System.out._
class Carrot {
    def helloTen = { println (“hello”); 10 }
}

class Soybean extends Carrot {
    override def helloTen() = 14
}

On a Carrot, I can access helloTen only without parentheses. On a Soybean, I can access the property with or without parentheses. If I cast a Soybean to a Carrot, then I can access helloTen only without parentheses. Either way, the Soybean’s helloTen property evaluates to 14, as a good polymorphic method should.

Stranger still, reverse it: if Carrot defines helloTen with parentheses and Soybean without, then a Carrot (or a Soybean cast to a Carrot) will helloTen with or without parentheses — but a Soybean will only helloTen without parentheses! Therefore, a method call that works on the superclass errors on the subclass. Does this sound like a violation of LSP to you? Technically instances of the subclass can be substituted for instances of the superclass, but the interface of the subclass is smaller than that of the superclass. Wah? If this makes sense to you, please comment.

For another method-declaration subtlety, consider the equals sign.

I’m running Scala 2.9.2.

Mental revolution

The book Structure of Scientific Revolutions (1962, Thomas Kuhn) brought the word paradigm into common use. Ideas from fifty years ago about research science apply today to computer science and the software industry. This is one parallel Kuhn makes, extended to illuminate how we think about programming.

The human mind does not perceive objects incrementally, feature by feature. We grasp images as coherent wholes. Sometimes when we step back, we can see the object in a new way. When we step back even farther, we might perceive it as something more basic and universal.

For instance, consider:

What do you see first, the duck or the rabbit? Now that I mention them, do you see them both? You can switch back and forth between them at will. If you stare at the picture long enough, you might see it instead as a collection of lines. You can perceive these lines as forming a duck or a rabbit, but in both cases you see the more universal nature of the lines.

This is like the wave-particle duality of light. A millenium ago, light was pictured as a particle. About five hundred years ago, Descartes observed that it behaved like a wave. Newton saw light as particles. Maxwell showed that light is waves. Einstein saw the particle nature of light again, and finally combined the two. Stepping back, it turns out that all particles have wave-like properties. Just as all duck drawings and all rabbit drawings are composed of lines, all matter has a quantized wave nature.

This same process of discovery can apply to software design. Take, for instance, the Strategy Pattern. Say we need to tell our SearchEngine at construction which RankingAlgorithm it should use. In an object-oriented design, such as for Java, it looks like this:

From a functional programming paradigm, it’s simpler. For a first implementation, we might give the search a lambda or a reference to a ranking function that translates a document to something orderable.

search :: (Document -> Ord) -> Doc[] -> String

These are two ways to view the same solution – either we’re implementing the Strategy pattern, or we’re passing in a function. When both of these views make sense, take a step back and observe that in both cases we’re doing the same thing: we’re passing a behavior. Look at it as a Strategy or as function-passing, whatever is better suited to our environment. Understanding both views and the common principle behind them gives a broader perspective on design.

This is a simple example, but the principle applies to many concepts in programming. Playing with Hadoop and then doing list processing in a functional language can show the common nature of map-reduce. Seeing the commonalities between two views of the same concept shows what is core to map-reduce and what is an implementation detail specific to Hadoop.

Get too focused on the duck, and you might never see the lines. In software, as in life, it helps to adopt a new paradigm. After we see a problem in a new light, we can step back and look for the broader concepts. This leads to a new level of understanding we can never see if we keep insisting that light is a wave and that picture has a beak.

The confluence of FP and OO

Michael Feathers has a great blog post up today about how object-oriented and functional programming styles are suited to different portions of an application.

Specifically, the object-oriented style fits the high-level application components. The original intention of OO was for objects to pass messages to each other, which is suited to a SOA style and asynchronous message-passing. At this level, components should tell each other what to do, rather than asking for information (as return values). OO and top-down design work well together.

The functional style is better suited to the low-level components. Within objects, a functional style is cleaner and simpler for computations. A functional style is friendlier to an iterative, test-driven approach.

There is one more piece where functional precepts can help us become even more object-oriented, in the message-passing sense. We can make more messages asynchronous when we can pass callbacks. These functions-as-data let us specify what happens next, removing the need to wait for a return value. This looks different from an imperative style, but it is embraced by JavaScript and Node.js, and it’s getting more ubiquitous by the day. It’s suited to asynchronicity, which enables more OO-style message passing.

We can embrace OO and FP in their areas of strength. F# and Scala seem very important in this light. They take away the pain of crossing the seam between OO and FP. We can even embrace the callback (or continuation) style without making our code unreadable: in F#, computation expressions can break imperative-looking code into pieces that execute as each message-pass is completed.

The hybrid languages give us opportunity to optimize our code at both high and low levels, to break our application into large object-oriented chunks and implement each solution functionally. When both paradigms have full language support, we can employ the strengths of each and interoperate at will.