Software Simply

Dependent Types are a Runtime Maybe

2021-08-26T10:23:00.000-04:00

Awhile back I was discussing dependent types with someone and we ended up concluding that dependent types can always be replaced by a runtime Maybe. This seemed to me then (and still does today) as a fairly surprising and provocative conclusion. So I thought I'd put the idea out there and see what people think.

Let's look at a few examples that are commonly used to illustrate dependent types:

Vectors of length N
Matrices of size m x n
Sorted lists
Height-balanced trees (trees where the height of subtrees differ by at most one)

The argument is roughly as follows. All of these examples ultimately boil down to enforcing some kind of constraint on some data types. The more powerful your dependent type system, the more rich and expressive will be the constraints that you can enforce. If we take this thought experiment to its logical conclusion, we end up with a dependent type system that allows us to enforce any constraint that can be computed.

The important realization here is that every one of the above dependent type examples are a constraint that can also be enforced by a smart constructor. The smart constructor pattern is roughly this:

module Foo

( Foo

, mkFoo

-- Any other functionality that Foo supplies

)

data Foo = ...

mkFoo :: FooInputs -> Maybe Foo

You can express all of the above dependent type constraints using this pattern. VecN can simply hold a vector and the length N constraint can be enforced in mkVecN. Similarly, SortedList can simple hold a list and the mkSortedList can sort its input and/or return Nothing if its input isn't sorted. The smart constructor mkFoo can contain arbitrarily complex Turing-complete constraints and return a Just whenever they're satisfied or a Nothing if they're not.

The key difference between dependent types and a smart constructor is that with dependent types the constraint is enforced at compile time and with a smart constructor it is checked at runtime. This suggests a rule of thumb for answering the question of whether you should use dependent types:

If the cost (TCO...i.e. the sum total of dev time, readability of the resulting code, and all the ongoing maintenance) of using a dependent type is less than the cost of handling the Nothing cases at runtime, then you should use a dependent type. Otherwise, you should just use a smart constructor.

The interesting thing here is that Haskell gives us a fantastic set of tools for handling runtime Nothing values. The Maybe type is has instances of Functor, Applicative, and Monad which allow us to avoid a lot of the code overhead of checking the failure cases and handling them appropriately. It is often possible to front load the checking of the constraint with a case statement near the top level:

case mkFoo inputs of

Nothing -> handleError

Just a -> handleSuccess a

Then all the rest of your code will be working with Foo, which is structurally guaranteed to have the properties you want and allows the use of simplified code that doesn't bother checking the error conditions.

My takeaway from this argument is that you should only reach for dependent types when dealing with situations where you can't front-load the error handling and the cost of having Maybe a's floating around your code exceeds the cost of the dependent type machinery.

What do you think? Am I missing something here? I'd love to see if anyone has practical examples of dependent types that can't be boiled down to this kind of smart constructor and runtime Maybe or where the cost of doing so is exceptionally high.

Setting Up A Private Nix Cache

2018-07-24T02:18:00.000-04:00

I recently went through the process of setting up a private Nix binary cache. It was not obvious to me how to go about it at first, so I thought I would document what I did here. There are a few different ways of going about this that might be appropriate in one situation or another, but I’ll just describe the one I ended up using. I need to serve a cache for proprietary code, so I ended up using a cache served via SSH.

Setting up the server

For my cache server I’m using an Amazon EC2 instance with NixOS. It’s pretty easy to create these using the public NixOS 18.03 AMI. I ended up using a t2.medium with 1 TB of storage, but the jury is still out on the ideal tradeoff of specs and cost for our purposes. YMMV.

The NixOS AMI puts the SSH credentials in the root user, so log in like this:

ssh -i /path/to/your/key.pem root@nixcache.example.com

To get your new NixOS machine working as an SSH binary cache there are two things you need to do: generate a signing key and turn on cache serving.

Generate a signing key

You can generate a public/private key pair simply by running the following command:

nix-store --generate-binary-cache-key nixcache.example.com-1 nix-cache-key.sec nix-cache-key.pub

Turn on SSH Nix store serving

NixOS ships out of the box with a config option for enabling this, so it’s pretty easy. Just edit /etc/nixos/configuraton.nix and add the following lines:

  nix = {
    extraOptions = ''
      secret-key-files = /root/nix-cache-key.sec
    '';

    sshServe = {
      enable = true;
      keys = [
        "ssh-rsa ..."
        "ssh-rsa ..."
        ...
      ];
    };
  };

The extraOptions section makes the system aware of your signing key. The sshServe section makes the local Nix store available via the nix-ssh user. You grant access to the cache by adding your users’ SSH public keys to the keys section.

Setting up the clients

Now you need to add this new cache to your users’ machines so they can get cached binaries instead of building things themselves. The following applies to multi-user Nix setups where there is a Nix daemon that runs as root. This is now the default when you install Nix on macOS. If you are using single-user Nix, then you may not need to do all of the following.

You need to have an SSH public/private key pair for your root user to use the Kadena Nix cache. This makes sense because everything in your local Nix store is world readable, so private cache access needs to be semantically controlled on a per-machine basis, not a per-user basis.

Generating a Root SSH Key

To generate an SSH key for your root user, run the following commands. After the ssh-keygen command hit enter three times to accept the defaults. It is important that you not set a password for this SSH key because the connection will be run automatically and you won’t be able to type a password. You’ll do the rest of the section as the root user, so start by entering a root shell and generating an SSH key pair.

sudo su -
ssh-keygen -b 4096

Next ssh to the cache server. This will tell you that the authenticity of the server can’t be established and ask if you want to continue. Answer ‘yes’. After it connects and prompts you for a password, just hit CTRL-c to cancel.

ssh nixcache.example.com

This has the effect of adding the server to your .ssh/known_hosts file. If you didn’t do this, SSH would ask you to verify the host authenticity. But SSH will be called automatically by the Nix daemon and it will fail.

Now cat the public key file.

cat ~/.ssh/id_rsa.pub

Copy the contents of this file and send your key to the administrator of the nix cache.

Telling Nix to use the cache

In your $NIX_CONF_DIR/nix.conf, add your cache to the substituters line and add the cache's public signing key (generated above with the nix-store command or given to you by your cache administrator) to the trusted-public-keys line. It might look something like this:

substituters = ssh://nix-ssh@nixcache.example.com https://cache.nixos.org/
trusted-public-keys = nixcache.example.com-1:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa= cache.nixos.org-1:6NCHdD59X431o0gWypbMrAURkbJ16ZPMQFGspcDShjY=

Now you need to restart the nix daemon.

On mac:

sudo launchctl stop org.nixos.nix-daemon
sudo launchctl start org.nixos.nix-daemon

On linux:

sudo systemctl restart nix-daemon.service

Populating the Cache

To populate the Nix cache, use the nix-copy-closure command on any nix store path. For instance, the result symlink that is created by a nix-build.

nix-copy-closure -v --gzip --include-outputs --to root@nixcache.example.com <nix-store-path>

After you copy binaries to the cache, you need to sign them with the signing key you created with the nix-store command above. You can do that by running the following command on the cache server:

nix sign-paths -k nix-cache-key.sec --all

It’s also possible to sign packages on the machines that build them. This would require copying the private signing key around to other servers, so if you’re going to do that you should think carefully about key management.

Maintenance

At some point it is likely that your cache will run low on disk space. When this happens, the nix-collect-garbage command is your friend for cleaning things up in a gradual way that doesn't suddenly drop long builds on your users.

Simplicity

2018-07-09T15:48:00.000-04:00

I'm reposting this here because it cannot be overstated. I've been saying roughly the same thing for awhile now. It's even the title of this blog! Drew DeVault sums it up very nicely in his opening sentences:

The single most important quality in a piece of software is simplicity. It’s more important than doing the task you set out to achieve. It’s more important than performance.

Here's the full post: https://drewdevault.com/2018/07/09/Simple-correct-fast.html

I would also like to add another idea. It has been my observation that the attributes of "smarter" and "more junior" tend to be more highly correlated with losing focus on simplicity. Intuitively this makes sense because smarter people will tend to grasp complicated concepts more easily. Also, smarter people tend to be enamored by clever complex solutions. Junior engineers usually don't appreciate how important simplicity is as much as senior engineers--at least I know I didn't! I don't have any great wisdom about how to solve this problem other than that the first step to combating the problem is being aware of it.

Fake: Generating Realistic Test Data in Haskell

2018-03-17T09:20:00.000-04:00

On a number of occasions over the years I've found myself wanting to generate realistic looking values for Haskell data structures. Perhaps I'm writing a UI and want to fill it in with example data during development so I can see how the UI behaves with large lists. In this situation you don't want to generate a bunch of completely random unicode characters. You want things that look plausible so you can see how it will likely look to the user with realistic word wrapping, etc. Later, when you build the backend you actually want to populate the database with this data. Passing around DB dumps to other members of the team so they can test is a pain, so you want this stuff to be auto-generated. This saves time for your QA people because if you didn't have it, they'd have to manually create it. Even later you get to performance testing and you find yourself wanting to generate several orders of magnitude more data so you can load test the database, but you still want to use the same distribution so it continues to look reasonable in the UI and you can test UI performance at even bigger scale.

Almost every time I've been in this situation I thought about using QuickCheck's Arbitrary type class. But that never seemed quite right to me for a couple reasons. First, Arbitrary requires that you specify functions for shrinking a value to simpler values. This was never something I needed for these purposes, so it seemed overkill to have to specify that infrastructure. EDIT: I was mistaken with this. QuickCheck gives a default implementation for shrink. Second, using Arbitrary meant that I had to depend on QuickCheck. This always seemed too heavy to me because I didn't need any of QuickCheck's property testing infrastructure. I just wanted to generate a few values and be done. For a long time these issues were never enough to overcome the activation energy needed to justify releasing a new package.

More recently I realized that the biggest reason QuickCheck wasn't appropriate is because I wanted a different probability distribution than the one that QuickCheck uses. This isn't about subtle differences between, say, a normal versus an exponential distribution. It's about the bigger picture of what the probability distributions are accomplishing. QuickCheck is significantly about fuzz testing and finding corner cases where your code doesn't behave quite as expected. You want it to generate strings with things like different kinds of quotes to verify that your code escapes things properly, weird unicode characters to check encoding issues, etc. What I wanted was something that could generate random data that looked realistic for whatever kind of realism my domain needed. These two things are complementary. You don't just want one or the other. Sometimes you need both of them at the same time. Since you can only have one instance of the Arbitrary type class for each data type, riding on top of QuickCheck wouldn't be enough. This needed a separate library. Enter the fake package.

