Kleisli Composition à la Up-Goer Five

When you have a way to turn thing one into thing two, and you also have a way to turn thing two into thing three, you can put those ways of turning things into other things together, to make a way to turn thing one straight into thing three. That’s easy.

But if instead you only have a way to turn thing one into a box that has thing two inside, and a way to turn thing two into a box that has thing three inside, it’s harder, because you usually aren’t allowed to take anything out of a box. If you put those ways of turning things into boxes of other things together, you usually end up with a way to turn thing one into a box that has a box inside, that finally has thing three inside. That’s too many boxes!

Some boxes are cool, though: when you have a cool box that has another cool box inside, you’re allowed to throw one of the cool boxes away so that you only have one cool box left. That means that if you have a way to turn thing one into a cool box with thing two inside, and a way to turn thing two into a cool box with thing three inside, you aren’t left with too many boxes when you put them all together, only one.

There are different kinds of cool boxes. One kind of cool box lets you take things out, but only if you wait until they’re ready. So if you have a way to turn thing one into a cool box that will let you get thing two out later, and a way to turn thing two into a cool box that will let you get thing three out later, you can put them together to make a way to turn thing one straight into a cool box that will let you get thing three out later.

Another kind of cool box is almost like the first kind, but when you take things out, you might also get a surprise on the side. You usually don’t like surprises, so it’s best to wait until the world ends before you try to take things out. It’s safe to put them together though, just like before: if you have a way to turn thing one into a surprise-box of thing two, and a way to turn thing two into a surprise-box of thing three, you can make a way to turn thing one straight into a surprise-box of thing three without fucking up the surprises.

Another kind of cool box that people often use can have many of the same thing inside. So if you have a way to turn thing one into a cool box with many thing twos inside, and a way to turn thing two into a cool box with many thing threes inside, you can put them together to make a way to turn thing one straight into a cool box with many thing threes inside.

So remember the easy first part: when you have a way to turn thing one into thing two, and you also have a way to turn thing two into thing three, you can make a way to to turn thing one straight into thing three. You can keep doing this over and over until you run out of numbers for things. Cool boxes are just the same: when you have a way to turn thing one into a cool box of thing two, and a way to turn thing two into a cool box of thing three, you can always make a way to turn thing one straight into a cool box of thing three no matter what kind of cool box you have.

Edit

Sometimes people like to explain the cool boxes as if they were a kind of food. This kind of food first came from a warmer part of the world, down from where I live but not too far, where most people fear God and sometimes have serious eyebrows. Many things can go on the inside of the food, like stuff that grows from the ground, and other stuff that comes from dead animals. Only one thing goes on the outside of the food: a wrap that you can eat.

I like this wrapped food, and the people who make it, but I think it’s too hard to see why the cool boxes are cool if you try to imagine they are like it. Because if the wrapping has thing one inside, and you want thing two instead, you probably can’t fix it without hurting the food: the inside will get all over you, and you’ll just have to buy a new one.

Tagged , ,

Coupling in Object-Oriented Programming

I’ve been known to badmouth object-oriented programming, and I want to formalize a bit of that badmouthing in this post.

Before I start: the actual definition of OOP remains a topic of some controversy, with some people arguing it doesn’t even exist (I disagree), so I’m not going to go down that rathole. I’ll settle here for “I know it when I see it.” Those were the famous words of U.S. Supreme Court Justice Potter Stewart when asked to define hardcore pornography, and I think it’s apropos here because I would also like to talk about obscene coupling.

I’m funny.

Anyway, there seems to be some general hand-wavey consensus that “objects” are entities that have properties, behavior and identity:

  • When we talk about object properties, we usually mean “fields,” as in the stuff that lives in a struct; more formally, the components of a product type. It’s commonly considered a best practice to regard fields as an “implementation detail,” hiding them away behind behaviors that express how to construct an object and how to accessing and modifying an object’s properties.

  • When we talk about object behavior, we usually mean “methods,” as in functions or procedures with open recursion. Typically this means that each function takes a handy, implicit this or self reference parameter, to provide a starting point from which to access fields of the receiving object. This is also complicated by dynamic dispatch: the caller of a method needn’t know whether that method is implemented in a superclass or a subclass.

  • When we talk about object identity, there’s some ambiguity: we might mean “value identity,” where two object references are considered identical if the fields of their referents are pairwise identical; we usually hand-write a method (like equals) to express that. On the other hand, we might mean “reference identity,” where two object references are considered identical only if they point to the same memory address.

This is pretty standard in the mainstream object-oriented programming languages I’m familiar with. People seem to accept all this as normal, and at least in the Java ecosystem, most commonly-used frameworks require developers to program in this JavaBeans-ish style.

Now put all that aside for a moment. Another thing most engineers at least claim to agree with, and accept as normal, is the proposition that coupling is bad. For whatever definition of “module” you choose—and note that this is not at all specific to OOP—when one module is allowed to explicitly depend on another, that almost inevitably devolves into a ball of mud in which all modules are allowed to depend on all other modules.

The notion that decoupling or “loose coupling” is preferable gives rise to all kinds of awkwardly-stated laws and misguided ideas about what objects should know about what other objects and what things should be objects at all. Despite our best efforts, at the end of the day we end up with the same ball of mud regardless. I think this is because an object itself, as defined above, is already too tightly coupled. We have this long-standing collective cognitive dissonance in which, although we all know that coupling is bad, we’re perfectly happy to accept the idea that data, behavior and identity should all be lumped together.

