Why isn’t Crux a pure functional language?

Nicolas Hery asked on Twitter: “[Why isn’t Crux] pure like Haskell/Elm/etc.?” Good question, and one worth writing about.

First of all, the term “pure functional language” isn’t terribly enlightening. It’s certainly not useful for communication, because everyone has or invents their own definition on the fly.

There are a few independent ideas here: mutable vs. immutable data structures, mutable vs. immutable names/variables, and whether effects are tracked.

Regarding mutable vs. immutable data structures: in reality, mutable data structures are simply unavoidable. At some point you need to update your in-memory representation. There are ways to encode that with immutable data structures, but they get awkward fast. In addition, constantly producing new immutable values places a great deal of pressure on the garbage collector – often it’s fastest just to update your data in-place. Immutable data is a fantastic tool, used appropriately, but it sucks when it’s a straitjacket.

Regarding mutable vs. immutable local variables: imagine you want to sum up the elements in an array. If Crux were pure-functional, that
could be written something like:

fun sum_(list, index) {
  if index >= len(list) {
    0
  } else {
    list[index] + sum_(list, index + 1)
  }
}
fun sum(list) {
  sum_(list, 0)
}

Oh wait, that’s not tail-recursive, so it’ll blow up the stack with a long enough list. Let’s rewrite it:

fun sum_(list, index, total) {
  if index >= len(list) {
    total
  } else {
    sum_(list, index + 1, total + list[index])
  }
}
fun sum(list) {
  sum_(list, 0, 0)
}

OK, now we’re tail recursive. For efficiency, however, the compiler needs to turn that into a tight loop of instructions, storing the accumulators in registers. Wait, so you’re saying the language forced me to translate a simple imperative function (sum the elements in a list) into a tail-recursive loop, which the compiler then has to convert back into imperative code for efficiency? Why can’t the compiler just turn my natural imperative loop into a tail-recursive implementation, if that’s what it really wants? (It definitely could.) And it gets even worse the larger your functions become, especially if they have early exits and multiple “mutable variables”. In short, tail calls are great, when appropriate, but always programming with tail recursion is like someone rejecting all your commits with “Nope, you must contort your code for my pleasure.” And I shudder to think of what a tail-recursive implementation of a huge interpreter loop with lots of mutable variables would look like.

Tail calls are great, but being forced to write tail-recursive loops is dumb and one of my biggest annoyances with Haskell. Instead, why not just write:

fun sum(list) {
  let mutable total = 0
  for i in list {
      total += i
  }
  return total
}

Crux makes that natural.

However! Everything I said above is independent of what the defaults are. Crux variables and values are immutable by default, since that’s the common case. Sum types are always immutable. The only things that can be mutable are record fields and locals, but, again, you must opt into that functionality. It’s not annoying in practice; since everything’s an expression in Crux, there’s less need to mutate locals.

Okay, so instead let’s presume that most people consider pure functional to mean “has restricted side effects”, like Haskell.

Personally, I’m a huge fan of monads in Haskell, and the amazing
things they enable.

However, they come at a large cost: since nearly everything is a Monad, the error messages get really complicated, especially when the compiler thinks you meant the Maybe monad or a function monad. (Isn’t it crazy how, in Haskell, Integers aren’t a Monoid by default, but all functions are Monads?)

Eventually I’d love Crux to have an effect tracking system. Different syntax between pure code and effectful code is unacceptable, so the Haskell approach is a no-go. I am excited, however, about row-typed effect systems like Koka. (Notably, it should be okay for pure functions to use mutable locals, like the sum function above.) Future work!

To summarize, I think we can achieve most of the benefits of “pure functional programming” while retaining accessible syntax and allowing mutability as desired and convenient.

The Story of Haskell at IMVU

An interesting blog post and its corresponding comment thread on Hacker News made me realize that, while I’d told the story of Haskell at IMVU to many people, I’d never written it down. :)

IMVU’s backend had been written in PHP from the beginning. Startup code is always gross, but after years of learning PHP’s ins and outs, we bent it to our will. Part of me looks back and says “It wasn’t that bad”, and indeed, it has a lot of great properties. But then I remember the horror.

The terrible straight-line performance, the lack of concurrent IO, the insane memory usage… Once the codebase reached about a million lines, the latency on our REST service response times was over half a second and in the worst case several seconds. For some types of services, that’s okay, but IMVU strives to be a real-time, delightful experience, and service latency on interactive things like dressing up, browsing the catalog, sending messages to your friends, and shopping is really important.

Some of the performance-minded of us tried to get PHP to be fast, but it was basically intractable, and we couldn’t afford to fork PHP with a high-performance JIT like Facebook ended up doing years later.

The combination of PHP’s awful performance, terrifying pitfalls, and the fact that millions of lines of code in a dynamic language (even with copious test coverage) makes it really hard to refactor, led us to evaluate alternatives. Someone suggested Java (which would have been totally fine in hindsight) but the infrastructure team decided to adopt this newfangled Node.js thing. Node sucked. This predated ES6, promises, and the rich ecosystem of npm, so we spent far too long rebuilding basic, basic, infrastructure (like propagating stack traces across async operations) in Node that we already had in PHP, and it still wasn’t as good. In the end we decided to drop Node and stick with PHP.