The fake package provides a type class called Fake which is a stripped down version of QuickCheck's Arbitrary type class intended for generating realistic data. With this we also include a random value generator called FGen which eliminates confusion with QuickCheck's Gen and helps to minimize dependencies. The package does not provide predefined Fake instances for Prelude data types because it's up for your application to define what values are realistic. For example, an Int representing age probably only needs to generate values in the interval (0,120].

It also gives you a number of "providers" that generate various real-world things in a realistic way. Need to generate plausible user agent strings? We've got you covered. Want to generate US addresses with cities and zip codes that are actually valid for the chosen state? Just import the Fake.Provider.Address.EN_US module. But that's not all. Fake ships with providers that include:

Correctly formatted US social security numbers
Various English parts of speech
English names, including gender-appropriate first names
US phone numbers with valid area codes and prefixes

See the full list here.

I tried to focus on providers that I thought would be broadly useful to a wide audience. If you are interested in a provider for something that isn't there yet, I invite more contributions! Similar packages exist in a number of other languages, some of which are credited in fake's README. If you are planning on writing a new provider for something with complex structure, you might want to look at some of those to see if something already exists that can serve as inspiration.

One area of future exploration where I would love to see activity is something building on top of fake that allows you to generate entire fake databases matching a certain schema and ensuring that foreign keys are handled properly. This problem might be able to make use of fake's full constructor coverage concept (described in more detail here) to help ensure that all the important combinations of various foreign keys are generated.

Efficiently Improving Test Coverage with Algebraic Data Types

2018-03-16T14:06:00.000-04:00

Think of a time you've written tests for (de)serialization code of some kind, say for a data structure called Foo. If you were using the lowest level of sophistication you probably defined a few values by hand, serialized them, deserialized that, and verified that you ended up with the same value you started with. In Haskell nomenclature we'd say that you manually verified that parse . render == id. If you were a little more sophisticated, you might have used the QuickCheck library (or any of the numerous similar packages it inspired in other languages) to verify the parse . render == id property for a bunch of randomly generated values. The first level of sophistication is often referred to as unit testing. The second frequently goes by the term property testing or sometimes fuzz testing.

Both unit testing and property testing have some drawbacks. With unit testing you have to write fairly tedious boilerplate of listing by hand all the values you want to test with. With property testing you have to write a precise specification of how to generate the different cases randomly. There is a package called generic-arbitrary that can automatically derive these generators for you generically, but that approach often ends up testing many values that aren't giving you any increase in code coverage. To see this, consider the example of testing this domain-specific data type:

data MyError e a = Failure e | Success a

Here is what we get using generic-arbitrary to generate test values:

λ import Test.QuickCheck
λ import Test.QuickCheck.Arbitrary.Generic
λ let g = genericArbitrary :: Gen (MyError Int Bool)
λ mapM_ print =<< generate (replicateM 20 g)
Success True
Success True
Success False
Success False
Success True
Failure 17
Failure 8
Failure (-29)
Failure (-14)
Success True
Failure 22
Failure (-2)
Success False
Success True
Success False
Failure (-15)
Success False
Success True
Failure (-5)
Failure (-5)

It is testing the exact same value multiple times. But even if it had a mechanism for deduplicating the values, do you really need so many different test cases for the serialization of the Int in the Failure case? I'm testing my serialization code for the MyError type, so I probably don't care about testing the serialization of Int. I would take it as a given that the libraries I'm using got the serialization for Int correct. If we take this assumption as a given, then for the above case of testing MyError Int Bool, I would really only care about two cases, the Failure case and the Success case. Testing serializations for Int and Bool are out of the scope of my concern because from the perspective of my project they are primitives.

What we really want to test is something I call "full constructor coverage". With this pattern of generation you only generate enough values to exercise each constructor your your type hierarchy once. This gets you better code coverage while testing many fewer values. If we wanted exhaustive testing, the number of values you'd need to test are given by this relation:

-- Product type
numCases (a, b) = numCases a * numCases b
-- Sum type
numCases (Either a b) = numCases a + numCases b

This is precisely what the "algebraic" in "algebraic data types" is referring to. For product types the number of inhabitants is multiplied, for sum types it is added. However, if we're going for full constructor coverage, the number of values we need to test is reduced to the following relation:

numCases (a, b) = max (numCases a) (numCases b)
numCases (Either a b) = numCases a + numCases b

For complex types, replacing the multiplication with the max greatly reduces the number of values you need to test. Here's what full constructor coverage looks like for MyError:

λ import Fake
λ let g = unCoverage (gcover :: Coverage (MyError Int Bool))
λ mapM_ print =<< generate (sequence g)
Failure 75
Success False

At this point readers might be thinking, "Who cares? Computers are fast." Well, QuickCheck defaults to generating 100 test cases for each property, but complex types can easily make this insufficient. You can increase how many test cases it generates, but that will make your test suite slower and you probably won't know what the right number is to get the level of coverage you are aiming for. In my experience slower test suites can cause tangible business impact in production systems in terms of possibly longer downtimes when problems are encountered in production and you have to wait for tests to pass before you can deploy a fix. At the end of the day, naive randomized test case generation very unlikely to score as well as the full constructor coverage method under the metric of lines of code covered per test case.

The good news is that Haskell's algebraic data types give us exactly what we need to get full constructor coverage in a completely automatic way. It is a part of the fake package and you can use it today. You can see example uses in the test suite. In a dynamically typed language you don't have knowledge of the constructors and forms they take. All variables can hold any data, so you don't have any knowledge of structure to guide you. Thanks to types, Haskell knows that structure.

Armor Your Data Structures Against Backwards-Incompatible Serializations

2018-03-15T08:38:00.000-04:00

As almost everyone with significant experience managing production software systems should know, backwards compatibility is incredibly important for any data that is persisted by an application. If you make a change to a data structure that is not backwards compatible with the existing serialized formats, your app will break as soon as it encounters the existing format. Even if you have 100% test coverage, your tests still might not catch this problem. It’s not a problem with your app at any single point in time, but a problem with how your app evolves over time.

One might think that wire formats which are only used for communication between components and not persisted in any way would not be susceptible to this problem. But these too can cause issues if a message is generated and a new version of the app is deployed before the the message is consumed. The longer the message remains in a queue, redis cache, etc the higher the chances of this occurring.

More subtly, if you deploy a backwards incompatible migration, your app may persist some data in the new format before it crashes when it receives the old format. This can leave your system in the horrible state where not only will it not work with the new code, but rolling back to the old code won’t work either because the old code doesn’t support the new serialized format! You have two incompatible serializations active at the same time! Proper migration systems can reduce the chances of this problem occurring, but if your system has any kind of queueing system or message bus, your migrations might not be applied to in-flight messages. Clearly we need something to help us protect against this problem. Enter the armor package.

Armor is a Haskell package that saves serialized versions of your data structures to the filesystem and tests that they can be correctly parsed. This alone at a single point in time verifies that parse . render == id which is a property that you usually want your serializations to have. But in addition to that, armor tracks a version number for your data structures and uses that to accumulate historical serialization formats over time. It stores the serialized bytes in `.test` files that you check into source control. This protects against backwards-incompatible changes and at the same time avoids cluttering up your source code with old versions of the data structure.

Armor does this while being completely agnostic to the choice of serialization library. In fact, it can support any number of different serialization formats simultaneously. For more information check out the literate Haskell tutorial in the test suite.

Credits

Inspiration for this package came from Soostone's safecopy-hunit package.

Details were refined in production at Formation (previously Takt).

Talk: Real World Reflex

2017-04-23T08:00:00.000-04:00

I recently gave a talk at BayHac about some of the things I've learned in building production Reflex applications. If you're interested, you can find it here:
video
slides
github

On Haskell Documentation

2016-12-26T11:02:00.000-05:00

The following started out as a response to a Hacker News comment, but got long enough to merit a standalone blog post.

I think the root of the Haskell documentation debate lies in a pretty fundamental difference in how you go about finding, reading, and understanding documentation in Haskell compared to mainstream languages. Just last week I ran into a situation that really highlighted this difference.

I was working on creating a Haskell wrapper around the ACE editor. I initially wrote the wrapper some time ago and got it integrated into a small app. Last week I needed ACE integration in another app I'm working on and came back to the code. But I ran into a problem...ACE automatically makes AJAX requests for JS files needed for pluggable syntax highlighters and themes. But it was making the AJAX requests in the wrong place and I needed to tell it to request them from somewhere else. Depending on how interested you are in this, you might try looking through the ACE documentation on your own before reading on to see if you can find the answer to this problem.

When you go to the ACE home page, the most obvious place to start seems to be the embedding guide. This kind of guide seems to be what people are talking about when they complain about Haskell's documentation. But this guide gave me no clues as to how to solve my problem. The embedding guide then refers you to the how-to guide. That documentation didn't help me either. The next place I go is the API reference. I'm no stranger to API references. This is exactly what I'm used to from Haskell! I look at the docs for the top-level Ace module. There are only three functions here. None of them what I want. They do have some type signatures that seem to help a little, but it doesn't tell me the type of the `edit` function, which is the one that seems most likely to be what I want. At this point I'm dying for a hyperlink to the actual code, but there are none to be found. To make a long story short, the thing I want is nowhere to be found in the API reference either.

I only solved the problem when a co-worker who has done a lot of JS work found the answer buried in a closed GitHub issue. There's even a comment on that issue by someone saying he had been looking for it "for days". The solution was to call ace.config.set('basePath', myPath);. This illustrates the biggest problem with tutorial/how-to documentation: they're always incomplete. There will always be use cases that the tutorials didn't think of. They also take effort to maintain, and can easily get out of sync over time.

I found this whole experience with ACE documentation very frustrating, and came away feeling that I vastly prefer Haskell documentation. With Haskell, API docs literally give you all the information needed to solve any problem that the API can solve (with very few exceptions). If the ACE editor was written natively in Haskell, the basePath solution would be pretty much guaranteed to show up somewhere in the API documentation. In my ACE wrapper you can find it here.

Now I need to be very clear that I am not saying the types are enough and saying the state of Haskell documentation is good enough. There are definitely plenty of situations where it is not at all obvious how to wrangle the types to accomplish what you want to accomplish. Haskell definitely needs to improve its documentation. But this takes time and effort. The Haskell community is growing but still relatively small, and resources are limited. Haskell programmers should keep in mind that newcomers will probably be more used to tutorials and how-tos. And I think newcomers should keep in mind that API docs in Haskell tell you a lot more than in other languages, and be willing to put some effort into learning how to use these resources effectively.