Let’s go through a simple scenario in Java: say I have a simple class called Dog (because I like dogs), which maybe has a few properties like name, height and weight… details aren’t important.

  • I want to log some information about Dog objects that are constructed, so I implement a Dog.toString method that formats the object’s properties as a String; that’s pretty typical. Note that this introduces an API dependency on String, although it’s not a big deal, since String and Object.toString are ubiquitous in Java. It’s very unlikely we’d break any client code by changing the API to take different parameters or return a different type.

  • Now let’s say I’m running a doggy daycare, and I want to print out a list containing the names of all the dogs scheduled for the day. Just the names, though, meaning our Dog.toString isn’t what we want. So we need another method, Dog.getName. Oh, you assumed we already had that? Heh, cute. After implementing that, we can make a new Dogs utility class with a helper method, String getNames(List<Dog> dogs). Refactoring for the win.

  • The thing is, my doggy daycare application I’m building actually needs to be a REST web service, and I need to serialize my Dog objects to JSON. I pull in jackson-core as a dependency. Now, I don’t want to expose this to other clients of Dog, so instead I provide a method void toJson(OutputStream out) on the assumption that I’ll be writing these things to something like an HttpServletResponse object.

  • The next thing I need to deal with is, I’d like my list of Dog objects to be alphabetically sorted by name. So I make Dog implement Comparable<Dog>. This should be consistent with equals, so I implement value identity based on name as well.

  • Everything finally works, and I decide it’d be nice to provide my code as a library for others to use in their doggy daycare businesses. I publish a binary JAR and the JavaDoc for my API, and suddenly I’m getting emails from users who say they need XML serialization, they need to write to NIO ByteBuffer instead of OutputStream, and they need to sort dogs by their weight. They also don’t want the unnecessary runtime dependency on jackson-core, they want toString to format things differently for debugging purposes, and they want value identity to be based on all properties, not just name.

    One user also has created a Puppy subclass, and has a SortedSet<Puppy> using a custom Comparator<Puppy> which sorts puppies by age. She can’t pass that SortedSet<Puppy> into my getNames method; she tries to convert it to a List<Puppy>, which doesn’t work either. I get email telling me I should have used Iterable<? extends Dog>.

Now I’m in trouble: my simple Dog and Dogs classes are getting bigger and bigger, more tightly coupled to other libraries (including the perhaps innocuous Java standard library), and have to be safe for subclassing. I’m tempted to blame this bloat on my users, since I have to anticipate all of their needs, but it’s really not their fault. The fundamental problem is that every method I write hardcodes some assumption about how the Dog class should be used, and every one of these assumptions induces a dependency of some sort.

So, if an object or a class is a kind of data type that has not only properties, but also polymorphic behavior and identity as well, then avoiding coupling in an object-oriented codebase must be damn near impossible. Sure, we expect many data types to have necessary dependencies on other constituent types (perhaps defined in other libraries), for example: if my Dog type has a name property, I’m not going to waste time attempting to somehow abstract away the dependency on String. But behavior and identity are another story, for example: even if you believe there’s only one sensible way to convert a Dog to JSON, you certainly wouldn’t expect Dog to depend on JSON.

Data is just data. Contrary to object-oriented idiom, data isn’t sentient and needn’t be anthropomorphized. I think it’s perfectly legit to have a tiny library that just defines data types—what Martin Fowler calls an “anemic domain model”—with no logic operating on those types at all! If you want to do stuff with that library in your application, that’s awesome, knock yourself out. And if you think I want to do the same kind of stuff with that library, that’s even more awesome, extract a library encapsulating that functionality. I might use it, I might not, or maybe I’ll use it only in certain scenarios (test vs. production, for example). The point is that the clear separation between data and behavior is what permits that choice.

Tagged , ,

Dreaming of a New PL

I’ve been wanting to create a new programming language for about the last eight years or so.

Problem is, I haven’t had much clue what I would want a new programming language to look like, and even less of a clue how to actually create one. I’ve written some very simple compilers and interpreters before, so I know bits and pieces about parsing and code generation, but that’s a far cry from knowledge of programming language design.

I’d really like to change this, but I need help. There’s no way I can do this alone. So I figure I’ll write up some ideas I’ve had recently, and see if anybody who actually knows something about building languages wants to help.

I think the best way to explain what I’m thinking about right now is by comparison with existing programming languages. Specifically, there are things I like and dislike about Haskell, and things I like and dislike about Scala. So I’ll just describe those things as best I can, and see if that ends up painting a clear enough picture of what I’d hope to see in a new language.

Haskell Likes

  • Principal types. I’ve written about this before: I think explicit type annotations should be a matter of style—it’s a good idea to annotate types for an API rather than allow them to be inferred—rather than a matter of necessity. Haskell does admit some language extensions that defeat this, such as rank-N types, but for the most part it’s possible to infer a “most appropriate” type for any given expression.
  • Simple, minimal syntax. Seriously, the syntax of Haskell is not much more complex than that of the lambda calculus, and I like the use of layout to delineate blocks (see Okasaki’s post, “In praise of mandatory indentation for novice programmers”).
  • Currying and partial application for both functions and type constructors. I feel like this might be somewhat underappreciated, so maybe worth mentioning: just as it’s helpful to partially apply a function as in map (+1) [1..10], where (+) is a function of two parameters, it’s also helpful to describe a type as in instance Monad (State s), where State is a type constructor of two type parameters.
  • Pure functions. (Need I say more?)