Fast forward a year or two…

There were some people at IMVU who had dabbled with Haskell, but it always seemed too idealistic and not very practical. In fact, one weekend, Andy went home with the explicit goal of proving that Haskell was stupid and not good for writing production software.

He came back on Monday glowing. “Haskell is perfect for web services! We should use it! It’s fast and safe and concurrent!” We smiled and nodded (sometimes Andy gets enthusiastic about new things) and went on with our daily work. But in the evenings and weekends he plugged away, and built a prototype web service that was 1) dramatically faster than the corresponding PHP services 2) actually quite short in implementation and 3) surprisingly clear. Huh, maybe this Haskell thing did have legs.

OK, so let’s consider the possibility that Haskell could be something IMVU could adopt. How we would vet it?

We started by, during the next hack week, forming a small team of everyday engineers to learn Haskell and work on a feature. We learned two things: teaching Haskell was a nontrivial problem. BUT, Haskell newcomers hacking on the codebase only caused one regression, and that regression actually exposed a bug in some of our infrastructure. Well that’s pretty cool. For years, IMVU had a tradition of throwing new engineers into the deep end, after which they’d invariably take down the site, and then we’d demonstrate that we’re egoless and all failures are an opportunity to improve our process with a postmortem. What if Haskell could help us avoid some of these problems?

Over time we slowly ramped up Haskell within the company. At first we had growing pains. The infrastructure in our PHP stack was extremely mature and well-baked. The corresponding infrastructure in our Haskell (error reporting, DB access, unit testing) was not. It took us a while to sort out exactly what our Haskell best practices would be, and by that point a few people started to get a negative vibe about Haskell. But we kept pushing forward.

(By the way, I keep saying “we”, but at this point I hadn’t written any Haskell yet, and was not particularly for or against it, even though I did think PHP was terrible.)

By this point we’d shipped at least two sets of mobile services on Haskell, and many people considered it a success. However… Tensions about Haskell had really started to heat up, with some people saying things like “I never want to even look at Haskell again” or “at this stage in my career I don’t want another programming language” or “I think we’re making a horrible mistake by building another stack, especially in Haskell.” People were complaining to their managers, and the managers were coming to me. Some people loved Haskell, some people hated it, but very few were in the middle.

As a neutral third party, and as someone with a lot of respect in the organization, the engineering managers sent me out to gather ground truth. I took my little black notebook and a pen and interviewed something like half the engineering team on their opinions on Haskell, whether they were fans or not. I spent an hour with each person, asking what they liked, what they didn’t like, what they thought we should do, etc.

I then collated all the feedback and presented back to the engineering managers and leadership team (of which I was a part too, but since I had no direct reports and had no experience with Haskell at IMVU, I was fairly unbiased). I don’t have my report handy, but it went approximately like this:

75% of the people I interviewed were positive about or fine with Haskell.

25% of the people had major concerns. The concerns, in roughly decreasing priority, were:

  • Haskell strings suck
    • Specifically there’s a lot of cognitive overhead in switching between the five common string representations as needed
  • Syntactic concerns
    • Haskell’s syntax is iconoclastic: parens, $, /= instead of !=
    • some people in the Haskell community love point-free style
    • cognitive overhead in switching between pure and monadic style
    • let vs. where
  • concerns about a second backend stack
    • duplicate infrastructure across PHP and Haskell
  • concerns about it not being a mainstream language
    • teaching the whole organization
    • interaction between Haskell experts and novices sometimes leaves the novices feeling dumb or inadequate
    • bus factor to organization on key infrastructure
    • Haskell is less debuggable by ops engineers

The wins were:

  • GHC’s support for safe concurrent programming is world-class
  • Sound type safety led to refactoring being a breeze
  • Fun, stretches the mind (for some people)

Ultimately, we settled on a middle ground. We would not deprecate PHP, but we would continue to support Haskell as a technology stack. We had specific services in mind that needed high throughput and low latency (<100 ms) and we knew that PHP could not achieve those. That said, we respected the fact that several engineers, even those in leadership roles, put their foot down and said they didn’t want to touch Haskell. (From my perspective it was kind of a weird experience. Highly-skilled people that I respect just got really angry and irrational and basically refused to even try to learn Haskell, which resulted in a culture divide in the company.)

In the end, I never did manage to convince some of my peers to try it. That said, there were many engineers who loved Haskell and we built a great deal of critical infrastructure in it. The Haskell infrastructure basically hums like a well-oiled machine. Perfectly reliable unit tests. Concurrent batched IO. Abstractions for things like timeouts and running tasks on other threads while correctly bubbling failures. Fantastic support for safely encoding and decoding JSON. One of the best benchmarking tools I’ve ever used.

