ICFP 2018

This year again ICFP and the Haskell Symposium are full of interesting talks that I want to shortly present. I highlighted a single sentence in each section to try to summarize the main idea so that you can skim the whole thing and stop at what looks interesting to you.

ICFP Day 1

Capturing the Future by Replaying the Past (Functional Pearl)

Delimited continuations are incredibly powerful because they allow us to implement any monadic effect. They also allow some elegant implementations, for example the 8 queens problem can be implemented using a non-determinism effect. Unfortunately delimited continuations are not supported by every programming language. Or are they? Actually the authors of this paper show that mutable state + exceptions is all that is required to implement delimited continuations (except in C, read the paper for the details). There is a performance hit if we compare their implementation with a direct support from languages which support delimited continuations but this is not that bad.

For me this paper was the opportunity, one more time, to try to wrap my head around continuations. For example I realized that the notation with reset and shift was a bit confusing. In an expression such as reset (shift (\k -> k 2)) I actually need to focus my attention on the body of the shift rather than the body of the reset. And the body of the shift says “do k 2”. What’s the k? Well it is whatever is outside of the shift and inside the reset so that’s 1 + _ and eventually the result is 3. It becomes a bit trickier to interpret expressions like reset (shift (1 + k 2) * shift (1 + k 3)) but still possible. “Do 1 + k 2”. What is k? It is x * shift (1 + k 3). Which by the previous reasoning is k = 1 + x * 3. Now applied to 1 + k 2 gives 1 + 1 + 2 * 3 which equals to 8. This also explains the term “thermometer continuations” where the authors store a list of executions created by the various shifts in a reset expression.

Versatile Event Correlation with Algebraic Effects

This paper presents the design of language supporting “versatile joins”, that is the many ways we would like to correlate different sources of (asynchronous) events: “when you receive a ‘stock price update’ event and ‘user buy event’ for the same quantity and a ‘market is opened event’ then emit a ‘stock buy event’”. Conceptually this means making a cartesian product of all the event sources and restricting the resulting tuples to the ones that are “interesting”. Said another way, this can be interpreted as having a way to enumerate this cartesian product, filter out some tuples, combine them in some way and yield the result. It turns out that all those actions can be implemented as effects in a language supporting algebraic effects and effect handlers.

For example selecting the last event for a given event stream corresponds to the handling of a push effect for that stream. and joining several streams corresponds to the interpretation of several push 1, push 2, ..., push n effects. This provides a very modular way to describe combinations like “with the latest occurrence of stock and price for a given article emit an availability event”.

The paper shows that with a limited set of effects, like push but also trigger to trigger the materialization of a tuple or get/set to temporarily store events, we can reproduce most of the behaviours exposed by so-called “complex event processing” (CEP) libraries: windowing, linear/affine consumption, zipping, and so on.

The simple essence of automatic differentiation

One of the distinguished papers of the conference, classical Conal Elliot work, a work of art. The explosion of machine learning methods using neural networks brought back the need to have efficient ways to compute the derivative of functions. When you try to fit the parameters of a neural network to match observed data you typically use “gradient descent” methods which require to compute the partial derivative of functions with thousands of input variables and generally just one output!

The basic idea behind “automatic differentiation” is to build functions with their associated derivative functions. Since many functions are not differentiable, what we can do is to build the ones that are! You start by creating simple functions for which you know the derivative and use some rules for creating more complex functions from the simple ones, calculating the corresponding derivative as you go, using well-known rules for deriving functions. For example the “chain rule” for the derivative of the composition of 2 functions. In practice the derivative of a function can be built out of a few operations: function composition, parallel product, cartesian product, and linear functions (like +).

Actually those operations are pretty universal. If we abstract a bit by using category theory concepts we can define the derivative of a function in terms of operations from a category, a “monoidal” category, a “cartesian” category. Then by varying the category, taking other categories than Haskell functions for example, we can derive very useful programs. This is not new and was presented in “compiling to categories”, there is even a Haskell plugin supporting this construction automatically!

The paper builds on this idea for automatic differentiation and shows that using the “continuation of a category”, or the “dual of a category” or taking matrices as a category we get straightforward implementations of the differentiation of functions. In particular we get a simple implementation of the “reverse mode” of differentiation which does not mutate state like traditional algorithms and which can hence be easily parallelizable.

ICFP Day 2

Competitive Parallelism: Getting Your Priorities Right

This is yet another “let’s create a language to solve a specific problem” but an important one which is the definition of priorities in a concurrent program. What we typically want is to be able to specify a partial order to define which thread “has a higher priority”, make sure that high-priority threads don’t depend on low-priority ones (the “priority inversion” problem), get an efficient way to schedule those threads on processors and get some bounds on the total computation time/latency of a high priority thread for a given program.

The authors have defined and implemented a language called “PriML” extending Standard ML with some new primitives, priority, order, a modal type system and a scheduler to support all these objectives. I wonder how we could design languages and compilers so that anyone can benefit from those features rather sooner than later but this seems to provide a good solution to the priority inversion problem that jeopardized the Mars Pathfinder mission.

Fault Tolerant Functional Reactive Programming (Functional Pearl)

Ivan Perez and his team have already shown how to use a “Monadic Stream” representation to implement all the operators of various FRP (Functional Reactive Programming) libraries in Haskell. FRP can be used to represent various components of a Mars rover for example where there are various sensors and processors controling the behaviour of the rover.

Since this “monadic streams” representation allows you to change the “base” monad for streaming values they now use a variant of the Writer monad to represent fault information in computations: “what’s is the probability that the value returned by a sensor is incorrect?”, “if it is incorrect, what is the likely cause for the failure?”. Then combining different reactive values will cumulate failure probabilities. However you can also introduce redundant components which will reduce the failure rate! Their library also tracks the failure causes at the type level so that you can have ways to handle a failure and the compiler can check that you have handled all possible failures for a given system.

Report on ICFP and Climate Change

Not a technical paper but a report on what SIGPLAN plans to do to reduce carbon emissions. Benjamin Pierce presented the rationale for doing something and announced that next year ICFP 2019 might become carbon neutral by raising the price of tickets to buy carbon offsets. I personally bought my own carbon offset for my trip to ICFP this year and I hope this will inspire other people to do the same, we just don’t have much time left to act on climate change.

What You Needa Know about Yoneda: Profunctor Optics and the Yoneda Lemma (Functional Pearl)

What category theory is good for again? Well some results from category theory show up in many contexts and give us practical ways to transform some problems into others that are easier to deal with. The Yoneda lemma is one such result. It kind of says that the result of “transforming” a value a, noted f a is entirely determined by how all the objects that have a relation with a are being transformed: forall x . (a -> x) -> f x.

Using Haskell and assuming that f is a functor the equivalence is pretty obvious. If I have forall x . (a -> x) -> f x I can just set x to be a to get a f a. In the other direction, if I have an f a I also have a forall x . (a -> x) -> f x, that’s the fmap operation! In retrospect that’s kind of meh, what’s the big deal? Well we can prove tons of stuff with this lemma. For example monads have a bind operation: bind :: m a -> (a -> m b) -> m b. By using the Yoneda lemma we can prove that this is totally equivalent to having a join operation: join :: m (m a) -> m a!

Another application of this lemma and the meat of this paper is the derivation of profunctor optics as found in the Haskell lens library, from the “classical” representation as a getter and setter. Why is that even useful? It is useful because the profunctor formulation uses a simple function to support lens operations. This means that to compose 2 lenses you can just use function composition. The Yoneda lemma helped us going from one representation to a more useful one!

Generic Deriving of Generic Traversals

