Efficient Amortised and Real-Time Queues in Haskell

Friday, 15 January 2016, by Edsko de Vries.
Filed under coding.

A queue is a datastructure that provides efficient—O(1)—operations to remove an element from the front of the queue and to insert an element at the rear of the queue. In this blog post we will discuss how we can take advantage of laziness to implement such queues in Haskell, both with amortised and with worst-case O(1) bounds.

The results in this blog post are not new, and can be found in Chris Okasaki’s book “Purely Functional Data Structures”. However, the implementation and presentation here is different from Okasaki’s. In particular, the technique we use for real-time datastructures is more explicit and should scale to datastructures other than queues more easily than Okasaki’s.

(Read more …)

Haskell courses in New York City

Tuesday, 12 January 2016, by Adam Gundry.
Filed under community, training, well-typed.

Well-Typed is happy to announce that once again we will be running Haskell training courses in New York alongside

C◦mp◦se conference

Thursday, February 4 – Sunday, February 7, 2016, New York City

This conference is focused on typed functional programming and features a keynote by Eugenia Cheng and an excellent line-up of talks including one by our own Austin Seipp on Cryptography and verification with Cryptol. There’s also an “unconference” with small workshops and tutorials as well as the opportunity to get your hands dirty and try things out yourself.

For several years now, we have been running successful Haskell courses in collaboration in Skills Matter. The New York courses will be taught by Duncan Coutts, co-founder and partner at Well-Typed. He’s an experienced teacher and is involved in lots of commercial Haskell development projects at Well-Typed.

You can participate in our Haskell courses directly before or directly after C◦mp◦se in February, or if that doesn’t suit we are running two of the courses in London this April:

Fast Track to Haskell

Tuesday, February 2 – Wednesday, February 3, 2016, New York City
(and Monday, April 4 – Tuesday, April 5, 2016, London)

Find out more or register here.

This course is for developers who want to learn about functional programming in general or Haskell in particular. It introduces important concepts such as algebraic datatypes, pattern matching, type inference, polymorphism, higher-order functions, explicit effects and, of course, monads and provides a compact tour with lots of hands-on exercises that provide a solid foundation for further adventures into Haskell or functional programming.

Guide to Haskell Performance and Optimization

Monday, February 8 – Tuesday, February 9, 2016, New York City
(and Wednesday, April 6 – Thursday, April 7, 2016, London)

Find out more or register here.

This brand-new course looks under the surface of Haskell at how things are implemented, including how to reason about performance and optimize your programs, so that you can write beautiful programs that scale. It covers the internal representation of data on the heap, what exactly lazy evaluation means and how it works, how the compiler translates Haskell code to a target language via several internal representations, what you can and cannot reasonably expect the compiler to do, and how you can tweak the optimizer behaviour by using compiler pragmas such as inlining annotations and rewrite rules.

Guide to the Haskell Type System

Wednesday, February 10, 2016, New York City

Find out more or register here.

This course is a one-day introduction to various type-system extensions that GHC offers, such as GADTs, rank-n polymorphism, type families and more. It assumes some familiarity with Haskell. It does not make use of any other advanced Haskell concepts except for the ones it introduces, so it is in principle possible to follow this course directly after Fast Track. However, as this course focuses on the extreme aspects of Haskell’s type system, it is particularly recommended for participants who are enthusiastic about static types and perhaps familiar with a strong static type system from another language.

Well-Typed training courses

In general, our courses are very practical, but don’t shy away from theory where necessary. Our teachers are all active Haskell developers with not just training experience, but active development experience as well. In addition to the courses in New York, we regularly offer courses in London.

We also provide on-site training on requests nearly anywhere in the world. If you want to know more about our training or have any feedback or questions, have a look at our dedicated training page or just drop us a mail.


Dependently typed servers in Servant

Wednesday, 02 December 2015, by Edsko de Vries, Andres Löh.
Filed under coding.

Suppose we have a webserver that can perform different kinds of operations on different kinds of values. Perhaps it can reverse or capitalize strings, and increment or negate integers:

# curl http://localhost:8081/example/reverse
elpmaxe

# curl http://localhost:8081/example/caps
EXAMPLE

# curl http://localhost:8081/1234/inc
1235

# curl http://localhost:8081/1234/neg
-1234

Moreover, it can echo back any value:

# curl http://localhost:8081/example/echo
example

# curl http://localhost:8081/1234/echo
1234

However, it does not make sense to try to reverse an integer or increment a string; requesting either of

http://localhost:8081/1234/reverse
http://localhost:8081/example/inc

should result in HTTP error.

This is an example of a dependently typed server: the value that we are given as input determines the type of the rest of the server. If we get a string as input, we expect a string operation as the second argument and the response is also a string; if we get an integer as input, we expect an integer operation as the second argument and the response is also an integer.

(Read more …)

Implementing a minimal version of haskell-servant

Wednesday, 04 November 2015, by Andres Löh.
Filed under coding.

Recently, there was a question on Stack Overflow on how Servant actually works. Others were quick to suggest the Servant paper as a thorough explanation of the approach and the implementation.

As a co-author, I’m obviously happy if the paper is being read, but it’s also 12 pages long in two-column ACM style. And while it explains the implementation, it does not necessarily make it easier to start playing with the code yourself, because it only shows excerpts, and code snippets in a paper are not easily runnable.

At the same time, whenever I want to demonstrate a new concept in the Servant context, or play with new ideas, I find myself not impementing it in the main Servant code base, but rather to create a small library that is “like Servant”, built on the same principles, but much simpler, so that I have less work to do and can evaluate the ideas more quickly. I’ve talked to some other contributors, and at least some of them are doing the same. So I thought it might be useful to develop and present the code of “TinyServant”, which is not exactly tiny, but still small compared to the full Servant code base, strips away a lot of duplication and unessential extras, but is still complete enough so that we can observe how Servant works. Obviously, this still won’t explain everything that one might want to know about the implementation of Servant, but I hope that it will serve as a useful ingredient in that process.

This blog post is a somewhat revised and expanded version of my Stack Overflow answer.

This is not a general tutorial on Servant and using Servant. For learning how to use Servant, the official Servant tutorial or the general documentation section of the Servant home page are better starting points.

(Read more …)

Haskell Hackathon, Haskell eXchange, Haskell courses in London, October 2015

Friday, 11 September 2015, by Andres Löh.
Filed under well-typed, community, training.

Haskell events in London

In the time from 5–13 October, we are (co-)organizing a number of Haskell-related events in London, with Skills Matter.

Here’s the overview:

Haskell infrastructure Hackathon

We’ll co-organize and participate in a two-day Haskell Hackathon, which takes place directly after the Haskell eXchange.

This Hackathon aims at bringing together Haskell developers – both beginners and experts – who want to help improve the Haskell infrastructure, predominantly Hackage and Cabal.

We’ll aim to arrange some introductory overview talks, to e.g. provide an overview over the code bases and the most important open issues.

Participation is free, but please register via Skills Matter.

(Read more …)

Hackage Security Beta Release

Tuesday, 25 August 2015, by Edsko de Vries, Duncan Coutts.
Filed under cabal, community, industrial-haskell-group.

Well-Typed and the Industrial Haskell Group are very happy to announce the beta release of the hackage-security library, along with its integration in hackage-server and cabal-install. The new security features of hackage are now deployed on the central server hackage.haskell.org and there is a beta release of cabal available. You can install it through

cabal install \
  http://www.well-typed.com/hackage-security/Cabal-1.23.0.0.tar.gz \
  http://www.well-typed.com/hackage-security/cabal-secure-beta.tar.gz \
  http://www.well-typed.com/hackage-security/hackage-security-0.4.0.0.tar.gz \
  http://www.well-typed.com/hackage-security/tar-0.4.2.2.tar.gz

This will install a cabal-secure-beta binary which you can use alongside your normal installation of cabal.