Since one of the biggest concerns about Haskell was education, I taught a sequence of four or five classes for the engineering team with my take on how it should be taught. Traditional Haskell materials tend to talk about laziness and currying and all this FP junk that is certainly interesting and different, but mostly irrelevant to people trying to come in hot and get the job done. Instead, I focused on specifics first, and then generalizations.

“You know how you can add two integers and get a new integer back? Well, you can also add two floating point numbers. Int and Float are instances of Num.”

“You know how you can concatenate strings? And concatenating with the empty string gives you the same value? It turns out many things satisfy these properties. They’re called Monoids.”

“You know how you can map across a list? We do it all the time in PHP or Python. Well you can also map across Maybe. Think of Maybe as a list that can have either zero or one element. Things that can be mapped are called Functors.”

etc. etc.

We started with specific examples of how to do stuff with Haskell, then talked about type classes, and the final optional class was about how Haskell is compiled down to the machine. You’d have to ask the attendees how much they remember, but the classes were well-reviewed at the time. :)

In summary, I definitely wouldn’t say that Haskell was a failure. GHC is an amazing piece of technology, and IMVU built infrastructure in it that wouldn’t have been possible in PHP. I also can’t say Haskell was a resounding success. I was truly disturbed by the culture drama that it brought. And, frankly, saddened and confused by how some people closed their minds. Personally, I would have happily traded a lot of Haskell’s safety for avoiding drama. I sometimes wonder what would have happened had we chosen Java instead of Node.js back in 2010. We could have hit our performance goals in Java too.

Oh well. Many of us still love Haskell. It’s not going away. I left IMVU last year (needed some more experience elsewhere) but I personally miss Haskell a great deal. If I were starting a new project with people that I trusted, I’d definitely reach for Haskell first. The expressiveness, brevity, and safety let you move extremely quickly, and Haskell is definitely mature enough for production use.

Designing Crux – Import Statements

Manipulating a module’s import list is a high-frequency activity in modern programming languages. Sadly, few popular languages perfect the usability of the import list.

To do a good job in Crux, let’s start from the use cases, roughly sorted by importance:

  • import a module and refer to it by a qualified import name
  • import a list of names unqualified into this module’s scope
  • import everything unqualified into this module’s scope
  • import a module solely for its side effects, without importing any symbols
  • visually scan the import list
  • sort the import list (with Emacs’s sort-lines or the like)
  • and, of course, tools must easily parse the import list

Designing for usability means optimizing for the most common use cases, while making sure the less common use cases are still possible.

The most common use case is to import a module and refer to it qualified. Consider this hypothetical syntax:

import fs.path
path.combine("/usr", "local")

The qualified import reference (here, path) defaults to the last segment of the module name. Now, for this to work well, the basename has to be short, distinct, and meaningful.

Haskell gets this wrong.

import qualified Data.ByteString as BS

From left to right: import qualified is long to start with. Then you have most packages in some kind of arbitary namespace like Data. Then, since ByteString is too long to be convenient (especially with the mixed case), people typically name the import BS. Typically being the key word. Sometimes people name it Bytes. Sometimes ByteString. Sometimes B. Sometimes Data.ByteString.Char8 is imported as BS. The fact that the programmer has to make a choice here naturally leads to inconsistency.

Go does a great job here. In Go, you import like this:

import "fs/path"

Afterwards, path functions can be accessed as path.Function. Short and meaningful.

Go goes even further and provides guidelines for naming functions in the context of a module. Conventions tend to be copied, so by setting a good standard early on, Go positively affected every project built then on.

ES6 modules are also pretty interesting. They are statically analyzable and syntactically lightweight, but they have a fairly significant problem at scale: sorting imports.

import Dispatcher from 'flux/dispatcher';
import {foo, bazzle} from 'app/utils';

The problem with having the list of imported symbols first is that they can’t easily be machine-sorted. Every ES6 project I’ve worked on has encouraged its engineers to sort the imports by hand. Also, the import list coming first gets annoying when import lists are long.

import {
  foo, bar, baz,
  qux, harf, barf,
  hurp, floop
} from 'my_module';

With Crux, we learned from all of the above import systems and came up with something that meets every use case. Here is the proposed syntax:

import {
  bytes,
  flux.dispatcher,
  my_encoding_system as mes,
  imported_only_for_side_effects as _,
  utils(foo, bar, baz),
  more_utils(
    foo2,
    bar2,
    baz2,
  ),
  all_the_utils(...), // import everything into scope
}

The easiest import syntax is most common one, but other types of imports, like renaming the import or importing some symbols unqualified, are straightforward too.

This directly satisfies all of our use cases!

We may change our minds and make the commas after each import optional in the future.

Side Note: Implicit vs. Explicit Imports

OCaml and Java allow qualifying names at their use sites, making import statements unnecessary. Import statements are syntax sugar at that point. I don’t have a strong justification here, but Crux went with explicit import statements (like Go, Python, Haskell, ES6) because it’s easier for humans and machines to see a module’s dependencies at a glance.

Designing Crux – Methods

Crux’s foundations are rooted in the ML language family. Everything is a function. Haskell has this property too, but there is a really sucky aspect of an everything-is-a-function world.