This is a new Haskell library which gives us lenses for any datatype deriving Generic. One application is to solve the “record problem” in Haskell where there can be clashes when 2 different records have the same name for one of their fields. In that case person ^. field@"name" will return the name of a Person and dog ^. field@"name" will work similarly. But the library can do much more. It allows you to select/update elements in a data structure by type, position, constraint (all the elements of the Num typeclass for example) and even by structure! So you can focus on all the fields of a Scrollbar that makes it a Widget and apply a function to modify the relevant Widget fields. This will return a Scrollbar with modified fields.

ICFP Day 3

Partially-Static Data as Free Extension of Algebras

Some programs can use “multi-stage” programming to create much faster versions of themselves when we know some of the parameters. For example a power function for a given power, say 4, can be specialized into x * x * x * x which requires no conditionals, no recursion. However this misses another optimisation. Once we have computed the first x * x we could reuse it to compute the final result let y = x * x in y * y.

This paper shows how to use the properties of some algebras to optimize code generated by staged programs. This is a nice improvement and general framework for a domain that is not mainstream yet (staged programming) but we know that this is probably the future for writing programs which are both nicely abstract and very efficient.

Relational Algebra by Way of Adjunctions

Wonderful presentation by Jeremy Gibbons and Nicolas Wu where they decide to present their paper as a conversation around a cup of coffee and some equations and diagrams on napkins. The essence of their paper is to present operations and optimisations on sql tables (the “relational algebra”) as given by adjunctions. Adjunctions are a tool from category theory showing how some “problems” in a given domain can be translated and solved in another domain, then the solution can be “brought back” to the original domain (this is all of course a lot more formal than what I just wrote :-)).

Something to be noted, in their description of table joins they need to use a monad which is a “graded” monad where each bind operation aggregates some “tags”, here the keys to the elements of the tables. This is way over my head but circling around the subject over and over I might understand everything one day :-).

Strict and Lazy Semantics for Effects: Layering Monads and Comonads

If you consider throwing exceptions as having a monadic effect and laziness (consuming or not a value) a comonadic effect then you can transform expressions having those effects into a pure language having monads and comonads. Unfortunately they don’t always compose, unless when they are “distributive”, if there’s a way to permute the monad m and the comonad c. The paper proposes to “force” one or the other interpretation to solve this dilemma. Either have a “monadic priority” which gives us “strict semantic” for those expressions having both effects or use a “comonadic priority” which gives us a “lazy semantic” for those expressions.

The cool theorem is that if the monad and comonad distribute then both choices give us the same result. The corollary is that if they don’t distribute then choosing a lazy or a strict semantic always give us different results!

What’s the Difference? A Functional Pearl on Subtracting Bijections

This is more of a mathematical puzzle than something that’s useful for day to day programming. When trying to evaluate some number of combinations (“how many ways can 3 people of a group have the same birthday?”), it can be useful to “remove” parts of some sets that we can count because they are in bijection with other well known sets (like the set of all the natural numbers). This is also a tricky operation.

The paper proves that there is an algorithm for substracting bijections which makes sense and which always terminates. I still have the naive feeling that the algorithm they presented could be simplified but I’m probably very wrong.

Ready, Set, Verify! Applying hs-to-coq to Real-World Haskell Code (Experience Report)

Good news: the Haskell containers library is bug free! How was that proven? By taking the Haskell code and translating it to Coq code, using as a specification typeclass laws and quickcheck properties from the test suite. This tool hs-to-coq is now used in other contexts to write some specifications in Haskell and prove them with Coq. It can not yet be used to prove concurrency properties but the team is thinking about it.

Haskell Symposium Day 1

Neither Web nor Assembly

Indeed WebAssembly is designed to be a low-level VM, performant and secure. The design of WA is supported by a formal specification, and a mechanical proof (in Isabel, Coq and K are underway). It is entirely standardised and supported, that’s a first, by all major browser vendors. So much that the proposal process mandates that any proposal must be implemented by 2 major implementations at least.

So far mostly C/C++ and Rust are supported because some higher-level language features required by other languages are still not available like tail calls (kind of important for functional languages :-)), exception management or garbage collection. A Haskell compiler (Asterius) is underway, being done by Tweag, and the vision is to be able to replace GHCJS on the mobile client wallets which are executing code for the Cardano blockchain.

AutoBench

This is a neat tool coupling QuickCheck and Criterion to benchmark different functions and see which ones have the best runtime behaviour. Some limitations though: benchmarks are only performed across one notion of “size” whereas general functions might depend on various parameters and also this is limited to pure functions for now.

Improving Typeclass Relations by Being Open

A great idea. Introduce a typeclass “morphism” to automatically create instances. For example if you have a typeclass for a partial order you would like to automatically get an instance for it everytime you have an Ord a instance for any type a. This new declaration class morphism Ord a => PartialOrd a would have solved many compatibility issues with the introduction of the infamous Functor / Applicative / Monad modification in Haskell.

Rhine: FRP with Type-Level Clocks

This is an addition to the “monadic streaming” framework introduced by Ivan Perez and his team. This provides some clock abstraction and synchronization mechanisms to make sure that different event sources emitting events at different rates can properly work together. It also provides a conceptual unification of “events” and “behaviours” from FRP: “events are clocks and behaviours are clock-polymorphic”.

Ghosts of departed proofs (Functional Pearl)

“Existential types” are a great way to hide information in an API. Indeed a function can give you a value of a given type without you being able to do anything with that value instead of returning it to the API, proving that you are really returning something you have been given, not something that you have fabricated. But you don’t necessary need a value to enforce constraints on your API, you can use a “phantom type” to tag a computation with a specific type, for which there are no corresponding value.

One cool thing you can do is encode proofs with these phantom types. For example you can embed the proof that a list has been sorted. This is all free at runtime because those proofs only exist at compile time. Even better you can create a type representing proofs, with all the classical logical combinators and, or, implies,… and associate them with values. This is all implemented in the gdp library.

Haskell Symposium Day 2

Deriving Via: or, How to Turn Hand-Written Instances into an Anti-pattern

DerivingVia is a way to reduce boilerplate which just landed in GHC 8.6.1. With DerivingVia you can declare trivial instances for data types by reusing known instances for other types. For example you can declare a Monoid instance for the datatype newtype Pair = Pair Int Int with deriving Monoid via (Sum Int, Mul Int). The generated instance will add the first element of the pair and multiply the second one.

Type Variables in Patterns

This is the complement to type applications in expressions: type applications in patterns. Being able to “extract” types from a pattern allows to properly name a given type to use it to type another expression. For example it will be possible to bind the existential type a in data MyGadt b where Mk :: (Show a) => a -> MyGadt Int in a pattern match by writing

case expr of MyGadt @a a ->
  print a where

  -- here the type `a` has been bound in the pattern match
  print :: a -> Text
  print = T.pack (show a)

The implementation should start before the end of the year.

The Thoralf Plugin: For Your Fancy Type Needs

This Haskell plugin uses a SMT solver to solve some of the obvious type constraints which GHC is not able to solve by itself.

Suggesting Valid Hole Fits for Typed-Holes (Experience Report)

Another useful tool for programming in Haskell. In Haskell we can use “type holes” giving the type that is expected in a given place and also some values which can fit that hole. Unfortunately type holes can be pretty useless with some expressions, using lenses for example. Now the suggestions for what can be put in the hole have been vastly improved by looking at all the functions in scope which could create a value for the hole. For example _ :: [Int] -> Int will suggest Prelude.head and Prelude.last. But we can go further and ask for some “refinement”: which function, having itself a hole could be used to fill in the hole? In the example above foldr could also be used provided that foldr has the right parameters.