Haskell Dislikes

  • I don’t like laziness by default. I do appreciate the elegance of composition in writing a function and only demanding a portion of its result (see Edward Kmett’s comments on the recent “Putting Haskell Down” thread), but I feel like it’s sort of a deal-breaker to require the routine use of profiling to hunt down space leaks and so on, when GHC’s strictness analysis doesn’t behave how you’d expect. I’d be very happy for somebody to change my mind about this, but so far I think optional laziness is better.
  • Monads are clunky. There, I said it. They are far from the panacea of “programmable semicolons” we’ve made them out to be. And since monads don’t compose, monad transformers are clunkier still. The syntactic noise of all the various types of lifting we do (>>=, <$> / <*>, etc.) is unsatisfying, and in some ways monads make debugging more difficult as well.
  • Related to the above, all of our “real-world” side effects in Haskell are relegated to the IO monad. This conflates the effects of reading from a mutating environment with the effects of writing to the environment, and lumps different portions of that environment (disk, network, memory, etc.) all into the same bucket. We need a better effects system. I’m very interested in Conor McBride’s work on “Frank” (described informally in comments on the same “Putting Haskell Down” thread from above), Daan Leijen’s work on “Koka” and others.
  • One could easily argue that this is a good thing, but I find it frustrating that Haskell doesn’t allow cycles in a module dependency graph. Sometimes I want mutually dependent modules, even if only to break a large file into two pieces.
  • Records are terribad, and I think we essentially need function overloading for them to work. For example, if I define a record data Foo { name :: String }, then I can’t also define data Bar { name :: String } in the same module: the two name fields collide.
  • Existential types are ugly. If I want a heterogeneous list of things that have Eq and Show type class instances, I need to put them in some sort of a “box” to homogenize them: data Box = Box (forall a. (Eq a, Show a) => a). Then I need to make Box an instance of Eq and Show, and finally I can create a list of boxes. This is straightforward in a language with subtype polymorphism, but I’m by no means saying that subtype polymorphism is what I want…
  • Scrap-your-boilerplate is bananas, and on a somewhat related note, there needs to be a better general mechanism for automatically deriving type class instances.

Scala Likes

  • Pattern matching is a big deal in functional languages, particularly when you have algebraic data types and whatnot. I really like Scala’s unapply / unapplySeq machinery for customizing pattern matching (and find it somewhat astonishing that Haskell has no equivalent).
  • I think in some sense, Scala treats type classes as more of a first-class citizen than Haskell does: they are named values that can be imported explicitly and overridden through scoping rules.
  • I like Scala’s placeholder syntax for partial function application better than Haskell’s. My Haskell example from above, map (+1) [1..10], is written in Scala as 1 to 10 map { _ + 1 }. To my eye, “something plus one” reads more intuitively than just “plus one.” This becomes a bigger deal when you have a function of multiple parameters, say three or more, and you want to partially apply some arbitrary subset of those arguments not necessarily in order. Note however that Scala currently has no such equivalent for partial type constructor application, so we resort to the horrible “type lambda trick” instead.
  • Strict evaluation by default, with optional laziness.
  • Scala targets the JVM. This is also something of a “dislike,” perhaps, since the JVM has its shortcomings with respect to functional languages—lack of tail calls most notably. But I feel like the JVM is indisputably solid: it’s fast, it’s stable, it’s mature, and it has a massive ecosystem of existing tools and open source libraries to work with.

Scala Dislikes

I hate to sound snarky, but this list is too big to put in writing. With all respect due to Odersky for his research on object calculi, I just don’t think I find objects particularly useful. I think Shields and Peyton-Jones’s “First-Class Modules for Haskell” paper is trying to change my mind (particularly since Haskell’s record system is so weak), but I don’t think I’m convinced yet. I also think Scala’s syntactic rules are generally ridiculous (I’ve bitched about this before). Pretty much all my other complaints are subsumed by these two in some way.

I really don’t want to sound like a Scala hater; hopefully my lists of Haskell dislikes and Scala likes make any complaints I have about Scala apolitical at least…

Conclusion

Reviewing my likes and dislikes here, I probably have some conflicting—or at least challenging—desires. It sounds like I want a minimalistic, strict functional language on the JVM with a novel system of effects, good type inference, easy-to-use bounded existentials and records, and flexible type classes and pattern matching. Oh, and type-safe reflection too.

So who wants to help?

Tagged

Scala Rage: Pattern-Matching

Sometimes Scala makes me happy. Sometimes Scala makes me angry. This post is about the latter.

def contrivedExample[A, B, C](a: A, b: B, c: C): Unit = a match {
  case b => println("matched b")
  case c => println("matched c")
  case _ => println("matched neither")
}

Somebody learning Scala might reasonably intuit that this method would be logically equivalent to:

def contrivedExample[A, B, C](a: A, b: B, c: C): Unit =
  if (a == b)
    println("matched b")
  else if (a == c)
    println("matched c")
  else
    println("matched neither")

Instead, they get the cryptic compiler error:

error: unreachable code
case c => println("matched c")
                 ^

error: unreachable code
case _ => println("matched neither")
                 ^

This is because the patterns written above are variable patterns: “A variable pattern x is a simple identifier which starts with a lower case letter” (§8.1.1). Variable patterns are irrefutable: they always match, thus subsequent patterns will never be reached. The patterns above are not, as somebody learning Scala might expect, stable identifier patterns, because “a stable identifier pattern may not be a simple name starting with a lower-case letter” (§8.1.5). Hence the following compiles and works as one would expect:

def contrivedExample[A, B, C](A: A, B: B, C: C): Unit = A match {
  case B => println("matched B")
  case C => println("matched C")
  case _ => println("matched neither")
}

First of all, I wonder how many new Scala developers have no freaking idea that the “unreachable code” error is actually telling them this. Also, this contradicts most typical naming conventions. Upper-case method parameter names? No, thanks. Instead, we have to explicitly indicate that the patterns are stable identifier patterns by referencing our lower-case identifiers in backquotes:

def contrivedExample[A, B, C](a: A, b: B, c: C): Unit = a match {
  case `b` => println("matched b")
  case `c` => println("matched c")
  case _ => println("matched neither")
}

As one of the lucky few people in the world right now with the rare privilege of teaching new Scala developers, guess how much time I feel like spending on stupid shit like this. Really, guess how much! Well, here are two hints:

  1. Upon seeing this quirk, students invariably ask questions: Why the arbitrary choice to use upper and lower case to distinguish between stable identifier patterns and variable patterns? Why does Scala permit name shadowing? What’s the special backquote syntax about? I can easily explain that the backquote syntax is a nice, general way of allowing Scala keywords to be used as identifiers (which is important when referencing code built in other JVM languages), so we can reuse that mechanism for disambiguation here… But to the other two questions, I seriously can’t provide justifiable answers.

  2. Teaching any topic, Scala included, involves some degree of “cheerleading,” motivating students to bring a sense of excitement about the topic back to their respective development teams. If they go back to work utterly stoked about Scala, that will clearly benefit more people than if they return with any sense of skepticism. What impression should it leave, if in the middle of introducing pattern matching — one of Scala’s most powerful features — they see this glaring issue?