How to Get a Haskell Job

2016-08-03T10:02:00.000-04:00

Over and over again I have seen people ask how to get a full time job programming in Haskell. So I thought I would write a blog post with tips that have worked for me as well as others I know who write Haskell professionally. For the impatient, here's the tl;dr in order from easiest to hardest:

IRC
Local meetups
Regional gatherings/hackathons
Open source contributions
Work where Haskell people work

First, you need to at least start learning Haskell on your own time. You had already started learning how to program before you got your first programming job. The same is true of Haskell programming. You have to show some initiative. I understand that for people with families this can be hard. But you at least need to start. After that, far and away the most important thing is to interact with other Haskell developers so you can learn from them. That point is so important it bears repeating: interacting with experienced Haskell programmers is by far the most important thing to do. Doing this at a job would be the best, but there are other things you can do.

1. IRC. Join the #haskell channel on Freenode. Lurk for awhile and follow some of the conversations. Try to participate in discussions when topics come up that interest you. Don't be afraid to ask what might seem to be stupid questions. In my experience the people in #haskell are massively patient and willing to help anyone who is genuinely trying to learn.

2. Local meetups. Check meetup.com to see if there is a Haskell meetup in a city near you. I had trouble finding a local meetup when I was first learning Haskell, but there are a lot more of them now. Don't just go to listen to the talks. Talk to people, make friends. See if there's any way you can collaborate with some of the people there.

3. Larger regional Haskell events. Find larger weekend gatherings of Haskell developers and go to them. Here are a few upcoming events that I know of off the top of my head:

The first event like this that I went to was Hac Phi a few years back. Going there majorly upped my game because I got to be around brilliant people, pair program with some of them, and ultimately ended up starting the Snap Web Framework with someone I met there. You might not have a local meetup that you can go to, but you can definitely travel to go to one of these bigger weekend events. I lived a few hours away from Hac Phi, but I know a number of people who travel further to come. If you're really interested in improving your Haskell, it is well worth the time and money. I cannot emphasize this enough.

4. Start contributing to an open source Haskell project. Find a project that interests you and dive in. Don't ask permission, just decide that you're going to learn enough to contribute to this thing no matter what. Join their project-specific IRC channel if they have one and ask questions. Find out how you can contribute. Submit pull requests. This is by far the best way to get feedback on the code that you're writing. I have actually seen multiple people (including some who didn't strike me as unusually talented at first) start Haskell and work their way up to a full-time Haskell job this way. It takes time and dedication, but it works.

5. Try to get a non-haskell job at a place where lots of Haskell people are known to work. Standard Chartered uses is Haskell but is big enough to have non-Haskell jobs that you might be able to fit. S&P Capital IQ doesn't use Haskell but has a significant number of Haskell people who are coding in Scala.

Measuring Software Fragility

2016-08-02T07:12:00.000-04:00

While writing this comment on reddit I came up with an interesting question that I think might be a useful way of thinking about programming languages. What percentage of single non-whitespace characters in your source code could be changed to a different character such that the change would pass your CI build system but would result in a runtime bug? Let's call this the software fragility number because I think that metric gives a potentially useful measure of how bug prone your software is.

At the end of the day software is a mountain of bytes and you're trying to get them into a particular configuration. Whether you're writing a new app from scratch, fixing bugs, or adding new features, the number of bytes of source code you have (similar to LOC, SLOC, or maybe the compressed number of bytes) is rough indication of the complexity of your project. If we model programmer actions as random byte mutations over all of a project's source and we're trying to predict the project's defect rate this software fragility number is exactly the thing we need to know.

Now I'm sure many people will be quick to point out that this random mutation model is not accurate. Of course that's true. But I would argue that in this way it's similar to the efficient markets hypothesis in finance. Real world markets are obviously not efficient (Google didn't become $26 billion less valuable because the UK voted for brexit). But the efficient markets model is still really useful--and good luck finding a better one that everybody will agree on.

What this model lacks in real world fidelity, it makes up for in practicality. We can actually build an automated system to calculate a reasonable approximation of the fragility number. All that has to be done is take a project, randomly mutate a character, run the project's whole CI build, and see if the result fails the build. Repeat this for every non-whitespace character in the project and count how many characters pass the build. Since the character was generated at random, I think it's reasonable to assume that any mutation that passes the build is almost definitely a bug.

Performing this process for every character in a large project would obviously require a lot of CPU time. We could make this more tractable by picking characters at random to mutate. Repeat this until you have done it for a large enough number of characters and then see what percentage of them made it through the build. Alternatively, instead of choosing random characters you could choose whole modules at random to get more uniform coverage over different parts of the language's grammar. There are probably a number of different algorithms that could be tried for picking random subsets of characters to test. Similar to numerical approximation algorithms such as Newton's method, any of these algorithms could track the convergence of the estimate and stop when the value gets to a sufficient level of stability.

Now let's investigate actual fragility numbers for some simple bits of example code to see how this notion behaves. First let's look at some JavaScript examples.

It's worth noting that comment characters should not be allowed to be chosen for mutation since they obviously don't affect the correctness of the program. So the comments you see here have not been included in the calculations. Fragile characters are highlighted in orange.

// Fragility 12 / 48 = 0.25
function f(n) {
  if ( n < 2 ) return 1;
  else return n * f(n-1);
}

// Fragility 14 / 56 = 0.25
function g(n) {
  var p = 1;
  for (var i = 2; i <= n; i++ ) {
    p *= i;
  }
  return p;
}

First I should say that I didn't write an actual program to calculate these. I just eyeballed it and thought about what things would fail. I easily could have made mistakes here. In some cases it may even be subjective, so I'm open to corrections or different views.

Since JavaScript is not statically typed, every character of every identifier is fragile--mutating them will not cause a build error because there isn't much of a build. JavaScript won't complain, you'll just start getting undefined values. If you've done a signifciant amount of JavaScript development, you've almost definitely encountered bugs from mistyped identifier names like this. I think it's mildly interesting that the recursive and iterative formulations if this function both have the same fragility. I expected them to be different. But maybe that's just luck.

Numerical constants as well as comparison and arithmetic operators will also cause runtime bugs. These, however, are more debatable because if you use the random procedure I outlined above, you'll probably get a build failure because the character would have probably changed to something syntactically incorrect. In my experience, it semes like when you mistype an alpha character, it's likely that the wrong character will also be an alpha character. The same seems to be true for the classes of numeric characters as well as symbols. The method I'm proposing is that the random mutation should preserve the character class. Alpha characters should remain alpha, numeric should remain numeric, and symbols should remain symbols. In fact, my original intuition goes even further than that by only replacing comparison operators with other comparison operators--you want to maximize the chance that new mutated character will cause a successful build so the metric will give you a worst-case estimate of fragility. There's certainly room for research into what patterns tend come up in the real world and other algorithms that might describe that better.

Now let's go to the other end of the programming language spectrum and see what the fragility number might look like for Haskell.

// Fragility 7 / 38 = 0.18
f :: Int -> Int
f n
  | n < 2 = 1
  | otherwise = n * f (n-1)

Haskell's much more substantial compile time checks mean that mutations to identifier names can't cause bugs in this example. The fragile characters here are clearly essential parts of the algorithm we're implementing. Maybe we could relate this idea to information theory and think of it as an idea of how much information is contained in the algorithm.

One interesting thing to note here is the effect of the length of identifier names on the fragility number. In JavaScript, long identifier names will increase the fragility because all identifier characters can be mutated and will cause a bug. But in Haskell, since identifier characters are not fragile, longer names will lower the fragility score. Choosing to use single character identifier names everywhere makes these Haskell fragility numbers the worst case and makes JavaScript fragility numbers the best case.

Another point is that since I've used single letter identifier names it is possible for a random identifier mutation in Haskell to not cause a build failure but still cause a bug. Take for instance a function that takes two Int parameters x and y. If y was mutated to x, the program would still compile, but it would cause a bug. My set of highlighted fragile characters above does not take this into account because it's trivially avoidable by using longer identifier names. Maybe this is an argument against one letter identifier names, something that Haskell gets criticism for.

Here's the snippet of Haskell code I was talking about in the above reddit comment that got me thinking about all this in the first place:

// Fragility 31 / 277 = 0.11
data MetadataInfo = MetadataInfo
    { title       :: Text
    , description :: Text
    }

pageMetadataWidget :: MonadWidget t m => Dynamic t MetadataInfo -> m ()
pageMetadataWidget i = do
    el "title" $ dynText $ title <$> i
    elDynAttr "meta" (mkDescAttrs . description <$> i) blank
  where
    mkDescAttrs desc =
      "name" =: "description" <>
      "content" =: desc

In this snippet, the fragility number is probably close to 31 characters--the number of characters in string literals. This is out of a total of 277 non-whitespace characters, so the software fragility number for this bit of code is 11%. This half the fragility of the JS code we saw above! And as I've pointed out, larger real world JS examples are likely to have even higher fragility. I'm not sure how much we can conclude about the actual ratios of these fragility numbers, but at the very least it matches my experience that JS programs are significantly more buggy than Haskell programs.

The TDD people are probably thinking that my JS examples aren't very realistic because none of them have tests, and that tests would catch most of the identifier name mutations, bringing the fragility down closer to Haskell territory. It is true that tests will probably catch some of these things. But you have to write code to make that happen! It doesn't happen by default. Also, you need to take into account the fact that the tests themselves will have some fragility. Tests require time and effort to maintain. This is an area where this notion of the fragility number becomes less accurate. I suspect that since the metric only considers single character mutations it will underestimate the fragility of tests since mutating single characters in tests will automatically cause a build failure.

There seems to be a slightly paradoxical relationship between the fragility number and DRY. Imagine our above JS factorial functions had a test that completely reimplemented factorial and then tried a bunch of random values Quickcheck-style. This would yield a fragility number of zero! Any single character change in the code would cause a test failure. And any single character change in the tests would also cause a test failure. Single character changes can no longer classified fragile because we've violated DRY. You might say that the test suite shouldn't reimplement algorithm--you should just specific cases like f(5) == 120. But in an information theory sense this is still violating DRY.