Imports.

Here’s a common experience I have with Haskell:

let url = getCustomerUrl myCustomerId

OK, I have a string.

I need to check if it starts with “https://”

Scroll to top of file… That means I need to call the startsWith function. What module does it live in again?

Think… is this a Text or a ByteString? Or maybe a String? That determines which module I import…

This is a very common bit of friction, and it comes up all the time in Haskell, both for the standard library and your own code.

Now let’s hypothesize what reading from a data store might feel like in a world with explicit imports:

OK, my React component has an env prop.

I know the UserStore is on the env, but I need to import the Environment module to call getUserStore:

let userStore = Environment.getUserStore(env).

Now I want the list of users, so import UserStore and:

let users = UserStore.getUserList(userStore)

I can see it now: “Why can’t I just write let users = env.getUserStore().getUserList()? Crux sucks!”

In addition, assuming a roughly-one-type-per-module structure, each type gets two “names” that must be used: the module name and the type name. If types are refactored to live in different modules, all the callers have to be updated with new imports. Finally, if those names diverge, it could get confusing.

Dynamic languages like JavaScript and Python solve this usability issue by implementing all method calls with dynamic lookup. Besides the obvious performance hit, this can make analyzing the call graph nontrivial — both by humans and tools.

Languages like C++ and Java and Go take a different approach: they make methods a first-class concept. This adds some complication to the language when you want to use a method as a normal function. C++ has adapters that let you use members as functions sometimes but it’s nicer if methods are just functions.

Crux is not an object-oriented language, but we want the usability benefits of “method syntax”, sometimes known as type-directed name resolution:

  1. with no dynamic dispatch
  2. without any specialize method concept — methods should just be normal functions
  3. and, importantly, while still supporting bidirectional type inference for record types

The reason we have to worry about a conflict with type inference is because records already use dot syntax. Consider the following function:

fun distance(start, end) {
  return sqrt(sqr(end.x - start.x) + sqr(end.y - start.y))
}

Notice no type annotations! The distance function is inferred to take two records, each of which has floating point x and y properties. It returns a float.

Since we think it’s important that . syntax be used for records, Crux uses an arrow -> for method calls. Method calls only work when the type is known. Fortunately, in most programs, the type inference engine already knows the concrete types of most things. If you try to write a function like:

fun isHTTPSURL(url) {
  return url->startsWith("https://")
}

you will get a type error, since it doesn’t know what url is. The fix is easy: provide a type annotation on the argument:

fun isHTTPSURL(url: String) {
  return url->startsWith("https://")
}

In practice, most of the time, the type is known from context. Let’s go back to the Flux UserStore example. With method syntax, it would be spelled:

let users = env->getUserStore()->getUserList()

-> is mainly a way to avoid imports. a->b() can be read as “assuming the type of a is known, look up the symbol b in the module that defined a, and call b(a)”

The env example works because the type of env is known. Therefore, the location of the getUserStore() function is known, and it’s known to return a UserStore, so getUserList is looked up there. No type annotations required, there’s nothing special about member functions, and we achieve all the performance and tooling benefits of static dispatch!

One note: for simplicity, we have been applying the rule that the type must have been inferred before the method call is resolved. Technically, this is more restrictive than necessary. Consider the following example:

fun addSuffix(p) {
  if p->endsWith(".json") {
    return p
  } else {
    return p + ".json"
  }
}

The p + ".json" expression proves that p’s type is String, and therefore p->endsWith(".json") could be resolved. However, supporting this kind of backwards knowledge transfer would complicate the compiler (I think). Perhaps we’ll look into fixing it later. :)

Another note: sometimes you simply want to reference a “member function” without having a particular instance in mind. You might have the type name in scope, but don’t want to bother importing. We’ve considered support syntax like &String::startsWith to reference the startsWith function in the module that defines the String type. It could be useful in situations like ["foo", "bar", "baz"]->map(&String::length).

Two Kinds of Servers

Occasionally I overhear (or get sucked into) an argument that goes like this:

“Go is the best language for writing servers because X.”

“No, you neanderthal, Haskell is, because Y.”

“Well I’ve never needed Y! And Haskell is too out of touch with real problems.”

“But how can you tolerate such a limited and poorly-designed tool?”

“Well, I like to use it and I get stuff done, so what do you care?”

Rarely do these types of discussions change anyone’s mind. :)

People will argue all day long in a vacuum about what languages is best, but languages are tools and proper evaluation of a tool must be tied to a concrete context. Thus, the subject at hand: there are two types of servers. Specialized single-purpose servers differ from general business application servers.

Single-Purpose Infrastructure

Single-purpose infrastructure, like databases, request proxies, and messaging systems emphasize latency, throughput, reliability, and efficient use of hardware. Some examples are Redis, MySQL query proxies, and nginx. The choice of programming language matters to the extent that it facilitates the performance and reliability goals of the infrastructure. For these types of servers, Go is actually a great language. With Go, you get performance comparable to the JVM, a bunch of high-quality libraries, and the ability to plop your static binary onto any machine or container.