For a more detailed discussion of the rationale behind this project, see the annoucement of the alpha release or the initial announcement of this project. We will also be giving a talk about the details at the upcoming Haskell Implementors Workshop. In the remainder of this blog post we will describe what’s available, right now.

(Read more …)

Parametricity Tutorial (Part 2): Type constructors and type classes

Friday, 14 August 2015, by Edsko de Vries.
Filed under coding.

This is part 2 of a two-part series on parametricity.

In part 1 we covered the basics: constant types, functions and polymorphism (over types of kind *). In this post we will deal with more advanced material: type constructors, type classes, polymorphism over type constructors and type constructor classes.

(Read more …)

Lightweight Checked Exceptions in Haskell

Friday, 31 July 2015, by Edsko de Vries, Adam Gundry.
Filed under coding.

Consider this function from the http-conduit library:

-- | Download the specified URL (..)
--
-- This function will 'throwIO' an 'HttpException' for (..)
simpleHttp :: MonadIO m => String -> m ByteString

Notice that part of the semantics of this function—that it may throw an HttpException—is encoded in a comment, which the compiler cannot check. This is because Haskell’s notion of exceptions offers no mechanism for advertising to the user the fact that a function might throw an exception.

Michael Snoyman discusses some solutions to this problem, as well as some common anti-patterns, in his blog post Exceptions Best Practices. However, wouldn’t it be much nicer if we could simply express in the type that simpleHttp may throw a HttpException? In this blog post I will propose a very lightweight scheme to do precisely that.

If you want to experiment with this yourself, you can download CheckedRevisited.hs (tested with ghc 7.2, 7.4, 7.6, 7.8 and 7.10).

Note. This is an improved version of this blog post; Checked.hs demonstrates the previous approach; see also the discussion on reddit on the original post and on the improved version.

(Read more …)

Hackage Security Alpha Release

Wednesday, 08 July 2015, by Edsko de Vries.
Filed under cabal, community, industrial-haskell-group.

Well-Typed is very happy to announce the first alpha release of the Hackage Security library, along with integration into both cabal-install and the Hackage server and a tool for managing file-based secure repositories. This release is not yet ready for general use, but we would like to invite interested parties to download and experiment with the library and its integration. We expect a beta release running on the central Hackage server will soon follow.

Hackage Security and related infrastructure is a project funded by the Industrial Haskell Group to secure Hackage, the central Haskell package server. A direct consequence of this work is that we can have untrusted Hackage mirrors (mirror selection is directly supported by the library). A minor but important additional side goal is support for incremental updates of the central Hackage index (only downloading information about new packages, rather than all packages).

TL;DR: Hackage will be more secure, more reliable and faster, and cabal update should generally finish in seconds.

(Read more …)

Dependencies for Cabal Setup.hs files and other goodies

Monday, 06 July 2015, by Duncan Coutts.
Filed under cabal, community, industrial-haskell-group.

No untracked dependencies!

Years ago, back when Isaac Potoczny-Jones and others were defining the Cabal specification, the big idea was to make Haskell software portable to different environments. One of the mantras was “no untracked dependencies!”.

The problem at the time was that Haskell code had all kinds of implicit dependencies which meant that while it worked for you, it wouldn’t build for me. For example, I might not have some other module that it needed, or the right version of the module.

So of course that’s what the build-depends in .cabal files is all about, requiring that the author of the code declare just what the code requires of its environment. The other important part is that the build system only lets your code see the dependencies you’ve declared, so that you don’t accidentally end up with these untracked dependencies.

This mantra of no untracked dependencies is still sound. If we look at a system like nix, part of what enables it to work so well is that it is absolutely fanatical about having no untracked dependencies.

Untracked dependencies?!

One weakness in the original Cabal specification is with Setup.hs scripts. These scripts are defined in the spec to be the entry point for the system. According to the Cabal spec, to build a package you’re required to compile the Setup.hs script and then use its command line interface to get things done. Because in the original spec the Setup.hs is the first entry point, it’s vital that it be possible to compile Setup.hs without any extra fuss (the runhaskell tool was invented just to make this possible, and to make it portable across compilers).