Yeah. This doesn’t make me happy.


Edit: On Twitter, @missingfaktor asked the very fair question:

How else should that have been done? What do you propose?

A few ideas:

  1. Simply disallow name shadowing, since I think permitting shadowing (§2) is a dangerous idea to begin with, and directly gives rise to this problem. If a case clause could be interpreted ambiguously as either declaring and binding a new variable or referencing an existing one in scope, obviously it must be the latter because the former would shadow the existing binding. The compiler should at a minimum warn on name shadowing (like the erstwhile -Ywarn-shadowing) and issue a more helpful error message than “unreachable code” in the above case.

  2. Use an obvious syntax to distinguish between the two types of pattern. For example, case a might be a variable pattern and case == a might be a stable identifier pattern. Or case a might be a stable identifier pattern, and case val a might be a variable pattern. I don’t know if either of these choices are good, but I like them better from a “principle of least surprise” perspective than what we have currently.

  3. Fix inconsistencies in the spec regarding the different kinds of identifier. For example, §1.1 introduces the terms “plain identifier”, “variable identifier” and “constant identifier.” §8.1.1 and §8.2 introduce the term “simple identifier.” These aren’t all well defined, and aren’t used consistently in the places where they matter. I’d argue that case shouldn’t matter anywhere, since Scala allows code written in most natural languages (i.e. identifiers need not be written in Latin characters) and many natural languages don’t have case in their writing systems. At any rate, going through the process of cleaning this up might bring us to a solution where, for example, variable references in case clauses must always be enclosed in backquotes.

On the other hand, a ludicrous non-starter in my opinion would be to say that upper and lower case matter… It’s amusing at best to observe that case affects case.

Tagged , ,

Reading Your Future

In the Scala courses I teach, I usually try to spend as much time as I can discussing monads. I usually like to start with Option, showing how you can reduce something like:

if (a != null) {
  val b = somethingThatCouldFail(a)
  if (b != null) {
    val c = somethingElseThatCouldFail(b)
    if (c != null) somethingAwesome(c) else null
  } else null
} else null

to:

optionA flatMap { a =>
  somethingThatCouldFail(a) flatMap { b =>
    somethingElseThatCouldFail(b) map { c =>
      somethingAwesome(c)
    }
  }
}

to:

for {
  a <- optionA
  b <- somethingThatCouldFail(a)
  c <- somethingElseThatCouldFail(b)
} yield somethingAwesome(c)

I try to use that to motivate the general principle that, when you structure your code this way, you disentangle some “pure” behavior from some separate “monadic” behavior. I avoid formalizing what I mean by “pure” and “monadic,” instead waving my hands a little bit and saying that the pure behavior is generally the stuff we care about; in this case:

(somethingThatCouldFail andThen somethingElseThatCouldFail andThen somethingAwesome)(a)

… and the monadic behavior is generally the stuff we want to hide; in this case, the null checks. In other words, we hide the monadic logic, indicating its presence only in the type.

We derive the appropriate map and flatMap methods for Option, and although I find in my courses that this is a pretty decent place to start from, I don’t like leaving it this way. This treatment of the topic alone could easily lead students to assume that monads are solely for error-handling, in the same way that many monad tutorials for Haskell led readers to assume they were solely for IO. So we quickly branch into other practical uses of this design principle.

Two topics that often elicit post-traumatic stress responses from any Java web development refugee are asynchronous tasks and inversion of control. The former is an issue as it relates to concurrency: you might want to kick off a chain of asynchronous tasks, each depending on the previous, all in the context of some ExecutorService. The latter is an issue because you invariably wind up using a dependency injection framework such as Spring, which makes your code tricky to debug. And it happens that we can model both of these as monadic constructs.

So… I might be a bit late to the party, but I just noticed that there’s a very cute similarity between how those two things are modeled. That’s what I want to talk about in this post.


Composing Asynchronous Tasks with Future

Let’s start with Future, which represents a computation that might block or somehow take a while to complete. The type of this computation is really just a function of arity zero:

() => A

So a Future is just a simple class to wrap this function, like

class Future[A](val run: () => A)

You might use this for something like:

import java.net.{ ServerSocket, Socket }

val server: ServerSocket = new ServerSocket(31337)
val futureClient: Future[Socket] = new Future(server.accept)

Okay, but not particularly handy yet. If we simply want to get a client socket, we could just call server.accept directly, instead of our extra level of indirection futureClient.run(). The point of wrapping it up this way is to eventually do something with the client socket, modeling something like a callback: once run completes, producing its A value, we want to immediately do some work f: A => B. In other words, we want to compose the original Future[A] with f to produce a new Future[B].

For example, let’s say that once futureClient eventually produces an actual client socket we can work with, we want to get the number of bytes available for reading from it. Since this blog post is about monads, and since we looked briefly at Option already, we know we want to write something that looks like:

val futureAvailable: Future[Int] =
  futureClient map { _.getInputStream.available }

We implement map by constructing a new Future[B], whose new run function will just run the old one and apply f to the result:

class Future[A](val run: () => A) {
  def map[B](f: A => B): Future[B] =
    new Future(() => f(run()))
}

This is pretty useful, but I’ve sort of cheated here by choosing a function (available) that I know is non-blocking. Let’s be a bit more realistic, and say that we want to actually read a line from the client socket’s input stream, which could indeed block! We want to wrap this blocking call in a Future, just like we wrapped the blocking server.accept:

import java.io.{ BufferedReader, InputStreamReader }

def readLine(client: Socket): Future[String] = {
  val in = new BufferedReader(new InputStreamReader(client.getInputStream))
  new Future(in.readLine)
}

But then we have a problem when we try compose this function with our futureClient using map:

val futureFutureLine: Future[Future[String]] = futureClient.map(readLine)