Does this mean that the fragility number is not very useful? Maybe. I don't know. But I don't think it means that we should just throw away the idea. Maybe we should just keep in mind that this particular formulation doesn't have much to tell us about the fragility more complex coordinated multi-character changes. I could see the usefulness of this metric going either way. It could simplify down to something not very profound. Or it could be that measurements of the fragility of real world software projects end up revealing some interesting insights that are not immediately obvious even from my analysis here.

Whatever the usefulness of this fragility metric, I think the concept gets is thinking about software defects in a different way than we might be used to. If it turns out that my single character mutation model isn't very useful, perhaps the extension to multi-character changes could be useful. Hopefully this will inspire more people to think about these issues and play with the ideas in a way that will help us progress towards more reliable software and tools to build it with.

EDIT: Unsurprisingly, I'm not the first person to have thought of this. It looks like it's commonly known as mutation testing. That Wikipedia article makes it sound like mutation testing is commonly thought of as a way to assess your project's test suite. I'm particularly interested in what it might tell us about programming languages...i.e. how much "testing" we get out of the box because of our choice of programming language and implementation.

"cabal gen-bounds": easy generation of dependency version bounds

2015-08-18T00:40:00.001-04:00

In my last post I showed how release dates are not a good way of inferring version bounds. The package repository should not make assumptions about what versions you have tested against. You need to tell it. But from what I've seen there are two problems with specifying version bounds:

Lack of knowledge about how to specify proper bounds
Unwillingness to take the time to do so

Early in my Haskell days, the first time I wrote a cabal file I distinctly remember getting to the dependencies section and having no idea what to put for the version bounds. So I just ignored them and moved on. The result of that decision is that I can no longer build that app today. I would really like to, but it's just not worth the effort to try.

It wasn't until much later that I learned about the PVP and how to properly set bounds. But even then, there was still an obstacle. It can take some time to add appropriate version bounds to all of a package's dependencies. So even if you know the correct scheme to use, you might not want to take the time to do it.

Both of these problems are surmountable. And in the spirit of doing that, I would like to propose a "cabal gen-bounds" command. It would check all dependencies to see which ones are missing upper bounds and output correct bounds for them. I have implemented this feature and it is available at https://github.com/mightybyte/cabal/tree/gen-bounds. Here is what it looks like to use this command on the cabal-install package:

$ cabal gen-bounds
Resolving dependencies...

The following packages need bounds and here is a suggested starting point.
You can copy and paste this into the build-depends section in your .cabal
file and it should work (with the appropriate removal of commas).

Note that version bounds are a statement that you've successfully built and
tested your package and expect it to work with any of the specified package
versions (PROVIDED that those packages continue to conform with the PVP).
Therefore, the version bounds generated here are the most conservative
based on the versions that you are currently building with.  If you know
your package will work with versions outside the ranges generated here,
feel free to widen them.


network      >= 2.6.2 && < 2.7,
network-uri  >= 2.6.0 && < 2.7,

The user can then paste these lines into their build-depends file. They are formatted in a way that facilitates easy editing as the user finds more versions (either newer or older) that the package builds with. This serves to both educate users and automate the process. I think this removes one of the main frustrations people have about upper bounds and is a step in the right direction of getting more hackage packages to supply them. Hopefully it will be merged upstream and be available in cabal-install in the future.

Why version bounds cannot be inferred retroactively (using dates)

2015-08-16T14:40:00.000-04:00

In past debates about Haskell's Package Versioning Policy (PVP), some have suggested that package developers don't need to put upper bounds on their version constraints because those bounds can be inferred by looking at what versions were available on the date the package was uploaded. This strategy cannot work in practice, and here's why.

Imagine someone creates a small new package called foo. It's a simple package, say something along the lines of the formattable package that I recently released. One of the dependencies for foo is errors, a popular package supplying frequently used error handling infrastructure. The developer happens to already have errors-1.4.7 installed on their system, so this new package gets built against that version. The author uploads it to hackage on August 16, 2015 with no upper bounds on its dependencies. Let's for simplicity imagine that errors is the only dependency, so the .cabal file looks like this:

name: foo
build-depends:
  errors

If we come back through at some point in the future and try to infer upper bounds by date, we'll see that on August 16, the most recent version of errors was 2.0.0. Here's an abbreviated illustration of the picture we can see from release dates:

If we look only at release dates, and assume that packages were building against the most recent version, we will try to build foo with errors-2.0.0. But that is incorrect! Building foo with errors-2.0.0 will fail because errors had a major breaking change in that version. Bottom line: dates are irrelevant--all that matters is what dependency versions the author happened to be building against! You cannot assume that package authors will always be building against the most recent versions of their dependencies. This is especially true if our developer was using the Haskell Platform or LTS Haskell because those package collections lag the bleeding edge even more. So this scenario is not at all unlikely.

It is also possible for packages to be maintaining multiple major versions simultaneously. Consider large projects like the linux kernel. Developers routinely do maintenance releases on 4.1 and 4.0 even though 4.2 is the latest version. This means that version numbers are not always monotonically increasing as a function of time.

I should also mention another point on the meaning of version bounds. When a package specifies version bounds like this...

name: foo
build-depends:
  errors >= 1.4 && < 1.5

...it is not saying "my package will not work with errors-1.5 and above". It is actually saying, "I warrant that my package does work with those versions of errors (provided errors complies with the PVP)". So the idea that "< 1.5" is a "preemptive upper bound" is wrong. The package author is not preempting anything. Bounds are simply information. The upper and lower bounds are important things that developers need to tell you about their packages to improve the overall health of the ecosystem. Build tools are free to do whatever they want with that information. Indeed, cabal-install has a flag --allow-newer that lets you ignore those upper bounds and step outside the version ranges that the package authors have verified to work.

In summary, the important point here is that you cannot use dates to infer version bounds. You cannot assume that package authors will always be building against the most recent versions of their dependencies. The only reliable thing to do is for the package maintainer to tell you explicitly what versions the package is expected to work with. And that means lower and upper bounds.

Update: Here is a situation that illustrates this point perfectly: cryptonite issue #96. cryptonite-0.19 was released on August 12, 2016. But cryptonite-0.15.1 was released on August 22, 2016. Any library published after August 22, 2016 that depends on cryptonite-0.15.1 would not be able to build if the solver used dates instead of explicit version bounds.

The Problem with Curation

2015-06-03T13:02:00.000-04:00

Recently I received a question from a user asking about "cabal hell" when installing one of my packages. The scenario in question worked fine for us, but for some reason it wasn't working for the user. When users report problems like this they usually do not provide enough information for us to solve it. So then we begin the sometimes arduous back and forth process of gathering the information we need to diagnose the problem and suggest a workaround or implement a fix.

In this particular case luck was on our side and the user's second message just happened to include the key piece of information. The problem in this case was that they were using stackage instead of the normal hackage build that people usually use. Using stackage locks down your dependency bounds to a single version. The user reporting the problem was trying to add additional dependencies to his project and those dependencies required different versions. Stackage was taking away degrees of freedom from the dependency solver (demoting it from the driver seat to the passenger seat). Fortunately in this case the fix was simple: stop freezing down versions with stackage. As soon as the user did that it worked fine.

This highlights the core problem with package curation: it is based on a closed-world assumption. I think that this makes it not a viable answer to the general question of how to solve the package dependency problem. The world that many users will encounter is not closed. People are constantly creating new packages. Curation resources are finite and trying to keep up with the world is a losing battle. Also, even if we had infinite curation resources and zero delay between the creation of a package and its inclusion in the curated repository, that would still not be good enough. There are many people working with code that is not public and therefore cannot be curated. We need a more general solution to the problem that doesn't require a curator.

LTMT Part 3: The Monad Cookbook

2014-12-19T02:01:00.000-05:00

Introduction

The previous two posts in my Less Traveled Monad Tutorial series have not had much in the way of directly practical content. In other words, if you only read those posts and nothing else about monads, you probably wouldn't be able to use monads in real code. This was intentional because I felt that the practical stuff (like do notation) had adequate treatment in other resources. In this post I'm still not going to talk about the details of do notation--you should definitely read about that elsewhere--but I am going to talk about some of the most common things I have seen beginners struggle with and give you cookbook-style patterns that you can use to solve these issues.

Problem: Getting at the pure value inside the monad

This is perhaps the most common problem for Haskell newcomers. It usually manifests itself as something like this:

main = do
    lineList <- lines $ readFile "myfile.txt"
    -- ... do something with lineList here

That code generates the following error from GHC:

    Couldn't match type `IO String' with `[Char]'
    Expected type: String
      Actual type: IO String
    In the return type of a call of `readFile'

Many newcomers seem puzzled by this error message, but it tells you EXACTLY what the problem is. The return type of readFile has type IO String, but the thing that is expected in that spot is a String. (Note: String is a synonym for [Char].) The problem is, this isn't very helpful. You could understand that error completely and still not know how to solve the problem. First, let's look at the types involved.

readFile :: FilePath -> IO String
lines :: String -> [String]

Both of these functions are defined in Prelude. These two type signatures show the problem very clearly. readFile returns an IO String, but the lines function is expecting a String as its first argument. IO String != String. Somehow we need to extract the String out of the IO in order to pass it to the lines function. This is exactly what do notation was designed to help you with.

Solution #1

main :: IO ()
main = do
    contents <- readFile "myfile.txt"
    let lineList = lines contents
    -- ... do something with lineList here

This solution demonstrates two things about do notation. First, the left arrow lets you pull things out of the monad. Second, if you're not pulling something out of a monad, use "let foo =". One metaphor that might help you remember this is to think of "IO String" as a computation in the IO monad that returns a String. A do block lets you run these computations and assign names to the resulting pure values.

Solution #2

We could also attack the problem a different way. Instead of pulling the result of readFile out of the monad, we can lift the lines function into the monad. The function we use to do that is called liftM.

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

The associativity of the -> operator is such that these two type signatures are equivalent. If you've ever heard Haskell people saying that all functions are single argument functions, this is what they are talking about. You can think of liftM as a function that takes one argument, a function (a -> b), and returns another function, a function (m a -> m b). When you think about it this way, you see that the liftM function converts a function of pure values into a function of monadic values. This is exactly what we were looking for.

main :: IO ()
main = do
    lineList <- liftM lines (readFile "myfile.txt")
    -- ... do something with lineList here

This is more concise than our previous solution, so in this simple example it is probably what we would use. But if we needed to use contents in more than one place, then the first solution would be better.

Problem: Making pure values monadic

Consider the following program:

import Control.Monad
import System.Environment
main :: IO ()
main = do
    args <- getArgs
    output <- case args of
                [] -> "cat: must specify some files"
                fs -> liftM concat (mapM readFile fs)
    putStrLn output