And… this is all available in GHC 8.6.1 already and even able to use the new doc feature adding documentation to the suggestions.

A Promise Checked Is a Promise Kept: Inspection Testing

When the documentation of a library like generic-lens says “the generated code is performant because it is the same as manually written code”, can you really trust it? It turns out that version 0.4.0.0 of that library was breaking that promise and it was fixed is 0.4.0.1.

Fortunately, inspection-testing is a GHC plugin to save the day. With that plugin you can instruct GHC to check the generated GHC Core code: inspect $('genericAgeLens === 'manualAgeLens). You can also test if you have unwanted allocations in your code. For example the Data.Text package has many functions which are supposed to be “subject to fusion” but inspection testing proves that they are not.

Branching Processes for QuickCheck Generators

Dragen is library generating QuickCheck’s Arbitrary instances for recursive datastructures. The cool thing is that you can specify the “depth” and the distribution of all constructors in the generated values. So you can ask for trees of depth 5 with a proportion of Int nodes which is twice the number of Text nodes.

Coherent Explicit Dictionary Application for Haskell

Finally a way to avoid the “one instance of a typeclass per type only!” limitation. This implemented proposal allows to materialize a typeclass instance as a “Dictionary” and then do an explicit “dictionary application” to specify which dictionary you want to apply. For example you can write nubCI = nub @{ eqOn (map toLower) } where eqOn produces a dictionary.

The main concern with this type of proposal is that we could break coherence which is guaranteed to happen where there’s only one instance per type. Set operations for example can not be used with 2 different Ord dictionaries. This can actually be checked by looking at the “role” of the type variable a in Set a. It is “nominal” whereas this proposal only works with “representational” roles. Otherwise if you try to do a dictionary application where there’s any possibility that you then get 2 different instances for the same typeclass then you get a warning.

Theorem Proving for All: Equational Reasoning in Liquid Haskell (Functional Pearl)

Such a brilliant idea, since theorems are types and proofs are code, let’s write the theorems as Liquid Haskell types and proofs as Haskell code! Then LiquidHaskell is able check if your proof of reverse (reverse xs) == xs is correct. You will not get all the support you can get from a general theorem prover environment but I think this is a neat teaching tool at least. And the proofs disappear at runtime, nice.

(Haskell) modules for the masses

Update! A library providing this approach based on a different implementation is available on Github: https://github.com/etorreborre/registry

I have now been working with Haskell for around 3 months and I can say that it is a pretty enjoyable experience. Using Functional Programming is a lot more straightforward than with Scala and I rarely have to fight the syntax. I haven't been severely bitten by laziness yet (meaning I cannot call myself an "experienced" Haskell developer :-)) and I am even starting seeing the advantages of it in terms of mental flow: "I don't have to care about this, if it's not evaluated it will cost me nothing".

I have also had my share of head scratching with the mtl (Monad Transformer Library) and with lenses. But this is not what I want to write about today. My big preoccupation is not so much how we can use technique X or Y to write something in the small, but rather how we can write code in the large. Already at the level of a service using a database, writing to S3 and publishing/subscribing to an event broker the question of code organisation becomes a major one.

Organising Haskell code

In languages like Scala you have packages, traits and classes and various dependencies injection libraries to give you some guidance. In Haskell you will have to read a handful of blog posts and make your own opinion. Should you use Free Monads and an "onion architecture"? Should you use the mtl, the "next level mtl with classy optics" or a bit of both? Or maybe the Service Pattern? Should we call it the Handle Pattern? There is also a library for dependency injection using Template Haskell.

With my previous Scala project I experimented with new ideas for dependency injection and we open-sourced a library called Grafter to support this approach. This library has served us well even if it could definitely be improved. In Grafter we use a cool technique called "tree rewriting" to help with the wiring and re-wiring of our application. But that library relies on some "tricks" which are not available to Haskell, like the capability to collect objects of a given type at runtime (effectively doing an isInstanceOf test) or reflection to access the properties of a given case class. Not only we cannot do that in Haskell but we don't even have objects to begin with!

So with Haskell I was forced to revisit my choices for structuring code. Maybe I should start with what I want to achieve?

My objectives

My overall goal is to be fairly productive producing code across several applications and teams, possibly sharing libraries, in an environment where objectives can shift really fast.

This means:

1. be able to declare components having a public interface which is just a list of functions. "Information hiding" is not just something we learn in textbooks, it is very important to isolate from changes and prevent everything to become a huge bowl of spaghetti. Also in the kind of systems I am working on, code reuse and evolution does not happen at the function level. One day you use service 1 to get product definitions, the next you have to use service 2 and up to 10 functions need to be reimplemented. So the good old idea of "component" still makes sense.

2. have simple function definitions, with mostly IO for an easy interoperability of different components. In Haskell, functions, especially the effectful ones, can easily be abstracted to be returning some monad m with all sorts of constraints: MonadReader, MonadBaseControl, MonadCatch, MonadFileSystem, MonadLogger and so on. At first glance this doesn't look like a major issue but my (limited) experience tells me that this leads to: 1. complex type signatures 2. playing lots of type tetris when interacting with several such functions. Not fun.

3. have components declare their dependencies and configuration at their declaration site. This way they are kind of "self-contained" and it should be easy to just extract one of them to a new library for sharing

4. have a way to easily wire a full application from a list of all wanted components and configurations. If a new dependency is added to a component, we shouldn't have to change the wiring code. This really helps with maintaining the code. You need a new service? Just add a dependency. You want to split an existing component in 2? This is just 2 or 3 steps.

5. have a way to replace specific components in an existing application. This is useful in all sorts of situations. For example you want to test how well your application performs if one endpoint responds faster, or always respond "ok". Just write replace component or something similar and you're done. When you want to test a complex piece of business logic orchestrating different services you can just mock them out, all of them, or just some of them.

My hunch is that all of this is crucial to scale development to grow a medium size application or to grow a team working on interrelated services.

A design space

Interfaces

Objective n.1 can be satisfied by either using typeclasses or creating a record of functions. Typeclasses can declare their requirements: I can do MonadFileSystem if I know how to do MonadIO for example. And typeclasses can have instances, even with some rules of overriding them. Having some language support is nice! Or is it?

First of all you need to understand how typeclass resolution works and understand the difference between Overlapping and Overlappable. Then you might have to jump through some hoops when mixing different components together having different constraints. Haskell is so polymorphic that it is only when you are really executing an expression that the underlying data structure supporting the constraints "appears". For example if I runReaderT action r then the MonadReader r constraint on action gets resolved and action appears to be a ReaderT r m a. This possibility of delaying the selection of the concrete data structure in Haskell is a great force, but it makes the code also hard to understand because you have to run the typeclass resolution algorithm in your head to understand what's going on.