We only want a Future[String], just like we only wanted a Future[Int] previously. We don’t want to have to say .run().run(). Okay, again, this is still a blog post about monads in Scala, so we know we want our code to look like:

val futureLine: Future[String] = futureClient.flatMap(readLine)

The naïve implementation of flatMap is even simpler than map:

class Future[A](val run: () => A) {
  def map[B](f: A => B): Future[B] =
    new Future(() => f(run()))

  def flatMap[B](f: A => Future[B]): Future[B] =
    f(run())
}

Just run this and apply f! This is algebraically correct — the types line up and the monad laws are satisfied — but it’s totally inappropriate for our purposes because we don’t want to actually run anything yet. The map method didn’t cause our Future[A] to be evaluated, and neither should flatMap. We instead need the following:

class Future[A](val run: () => A) {
  def map[B](f: A => B): Future[B] =
    new Future(() => f(run()))

  def flatMap[B](f: A => Future[B]): Future[B] =
    new Future(() => f(run()).run())
}

So flatMap will produce a new Future[B], whose run function will run the old one and apply f (just like map). Since f produces a Future[B], and we don’t want to end up with a Future[Future[B]], we finally run the result of f. All good.

Now that we have this plumbing complete, we can write silly code like:

for {
  client1 <- new Future(server.accept)
  client2 <- new Future(server.accept)
  line1 <- readLine(client1)
  line2 <- readLine(client2)
} yield line1 == line2

… which is a Future[Boolean] indicating whether or not two clients sent the same message to the server. The important thing that this illustrates, similar to the Option example, is that all the callback-related shenanigans are pretty much hidden from the logic we care about here:

readLine(server.accept) == readLine(server.accept)

Inversion of Control with Reader

Now onto the topic of inversion of control. The general idea in IoC is that we expect that somebody, somewhere, will provide the environment our code depends on, rather than having to obtain it explicitly ourselves. For example, say we require a JDBC Connection to issue some queries. We could either create a Connection ourselves (using something horrible like JNDI, for example):

import java.sql.{ Connection, ResultSet }
import javax.naming.{ Context, InitialContext }
import javax.sql.DataSource

def query(sql: String): ResultSet = {
  val context: Context =
    new InitialContext
  val dataSource: DataSource =
    context.lookup("java:comp/env/jdbc/FooDB").asInstanceOf[DataSource]
  val connection: Connection =
    dataSource.getConnection
  connection.createStatement.executeQuery(sql)
}

Or we could just have it “injected,” which just means that somebody will call this function with the appropriate “dependency”:

def query(sql: String, connection: Connection): ResultSet =
  connection.createStatement.executeQuery(sql)

The latter is obviously cleaner, and allows us to vary DataSource as needed (for example, we’re likely to use a mock data source in unit tests). It’s particularly amenable to a pure functional style, because a computation that produces a value of type A and requires an environment E to be “injected” is really just a function:

E => A

We can make this explicit in our example:

def query(sql: String): Connection => ResultSet =
  _.createStatement.executeQuery(sql)

But it comes at a price: everywhere I need a Connection somewhere in my code, I have to provide it explicitly.

def doSomeQueries(connection: Connection): Int = {
  val foo: ResultSet = query("SELECT COUNT(*) FROM Foo")(connection) // ew!
  val bar: ResultSet = query("SELECT COUNT(*) FROM Bar")(connection) // ewww!!
  val baz: ResultSet = query("SELECT COUNT(*) FROM Baz")(connection) // ewwwww!!!
  foo.next().getInt(1) + bar.next().getInt(1) + baz.next().getInt(1)
}

Threading the connection dependency into doSomeQueries and then into query is messy and brittle. Well, to be fair, everything to do with JDBC is messy and brittle; we just don’t want to make the situation worse. Monads have successfully hidden our messes for us thus far, so let’s treat E => A as a monad as well.

First, as before, we wrap our “dependency injection” E => A in a class:

class Reader[E, A](val run: E => A)

The name “reader” is intended to imply that you can read from some externally-provided environment (with the subtlety that you can only read, not modify the environment in any way). So we could write, for example:

def query(sql: String): Reader[Connection, ResultSet] =
  new Reader(_.createStatement.executeQuery(sql))

This is like a slightly more sophisticated Future[ResultSet]: it lets us reference the query results that we will eventually have, once somebody provides a DataSource to issue the query against. Now, we want to clean up our verbose doSomeQueries in monadic style:

val doSomeQueries: Reader[Connection, Int] = for {
  foo <- query("SELECT COUNT(*) FROM Foo")
  bar <- query("SELECT COUNT(*) FROM Bar")
  baz <- query("SELECT COUNT(*) FROM Baz")
} yield foo.next().getInt(1) + bar.next().getInt(1) + baz.next().getInt(1)

So, as always, we need to provide appropriate map and flatMap implementations:

class Reader[E, A](val run: E => A) {
  def map[B](f: A => B): Reader[E, B] =
    new Reader(env => f(run(env)))

  def flatMap[B](f: A => Reader[E, B]): Reader[E, B] =
    new Reader(env => f(run(env)).run(env))
}

Here, map is simple function composition: to map some f: A => B over a Reader[E, A], we create a new Reader[E, B] whose run function runs the original reader and applies f. The flatMap method is a bit more interesting: we do the same composition as in map, but since f itself produces a Reader[E, B], we have to “inject” the environment there as well. Otherwise we’d end up with a Reader[E, Reader[E, B]]!

tl;dr

The thing I noticed — and again, I’m probably the last person to notice this, but I figured I’d write about it anyway — is that the map and flatMap implementations of Future and Reader look nearly identical:

// map
new Future(() => f(run()))
new Reader(env => f(run(env)))

// flatMap
new Future(() => f(run()).run())
new Reader(env => f(run(env)).run(env))

In other words, we could essentially write:

type Future[A] = Reader[Unit, A]