But by having the Setup.hs as the primary entry point, it meant that it’s impossible to reliably use external code in a Setup.hs script, because you cannot guarantee that that code is pre-installed. Going back to the “no untracked dependencies” mantra, we can see of course that all dependencies of Setup.hs scripts are in fact untracked!

This isn’t just a theoretical problem. Haskell users that do have complex Setup.hs scripts often run into versioning problems, or need external tools to help them get the pre-requisite packages installed. Or as another example: Michael Snoyman noted earlier this year in a diagnosis of an annoying packaging bug that:

As an aside, this points to another problematic aspect of our toolchain: there is no way to specify constraints on dependencies used in custom Setup.hs files. That’s actually caused more difficulty than it may sound like, but I’ll skip diving into it for now.

The solution: track dependencies!

As I said, the mantra of no untracked dependencies is still sound, we just need to apply it more widely.

These days the Setup.hs is effectively no longer a human interface, it is now a machine interface used by other tools like cabal or by distro’s install scripts. So we no longer have to worry so much about Setup.hs scripts always compiling out of the box. It would be acceptable now to say that the first entry point for a tool interacting with a package is the .cabal file, which might list the dependencies of the Setup.hs. The tool would then have to ensure that those dependencies are available when compiling the Setup.hs.

So this is exactly what we have now done. Members of the Industrial Haskell Group have funded us to fix this long standing problem and we have recently merged the solution into the development version of Cabal and cabal-install.

From a package author’s point of view, the solution looks like this: in your .cabal file you can now say:

build-type: Custom

custom-setup
  setup-depends: base >= 4.6,
                 directory >= 1.0,
                 Cabal >= 1.18 && < 1.22,
                 acme-setup-tools == 0.2.*

So it’s a new stanza, like libraries or executables, and like these you can specify the library dependencies of the Setup.hs script.

Now tools like cabal will compile the Setup.hs script with these and only these dependencies, just like it does normally for executables. So no more untracked dependencies in Setup.hs scripts. Newer cabal versions will warn about not using this new section. Older cabal versions will ignore the new section (albeit with a warning). So over time we hope to encourage all packages with custom setup scripts to switch over to this.

In addition, the Setup.hs script gets built with CPP version macros (MIN_VERSION_{pkgname}) available so that the code can be made to work with a wider range of versions of its dependencies.

In the solver…

So on the surface this is all very simple and straightforward, a rather minor feature even. In fact it’s been remarkably hard to implement fully for reasons I’ll explain, but the good news is that it works and the hard work has also gotten us solutions to a couple other irksome problems.

Firstly, why isn’t it trivial? It’s inevitable that sooner or later you will find that your application depends on one package that has setup deps like Cabal == 1.18.* and another with setup deps like Cabal == 1.20.*. At that point we have a problem. Classically we aim to produce a build plan that uses at most one version of each package. We do that because otherwise there’s a danger of type errors from using multiple versions of the same package. Here with setup dependencies there is no such danger: it’s perfectly possible for me to build one setup script with one version of the Cabal library and another script with a different Cabal version. Because these are executables and not libraries, the use of these dependencies does not “leak”, and so we would be safe to use different versions in different places.

So we have extended the cabal solver to allow for limited controlled use of multiple versions of the same package. The constraint is that all the “normal” libraries and exes all use the same single version, just as before, but setup scripts are allowed to introduce their own little world where independent choices about package versions are allowed. To keep things sane, the solver tries as far as possible not to use multiple versions unless it really has to.

If you’re interested in the details in the solver, see Edsko’s recent blog post.

Extra goodies

This work in the solver has some extra benefits.

Improve Cabal lib API without breaking everything

In places the Cabal library is a little crufty, and the API it exposes was never really designed as an API. It has been very hard to fix this because changes in the Cabal library interface break Setup.hs scripts, and there was no way for packages to insulate themselves from this.