Worse, I experienced a strange bug 2 weeks ago with the nakadi-client library. After a refactoring I was making requests which were unauthenticated. How is that possible? I am using local to modify the environment of MonadNakadi which is some sort of MonadReader to access Zalando event bus. And I am indeed setting an authentication token on the requests. It turns out that I had 2 layers of Reader in my stack and I was probably not modifying the right one. I eventually refactored the code to set authentication earlier in the process without local and things were back to normal. My inability to understand what was going on lead to a bug which could not be caught by the compiler. Not cool. (the nakadi-client library is very cool though, I'm so grateful it exists :-)).

When I read about the Handle Pattern, that was an illumination, this is what I want, a simple collection of functions with a simple interface.

For example I might want to declare a Calculator as:

data Module =
  Module
  { add :: Int -> Int -> IO Int
  , multiply :: Int -> Int -> IO Int
  }

When I get such a record, the implementation is completely hidden, I am protected from any evolution of the implementation. How do I even create such a component? Like anything in Haskell, with a function:

new :: Adder.Module -> Multiplier.Module -> Module
new adder multiplier = Module (addWith adder) (multiplyWith multiplier)

Besides the guilty pleasure of reusing a well-known OO keyword this gives us a way to declare the dependencies for our component. And addWith, multiplyWith are (private) part of the module implementation.

Interoperability

Each function returns IO so the interoperability is maximal, no crazy constraints to accommodate. There is a small issue though. A small issue which drove me mad.

We need to operate our services, not just develop them. When something goes wrong in production it is incredibly useful to have a FlowId identifying requests coming from clients and flowing through all of our services. But if you have components returning IO values there is no way to pass this FlowId from one component to another. This necessitates a MonadReader FlowId constraint, or maybe a ReaderT FlowId IO a return type. Then we are back to more complex type signatures for something which is actually a very small concern in the scale of things. And that concern is "polluting" our whole ecosystem! Same if we want to use a logging library like katip we need to add something like MonadReader KatipContext everywhere. Just for a single small concern!

I tried many different ideas to get around this issue and end back in IO but nothing worked. Because I believe that nothing can work in a proper functional programming context. If you want the callee to know about its context and its caller, you need to pass some information! So you need a form of Reader and we decided to extend the IO type to RIO, just one more letter:

newtype RIO a = RIO { runRIO :: Env -> IO a }

where Env is defined as

data Env =
  Env
  { context   :: Maybe Context
  , namespace :: Namespace
  } deriving (Eq, Show)

This means that in addition to doing IO the functions of a component can require a bit of knowledge from the caller:

• a Context for example to pass the FlowId

• a Namespace (a list of names) for example to describe some nested processes: processing event { "eventId" = "123" } > getting master data > authenticating { "role" = "admin" }

Context and Namespace are essentially "stringly" data just modelling the context of the caller with the following properties:

• contexts can be replaced, setting a context removes the previous one
• namespaces are appended, like breadcrumbs on a website

I hear some of you saying that we could get fancy and use something like:

newtype RIO r a = RIO { runRIO :: r -> IO a }

Now we don't have to be concrete in the environment type. However we lose a lot in terms of simplicity and we risk having to deal with RIO r1 a and RIO r2 b and have to find ways to unify r1 and r2. No problem, let's use lenses! And then we go through even more complex type signatures.

I am clearly making a compromise here. By not using the most typed signature I expose myself to the danger of programming with strings. But I think this is worth it because we get easier code for things which matter a lot more than flow ids or contextual logging.

Configuration

Inside each "Module" file there should be a declaration for the module configuration:

data Config =
  Config
  { invertSigns :: Bool }

And new becomes:

new :: Config -> Adder.Module -> Multiplier.Module -> Module
new (Config invert) adder multiplier =
  Module (addWith invert adder)
         (multiplyWith multiplier)

addWith :: Bool -> Adder.Module -> Int -> Int -> RIO Int
addWith True  adder a b = pure (adder & add a b)
addWith False adder a b = pure (- (adder & add a b))

This way components are self-contained and easy to extract to libraries

Replacing components

What do we do about wiring a bunch of components and in particular how to replace one of them, right at the bottom of the stack? Do you need to recreate the full application, calling new all over the place?

I found a neat trick to do this: a "registry", and ... the State monad.

Let's create a data structure holding all the components we want to build:

data Modules =
  Modules
  { _adder      :: Maybe Adder.Module
  , _multiplier :: Maybe Multiplier.Module
  , _calculator :: Maybe Calculator.Module
  , _config     :: Config
  }

How do we make a calculator? We get it from Modules. If missing we create it with new by first getting its dependencies:

makeCalculator :: State Modules Calculator.Module
makeCalculator = do
  modules <- get
  case _calculator modules of
    Just c -> pure c
    Nothing -> do c <- new <$> makeConfig <*> makeAdder <*> makeMultiplier
                  _ <- put c
                  pure c

Then we put the newly created component in the registry, done. (recursively for all the dependencies!) With makeCalculator we can pass a Modules value where all the components are set to Nothing:

prodModules =
  Modules
  { _adder      = Nothing
  , _multiplier = Nothing
  , _calculator = Nothing
  , _config     = prodConfig
  }

Replacing a component is super easy, just set it in the registry:

testModules =
  prodModules
  { _adder = Just (testAdder)
  }

We can automate a bit of that with 2 typeclasses:

-- means that there is a possibility to get the Module from a registry s
-- (and possibly get nothing) and also to set it in the registry s
class Register s m where
  access :: s -> Maybe m
  register :: s -> m -> s

-- Make s m means that there is a way to build the module m given an initial configuration s
class Make s m where
  make :: State s m

Then for a given module a Makeable instance can be created like this:

instance ( Register s Module
         , Make s Config
         , Make s Adder.Module
         , Make s Multiplier.Module
         ) => Make s Module where
  makeIt = create3 new register make make make

This declares all the dependencies for a given component and make3 is just a function generalizing the makeCalculator above to any constructor using the implicit typeclass instances so there's nothing to implement. Adding/Removing a new dependency to a component becomes pretty trivial.

Inside the top level application we also need to create some Registry instances to describe how to interact with the "registry" for each component and how to "make" the various Config values from it:

-- | find the Adder module in the registry
instance Register Modules Adder.Module where
   access m = _adder s
   register s m = s { _adder = Just m }

-- | declare that `Adder.Config` can be made directly
--   by extracting the `Adder.Config` from the `Modules`
--   data structure.
--   This uses the `config` and `adderConfig` lenses generated for `Modules`
instance Make Modules Adder.Config where
  make = get <&> (^. config . adderConfig)

This part will be generated using Template Haskell in the future.

Starting services

The real story is always more complicated :-). Some components are "stateful" because they hold a database connection or a cache, so they have to be started. The solution to this new requirement is not difficult: use a new function returning a RIO Module and starting things. Then when doing the application wiring we operate in StateT RIO instead of just State. This is also what makes the big difference between Config and Module in a component file: Config is for pure data and Module can trigger some side effects for its creation.

Conclusion

This all very new and currently only tested on a medium-size service. But I really like this approach: not a lot of type magic, enough flexibility, clear guidance on how to write code. It is probable that we will get more questions along the road (otherwise why would the world need so big dependency injection libraries?), I will report on them. In the meantime please share your ideas, add your comments. Especially if you are thinking that we are making a huge mistake somewhere that should be addressed right now!

If at first it doesn't succeed...

If at first it doesn’t succeed, try something else

Today we start from a very common programmer need and we end up checking laws! With some considerations about software modularity.

I am currently implementing a command-line application in Haskell. This application needs a OAuthToken to access some webservice. There are 2 ways to get a token:

• with an environment variable: OAUTH_TOKEN
• with a call to another command-line tool, ztoken, which gives you a token based on your credentials

This translates to the following Haskell functions

getTokenFromEnvironment :: ExceptT GetTokenError IO OAuthToken

getTokenFromCommandLine :: ExceptT GetTokenError IO OAuthToken

Here I am using:

• IO as my base monad for interacting with the external world

• ExceptT GetTokenError as a way to declare an error if I cannot get a token because either I don’t have an OAUTH_TOKEN variable in my environment or ztoken does not accept my credentials. I leave other issues, like network access problems to exceptions in the IO monad

data GetTokenError =
  CommandLineError String |
  EnvironmentError String

What I really want now is a way to combine those 2 calls into one

getToken :: ExceptT GetTokenError IO OAuthToken