… and we wouldn’t be too far off. In reality, typical implementations of Future (e.g. in Finagle or Akka) will also deal with issues like failed or timed out computations; Reader doesn’t typically deal with those issues (although hey, it could). Regardless, I think this provides an interesting observation in the “which is cooler: objects or functions” debate:

  • If we model our world as objects, the problem of sequencing long-running tasks doesn’t seem at all related to the problem of avoiding hardcoded dependencies.
  • If we model our world as functions, on the other hand, these two problems have nearly identical solutions.
Tagged , , ,

Crouching Laziness, Hidden Strictness

I’ve once again reached the point that I seem to eventually reach in all my Haskell projects, where I find myself stumbling helplessly over code that is either lazier or stricter than I want it to be. Yesterday evening I posted a question on Stack Overflow asking about how one generally debugs this sort of thing, and sometime while I was sleeping I received what looks like a pretty good reply.

Good, but frustrating, for two reasons:

  1. Haskell having been around as long as it has, one would imagine there would be better tools for dealing with these common problems. Perhaps I’m spoiled by the wealth of comparatively good tools on the JVM platform, but debugging unwanted laziness using the profiler and unwanted strictness using trace seems very 1980’s. What seems even more horrifying is that when we want to do performance tuning, we don’t use the profiler (nope, that’s a debugging tool) but instead we manually inspect the Core code that the compiler produces.

  2. The Haskell language makes some effort to avoid hidden surprises, typically making them unsurprising by explicitly requiring them in type signatures (such as IO a or Maybe a). Why then shouldn’t laziness or strictness be visible, in some form, to the type system?

Let me pause at this point and make it clear that I have no idea what the fuck I’m talking about. I have no suggestion for how to provide what I think I want, no reason to believe that there is a solution at all, and for that matter no certainty that what I think I want is what I actually want. Let me again be clear that I’m talking out of my ass here.

That being said, my ass is reasonably intelligent as asses go. So it did have one thought: what if we could do a similar trick to what’s done in the ST monad, establishing sort of a sandbox for a computation:

runST :: (forall s. ST s a) -> a

The phantom type s defines the region we’re working in, so for some STRef s a, it can only be referenced within a particular runST. What if we could similarly define a region in which we can guarantee that certain values will not be forced? I’m picturing something like:

data Lazy l a -- "lazy region" monad
runLazy :: (forall l. Lazy l a) -> a

data LazyRef l a -- "lazy reference"
newLazyRef :: a -> Lazy l (LazyRef l a)
modifyLazyRef :: LazyRef l a -> (a -> a) -> Lazy l ()

You’d create a lazy ref for values that you want to guarantee you never read, and the only thing you can do with these refs is modify their eventual values. I don’t know, though… this doesn’t seem right. Hit me up on Twitter or something if you have any ideas.


Update: Tying the knot is for jerks. Any code that requires lazy evaluation not merely for economy but for correctness is too brittle for practical use. Laziness is awesome, and some algorithms are far more elegantly expressed lazily than strictly, but all these knot-tying shenanigans have persuaded me that optional laziness (à la Scala’s lazy val) rather than optional strictness (à la Haskell’s seq or bang patterns) is the correct bias for most problems.

Tagged ,

Tying the Knot, Redux

tl;dr: Use RWS and feed the W to the R for great justice.

A few weeks ago, while working on a side project, I went through some epic gyrations with the help of Stack Overflow, trying to figure out a good way to tie a particular kind of “knot” in Haskell. A bit of background first:

In an imperative language, where mutable data structures are common, if you want to build a data structure containing cycles (such as a circular linked list), you typically construct your nodes and then fix up the links after construction. For example:

public class Node<T> {
  private final T value;
  private Node<T> next;

  public Node(T value) { this.value = value; }
  protected void setNext(Node<T> next) { this.next = next; }
}

Node<Integer> n0 = new Node<Integer>(0);
Node<Integer> n1 = new Node<Integer>(1);
n0.setNext(n1);
n1.setNext(n0);

Fine, this was Java, so you got what you paid for. Let’s say you want to do this in Haskell now, in which data is immutable (unless you do some shenanigans with STRefs, for example). You’d declare your data type:

data Node a = Node {
  value :: a,
  next  :: Node a
}

And you can, as if by magic, write:

let n0 = Node { value = 0, next = n1 }
    n1 = Node { value = 1, next = n0 }

Of course there isn’t any magic occurring here; I don’t believe in magic. There are two behaviors at work:

  • First, let bindings are recursive, meaning that variables declared and bound within a single let block can all reference one another regardless of order. In other words, the variable name n1 is in scope for the declaration of n0 (and vice-versa, of course).
  • Second, expressions in Haskell are evaluated lazily by default. When we declare let n0 = Node 0 n1, it merely promises that when somebody needs the value of n0, it will be computed as a node containing the integer 0 and referencing the node n1, whatever that ends up being. We know that there is a node named n1, because (as discussed above) it was declared within the same let binding, but we don’t care about its value until the point when somebody eventually “forces” it.

These are very different from a typical imperative language, in which you’d expect a statement like to construct a node immediately and blow up, because n1 is “uninitialized” or “null” or some such nonsense. Anyway, this is a simple form of a technique called tying the knot. If you want to declare a bunch of interdependent variables, comprising some sort of recursive data structure, then declare them all in a single let binding, make sure nothing prematurely forces their strict evaluation in the scope of the let, and you’re golden.

But what if you’re trying to build up a big, possibly cyclic data structure based on some user input? You’re going to be doing some sort of parsing, probably using monadic parser combinators or something similar, and because your “knot” depends on user input, there isn’t any obvious way to structure your code such that the knot is tied in a single let binding. This problem was the essence of my thrashing and flailing about on Stack Overflow.