This program also has an error. GHC actually gives you three errors here because there's no way for it to know exactly what you meant. But the first error is the one we're interested in.

    Couldn't match type `[]' with `IO'
    Expected type: IO Char
      Actual type: [Char]
    In the expression: "cat: must specify some files"

Just like before, this error tells us exactly what's wrong. We're supposed to have an IO something, but we only have a String (remember, String is the same as [Char]). It's not convenient for us to get the pure result out of the readFile functions like we did before because of the structure of what we're trying to do. The two patterns in the case statement must have the same type, so that means that we need to somehow convert our String into an IO String. This is exactly what the return function is for.

Solution: return

return :: a -> m a

This type signature tells us that return takes any type a as input and returns "m a". So all we have to do is use the return function.

import Control.Monad
import System.Environment
main :: IO ()
main = do
    args <- getArgs
    output <- case args of
                [] -> return "cat: must specify some files"
                fs -> liftM concat (mapM readFile fs)
    putStrLn output

The 'm' that the return function wraps its argument in, is determined by the context. In this case, main is in the IO monad, so that's what return uses.

Problem: Chaining multiple monadic operations

import System.Environment
main :: IO ()
main = do
    [from,to] <- getArgs
    writeFile to $ readFile from

As you probably guessed, this function also has an error. Hopefully you have an idea of what it might be. It's the same problem of needing a pure value when we actually have a monadic one. You could solve it like we did in solution #1 on the first problem (you might want to go ahead and give that a try before reading further). But this particular case has a pattern that makes a different solution work nicely. Unlike the first problem, you can't use liftM here.

Solution: bind

When we used liftM, we had a pure function lines :: String -> [String]. But here we have writeFile :: FilePath -> String -> IO (). We've already supplied the first argument, so what we actually have is writeFile to :: String -> IO (). And again, readFile returns IO String instead of the pure String that we need. To solve this we can use another function that you've probably heard about when people talk about monads...the bind function.

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

Notice how the pattern here is different from the first example. In that example we had (a -> b) and we needed to convert it to (m a -> m b). Here we have (a -> m b) and we need to convert it to (m a -> m b). In other words, we're only adding an 'm' onto the 'a', which is exactly the pattern we need here. Here are the two patterns next to each other to show the correspondence.

writeFile to :: String -> IO ()
                     a ->  m b

From this we see that "writeFile to" is the first argument to the =<< function. readFile from :: IO String fits perfectly as the second argument to =<<, and then the return value is the result of the writeFile. It all fits together like this:

import System.Environment
main :: IO ()
main = do
    [from,to] <- getArgs
    writeFile to =<< readFile from

Some might point out that this third problem is really the same as the first problem. That is true, but I think it's useful to see the varying patterns laid out in this cookbook style so you can figure out what you need to use when you encounter these patterns as you're writing code. Everything I've said here can be discovered by carefully studying the Control.Monad module. There are lots of other convenience functions there that make working with monads easier. In fact, I already used one of them: mapM.

When you're first learning Haskell, I would recommend that you keep the documentation for Control.Monad close by at all times. Whenever you need to do something new involving monadic values, odds are good that there's a function in there to help you. I would not recommend spending 10 hours studying Control.Monad all at once. You'll probably be better off writing lots of code and referring to it whenever you think there should be an easier way to do what you want to do. Over time the patterns will sink in as form new connections between different concepts in your brain.

It takes effort. Some people do pick these things up more quickly than others, but I don't know anyone who just read through Control.Monad and then immediately had a working knowledge of everything in there. The patterns you're grappling with here will almost definitely be foreign to you because no other mainstream language enforces this distinction between pure values and side effecting values. But I think the payoff of being able to separate pure and impure code is well worth the effort.

Announcing C◦mp◦se :: Conference

2014-11-25T15:58:00.003-05:00

Since most of my content is about Haskell, I would like to take this opportunity to inform my readers of a new conference that I and the other co-organizers of the New York Haskell Meetup are hosting at the end of January. It's called C◦mp◦se, and it's a conference for typed functional programmers. Check out the website at http://www.composeconference.org/. We recently issued a call for papers. I know it's short notice, but the deadline is November 30. If you have something that you think would be interesting to typed functional programmers, we'd love to hear from you. Along with the conference we'll also be having one day be a less formal hackathon/unconference. If you would like to give a tutorial/demo at the unconference, email us at info@composeconference.org.

Field Accessors Considered Harmful

2014-08-10T17:33:00.001-04:00

It's pretty well known these days that Haskell's field accessors are rather cumbersome syntactically and not composable. The lens abstraction that has gotten much more popular recently (thanks in part to Edward Kmett's lens package) solves these problems. But I recently ran into a bigger problem with field accessors that I had not thought about before. Consider the following scenario. You have a package with code something like this:

data Config = Config { configFieldA :: [Text] }

So your Config data structure gives your users getters and setters for field A (and any other fields you might have). Your users are happy and life is good. Then one day you decide to add a new feature and that feature requires expanding and restructuring Config. Now you have this:

data MConfig = MConfig { mconfigFieldA :: [Text] }

data Config = Config { configMC :: MConfig
                     , configFieldX :: Text
                     , configFieldY :: Bool }

This is a nice solution because your users get to keep the functionality over the portion of the Config that they are used to, and they still get the new functionality. But now there's a problem. You're still breaking them because configFieldA changed names to mconfigFieldA and now refers to the MConfig structure instead of Config. If this was not a data structure, you could preserve backwards compatibility by creating another function:

configFieldA = mconfigFieldA . configMC

But alas, that won't work here because configFieldA is not a normal function. It is a special field accessor generated by GHC and you know that your users are using it as a setter. It seems to me that we are at an impasse. It is completely impossible to deliver your new feature without breaking backwards compatibility somehow. No amount of deprecated cycles can ease the transition. The sad thing is that it seems like it should have been totally doable. Obviously there are some kinds of changes that understandably will break backwards compatibility. But this doesn't seem like one of them since it is an additive change. Yes, yes, I know...it's impossible to do this change without changing the type of the Config constructor, so that means that at least that function will break. But we should be able to minimize the breakage to the field accessor functions, and field accessors prevent us from doing that.

However, we could have avoided this problem. If we had a bit more foresight, we could have done this.

module Foo (mkConfig, configFieldA) where



data Config = Config { _configFieldA :: [Text] }



mkConfig :: [Text] -> Config

mkConfig = Config



configFieldA = lens _configFieldA (\c a -> c { _configFieldA = a })

This would allow us to avoid breaking backwards compatibility by continuing to export appropriate versions of these symbols. It would look something like this.

module Foo
  ( MConfig
  , mkMConfig
  , mconfigFieldA
  , Config
  , mkConfig
  , configFieldA
  , configMC
  -- ...
  ) where

data MConfig = MConfig { _mconfigFieldA :: [Text] }
data Config = Config { _configMC :: MConfig
                     , _configFieldX :: Text
                     , _configFieldY :: Bool }

mkMConfig = MConfig

mkConfig a = Config (mkMConfig a) "" False

mconfigFieldA = lens _mconfigFieldA (\c a -> c { _mconfigFieldA = a })
configMC = lens _configMC (\c mc -> c { _configMC = mc })

-- The rest of the field lenses here

configFieldA = configMC . mconfigFieldA

Note that the type signatures for mkConfig and configFieldA stay exactly the same. We weren't able to do this with field accessors because they are not composable. Lenses solve this problem for us because they are composable and we have complete control over their definition.

For quite some time now I have thought that I understood the advantage that lenses give you over field accessors. Discovering this added ability of lenses in helping us preserve backwards compatibility came as a pleasant surprise. I'll refrain from opining on how this should affect your development practices, but I think it makes the case for using lenses in your code a bit stronger than it was before.

Haskell Best Practices for Avoiding "Cabal Hell"

2014-07-13T19:45:00.002-04:00

DEC 2020 UPDATE: A lot has changed since this post was written. Much of "cabal hell" is now a thing of the past due to cabal's more recent purely functional "nix style" build infrastructure. Some of the points here aren't really applicable any more, but many still are. I'm updating this post with strikethroughs for the points that are outdated.

I posted this as a reddit comment and it was really well received, so I thought I'd post it here so it would be more linkable. A lot of people complain about "cabal hell" and ask what they can do to solve it. There are definitely things about the cabal/hackage ecosystem that can be improved, but on the whole it serves me quite well. I think a significant amount of the difficulty is a result of how fast things move in the Haskell community and how much more reusable Haskell is than other languages.

With that preface, here are my best practices that seem to make Cabal work pretty well for me in my development.

1. I make sure that I have no more than the absolute minimum number of packages installed as --global. This means that I don't use the Haskell Platform or any OS haskell packages. I install GHC directly. Some might think this casts too much of a negative light on the Haskell Platform. But everyone will agree that having multiple versions of a package installed at the same time is a significant cause of build problems. And that is exactly what the Haskell Platform does for you--it installs specific versions of packages. If you use Haskell heavily enough, you will invariably encounter a situation where you want to use a different version of a package than the one the Haskell Platform gives you. The --global flag is not applicable any more now that we have the new v2-* commands.

2. Make sure ~/.cabal/bin is at the front of your path. Hopefully you already knew this, but I see this problem a lot, so it's worth mentioning for completeness.

3. Install happy and alex manually. These two packages generate binary executables that you need to have in ~/.cabal/bin. They don't get picked up automatically because they are executables and not package dependencies.

4. Make sure you have the most recent version of cabal-install. There is a lot of work going on to improve these tools. The latest version is significantly better than it used to be, so you should definitely be using it.

5. Become friends with "rm -fr ~/.ghc". This command cleans out your --user repository, which is where you should install packages if you're not using a sandbox. It sounds bad, but right now this is simply a fact of life. The Haskell ecosystem is moving so fast that packages you install today will be out of date in a few months if not weeks or days. We don't have purely functional nix-style package management yet, so removing the old ones is the pragmatic approach. Note that sandboxes accomplish effectively the same thing for you. Creating a new sandbox is the same as "rm -fr ~/.ghc" and then installing to --user, but has the benefit of not deleting everything else you had in --user. UPDATE: Removing the .ghc directory is still potentially useful to know but much less of an issue now.

6. ~~If you're not working on a single project with one harmonious dependency tree, then use sandboxes for separate projects or one-off package compiles.~~ Sandboxes have been deprecated in lieu of the new build approach.

7. Learn to use --allow-newer. Again, things move fast in Haskell land. If a package gives you dependency errors, then try --allow-newer and see if the package will just work with newer versions of dependencies.

8. Don't be afraid to dive into other people's packages. "cabal unpack" makes it trivial to download the code for any package. From there it's often trivial to make manual changes to version bounds or even small code changes. If you make local changes to a package, then you can either install it to --user so other packages use it, or you can do "cabal sandbox add-source /path/to/project" to ensure that your other projects use the locally modified version. If you've made code changes, then help out the community by sending a pull request to the package maintainer. Edit: bergmark mentions that unpack is now "cabal get" and "cabal get -s" lets you clone the project's source repository.

9. If you can't make any progress from the build messages cabal gives you, then try building with -v3. I have encountered situations where cabal's normal dependency errors are not helpful. Using -v3 usually gives me a much better picture of what's going on and I can usually figure out the root of the problem pretty quickly.

Implicit Blacklisting for Cabal

2014-05-16T13:20:00.000-04:00

I've been thinking about all the Haskell PVP discussion that's been going on lately. It should be no secret by now that I am a PVP proponent. I'm not here to debate the PVP in this post, so for this discussion let's assume that the PVP is a good thing and should be adopted by all packages published on Hackage. More specifically, let's assume this to mean that every package should specify upper bounds on all dependencies, and that most of the time these bounds will be of the form "< a.b".

Recently there has been discussion about problems encountered when packages that have not been using upper bounds change and start using them. The recent issue with the HTTP package is a good example of this. Roughly speaking the problem is that if foo-1.2 does not provide upper bounds on it's dependency bar, the constraint solver is perpetually "poisoned" because foo-1.2 will always be a candidate even long after bar has become incompatible with foo-1.2. If later foo-3.9 specifies a bound of bar < 0.5, then when bar-0.5 comes out the solver will try to build with foo-1.2 even though it is hopelessly old. This will result in build errors since bar has long since changed its API.

This is a difficult problem. There are several immediately obvious approaches to solving the problem.

Remove the offending old versions (the ones missing upper bounds) from Hackage.
Leave them on Hackage, but mark them as deprecated/blacklisted so they will not be chosen by the solver.
Go back and retroactively add upper bounds to the offending versions.
Start a new empty Hackage server that requires packages to specify upper bounds on all dependencies.
Start a new Hackage mirror that infers upper bounds based on package upload dates.

All of these approaches have problems. The first three are problematic because they mess with build reproducibility. The fourth approach fragments the community and in the very best case would take a lot of time and effort before gaining adoption. The fifth approach has problems because correct upper bounds cannot always be inferred by upload dates.

I would like to propose a solution I call implicit blacklisting. The basic idea is that for each set of versions with the prefix a.b.c Cabal will only consider a single one: the last one. This effectively means that all the lower versions with the prefix a.b.c will be implicitly blacklisted. This approach should also allow maintainers to modify this behavior by specifying more granular version bounds.

In our previous example, suppose there were a number of 0.4 versions of the bar package, with 0.4.3.3 being the last one. In this case, if foo specified a bound of bar < 0.5, the solver would only consider 0.4.3.3. 0.4.3.2 and 0.4.3.1 would not be considered. This would allow us to completely hide a lack of version bounds by making a new patch release that only bumps the d number. If that release had problems, we could address them with more patch releases.

Now imagine that for some crazy reason foo worked with 0.4.3.2, but 0.4.3.3 broke it somehow. Note that if bar is following the PVP, that should not be the case. But there are some well-known cases where the PVP can miss things and there is always the possibility of human error. In this case, foo should specify a bound of bar < 0.4.3.3. In this case, the solver should respect that bound and only consider 0.4.3.2. But 0.4.3.1 would still be ignored as before.

Implicit blacklisting has the advantage that we don't need any special support for explicitly marking versions as deprecated/blacklisted. Another advantage is that it does not cause any problems for people who had locked their code down to using specific versions. If foo specified an exact version of bar == 0.4.3.0, then that will continue to be chosen. Implicit blacklisting also allows us to leave everything in hackage untouched and fix issues incrementally as they arise with the minimum amount of work. In the above issue with HTTP-4000.0.7, we could trivially address it by downloading that version, adding version bounds, and uploading it as HTTP-4000.0.7.1.

All in all, I think this implicit blacklisting idea has a number of desirable properties and very few downsides. It fixes the problem using nothing but our existing infrastructure: version numbers. It doesn’t require us to add new concepts like blacklisted/deprecated flags, out-of-band “revision” markers to denote packages modified after the fact, etc. But since this is a complicated problem I may very well have missed something, so I'd like to hear what the community thinks about this idea.

Ember.js is driving me crazy

2014-01-28T00:27:00.000-05:00

For the past few months I've been working on a project with a fairly complex interactive web interface. This required me to venture into the wild and unpredictable jungle of Javascript development. I was totally unprepared for what I would find. Soon after starting the project it became clear that just using JQuery would not be sufficient for my project. I needed a higher level Javascript framework. After a doing a little research I settled on Ember.js.

The Zombie Code Apocalypse

Ember was definitely a big improvement over straight JQuery, and allowed me to get some fairly complex UI behavior working very quickly. But recently I've run into some problems. The other day I had a UI widget defined like this:

App.FooController = Ember.ObjectController.extend({
    // ...
});
App.FooView = Ember.View.extend({
    // ...
});

It was used somewhere on the page, but at some point I decided that the widget was no longer needed, so I commented out the widget's markup. I wasn't sure whether we would ultimately keep the widget or not, so I opted to keep the above javascript code for the controller and view around for awhile so it would be easily available if I later decided to re-enable that UI element.

Everything seemed to work fine until a few days later when I noticed that another one of my controls, Bar, was not being populated with data. After spending hours trying to figure out the problem, I finally happened to comment out the unused code for the Foo widget and the problem went away. WTF?!? Why should this have anything to do with the functioning of a completely unrelated widget? This makes absolutely no sense to me, and it completely violates the natural assumption that the controller and view for two completely unrelated controls would have no impact on each other. I would have liked to know the underlying cause, but I didn't want to waste time with it, so I just removed the code and moved on.

Spontaneously Changing Values

Maybe a week later I ran into another problem. Some data was changing when I didn't expect it to. I looked everywhere I could think of that might affect the data, but couldn't find anything. Again, I spent the better part of a day trying to track down the source of this problem. After awhile I was getting desperate, so I started putting print statements all over the place. I discovered that the data was changing in one particular function. I examined it carefully but couldn't find any hint of this data being impacted. Eventually I isolated the problem to the following snippet:

console.log(this.get('foo'));
this.set('bar', ...);
console.log(this.get('foo'));

The first log line showed foo with a value of 25. The second log line showed foo with a value of 0. This is utter madness! I set one field, and a completely different one gets changed! In what world does this make any shred of sense? This time, even when I actually figured out where the problem was happening I still couldn't figure out how to solve it. At least the first time I could just comment out the offending innocuous lines. Here I narrowed down the exact line that's causing the problem, but still couldn't figure out how to fix it. Finally I got on the #emberjs IRC channel and learned that Ember's set function has special behavior for values in the content field, which foo was a part of. I was able to fix this problem by initializing the bar field to null. WAT?!?

I was in shock. This seemed like one of the most absurd behaviors I've encountered in all my years of programming. Back in the C days you could see some crazy things, but at least you knew that array updates and pointer arithmetic could be dangerous and possibly overwrite other parts of memory. Here there's no hint. No dynamic index that might overflow. Just what we thought was a straightforward getter and setter for a static field in a data type.

Blaming Systems, Not People

Before you start jumping all over me for all the things I did wrong, hear me out. I'm not blaming the Ember developers or trying to disparage Ember. Ember.js is an amazing library and my application wouldn't exist without it or something like it. I'm just a feeble-minded Haskell programmer and not well-versed in the ways of Javascript. I'm sure I was doing things that contributed to the problem. But that's not the point. I've been around long enough to realize that there are probably good justifications for why the above behaviors exist. The Ember developers are clearly way better Javascript programmers than I will ever be. There's got to be a better explanation.

Peter Senge, in his book The Fifth Discipline, talks about the beer distribution game. It's a game that has been played thousands of times with diverse groups of people in management classes all over the world. The vast majority of people who play it perform very poorly. Peter points out that we're too quick to attribute a bad outcome to individual people when it should instead be attributed to the structure of the system in which those people were operating. This situation is no different.

Like the beer distribution game, Javascript is a complex system. The above anecdotes demonstrate how localized well-intentioned decisions by different players resulted in a bad outcome. The root of the problem is the system we were operating in: an impure programming language with weak dynamic typing. In a different system, say the one we get with Haskell, I can conclusively say that I never would have had these problems. Haskell's purity and strong static type system provide a level of safety that is simply unavailable in Javascript (or any other mainstream programming language for that matter).

The Godlike Refactoring

In fact, this same project gave us another anecdote supporting this claim. The project's back end is several thousand lines of Haskell code. I wrote all of the back end code, and since we have a pretty aggressive roadmap with ambitious deadlines the code isn't exactly all that pretty. There are a couple places with some pretty hairy logic. A few weeks ago we needed to do a major refactoring of the back end to support a new feature. I was too busy with other important features, so another member of the team worked on the refactoring. He had not touched a single line of the back end code before that point, but thanks to Haskell's purity and strong static type system he was able to pull off the entire refactoring single-handedly in a just a couple hours. And once he got it compiling, the application worked the first time. We are both convinced that this feat would have been impossible without strong static types.

Conclusion

I think there are a couple of interesting points worth thinking about here. First of all, the API chosen by Ember only hid the complexity, it didn't reduce it. What seemed to be a simple get() method was actually a more complex system with some special cases. The system was more complex than the API indicated. It's useful to think about the true complexity of a problem compared to the complexity of the exposed API.

The second point is that having the ability to make categorical statements about API behavior is very important. We use this kind of reasoning all the time, and the more of it we can do, the fewer the number of assumptions we will have to question when something isn't behaving as we expect. In this case, I made the seemingly reasonable categorical assumption that unused class definitions would have no effect on my program. But for some reason that I still don't understand, it was violated. I also made the categorical assumption that Ember's get() and set() methods worked like they would work in a map. But that assumption didn't hold up either. I encounter assumptions that don't hold up all the time. Every programmer does. But rarely are they so deeply and universally held as these.

So what can we learn from this? In The Fifth Discipline, Senge goes on to talk about the importance of thinking with a systems perspective; about how we need to stop blaming people and focus more on the systems involved. I think it's telling how in my 5 or 6 years of Haskell programming I've never seen a bug as crazy as these two that I encountered after working only a few months on a significant Javascript project. Haskell with it's purity and strong static type system allows me to make significantly more confident categorical statements about what my code can and cannot do. That allows me to more easily build better abstractions that actually reduce complexity for the end user instead of just hiding it away in a less frequented area.

Haskell Web Framework Matrix

2012-12-20T17:20:00.000-05:00

A comparison of the big three Haskell web frameworks on the most informative two axes I can think of.

Note that this is not intended to be a definitive statement of what is and isn't possible in each of these frameworks. As I've written elsewhere, most of the features of each of the frameworks are interchangeable and can be mixed and matched. The idea of this matrix is to reflect the general attitude each of the frameworks seem to be taking, because sometimes generalizations are useful.

Using Cabal With Large Projects

2012-11-08T10:46:00.002-05:00

DEC 2020 UPDATE: This post is mostly out of date. The main things that cabal-meta and cabal-dev provided have now been either integrated into cabal itself or been made obsolete by subsequent improvements.

In the last post we talked about basic cabal usage. That all works fine as long as you're working on a single project and all your dependencies are in hackage. When Cabal is aware of everything that you want to build, it's actually pretty good at dependency resolution. But if you have several packages that depend on each other and you're working on development versions of these packages that have not yet been released to hackage, then life becomes more difficult. In this post I'll describe my workflow for handling the development of multiple local packages. I make no claim that this is the best way to do it. But it works pretty well for me, and hopefully others will find this information helpful.

Consider a situation where package B depends on package A and both of them depend on bytestring. Package A has wide version bounds for its bytestring dependency while package B has narrower bounds. Because you're working on improving both packages you can't just do "cabal install" in package B's directory because the correct version of package A isn't on hackage. But if you install package A first, Cabal might choose a version of bytestring that won't work with package B. It's a frustrating situation because eventually you'll have to end up worrying about dependencies issues that Cabal should be handling for you.

The best solution I've found to the above problem is cabal-meta. It lets you specify a sources.txt file in your project root directory with paths to other projects that you want included in the package's build environment. For example, I maintain the snap package, which depends on several other packages that are part of the Snap Framework. Here's what my sources.txt file looks like for the snap package:

./
../xmlhtml
../heist
../snap-core
../snap-server

My development versions of the other four packages reside in the parent directory on my local machine. When I build the snap package with cabal-meta install, cabal-meta tells Cabal to look in these directories in addition to whatever is in hackage. If you do this initially for the top-level package, it will correctly take into consideration all your local packages when resolving dependencies. Once you have all the dependencies installed, you can go back to using Cabal and ghci to build and test your packages. In my experience this takes most of the pain out of building large-scale Haskell applications.

Another tool that is frequently recommended for handling this large-scale package development problem is cabal-dev. cabal-dev allows you to sandbox builds so that differing build configurations of libraries can coexist without causing problems like they do with plain Cabal. It also has a mechanism for handling this local package problem above. I personally tend to avoid cabal-dev because in my experience it hasn't played nicely with ghci. It tries to solve the problem by giving you the cabal-dev ghci command to execute ghci using the sandboxed environment, but I found that it made my ghci workflow difficult, so I prefer using cabal-meta which doesn't have these problems.

I should note that cabal-dev does solve another problem that cabal-meta does not. There may be cases where two different packages may be completely unable to coexist in the same Cabal "sandbox" if their set of dependencies are not compatible. In that case, you'll need cabal-dev's sandboxes instead of the single user-level package repository used by Cabal. I am usually only working on one major project at a time, so this problem has never been an issue for me. My understanding is that people are currently working on adding this kind of local sandboxing to Cabal/cabal-install. Hopefully this will fix my complaints about ghci integration and should make cabal-dev unnecessary.

There are definitely things that need to be done to improve the cabal tool chain. But in my experience working on several different large Haskell projects both open and proprietary I have found that the current state of Cabal combined with cabal-meta (and maybe cabal-dev) does a reasonable job at handling large project development within a very fast moving ecosystem.

A Practical Cabal Primer

2012-11-02T13:09:00.000-04:00

I've been doing full-time Haskell development for almost three years now, and while I recognize that Cabal has been painful to use at times, the current reality is that Cabal does what I need it to do and for the most part stays out of my way. In this post, I'll describe the Cabal best practices I've settled on for my Haskell development.

First, some terminology. GHC is the de facto Haskell compiler, Hackage is the package database, Cabal is a library providing package infrastructure, and cabal-install is a command line program (confusingly called "cabal") for building and installing packages, and downloading and uploading them from Hackage. This isn't a tutorial for installing Haskell, so I'll assume that you at least have GHC and cabal-install's "cabal" binary. If you have a very recent release of GHC, then you're asking for problems. At the time of this writing GHC 7.6 is a few months old, so don't use it unless you know what you're doing. Stick to 7.4 until maintainers have updated their packages. But do make sure you have the most recent version of Cabal and cabal-install because it has improved significantly.

cabal-install can install things as global or user. You usually have to have root privileges to install globally. Installing locally will put packages in your user's home directory. Executable binaries go in $HOME/.cabal/bin. Libraries go in $HOME/.ghc. Other than the packages that come with GHC, I install everything as user. This means that when I upgrade cabal-install with "cabal install cabal-install", the new binary won't take effect unless $HOME/.cabal/bin is at the front of my path.

Now I need to get the bad news over with up front. Over time your local Cabal package database will grow until it starts to cause problems. Whenever I'm having trouble building packages, I'll tinker with things a little to see if I can isolate the problem, but if that doesn't work, then I clean out my package repository and start fresh. On linux this can be done very simply with rm -fr ~/.ghc. Yes, this feels icky. Yes, it's suboptimal. But it's simple and straightforward, so either deal with it, or quit complaining and help us fix it.

I've seen people also say that you should delete the ~/.cabal directory as well. Most of the time that is bad advice. If you delete .cabal, you'll probably lose your most recent version of cabal-install, and that will make life more difficult. Deleting .ghc completely clears out your user package repository, and in my experience is almost always sufficient. If you really need to delete .cabal, then I would highly recommend copying the "cabal" binary somewhere safe and restoring it after you're done.

Sometimes you don't need to go quite so far as to delete everything in ~/.ghc. For more granular control over things, use the "ghc-pkg" program. "ghc-pkg list" shows you a list of all the installed packages. "ghc-pkg unregister foo-2.3" removes a package from the list. You can also use unregister without the trailing version number to remove every installed version of that package. If there are other packages that depend on the package you're removing, you'll get an error. If you really want to remove it, use the --force flag.

If you force unregister a package, then "ghc-pkg list" will show you all the broken packages. If I know that there's a particular hierarchy of packages that I need to remove, then I'll force remove the top one, and then use ghc-pkg to tell me all the others that I need to remove. This is an annoying process, so I only do it when I think it will be quicker than deleting everything and rebuilding it all.

So when do you need to use ghc-pkg? Typically I only use it when something breaks that I think should build properly. However, I've also found that having multiple versions of a package installed at the same time can sometimes cause problems. This can show up when the package I'm working on uses one version of a library, but when I'm experimenting in ghci a different version gets loaded. When this happens you may get perplexing error messages for code that is actually correct. In this situation, I've been able to fix the problem by using ghc-pkg to remove all but one version of the library in question.

If you've used all these tips and you still cannot install a package even after blowing away ~/.ghc, then there is probably a dependency issue in the package you're using. Haskell development is moving at a very rapid pace, so the upstream package maintainers may not be aware or have had time to fix the problem. You can help by alerting them to the problem, or better yet, including a patch to fix it.

Often the fix may be a simple dependency bump. These are pretty simple to do yourself. Use "cabal unpack foo-package-0.0.1" to download the package source and unzip it into the current directory. Then edit the .cabal file, change the bounds, and build the local package with "cabal install". Sometimes I will also bump the version of the package itself and then use that as the lower bound in the local package that I'm working on. That way I know it will be using my fixed version of foo-package. Don't be afraid to get your hands dirty. You're literally one command a way from hacking on upstream source.

For the impatient, here's a summary of my tips for basic cabal use:

Install the most recent versions of cabal-install
Don't install things with --global
Make sure $HOME/.cabal/bin is at the front of your path
Don't be afraid to use rm -fr ~/.ghc
Use ghc-pkg for fine-grained package control
User "cabal unpack" to download upstream code so you can fix things yourself

Using these techniques, I've found that Cabal actually works extremely well for small scale Haskell development--development where you're only working on a single package at a time and everything else is on hackage. Large scale development where you're developing more than one local package requires another set of tools. But fortunately we've already have some that work reasonably well. I'll discuss those in my next post.

Why Cabal Has Problems

2012-11-01T18:01:00.001-04:00

Haskell's package system, henceforth just "Cabal" for simplicity, has gotten some harsh press in the tech world recently. I want to emphasize a few points that I think are important to keep in mind in the discussion.

First, this is a hard problem. There's a reason the term "DLL hell" existed long before Cabal. I can't think of any package management system I've used that didn't generate quite a bit of frustration at some point.

Second, the Haskell ecosystem is also moving very quickly. There's the ongoing iteratees/conduits/pipes debate of how to do IO in an efficient and scalable way. Lenses have recently seen major advances in the state of the art. There is tons of web framework activity. I could go on and on. So while Hackage may not be the largest database of reusable code, the larger ones like CPAN that have been around for a long time are probably not moving as fast (in terms of advances in core libraries).

Third, I think Haskell has a unique ability to facilitate code reuse even for relatively small amounts of code. The web framework scene demonstrates this fairly well. As I've said before, even though there are three main competing frameworks, libraries in each of the frameworks can be mixed and matched easily. For example, web-routes-happstack provides convenience code for gluing together the web-routes package with happstack. It is 82 lines of code. web-routes-wai does the same thing for wai with 81 lines of code. The same thing could be done for Snap with a similar amount of code.

The languages with larger package repositories like Ruby and Python might also have small glue packages like this, but they don't have the powerful strong type system. This means that when a Cabal build fails because of dependency issues, you're catching an interaction much earlier than you would have caught it in the other languages. This is what I'm getting at when I say "unique ability to facilitate code reuse".

When you add Haskell's use of cross-module compiler optimizations to all these previous points, I think it makes a compelling case that the Haskell community is at or near the frontier of what has been done before even though we may be a ways away in terms of raw number of packages and developers. Thus, it should not be surprising that there are problems. When you're at the edge of the explored space, there's going to be some stumbling around in the dark and you might go down some dead end paths. But that's not a sign that there's something wrong with the community.

Note: The first published version of this article made some incorrect claims based on incorrect information about the number of Haskell packages compared to the number of packages in other languages. I've removed the incorrect numbers and adjusted my point.

LTMT Part 2: Monads

2012-04-17T08:30:00.000-04:00

In part 1 of this tutorial we talked about types and kinds. Knowledge of kinds will help to orient yourself in today's discussion of monads.

What is a monad? When you type "monad" into Hayoo the first result takes you to the documentation for the type class Monad. If you don't already have a basic familiarity with type classes, you can think of a type class as roughly equivalent to a Java interface. A type class defines a set of functions involving a certain data type. When a data type defines all the functions required by the type class, we say that it is an instance of that type class. When a type Foo is an instance of the Monad type class, you'll commonly hear people say "Foo is a monad". Here is a version of the Monad type class.

class Monad m where
    return :: a -> m a
    (=<<) :: (a -> m b) -> m a -> m b

(Note: If you're the untrusting type and looked up the real definition to verify that mine is accurate, you'll find that my version is slightly different. Don't worry about that right now. I did it intentionally, and there is a method to my madness.)

This basically says that in order for a data type to be an instance of the Monad type class, it has to define the two functions return and (=<<) (pronounced "bind") that have the above type signatures. What do these type signatures tell us? Let's look at return first. We see that it returns a value of type m a. This tells us that m has the kind signature m :: * -> *. So whenever we hear someone say "Foo is a monad" we immediately know that Foo :: * -> *.

In part 1, you probably got tired of me emphasizing that a type is a context. When we look at return and bind, this starts to make more sense. The type m a is just the type a in the context m. The type signature return :: a -> m a tells us that the return function takes a plain value a and puts that value into the context m. So when we say something is a monad, we immediately know that we have a function called return that lets us put arbitrary other values into that context.

Now, what about bind? It looks much more complicated and scary, but it's really pretty simple. To see this, let's get rid of all the m's in the type signature. Here's the before and after.

before :: (a -> m b) -> m a -> m b
after  :: (a -> b) -> a -> b

The type signature for after might look familiar. It's exactly the same as the type signature for the ($) function! If you're not familiar with it, Haskell's $ function is just syntax sugar for function application. (f $ a) is exactly the same as (f a). It applies the function f to its argument a. It is useful because it has very low precedence and is right associative, so it is a nice syntax sugar that allows us to eliminate parenthesis in certain situations. When you realize that (=<<) is roughly analogous to the concept of function application (modulo the addition of a context m), it suddenly makes a lot more sense.

So now what happens when we look at bind's type signature with the m's back in? (f =<< k) applies the function f to the value k. However, the crucial point is that k is a value wrapped in the context m, but f's parameter is an unwrapped value a. From this we see that the bind function's main purpose is to pull a value out of the context m and apply the function f, which does some computation, and returns the result back in the context m again.

The monad type class does not provide any mechanism for unconditionally pulling a value out of the context. The only way to get access to the unwrapped value is with the bind function, but bind does this in a controlled way and requires the function to wrap things up again before the result is returned. This behavior, enabled by Haskell's strong static type system, provides complete control over side effects and mutability.

Some monads do provide a way to get a value out of the context, but the choice of whether to do so is completely up to the author of said monad. It is not something inherent in the concept of a monad.

Monads wouldn't be very fun to use if all you had was return, bind, and derived functions. To make them more usable, Haskell has a special syntax called "do notation". The basic idea behind do notation is that there's a bind between every line, and you can do a <- func to unwrap the return value of func and make it available to later lines with the identifier 'a'.

You can find a more detailed treatment of do notation elsewhere. I hear that Learn You a Haskell and Real World Haskell are good.

In summary, a monad is a certain type of context that provides two things: a way to put things into the context, and function application within the context. There is no way to get things out. To get things out, you have to use bind to take yourself into the context. Once you have these two operations, there are lots of other more complicated operations built on the basic primitives that are provided by the API. Much of this is provided in Control.Monad. You probably won't learn all this stuff in a day. Just dive in and use these concepts in real code. Eventually you'll find that the patterns are sinking in and becoming clearer.

The Less Travelled Monad Tutorial: Understanding Kinds

2012-04-16T08:30:00.000-04:00

This is part 1 of a monad tutorial (but as we will see, it's more than your average monad tutorial). If you already have a strong grasp of types, kinds, monads, and monad transformers, and type signatures like newtype RST r s m a = RST { runRST :: r -> s -> m (a, s) } don't make your eyes glaze over, then reading this won't change your life. If you don't, then maybe it will.

More seriously, when I was learning Haskell I got the impression that some topics were "more advanced" and should wait until later. Now, a few years in, I feel that understanding some of these topics earlier would have significantly sped up the learning process for me. If there are other people out there whose brains work somewhat like mine, then maybe they will be able to benefit from this tutorial. I can't say that everything I say here will be new, but I haven't seen these concepts organized in this way before.

This tutorial is not for absolute beginners. It assumes a basic knowledge of Haskell including the basics of data types, type signatures, and type classes. If you've been programming Haskell for a little bit, but are getting stuck on monads or monad transformers, then you might find some help here.

data Distance = Dist Double
data Mass = Mass Double

This code defines data types called Distance and Mass. The name on the left side of the equals sign is called a type constructor (or sometimes shortened to just type). The Haskell compiler automatically creates functions from the names just to the right of the equals sign. These functions are called data constructors because they construct the types Distance and Mass. Since they are functions, they are also first-class values, which means they have types as seen in the following ghci session.

$ ghci ltmt.hs
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for helpghci> :t Dist
Dist :: Double -> Distance
ghci> :t Mass
Mass :: Double -> Mass
ghci> :t Distance
<interactive>:1:1: Not in scope: data constructor `Distance'