I’ll share an example from IMVU. IMVU’s primary content delivery system for all user-generated content, including 3D assets and user photos, was served by a pool of Perlbal proxies. This pool of machines served some of the highest traffic for the whole business, but the performance was not good and the code inside Perlbal was hard to maintain. Normally we wouldn’t have cared about the code except that we had discovered some race conditions in Perlbal. One of my coworkers finally got fed up and, within a couple weeks, replaced this entire part of our system with a replacement written in Go. Two machines (hooked up to 10g switches of course) running the Go implementation could serve all of the traffic previously allocated to the entire Perlbal pool. (We ended up running more instances for redundancy, however.) Not only was the new code faster, it was dramatically more maintainable. This was a big success story for Go.

Special-purpose servers usually have only a few skilled authors, clear goals, and eventually reach a point where they’re “done” and further maintenance is increasingly rare. (Though they might eventually be replaced with new infrastructure.)

Application Servers

On the other hand, every company has that server codebase with all the logic that makes the business go. You know the one. Where the code dates back to the founding of the company, and the programming language is whatever the founders liked at the time. :) It’s had hundreds of contributors from many backgrounds. Perhaps the original authors are no longer with the company. The needs of the code have evolved over time with the business, and after about four or five years it’s a person’s or team’s full-time job to manage large-scale refactoring.

I call these application servers, but I’ve heard the term “frontend server” used before too. Performance is a concern, but straight-line code execution is often less of an issue than efficient IO to the backend services.

Application servers are where the features live, and therefore they evolve with the needs of the business. The ability to define safe abstractions and refactor the code is more important than with special-purpose servers. Programming safety is also critical. You wouldn’t want somebody’s hack week feature to turn into a buffer overflow, runtime exception, corrupt data, or security vulnerability. Thus, type systems (or at least runtime invariant enforcement in languages like Python or PHP) are critical in application servers.

Go does not make a good language for application servers. The lack of immutable data makes it really awkward to enforce invariants. The lack of generics makes it awkward to express IO unless you generate code for each entity type in your database. Complicated arrangements of goroutines and channels are necessary to parallelize backend IO. Data structure traversals must be manually spelled out every time. Haskell, on the other hand is brilliant for application servers (assuming your team is comfortable with the learning curve). Libraries like Haxl allow specification of business rules in natural imperative style, while automatically extracting IO parallelism from the structure of the code. In Go, timeouts must be implemented manually every time, whereas in Haskell there is a single, always-correct timeout function. Go also doesn’t have anything like Haskell’s mapConcurrently, and while it can be done manually, it’s tricky to remain correct in the presence of unhandled errors. (In a high-reliability system, you probably want to transfer a runtime error like division by zero or null pointer dereference to your request handler’s error handler so it can be logged appropriately, rather than shutting down your whole server.) With Haskell, you can enforce 100% reliable unit tests or that transactions are never nested.

Even pre-generics Java was better than Go at defining invariants – with final, you could feel confident that a value is never changed after it’s initialized. This entire post by Dave Cheney could have been replaced with one sentence: “Too bad Go doesn’t support constant values in general.”

I’m not saying Go can’t be made to work for application servers, nor am I saying Haskell is necessarily the answer. Haskell has relatively poor usability characteristics, and I may write more about that later. But when you are trying to pick a language for a server, make sure you understand how it’s likely to evolve over time. A small group of people solving a focused problem is a completely different beast from hundreds of people hacking on business logic across years, so choose your language appropriately. :)

Designing Crux – Function Calls

Tupled vs. Curried Functions

Programming languages specify function argument lists in one of two ways: tuples or currying. Most mainstream languages use the former:

function add(x, y) {
    return x + y;
}

The function add takes two arguments. You can imagine the caller building up a tuple of arguments on the stack before calling the function.

Haskell and ML effect multi-argument functions with currying. For example:

add :: Int -> Int -> Int
add x y = x + y

This is equivalent to:

add :: Int -> (Int -> Int)
add x = \y -> x + y

That is, add is a function that takes an Int and returns another function which also takes an Int and returns an Int.

Currying is quite elegant. All functions take one argument, which makes certain types of metaprogramming easy. Curried function syntax is also extremely convenient: map (add 1) [1, 2, 3] returns [2, 3, 4].

However, there are some downsides to curried functions:

The first has to do with knowing when effects occur. In Haskell, where function application is always pure, this isn’t an issue. But since Crux allows unrestricted effects (more on this later), we want it to be obvious when side effects can happen. Consider this snippet of a hypothetical curried language:

add x y =
  print "adding " + toString x + " and " + toString y
  return x + y

Now consider this other definition:

add x =
  print "adding " + toString x
  return \y ->
    print " and " + toString y
    return x + y

Both functions have the same behavior when called like this:

add 1 2
add 1 3

But they would have different behavior with a partial application:

let addOne = add 1
addOne 2
addOne 3

That’s one argument against curried functions, though you could argue it’s a rare issue not worth worrying much about.