Let’s talk about monads for a minute. I won’t get into much detail on this, as it’s sort of a separate large-ish topic, but I want to introduce the Reader, Writer and State monads for anybody who’s not seen them before:

  • The Reader monad, sometimes called the Environment monad, simply lets you ask for some bit of immutable “global” state in the midst of a computation. For example:

    printenv :: Show r => Reader r String
    printenv = do
      env <- ask
      return (show env)
    

    This example is simplified in applicative style:

    printenv :: Show r => Reader r String
    printenv = show <$> ask
    

    But whatever. Question: how is this different from regular function application?

    printenv :: Show r => r -> String
    printenv env = show env
    

    Answer: it’s not. The map and >>= operations just represent function composition and application. You provide the function’s argument when you run the monad, and that argument is what ask gives you. That is all.

  • The Writer monad sounds intuitively like it should be the opposite of Reader somehow, but it’s probably best understood as its own separate thing. So never mind the fact that it has a function called tell (the obvious counterpart to ask)! Writer gives you something like a stream you can output to in the midst of a computation. To be precise, that stream can be any monoid, but just for an intuitive real-world example let’s say it’s a list of strings representing some logging information. For example:

    log :: Show a => a -> Writer [String] ()
    log a = tell [show a]
    

    Show and tell, nice.

  • Finally, Reader and Writer provide a good way of isolating their respective effects from some other stateful monadic computation. We have a number of common monads representing computations that may not be idempotent or referentially transparent, such as IO and ST, but one of the simplest and most common is State. So let’s roll with that.

    preincrement :: State Int Int
    preincrement = do
      i <- get
      put (i + 1)
      return (i + 1)
    
    postincrement :: State Int Int
    postincrement = do
      i <- get
      put (i + 1)
      return i
    

    Here we’re emulating the unary ++i and i++ operations from languages like C. The get and put functions are sort of the primitive operations to read and write the State. For fun, we can simplify these further using a common helper, modify, and applicative style (thanks to Reddit user LordGreyhawk for the comment):

    preincrement = modify (+1) *> get
    postincrement = get <* modify (+1)
    

Now, Reader, Writer and State are three great tastes that taste so great together, that there’s another monad called RWS which simply lumps them into a single type. For example, we can write:

type Contrived a = RWS Int [Int] Int a

contrived :: Contrived ()
contrived = do
  env <- ask         -- read from the fixed environment
  s0  <- get         -- grab the current state
  let s1 = s0 + env  -- increment the current state by the environment value
  put s1             -- update the state to the new, incremented value
  tell [s1]          -- log the new value

Finally, you probably want to run one of these things eventually, which looks like:

runRWS :: RWS r w s a -> r -> s -> (a, s, w)

This is the combination of runReader, runWriter and runState:

runReader :: Reader r a -> r -> a     -- consume a reader environment, produce a value
runWriter :: Writer w a -> (a, w)     -- produce a value and some writer output
runState  :: State s a -> s -> (a, s) -- consume an initial state, produce a value and final state

In other words, running an RWS computation consumes a reader environment and an initial state, and produces both a value, a final state and some writer output.


Okay, monadic digression time over. This all turns out to be very convenient for knot-tying in general: all we need to do is feed the writer output back into the reader environment. Doing so, exploiting lazy evaluation, makes it so that you can indirectly reference your eventual output before you have produced it! The Ouroboros in question looks like this:

type Knot k s a = RWS k k s a

tie :: Knot k s a -> s -> (a, s, k)
tie knot s0 =
  let (a, s1, k) = runRWS knot k s0 -- this is fucking interesting
  in (a, s1, k)

First, we say that Knot is a type synonym for an RWS monad, in which the reader and writer types are declared to be the same k thing. We haven’t talked yet about what might be a useful concrete type for k; we’ll get to that shortly. Next, tie takes a Knot and some initial state, and just like runRWS, it produces a triple containing some output value, the final state, and again one of these k things.

So check out the let binding: we call runRWS, which produces a triple containing a value k as its writer output. And what parameter do we pass as the reader environment for runRWS? Aha: k again. This is how we feed the snake its tail.

Note that if you’re feeling sassy, you can also implement tie using the fixed-point combinator:

tie :: Knot k s a -> s -> (a, s, k)
tie knot s =
  fix $ \ ~(_, _, k) -> runRWS knot k s -- this is severely fucking interesting

Now, let’s try to figure out an appropriate concrete data type for k. There’s no single correct answer for this, it depends on the problem you’re trying to solve, but let’s figure one example out just to get some satisfaction here.

Take our circular linked list example from before. I’ll simplify it just a little bit here, and add a Show instance so we can see what happens when we run our stuff:

data Node = Node {
  value :: Int,
  next  :: Node
} deriving Show

Okay, now we want to parse a list of pairs of Ints into our structure. For example, we want [(0, 1), (1, 2), (2, 0)] to be equivalent to the following code:

let n0 = Node { value = 0, next = n1 }
    n1 = Node { value = 1, next = n2 }
    n2 = Node { value = 2, next = n0 }

Since the second component of each pair is referencing some other node by its list offset, this means we need a Map from list offsets to the nodes that will eventually be found there. The Map will be our k type for this example. We’ll write to this map (which is conveniently a monoid) using tell, and query it using ask. We’ll also want some state to keep track of what our current offset is and what raw data we have left to parse. Let’s do this:

data ParserState = ParserState {
  current   :: Int,
  remaining :: [(Int, Int)]
}

type NodeParser a = Knot (Map Int Node) ParserState a

So far so good…

parse :: NodeParser ()
parse = do
  s <- get
  case remaining s of
    [] -> return ()
    ((val, ref) : rest) -> do
      m <- ask
      tell $ Map.singleton (current s) (Node val $ m ! ref)
      put  $ ParserState (current s + 1) rest
      parse

We get the current state and see how much input we have remaining. If we’re done, we’re done. Otherwise, pull the current node’s value and reference to the next node off of the list. Look the reference up in our map (which we will have constructed by the time we’re done) to find the next node, and write the newly constructed current node to the writer output. Update the state and recurse.

Finally, let’s feed this thing some data:

example :: Node
example =
  let (_, _, m) = tie parse $ ParserState 0 [(0, 1), (1, 2), (2, 0)]
  in (m Map.! 0)

