Posted in July 2012

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 , , , ,