However, a more serious issue has to do with consistent performance. Curried languages don’t actually produce new functions for every argument of every call. That would be way too slow. In practice, functions take multiple arguments at the machine-code level (where the number of arguments is their arity), and when the function’s definition is not known at compile-time, some dynamic arity checks are added to decide whether to create a new partially-applied function, call straight through to the implementation, or perform oversaturation.

These dynamic checks add a bit of runtime overhead, and since we want Crux to have obvious execution semantics, we decided not to use curried functions.

Finally, I want to mention a third downside of curried functions: the error messages. At least in Haskell, if you pass too few or too many arguments, you don’t get a very obvious error message.

Prelude> let f a b = a + b
Prelude> f 1 2
3
Prelude> f 1
<interactive>:31:1:
    No instance for (Show (a0 -> a0))
      (maybe you haven't applied enough arguments to a function?)
      arising from a use of ‘print’
    In the first argument of ‘print’, namely ‘it’
    In a stmt of an interactive GHCi command: print it
Prelude> f 1 2 3
<interactive>:32:1:
    Non type-variable argument in the constraint: Num (a -> t)
    (Use FlexibleContexts to permit this)
    When checking that ‘it’ has the inferred type
      it :: forall a t. (Num a, Num (a -> t)) => t
```

Syntax

Syntax is somewhat tangential to the issue at hand, and it’s certainly possible to use the f x y z syntax with tupled functions, but my experience teaching Haskell is that people get unnecessarily hung up on the "f x y z" call syntax and we decided against spending our strangeness budget here.

Conclusion

That was a long justification for saying that Crux’s function syntax and semantics are just like every other mainstream language. :)

fun add(x, y) {
    x + y
}

let four = add(2, 2)

Designing DFPL – The Name (Update)

Previously, I’d talked about the import of a programming language’s name.

I have a quick update on that front. Andy had originally named the project Crux, but we questioned if we wanted that name in the long term. So… when in doubt, run a survey!

I put together a simple survey with some front-runners. Two questions: “Which is your favorite?” followed by “Check all that you’d be okay with.” Crux came in 2nd place for the favorite but it was the one most people were okay with, and since it was the name we already had, we stuck with it. :)

Dropbox Hack Week: GraphQL Server in Haskell

Last week was hack week at Dropbox. I took the opportunity to explore the implementation of a GraphQL server that does optimal IO batching and concurrency.

Serial IO

A common performance problem in the implementation of web services is serial IO. Let’s say you have a service that returns the names of all of your friends. It’s easy and natural to implement it like this:

me = fetch_user_info(my_user_id)
friend_names = []
for friend_id in me.friends:
  friend_names.append(fetch_user_info(friend_id).name)
return friend_names

The problem is that each user info lookup for my friends occurs sequentially. Even with TCP connection pooling, that’s still a packet round-trip in the datacenter. “But that should be faster than 10 ms right?” Even if it is, it doesn’t take many friends to blow your performance budget and send your response time across the threshold of perceptible delay.

Moreover, this problem compounds on itself. If your inner functions have serial IO and you call them in a loop, you’ve just added potentially thousands of round-trips to your backend data sources. I would hazard a guess and say serial IO is the largest contributor to service response latencies.

Manually Batched IO

One solution is to always batch IO. Every function takes a list and returns a list. This can be made to work (indeed, I’ve achieved excellent performance by carefully, manually, batching) but doesn’t compose as your services scale. Sometimes it’s just too hard to know all of the data you will need to fetch, and the dependencies between that data.

OK, so serial IO is bad. More on that in a bit. Let’s talk about REST now.

REST

At IMVU, we went all-in on REST, building a rather substantial framework to make it easy to create REST services. We anticipated the fact that REST services tend to require many round-trips from clients, so we built a response denormalization system, where the service can anticipate the other services a client will need to hit and include their responses too.

This sounded great at first, and in fact was mostly an improvement from the prior state of affairs. But, at scale, REST has some challenging performance problems. For one, REST services have a defined schema, and they always return the data they advertise. As I mentioned, if a service doesn’t return all the data a client needs, the client needs to hit more services, increasing the number of client-to-server round-trips. In addition, because the service always returns the same set of data, it must query the backend database to fetch more data than the client even cares about.

This phenomenon tends to happen most frequently with core domain objects like users. Because users are so important, they accumulate relationships with so many pieces of data (e.g. list of subscribed experiments, contact lists, shopping carts, etc.), almost all of which is irrelevant to most clients.

Why GraphQL?

This is where GraphQL comes in. In GraphQL, the client specifies the data that it wants. There is only one request, even if the data is deeply nested, and the server only has to fetch exactly what’s needed.

Consider the query:

query HeroNameQuery {
    newhope_hero: hero(episode: NEWHOPE) {
        name
    }
    empire_hero: hero(episode: EMPIRE) {
        name
    }
    jedi_hero: hero(episode: JEDI) {
        name
    }
}

It looks up the hero of each of the first three Star Wars movies, fetches any information it needs from the backend, and returns only what is requested:

"data": {
    "HeroNameQuery": {
        "jedi_hero": {
            "name": "R2-D2"
        },
        "empire_hero": {
            "name": "Luke Skywalker"
        },
        "newhope_hero": {
            "name": "R2-D2"
        }
    }
}

There are GraphQL implementations for many languages but many of them don’t solve the serial IO problem I described to start this post. In fact, a naive GraphQL implementation might issue IO per field of each object requested.

For hack week, I wanted to explore the design of a GraphQL server that issued all of its backend IO in optimally concurrent batches.

Why Haskell?

Dropbox doesn’t use Haskell, but I find it to be a great language for exploring design spaces, particularly around execution models. Also, Facebook open sourced their excellent Haxl library which converts code written with serial IO into efficient batched requests. Haxl provides an effect type that, when it can understand that two data fetches are independent, runs them both in parallel. When all Haxl operations are blocked on backend data fetches, only then does it issue the backends. My prototype GraphQL resolvers are surprisingly naive, specified with sequential code. Haxl automatically batches up the requests and hands them to the DataSource for execution.

In addition, there is nothing clever about the GraphQL request handler or graph traversal and filtering — all cleverness is handled by Haxl.

At this point, you might be thinking “So was anything challenging about this project?” On the data fetch side, no, not really. :) However, I did run into one unexpected snag when using Haxl for data updates: because Haxl tries really hard — and in a general, composable way — to run your IO in parallel, you must be careful about how writes and reads are sequenced together. If you leave out the () <- on line 105, Haskell sequences the operations with >> instead of >>=, and Haxl’s >> uses the Applicative bind operation instead of the Monad bind operation, and thus it assumes it can run them in parallel. And, as you might expect, issuing a write and read to the same data concurrently doesn’t end well. :)

Conclusions

I am very thankful for jdnavarro’s excellent GraphQL query parser. With it, in four days, I was able to get a prototype GraphQL server up and running. Using Haxl and Hedis, I have it hooked up to a Redis data source, and it correctly batches all independent IO reads and runs them concurrently.

The Star Wars hero names query above results in two batched backend requests:

fetch star wars batch of size 3:
["FetchEpisode(Jedi)","FetchEpisode(Empire)","FetchEpisode(NewHope)"]
fetch star wars batch of size 2:
["FetchCharacter(1000)","FetchCharacter(2001)"]

You can even see that it noticed that R2-D2 is the hero of both movies, and only requested its info once.

The performance is pretty good: on some AWS instances, I measured about 3500 queries per second per machine and a query latency averaging 3 ms. Of course, that could worsen as permissions checks and so on are implemented. On the other hand, the code is completely unoptimized, full of lazy data structures and an unoptimized parser without a parser cache.

The prototype code is open sourced on the Dropbox GitHub.

It’s probably possible to build something like Haxl in Python with generators, but you’d have to give up standard loops and list comprehensions, instead using some kind of parallel map operation. You also would not benefit from anything that teases concurrency out of imperative functions like GHC’s upcoming ApplicativeDo extension. There are some things that Haskell’s restricted effects are uniquely good at. :)

I’d guess it would probably be even trickier to do a good implementation in Go given that the programmer has less control over goroutines than Python’s generators and Monads in Haskell. That said, perhaps someone will discover a clean, optimal implementation. We should pay attention to efforts like this.

I think GraphQL will be a huge deal for high-performance web services. It’s harder to implement than REST or traditional RPC services, but the reduction in response latencies could be substantial. Naive implementations aren’t going to have good performance, but if you are interested in aiming straight at the finish line, Haskell and Haxl will give you a head start.

Designing DFPL – The Name

Without hard evidence, it’s hard to say how much a language’s name matters, at least beyond basic Googleability.

Marketing has an effect on any kind of product, and programming languages are no exception.  Some names convey their different from other well-known languages, like C++ (an extension of C) or TypeScript (JavaScript but with a type system).  Java, Go, Python, and Ruby, on the other hand, are short, memorable words with neutral or positive connotations.  Bonus points for names that carry a family of associated words, e.g. Ruby and Gem.

Since our language is more of a synthesis of good ideas than a modification to an existing language, a short positive word seems to be the right strategy.

Crux is the first name we tried, though neither of us is thrilled with it.  We briefly tried the name Sneak, but everyone hated it.  Fig is short, neutral-to-positive, but nobody seemed excited by that name either.

Do you have suggestions?

The name affects the file extension, which ought to be short.  (Or am I the only one perpetually annoyed by the horizontal real estate consumed by .java and .coffee?)

Designing DFPL – The Broad Strokes

Why not Python?

I love Python. It’s easy to learn, predictable, and works well for a wide variety of programs. Python’s the first language where I regularly found myself writing programs and having them work on the first try. The problem with Python is that it breaks down at scale.

Performance

In my experience, whenever a Python codebase reaches a couple hundred thousand lines of code, performance becomes an issue. It’s well-known that Python’s straight-line perf is not even close to C or even Java. In addition, Python programs don’t make efficient use of memory: objects are large and sparse — programs consist of a lot of pointer-chasing. The garbage collector’s not great, and startup and module loading times become an issue at scale, especially for short-lived processes like unit tests, build scripts, or desktop applications.

There are Python JIT compilers, but JITs don’t really help with startup time or memory usage.

Parallelism

Python has a GIL, meaning it’s hard to write programs that make efficient use of the hardware. It’s possible to move CPU-bound work into C, but any kind of coordination between Python and C has to ping-pong across the GIL, which becomes a central bottleneck.

Launching multiple processes can help, but each process pays Python’s base process memory usage overhead, and they can’t easily share in-memory caches.

As we’ve seen from Haskell and Go, the ability to have convenient, lightweight, efficient parallelism is a big deal.

Maintainability

I talked about this in The Long-Term Problem With Dynamically Typed Languages. As codebases get huge, you really want to be able to lean on the computer in order to safely make changes. Type systems are mini proof assistants for expressing guarantees like "I never mix up binary data with textual data" or "I always check the case that optional values are empty". Unit tests help, but are "proof by example". Type systems add a meaningful layer of confidence, allowing software to scale to larger teams and faster changes.

Why not Haskell/Go/Rust/Scala/F#/Whatever?

I agree 100% with Patrick Walton here:

There is room for some statically-typed language to occupy the network-services niche where performance needs to be good—maybe 2x slower than optimal (note that this is not acceptable for all network services)—and speed of development trumps most other considerations. Some sort of hybrid of Swift, Rust, and Go, perhaps, as none of them are 100% ideal for this space.

The dynamic language space is relatively saturated at this point. Rust is doing a great job in the native machine performance space. F# and Swift and, to some degree, Scala are excellent choices for the .NET, Apple, and JVM ecosystems, respectively.

But as of yet, there’s nothing great in either the web frontend space or the application server space.

Haskell’s laziness, curried functions, and nonobvious operational semantics are not suitable for frontend code. While it’s an otherwise perfect language for writing application servers, its syntax is tragically divisive, and I have no hope that Haskell as it stands today will become mainstream.

Go’s type system somehow manages to be both verbose and not expressive enough. Go is sufficient for single-purpose servers, but, from first-hand experience, the lack of generics really hurts in application servers. (I probably owe an essay on the difference between the two types of servers.) The Go community tends to rely on idioms, but it would be better if the language was general and expressive enough to allow direction expression of things like timeouts and cancellation. Also, Go is not actually memory-safe. Go is especially frustrating because, if it had, say, generics and tuples instead of the more limited multiple-return-values, it would be a truly excellent programming language.

Rust’s concurrency is not lightweight enough, and the syntax is extremely verbose.

Scala has a significant platform dependency on the JVM. Check out the size of some Scala.js programs. Also Scala’s type system is insanely complex.

F# brings along a large .NET dependency. It also suffers from the ML syntax. (Actually, it has two syntaxes.)

Maybe Swift is great, but it was only just open sourced, and I’d be worried about the Obj-C platform dependency. I’ve yet to write any real Swift programs, but what I’ve seen looks great.

All of these languages are lovely and have their uses, but none are particularly satisfactory replacements for Go or TypeScript/JavaScript. That is, lightweight code that can run at high performance in a browser and on a concurrent, scalable server.

But, hold on, what about js_of_ocaml? This is where things get interesting. Andy used js_of_ocaml for a while and found that, on paper, Ocaml has all the right properties: it’s safe, high-performance, compiles to very concise, efficient JavaScript, expressive, concurrent, established… In fact, it’s nearly perfect… if you can stomach the syntax, that is. As I mentioned previously, at this point I’m convinced that ML-family languages haven’t caught on largely for reasons of taste (or lack thereof — just look at the js_of_ocaml website’s font selection).

The Goals

So what are we trying to do with this thing?

The language doesn’t need anything new or innovative. ML gives us how bidirectional type inference, sum types with pattern matching, and soundness. Haskell gives us overloading (i.e. type classes, i.e. type-indexed values). Go shows us how important a solid experience is, both for the first time and in daily use. Python shows us how it’s possible to connect predictable syntax and solid, composable semantics.

Thus, this is largely a human factors project. Our goal is to see if we can marry all of those things into one language.

Our goals are to have

  • Memory safety.
  • Static typing without heavyweight type annotations everywhere.
  • Language features that are composable.
  • A minimal runtime, with no large platform dependency.
  • Obvious execution semantics. Like imperative languages, you should be able to look at a program and understand its runtime behavior.
  • Tight, clean compilation to JavaScript. Should be a suitable alternative to TypeScript or CoffeeScript.
  • A reasonable replacement for Go or Node on the backend.
  • Cost-free abstractions.

Non-goals

  • C- or Rust-like performance. Rust is already doing a great job there.
  • Support for restricted effects. It’s not clear the usability cost is worth it.

Next time, I’ll either dive into one of the specific design decisions we’ve made, or talk about the language’s overall gestalt or texture.