The first thing which came to my mind was the Alternative type class and in particular the <|> operator:

(<|>) :: f a -> f a -> f a

This typeclass has an instance for ExceptT e provided that there is a Monoid e, meaning that I can accumulate errors. Actually what I just need is the Alt typeclass which just requires a Semigroup e. For this I need to adapt my error type a little bit:

data GetTokenError =
  CommandLineError String |
  EnvironmentError String |
  RepeatedErrors GetTokenError GetTokenError
  deriving (Eq, Show)

The RepeatedErrors case gives us the possibility to accumulate errors in the case of repeated failed calls to retrieve an OAuthToken. You could argue that it is not particularly well modelled because RepeatedErrors stores errors more like a tree rather than a list. But let’s leave it at that for now.

The Semigroup instance for GetTokenError looks like this:

instance Semigroup GetTokenError where
  e1 <> e2 = RepeatedErrors e1 e2

I can finally define:

getToken :: ExceptT GetTokenError IO OAuthToken
getToken =
  getTokenFromEnvironment <|>
  getTokenFromCommandLine

This is really nice because this is exactly what I want to express!

• get the token from the environment
• if that doesn’t work get it from the command line

More abstraction on the way

This looks all good but something is annoying. My functions are using ExceptT GetTokenError IO which is a very concrete monad stack. I am going to make further calls to other monad stacks to make HTTP calls and I might have to lift all over the place to align all the different stacks. This is even more annoying if I create a small library for getting tokens because I impose my stack choices on all clients of the API.

There is a way out of this, the monad transformers library (mtl). In the mtl there are all sorts of typeclasses abstracting features provided by monad transformers. One of them is MonadError:

class Monad m => MonadError e m | m -> e where
  throwError :: e -> m a
  catchError :: m a -> (e -> m a) -> m a

If a Monad has a MonadError instance then you can catch and throw errors. Nice. However there is a catch (no pun intended :-)). The | m -> e part of MonadError means that the Monad m you are going to eventually select to support the MonadError functionality is dependent on the error type e.

Concretely this means that this type signature propagates to the top of the application:

getToken :: (MonadError GetTokenError m, MonadIO m) => m OAuthToken

Indeed, if I mix other calls to getToken, for example

getPartitions :: (MonadError GetTokenError m, MonadIO m) => m [Partition]
getPartitions =
  do token <- getToken
     callService token partitionsRequest

Then the MonadError GetTokenError m constraints stays because m is tied to it forever. And if callService declares its own error type, I won’t be able to mix both getToken and callService calls:

callService :: (MonadError HttpError m, MonadIO m) :: OauthToken -> Request a -> a

Maybe one solution would be to define getPartitions as:

getPartitions :: (MonadError (GetTokenError Either ServiceError) m, MonadIO m) => m [Partition]

In a way we are back to the previous problem. We now have a “concrete stack” of errors where we just want “a” structure capable of holding both GetTokenError and HttpError.

Lenses to the rescue

A partial solution to the problem is given by lenses and is wonderfully explained by Georges Wilson in “next level mtl with classy optics” (I also recommend this gist by Nick Partridge):

-- create prisms for GetTokenError
makeClassyPrisms ''GetTokenError

-- now e is anything having a Prism allowing us to extract or inject a GetTokenError
getToken :: (MonadError e m, MonadIO m, AsGetTokenError e) => m OAuthToken

So it becomes kind of easier to mix calls having different error types:

getPartitions :: (MonadError e m, AsGetTokenError e, AsHttpError e, MonadIO m) => m [Partition]

This is probably a better way to mix different error types with MonadError. We don’t get rid of the functional constraint though. The error types still “bubble-up” to the top and the method used to do the authentication is exposed to the clients of getPartitions. So if we switch the authentication mechanism and get different error types we will have to change all the functions calling getPartitions.

I think we need to really take care of this kind of situation because it makes software a lot harder to evolve when a small change has ripple effects across all the software layers.

Errors translation / encapsulation

What we can do is to define a new error type subsuming GetTokenError and HttpError:

data ServiceError =
  AuthenticationError GetTokenError |
  CallError HttpError

makeClassy ''ServiceError

instance AsGetTokenError ServiceError
instance AsHttpError ServiceError

And we need a bit of boilerplate to do the translation between getToken and callService. To be able to “liberate” those 2 functions from their MonadError e m, MonadIO m constraints we can run them with the minimum stack which satisfies these constraints, this is ExceptT <error type> IO a:

runOAuthToken :: (MonadError e m, AsCliError e, MonadIO m) => ExceptT GetTokenError IO a -> m a
runOAuthToken = runExceptTIO (review _AuthenticationError)

runCallService :: (MonadError e m, AsCliError e, MonadIO m) => ExceptT HttpError IO a -> m a
runCallService = runExceptTIO (review _HttpError)

runExceptTIO :: (MonadError e m, MonadIO m) => (f -> e) -> ExceptT f IO a -> m a
runExceptTIO mapError ioa =
  do valueOrError <- liftIO (runExceptT ioa)
     fromEitherM (throwError . mapError) valueOrError

(fromEitherM comes from the from-sum package)

Then we can make both calls and “unify” them under new constraints:

getPartitions :: (MonadError e m, AsServiceError e, MonadIO m) => m [Partition]
getPartitions =
  do token <- runToken getToken
     runService (callService token partitionsRequest)

Alternatives?

Unfortunately being more abstract with getToken breaks the use of <|> which was so convenient. One option for fixing it is to define a similar operator for mtl classes:

(<|>) :: (MonadError e m, Semigroup e) => m a -> m a -> m a
(<|>) ma1 ma2 =
  catchError ma1 (\e1 ->
    catchError ma2 (\e2 ->
      throwError (e1 <> e2)))

But this still doesn’t work given the way we have defined our errors as prisms over a general error type! We need to define a extension of <|> which uses the appropriate Prism to aggregate errors:

(<|?>) :: (MonadError e m, Semigroup o) => Prism' e o -> m a -> m a -> m a
(<|?>) p ma1 ma2 = catchError ma1 (\e1 ->
  case e1 ^? p of
    Nothing -> throwError e1
    Just o1 ->
      catchError ma2 (\e2 ->
        case e2 ^? p of
          Nothing -> throwError e1
          Just o2 -> throwError (review p (o1 <> o2))))

And finally

getToken :: (MonadError e m, MonadIO m, AsGetTokenError e) => m OAuthToken
getToken =
  (<|?>) _GetTokenError
  getTokenFromEnvironment
  getTokenFromCommandLine

This is not syntactically as nice as before but we can improve that:

infix 4 <!>
infix 3 <?>

data Alternating a = Alternating a a

(<!>) :: MonadError e m => m a -> m a -> Alternating (m a)
(<!>) = Alternating

(<?>) :: (MonadError e m, Semigroup o) => Prism' e o -> Alternating (m a) -> m a
(<?>) = error "left to the reader"

getToken =
  _GetTokenError <?>
  getTokenFromEnvironment <|>
  getTokenFromCommandLine

What about laws?

This is not the happy end of the story. The Alternative type class specifies that <|> must be an associative operation. This means that we probably need to prove that our <|> and its evil twin <|?> are associative operators. What does that mean for instances of MonadError e m? By the way what is even a MonadError e m?

I was pretty shocked to realize that MonadError doesn’t come up with any laws in Haskell! We need to turn to Purescript for this:

-- | - Left zero: `throwError e >>= f = throwError e`
-- | - Catch:     `catchError (throwError e) f = f e`
-- | - Pure:      `catchError (pure a) f = pure a`

And we probably need an additional law for our <|> operator:

-- | - Catch associativity: `catchError (catchError ma f1) f2 =
--                           catchError ma (\e -> catchError (f1 e) f2)`

Since many instances already exist for MonadError the best we can do is to check if those laws hold for these instances.

I was at first very enthusiastic about that. There are 2 libraries in Haskell which can be used to retroactively find properties for a give API: quickspec and speculate. However I was unable to get any of them to compile / find laws. Since I had been shaving too many yaks on this application I decided to stop there. But I hope I will get some time to get those libraries to find laws.

Anyway, the best I could do was to check the laws for all the instances of MonadError: EitherT, ListT, MaybeT, ExceptT and so on. I verified a bunch of them using QuickCheck and they seem to hold. Actually if that wasn’t the case I would be surprised and would probably question the implementation. I also proved that the laws were holding for the Either instance of MonadError. It goes like this, for the associativity of catch:

-- this is what we want to prove
catchError (catchError m k2) k1 == catchError m (\\e -> catchError (k2 e) k1)

--> case 1: m = Left t
catchError (catchError (Left t) k2) k1 == catchError (Left t) (\\e -> catchError (k2 e) k1)

-- we apply on each side the definition of catchError for Either when the (m a)
-- value is a Left value which is to call the handler, CQFD
catchError (k2 t) k1 = catchError (k2 t) k1

--> case 2: m = Right a
catchError (catchError (Right a) k2) k1 == catchError (Right a) (\\e -> catchError (k2 e) k1)

-- we apply on each side the definition of catchError for Either when the (m a) value
-- is a Right value which is to leave it as it is, CQFD
catchError (Right a) k1 = Right a

-- we do it once more on the left side of the equation
Right a = Right a

I suspect that it is possible to prove the laws for other MonadError instances, StateT would probably be interesting.

What have we learned?

There are plenty of lessons for me in this exercise:

• Haskell is full of interesting generalization, <|> is one of them and worth spotting in production code

• Haskell libraries are not necessarily complete and can probably benefit from contributions

• The modularity story of Haskell is not as obvious as what you might think. I had to think hard to find a satisfying solution and one huge problem is still unsolved. How can I test my full application code with a dummy authentication, which would always succeed? This will be the subject of a following post!

ICFP 2017

I already blogged last year on ICFP, the awesome conference on Functional Programming, to share a neat trick.

This year I would like to do a small brain dump on some of the sessions which I really liked.

Workshop on higher-programming with effects

Programming a web server with effects

This is one of several talks showing the benefits of programming with a language with natively supports the description of effects in the type system: Koka. Not only Daan Leijen is a great presenter whose enthusiasm is contagious but with Koka it feels entirely natural to write asynchronous code with interleaving, cancellation, resource-cleanup and so on.

The also hints at something which got me really interested, the yield operator to create iterators can be seen as an effect. Coupled to the async support above this makes me think that a whole streaming library could be created as a set of effects!

Workshop on type-driven development

Type-directed diffing of structured data

A fantastic idea: can be do better than line-diffing to diff code and do AST diffs? The presenter introduced a language for representing AST patches (not as easy as it seems) then different possibilities for algorithms doing the diff (clearly a hard problem if you want to find the minimum diff).

ICFP

Super 8 languages for making movies

I’m not a big fan of dynamic languages but the power of Racket is impressive. The presenter shows how she created a “Tower of DSLs” to create a video-editing tool. Complete with parser, GUI, documentation, integration with video libraries in a lot less lines of code than anything else I know.

Faster coroutine pipelines

Coroutine pipelines are the functional way to create streaming libraries. However they can be made faster. How? But using an encoding based on continuations rather than the “direct” encoding. This trick seems to be pervasive. For example, for algebraic effects, ScalaEffekt uses such an encoding and gets much better performances than eff.

A unified approach for solving seven programming problems

Racket is at it again but with a secret weapon, miniKanren. If you view a computation as a “logical” relationship between a program and some outputs, it is very reasonable to ask your solver to find the programs which give you the right outputs. And find, for example, Quines which are programs which output themselves!

Generic functional parallel algorithms: parallel scan

Scans, computing the prefix sums of a list of ints, are an important ingredient in some algorithms, like regular expression search. If they can be performed in parallel it’s even better! This talk shows that a scan algorithm can be defined for generic datastructures, just defined by sums, products and functor composition. Then by adjusting the decomposition you get different amounts of parallelism and work to compose results.

Effect-driven quickchecking of compilers

Very entertaining presentation showing that it is entirely possible to generate well-type terms to test a compiler.

Compiling to categories

My favourite talk this year. What if you consider lambda and apply in the lambda calculus as 2 operations which could be interpreted differently? Conal Elliott developed a GHC plugin to transform Haskell expressions into objects in a category where function composition corresponds to the composition of morphisms in a category. What does that give us? Instead of applying functions and getting a result we can generate circuits computing them, differentiate them or do interval computations where the results are intervals instead of just being values.

Staged Generic Programming

Generic programming is cool. Write a few lines of code and let the compiler figure the right data structure and / or program. Unfortunately the performances might be very bad compared to hand-written code. With staging we can let the compiler be smarter and generate “unrolled” code which will perform as well as the hand-written one.

I was also glad to get to talk to Jeremy Yallop, the presenter, who is a very nice guy, now working at Docker on unikernels, something to keep an eye on!

Whip: higher-order contracts for modern services

This is looks more like a CUFP talk, with real applications in the industry :-). The idea is to install some “decorators” on webservices to check where contracts are being broken. They have a nice website and I am tempted to try this at work.

Haskell Symposium

Algebraic graphs with Class

A simple but very powerful to describe graphs “algebraically”. Some atoms: the empty graph, the singleton graph and 2 operations: overlay (sort of addition) and connect (sort of multiplication). Based on that you can represent any graph and encode any algorithm against that representation, which can then optimised for different purposes.

Quickspec / Speculate

Those 2 tools will generate the equations that you API is supposed to satisfy. For example, given [], ++ and reverse they should be able to generate reverse ([] ++ xs) == reverse xs. But even more, they can now generate implications and inequalities!

Composable networks and remote monads

The remote monad explores different ways of “grouping” operations when addressing remote services. After tried to do something similar for eff I appreciate a lot more the subject :-).

Testing with crowbar

Impressive example about finding bugs in a unicode library in 10 minutes which QuickCheck can not find in 1 week. The secret? Fuzzing and code coverage. Generate random sequence, turn them to test cases and mutate the sequences until you find some “interesting” part of the code. Those are likely to contain bugs.

ML Family workshop

State machines all the way down

My periodic reminder that I need to find some time to use Idris. Even more so after Edwin Brady said that the state machine programming with the type system tracking before/after state subsumes the effects library! He also told me that he was implementing the Idris compiler in Idris and this was a good example for him about “when not to go too far with types”.

Effects without monads: non determinism

Oleg Kiselyov is back, implementing non-determinism with TTFI (typed tagless final interpreters). This example is particularly interesting because he shows that monads are not necessary to interpret this mini-language. Not only that but that but they cannot even be used if your translation is about generating code. Because you cannot write code which will write code!

Bioinformatics: the typed tagless final way

A concrete example of people using TTFI in real life for large and extensible DSLs.

CUFP

Bonsai: DSL for serverless decisioning

This DSL is pretty simple, it is just decision trees (if / then / else) but compiled for maximum throughput for the ad industry.

Gens N’ Roses: appetite for reduction

Jacob Stanley talk on Hedgehog where shrinks come for free and failures are beautiful. A “must-use” for Haskell users.

Haskell implementors workshop

Syntactic musings

This was a lightning talk but it made me laugh. Those are proposals to improve haskell syntax with almost zero possibilities to be adopted :-):