So now that we can have packages have proper dependencies for their custom Setup.hs, the flip side is that we have an opportunity to make breaking changes to the Cabal library API. We have an opportunity to throw out the accumulated cruft, clean up the code base and make a library API that’s not so painful to use in Setup.hs scripts.

Shim (or compat) packages for base

Another benefit is that the new solver is finally able to cope with having “base shim” packages, as we used in the base 3.x to 4.x transition. For two GHC releases, GHC came with both base-3.x and base-4.x. The base-4 was the “true” base, while the base-3 was a thin wrapper that re-exported most of base-4 (and syb), but with some changes to implement the old base-3 API. At the time we adapted cabal to cope with this situation of having two versions of a package in a single solution.

When the new solver was implemented however support for this situation was not added (and the old solver implementation was retained to work with GHC 6.12 and older).

This work for setup deps has made it relatively straightforward to add support for these base shims. So next time GHC needs to make a major bump to the version of base then we can use the same trick of using a shim package. Indeed this might also be a good solution in other cases, perhaps cleaner than all these *-compat packages we’ve been accumulating.

It has also finally allowed us to retire the old solver implementation.

Package cycles involving test suites and benchmarks

Another feature that is now easy to implement (though not actually implemented yet) is dealing with the dependency cycles in packages’ test suites and benchmarks.

Think of a core package like bytestring, or even less core like Johan’s cassava csv library. These packages have benchmarks that use the excellent criterion library. But of course criterion is a complex beast and itself depends on bytestring, cassava and a couple dozen other packages.

This introduces an apparent cycle and cabal will fail to find an install plan. I say apparent cycle because there isn’t really a cycle: it’s only the benchmark component that uses criterion, and nothing really depends on that.

Here’s another observation: when benchmarking a new bytestring or cassava, it does not matter one bit that criterion might be built against an older stable version of bytestring or cassava. Indeed it’s probably sensible that we use a stable version. It certainly involves less rebuilding: I don’t really want to rebuild criterion against each minor change in bytestring while I’m doing optimisation work.

So here’s the trick: we break the cycle by building criterion (or say QuickCheck or tasty) against another version of bytestring, typically some existing pre-installed one. So again this means that our install plan has two versions of bytestring in it: the one we mean to build, and the one we use as a dependency for criterion. And again this is ok, just as with setup dependencies, because dependencies of test suites and benchmarks do not “leak out” and cause diamond dependency style type errors.

One technical restriction is that the test suite or benchmark must not depend on the library within the same package, but must instead use the source files directly. Otherwise there would genuinely be a cycle.

Now in general when we have multiple components in a .cabal file we want them to all use the same versions of their dependencies. It would be deeply confusing if a library and an executable within the same package ended up using different versions of some dependency that might have different behaviour. Cabal has always enforced this, and we’re not relaxing it now. The rule is that if there are dependencies of a test suite or benchmark that are not shared with the library or executable components in the package, then we are free to pick different versions for those than we might pick elsewhere within the same solution.

As another example – that’s nothing to do with cycles – we might pick different versions of QuickCheck for different test suites in different packages (though only where necessary). This helps with the problem that one old package might require QuickCheck == 2.5.* while another requires QuickCheck == 2.8.*. But it’d also be a boon if we ever went through another major QC-2 vs QC-3 style of transition. We would be able to have both QC-2 and QC-3 installed and build each package’s test suite against the version it requires, rather than freaking out that they’re not the same version.

Private dependencies in general

Technically, this work opens the door to allowing private dependencies more generally. We’re not pursuing that at this stage, in part because it is not clear that it’s actually a good idea in general.

Mark Lentczner has pointed out the not-unreasonable fear that once you allow multiple versions of packages within the same solution it will in practice become impossible to re-establish the situation where there is just one version of each package, which is what distros want and what most people want in production systems.

So that’s something we should consider carefully as a community before opening those flood gates.


Previous entries