We see here that Dist and Mass are functions that return the types Distance and Mass respectively. Frequently you'll encounter code where the type and the constructor have the same name (as we have here with Mass). Distance, however, illustrates that these are really two separate entities. Distance is the type and Dist is the constructor. Types don't have types, so the ":t" command fails for Distance.

Now, we need to pause for a moment and think about the meaning of these things. What is the Distance type? Well, when we look at the constructor, we can see that a value of type Distance contains a single Double. The constructor function doesn't actually do anything to the Double value in the process of constructing the Distance value. All it does is create a new context for thinking about a Double, specifically the context of a Double that we intend to represent a distance quantity. (Well, that's not completely true, but for the purposes of this tutorial we'll ignore those details.) Let me repeat that. A type is just a context. This probably seems so obvious that you're starting to wonder about me. But I'm saying it because I think that keeping it in mind will help when talking about monads later.

Now let's look at another data declaration.

data Pair a = MkPair a a

This one is more interesting. The type constructor Pair takes an argument. The argument is some other type a and that is used in some part of the data constructor. When we look to the right side, we see that the data constructor is called MkPair and it constructs a value of type "Pair a" from two values of type "a".

MkPair :: a -> a -> Pair a

The same thing we said for the above types Distance and Mass applies here. The type constructor Pair represents a context. It's a context representing a pair of values. The type Pair Int represents a pair of Ints. The type Pair String represents a pair of strings. And on and on for whatever concrete type we use in the place of a.