How to write bracket without parenthesis:

Instead of

bracket
  (acquire some resources)
  (do your stuff which might be
   pretty long)
  (and clean up)

Go (yes, bullet points!)

bracket
  . acquire some resources
  . do your stuff which might be
     pretty long
  . and clean up

Then set a value for a bunch of functions

context fixed (value) where
  add a = value + a
  mul a = value * a

to avoid the repetition of value and to avoid accidentally messing with it. This screams like “module/functor envy” to me.

The last one is crazy but brilliant. Get away with grouping with parentheses by removing whitespace where you want to indicate higher precedence

a+b * c+d

Why not :-)?

An experiment in fragment-based code distribution

I thought this idea could really not roll but now I am intrigued. Following Joe Armstrong’s “Why do we need modules at all?” Philip Schuster implemented a build system for haskell where each program is decomposed into “slices” containing just one function and its dependencies. Everything identified by numbers. Advantages: just compile and package what you need, never care about version numbers. But the job of curating all of that to get a coherent snapshot, oh boy! As a data point, running anything on Scotty requires 12.000 slices.

Conclusion

A very intense week as in the previous editions I have been to. I don’t know yet what will stick with me and influence my future work but there’s plenty to think about. I also enjoyed very much the discussions I had with Jonathan and Philipp, the authors of scala-effekt.

Specs2 4.x

It has been now almost 3 years since the last major version of specs2. But why would a new major version of a testing library be even needed? Because the world doesn’t stop revolving!

In particular Scala can now be compiled to JavaScript and even natively. It is then only natural that specs2 users want to use specs2 on their Scala.js projects:

How hard can this be? First of all specs2 3.x relies on scalaz-stream which doesn’t have a Scala.js build, and more largely on scalaz (which has a Scala.js build).

This is where an issue becomes an opportunity! If I need to find an alternative to scalaz-stream why not remove scalaz altogether? Indeed it is very inconvenient for a test library to rely on third-party libraries which might conflict with users libraries. Because of this conflict I have to publish several versions of specs2 for different versions of scalaz (7.0.x, 7.1.x, 7.2.x and so on). This is pretty time-consuming, not only because of having to wait for more than 30 minutes for all the jars to be published but also because I have to adapt to some small differences between each scalaz version.

Removing scalaz and scalaz-stream is easier said than done:

1. specs2 relies heavily on functional programming so I need the usual FP suspects: Functor, Applicative, Monad and so on

2. specs2 interacts with the file system, writes out to the console, executes specifications concurrently so it needs a way to control effects

3. specs2 is structured around the idea of a “stream of specification fragments” so it needs a streaming abstraction

All of this before I can even consider moving to a Scala.js build!

specs2 own FP / streaming infrastructure

Fortunately I have developed on the side many of the pieces needed above:

1. eff is a library to handle effects, including concurrency and resources management

2. producer is a simple streaming library designed to work with any Monad, including the Eff monad

3. origami implements a notion of composable “folds” which can be applied to any stream, which is a pattern I (re)-discovered on earlier versions of specs2: reporting the results of an executed specification is just “folding” the specification, a bit like using foldLeft on a List

A copy of those libraries is now included in the specs2-common module.

The only thing missing was the FP abstractions. It turns out that it is not too hard to implement the whole menagerie:

• Functor, Applicative, Monad, Traverse, Foldable, Monoid. Those typeclasses are very tied together
• Tree and TreeLoc for manipulating trees

I am greatly indebted to the Scalaz and cats projects for this code, which I reduced to the only parts I needed for specs2. Those abstractions and datatypes are now available in the specs2-fp module (not intended for external use).

Execution model

At the heart of specs2 is a Fragment, which is a Description and an Execution yielding a Result. The Description holds an informal description of the specified system and the Execution runs some Scala code to verify that behaviour.

Using Scala.js imposes a big change is specs2. We can never await to the get the result of executing a Fragment. Also since scalaz.concurrent.Task is out of the equation, in specs2 4.x an Execution is implemented using a scala.concurrent.Future, like this:

case class Execution(
 run:       Option[Env => Future[() => Result]],
 executing: Option[Throwable Either Future[Result]])

This is a lot more complicated than just Future[Result]. Why is that?

run takes an action to execute () => Result, possibly concurrently Future[() => Result] and which might depend on the environment Env => Future[() => Result]. You might wonder why we don’t simply use Env => Future[Result]. This is to allow the user to add some behaviour around the result, for example with the AroundEach trait and the def around[R : AsResult](r: =>R): Result method.

We also want to “stream” results, which are executed concurrently and display them as soon as they are available. This is done by having executing holding either a Throwable if we could not even start the execution or the Result being currently computed.

Note that we can never call await in a Scala.js program so when we are executing a Fragment the best we can get is the equivalent of Future[Result] (in reality an Action[Result] which is a type possibly having more effects than just concurrency).

This triggers major changes in the implementation of specs2 and there are rippling effects up to the Runners used to run a specification. However most of the users of specs2 should not be concerned with these changes as the “user” DSL for specs2 isn’t modified. However if you are on the JVM and really need to await to get the result of a fragment execution you can do so by using one of the methods in the org.specs2.control.ExecuteActions object. For example result.runAction(executionEnv) will return an Error Either Result. Running the same method on Scala.js will throw an exception.

Scala.js modules

“specs2 runs on Scala.js” is ever going to be a partial truth. There are many limitations related to Scala.js and this means that, while specs2-core can be used on any Scala.js project, there are some specs2 features and modules which cannot be used with Scala.js. Here is a list (up to my current knowledge):

1. the isolate argument to run each example in its own copy of the specification cannot be used (because this uses reflection to instantiate classes)

2. no custom Selector/Executor/Printer/Notifier can be passed from the command line (for the same reason)

3. the RandomSequentialExecution trait cannot be used because the implementation uses a TrieMap not available on Scala.js. This could be fixed in the future.

4. running only examples which previously failed with was x on the command-line is not possible because this accesses file system

5. all the modules where scala-xml is used don’t have a Scala.js version because there’s no scala-xml for Scala.js: specs2-form, specs2-html

6. modules accessing the file system cannot be used: specs2-html, specs2-markdown

7. the specs2-gwt module defines fragments based on the result of previous fragments, so it currently needs to await. This could be fixed potentially with a smart enough implementation in the future.

Breaking changes

A major version number is also the opportunity to fix some of the API flaws. I tried to limit the changes in the low-level API to the strict necessary but I also wanted to clean-up one important aspect of the high-level API.

When specs2 3.x came out I envisioned that there could be ways to create a specification from arguments passed on the command line, or from an ExecutionContext (to execute futures). With the addition of some traits like CommandLineArguments you could declare:

class MySpec extends Specification with CommandLineArguments {
  def is(args: CommandLine) = s2"""
    try this $ok
"""
}

or

class MySpec extends Specification { def is = s2"""
  try this $ex1
"""

  def ex1 = { implicit ec: ExecutionContext => Future(1) must be_==(1).await }
}

I later realized that it would be a lot more convenient to directly “inject” the command line arguments or the execution context in the specification like so:

class MySpec(args: CommandLine) extends Specification { def is = s2"""
  try this $ex1
"""

 def ex1 = { (1 + 1) must be_==(2).when(args.contains("universe-is-sane"))}
}

class MySpec(implicit ec: ExecutionContext) extends Specification { def is = s2"""
  try this $ex1
"""

  def ex1 = { Future(1) must be_==(1).await }
}