main :: IO ()
main = putStrLn $ show example

And we get an infinitely recursive traversal of our three-node, circularly linked list:

Node {value = 0, next = Node {value = 1, next = Node {value = 2, next = Node {value = 0, ...

Awesome.


Prologue: Two quick comments as I wrap up here.

  1. This was obviously a toy example. It would be much more realistic to be accepting input from some external source such as a file, in which case your input is monadic. The Knot monad can be easily adapted into a KnotT monad transformer, on top of whatever underlying monad is needed (e.g. IO). Just implement it in terms of RWST instead of RWS.

  2. I demonstrated knot-tying here in the context of parsing, but it works just as well in the context of serialization. The Map in that case is flipped: you need to look up the offsets at which each Node will eventually be stored, before they have necessarily been written there. This requires a bit of care to ensure that you don’t force strict evaluation of these offsets while writing. That also probably means you can’t do any nice output buffering performance tricks, but I’ll just say “whatever” to that for now.

Tagged , , ,

The Aerodynamic Drag – Type Inference Analogy

Okay, so. Welcome to my new blog.

I’m going to start this whole thing off with an odd analogy that I’ve had in my head for a little while now. I’m going to attempt to make some sort of point about type systems and type inference, and I’ll probably end up bashing Scala somehow. Here goes.

Let’s say you’re flying an airplane. Even better, let’s say you’re a student pilot, learning to fly an airplane. At some point, your instructor sits you down, says “let’s talk about drag,” and draws a graph looking something like this on the whiteboard:

Your flight instructor explains that there are two types of aerodynamic drag that affect small planes like the ancient, busted-ass little Piper you’re training in. One is called parasite drag, otherwise known as form drag or skin friction. It’s sort of the obvious one: the faster you attempt to fly, the more air resistance you face. Parasite drag is proportional to the square of the aircraft’s velocity. The other drag force is called induced drag, and is probably slightly less obvious: the slower a plane flies, the more wingtip vortices it generates due to redirection of airflow. Induced drag is inversely proportional to the square of velocity.

The important part here is that your total drag is the sum of the two. So if you look at the graph, you can see that there’s some velocity at which your airplane flies most efficiently, that is, with a minimum of drag. If you try to fly faster than this airspeed you’re fighting parasite drag, and if you try to fly slower you’re fighting induced drag. This optimally efficient airspeed has many names, but is often referred to simply as “best glide speed”: flying so as to minimize drag will take you the furthest distance in the event your crappy little engine dies.


What the fuck does this have to do with type systems? Right.

Let’s say your flight training budget dried up, and you grudgingly went back to the software industry. You are tasked now with evaluating which programming language might be good for a project, resulting in optimal developer productivity. You figure it’s important to choose a programming language with a strong, static type system (you still have a bit of PTSD from your Perl days, before you took up flying lessons), but you also know that there are many statically typed languages to choose from. Now, since productivity is naturally measured in dollars per keystroke, you want to minimize the number of keystrokes needed to bring in the dollars. Thus your ears perk up when I tell you that type inference is the secret to minimizing keystrokes.

Now I take you into a conference room and show you this graph:

There are two kinds of type annotations a developer has to manually, explicitly provide in a program: annotations due to a language’s lameness, and annotations due to a language’s awesomeness.

  • Languages with type systems that aren’t very powerful or expressive, such as Java (at the left of the graph), force you to write a lot of lame, obvious type signatures in your code. These are type signatures that, you figure, the compiler should be able to figure out for you, but it stubbornly refuses. For example:

    public static Map<Foo, Bar> makeMap() {
      Map<Foo, Bar> m = new HashMap<Foo, Bar>(); // I hate you so much.
      return m;
    }
    
  • On the other end of the spectrum, languages with type systems that are extremely powerful and expressive—dependently-typed languages (at the right of the graph, marked “dt”) such as Agda—also force you to write a lot of type signatures, because the compiler would never be able to infer correct types on its own. Type-checking in these languages is hard enough, type inference is undecidable. For example:

    not : Bool -> Bool
    not true = false
    not false = true
    

    One would figure that the Agda compiler could figure out the type of not based on its simple definition, but nope. An algorithm that could figure it out would absolutely fall flat on a dependent type.

So what about languages towards the middle, where the amount of both lameness-induced type annotations and awesomeness-induced type annotations is minimized? Well, it’s my belief that Hindley-Milner type systems (with Damas-Milner type inference) is basically the sweet spot. In other words, Haskell and ML are “just right.”

Somewhat toward the “lameness” side, you have Haskell 98 with its monomorphism restriction (see “mmr” on the graph), which prevents us from saying something like:

bind = (>>=)

without an accompanying type signature:

bind :: Monad m => m a -> (a -> m b) -> m b

Somewhat toward the “awesomeness” side, maybe, you have Scala’s object-oriented subtype polymorphism, which buys you things like simple heterogeneous collections:

class Pet { abstract def speak: String }
class Dog extends Pet { val speak = "woof" }
class Cat extends Pet { val speak = "go away, i do not require you" }
List(new Dog, new Cat) map { _.speak } // conveniently inferred as List[Pet]

To emulate this dynamic dispatch in Haskell, you’d need existential types which are a fair bit more cumbersome, and not standard in the language. That being said, here comes the Scala bashing I promised earlier: this kind of polymorphism absolutely ruins type inference, for not much benefit. It prevents inference entirely in certain scenarios, and leads to undesirable inferences in others. So although Scala’s type system is indeed more powerful than that of Haskell or ML, I wouldn’t call it more useful, thus its litany of required type annotations are actually lameness-induced and I need to reconsider the layout of my chart.


Okay, this is probably all a ridiculous analogy, but I’ve gone to the trouble of writing it up with pictures and all, so I’m sticking to it. The moral of the story is that languages with principal types—informally, languages in which suitable types can always be inferred for any well-typed expression—are the working software engineer’s “best glide speed.”

Tagged , , , ,