Again, this is all very straightforward. But there is a significant distinction between the two type constructors Pair and Distance. Pair requires a type parameter, while Distance does not. This brings us to the topic of kinds. (Most people postpone this topic until later, but it's not hard to understand and I think it helps to clarify things later.) You know those analogy questions they use on standardized tests? Here's a completed one for you:

values : types    ::   types : kinds

Just as we categorize values by type, we categorize type constructors by kind. GHCi lets us look up a type constructor's kind with the ":k" command.

ghci> :k Distance
Distance :: *
ghci> :k Mass
Mass :: *
ghci> :k Dist
<interactive>:1:1: Not in scope: type constructor or class `Dist'
ghci> :k Pair
Pair :: * -> *
ghci> :k Pair Mass
Pair Mass :: *

In English we would say "Distance has kind *", and "Pair has kind * -> *". Kind signatures look similar to type signatures because they are. When we use Mass as Pair's first type argument, the result has kind *. The Haskell report defines kind signatures with the following two rules.

The symbol * represents the kind of all nullary type constructors (constructors that don't take any parameters).
If k1 and k2 are kinds, then k1->k2 is the kind of types that take one parameter that is a type of kind k1 and return a type of kind k2.

As an exercise, see if you can work out the kind signatures for the following type constructors. You can check your work with GHCi.

data Tuple a b = Tuple a b
data HardA a = HardA (a Int)
data HardB a b c = HardB (a b) (c a Int)

Before reading further, I suggest attempting to figure out the kind signatures for HardA and HardB because they involve a key pattern that will come up later.

Welcome back. The first example is just a simple extension of what we've already seen. The type constructor Tuple has two arguments, so it's kind signature is Tuple :: * -> * -> *. Also if you try :t you'll see that the data constructor's type signature is Tuple :: a -> b -> Tuple a b.

In the case of the last two types, it may be a little less obvious. But they build on each other in fairly small, manageable steps. For HardA, in the part to the left of the equals sign we see that there is one type parameter 'a'. From this, we can deduce that HardA's kind signature is something of the form ? -> *, but we don't know exactly what to put at the question mark. On the right side, all the individual arguments to the data constructor must have kind *. If (a Int) :: *, then the type 'a' must be a type constructor that takes one parameter. That is, it has kind * -> *, which is what we must substitute for the question mark. Therefore, we get the final kind signature HardA :: (* -> *) -> *.

HardB is a very contrived and much more complex case that exercises all the above simple principles. From HardB a b c we see that HardB has three type parameters, so it's kind signature has the form HardB :: a -> b -> c -> *. On the right side the (a b) tells us that b :: * and a :: * -> *. The second part (c a Int) means that c is a type constructor with two parameters where its first parameter is a, which has the type signature we described above. So this gives us c :: (* -> *) -> * -> *. Now, substituting all these in, we get HardB :: (* -> *) -> * -> ((* -> *) -> * -> *) -> *.

The point of all this is to show that when you see juxtaposition of type constructors (something of the form (a b) in a type signature), it is telling you that the context a is a non-nullary type constructor and b is its first parameter.

Continue on to Part 2 of the Less Travelled Monad Tutorial