Now there were 2 ways to do the same thing, the second one being a lot easier than the first one. In specs2 4.x the traits supporting the first behavior org.specs2.specification.Environment, org.specs2.specification.CommandLineArguments, org.specs2.specification.ExecutionEnvironment have been removed. Same thing for the implicit conversions for functions like implicit ee: ExecutionEnv => Result to create examples.

This will demand some migration efforts for some users but the result will be more concise specifications.

Another word on injected execution environments. From specs2 3.8.9, 2 distinct execution environments are being used in specs2. One for the execution of the specification itself, the other one for the execution of the user examples (to map futures or await for results for example). This is to make sure that some incorrect user code doesn’t prevent the full specification from being executed.

With specs2 4.x we can go one step further and allow each specification to get its own dedicated execution environment and make sure that one specification execution doesn’t impact another one:

import org.specs2.specification.core.{Env, OwnExecutionEnv}

class MySpec extends(val env: Env) extends Specification with OwnExecutionEnv { def is = s2"""
    ...
"""
}

The injected env is used to pass command-line argument to a copy of the user execution env, implicitly available as a member of the OwnExecutionEnv trait. That trait also takes care of shutting down the execution environment once the specification has finished executing so as not to lose resources.

Feedback is essential

In conclusion, specs2 4.x should be a smaller gap from specs2 3.x than specs2 2.x to specs2 3.x. With a lot more to offer!

1. no more dependencies for specs2-core

2. a Scala.js version for specs2-core

3. better control on execution environments

The release notes can be found here.

Please, please, please ask on gitter, on the mailing-list, on twitter if you have any issue. And a big thank you for reporting any mistake, big or small, that I may have made on this release!

A neat trick from ICFP 2016

ICFP is an awesome conference where I can’t pretend I understand every presentation I’m attending but there is definitely lots of food for thought and some gems which makes it immensely worthwhile.

The gem I want to share here is a paper called “All sorts of permutations”.

This paper shows that you can use the filterM function with a predicate like a -> [True, False] and generate all the sublists of a list.

Similarly, you can evolve the sort function into sortM, taking a monadic comparison function: a -> a -> m Bool. If the comparison function is a -> a -> [True, False] the sortM function will generate the permutations of a list.

The paper goes on exploring if sortM generates all the permutations of a list or exactly the permutations of a list depending on the implementation of the sortM function (insertion sort, merge sort, quicksort,…) and tries to set various restrictions on the comparison function to get there.

At the end of the talk Philip Wadler asked the following question (paraphrased):

This is a neat trick to generate permutations but why should I teach it to my students, considering that there are more ‘classical’ implementations for getting the permutations of a list?"

I think that it is worth showing students because this sortM function gives us a very neat way of writing a QuickCheck generator for distinct elements!

It is indeed not uncommon to have to generate lists of distinct elements for testing applications. For example if you want to test a function scheduling different tasks and these tasks are supposed to be unique, but arriving in any order.

There is unfortunately no permutations :: [a] -> Gen [a] combinator in QuickCheck. So how can you produce random Lists with distinct elements?

One way is to take an existing list of distinct elements and shuffle it to get a random permutation of those elements. This is exactly what sortM gives us, we just need to use the right monad, which happens to be Gen instead of []!

Let’s take an example. Say you want to generate all the permutations of ["Homer", "Marge", "Bart", "Lisa"]

import Test.QuickCheck

-- An implementation of sortM
sortM :: Monad m => (a -> a -> m Bool) -> [a] -> m [a]
sortM _ [] = return []
sortM cmp (x : xs) = do
  ys <- sortM cmp xs
  insertM cmp x ys

insertM :: Monad m => (a -> a -> m Bool) -> a -> [a] -> m [a]
  insertM _ x [] = return [x]
  insertM cmp x yys@(y : ys) = do
    b <- cmp x y
    if b then return (x : yys)
    else fmap (y:) (insertM cmp x ys)

-- A generator for lists of distincts "Simpsons"
type Simpson = String

simpsons = ["Homer", "Marge", "Bart", "Lisa"]

distinctSimpsons :: Gen [Simpson]
distinctSimpsons = sortM (\_ _ -> choose(True, False)) simpsons

Let’s test it:

λ> sample distinctSimpsons
["Homer","Lisa","Marge","Bart"]
["Homer","Marge","Bart","Lisa"]
["Homer","Marge","Lisa","Bart"]
["Homer","Marge","Bart","Lisa"]
["Bart","Homer","Marge","Lisa"]
["Marge","Homer","Bart","Lisa"]
["Marge","Homer","Lisa","Bart"]
["Marge","Homer","Lisa","Bart"]
["Marge","Bart","Lisa","Homer"]
["Homer","Marge","Bart","Lisa"]
["Bart","Homer","Lisa","Marge"]

I think this answers Philip’s question, this is a nice application of the sortM “trick” which can be taught to students learning functional programming.

And what looks really promising is that this idea extends to the generation of other data structures. For example we can generate the partitions of a given set with groupByM:

partitionM :: Monad m => (a -> m Bool) -> [a] -> m ([a], [a])
partitionM _ [] = pure ([], [])
partitionM p (x : rest) = do
  b        <- p x
  (xs, ys) <- partitionM p rest
  if b then pure (x:xs, ys)
  else      pure (xs, x:ys)

groupByM :: Monad m => (a -> a -> m Bool) -> [a] -> m [[a]]
groupByM _ [] = pure []
groupByM cmp (x : rest) = do
  (xs, ys) <- partitionM (cmp x) rest
  ps       <- groupByM cmp ys
  pure $ (x:xs):ps

Then we can get all the set partitions of ["Homer","Lisa","Marge","Bart"]

λ> pl $ groupByM (\_ _ -> [True, False]) simpsons
[["Homer","Marge","Bart","Lisa"]]
[["Homer","Marge","Bart"],["Lisa"]]
[["Homer","Marge","Lisa"],["Bart"]]
[["Homer","Marge"],["Bart","Lisa"]]
[["Homer","Marge"],["Bart"],["Lisa"]]
[["Homer","Bart","Lisa"],["Marge"]]
[["Homer","Bart"],["Marge","Lisa"]]
[["Homer","Bart"],["Marge"],["Lisa"]]
[["Homer","Lisa"],["Marge","Bart"]]
[["Homer","Lisa"],["Marge"],["Bart"]]
[["Homer"],["Marge","Bart","Lisa"]]
[["Homer"],["Marge","Bart"],["Lisa"]]
[["Homer"],["Marge","Lisa"],["Bart"]]
[["Homer"],["Marge"],["Bart","Lisa"]]
[["Homer"],["Marge"],["Bart"],["Lisa"]]

or get some random partitions of that set:

λ> sample $ groupByM (\_ _ -> choose(True, False)) simpsons
[["Homer","Marge","Bart"],["Lisa"]]
[["Homer","Lisa"],["Marge","Bart"]]
[["Homer","Bart"],["Marge"],["Lisa"]]
[["Homer","Marge","Bart","Lisa"]]
[["Homer","Marge","Bart","Lisa"]]
[["Homer","Lisa"],["Marge"],["Bart"]]
[["Homer","Marge"],["Bart"],["Lisa"]]
[["Homer"],["Marge"],["Bart","Lisa"]]
[["Homer","Marge","Bart","Lisa"]]
[["Homer","Marge","Bart","Lisa"]]
[["Homer","Marge","Lisa"],["Bart"]]

Some partitions can be drawn twice but the generation should be uniform over the set of all possible partitions (it would be better to not take my word for it and prove it though :-)).

I suspect that this is more than a useful trick and that this deserves a more systematic treatment to understand all the data structures which we can generate by using the appropriate functions taking predicates or relations as parameters. But for now it is already useful as it is!