[ANN] Monads - the missing monad transformers library

We are doing program analysis in CMU, Cylab, and thus we deal a lot with computations. Since monads naturally denote computations, we finally ended up with our own library of monads. Here are the most notable features our library:

  1. The library is thoroughly documented;
  2. The monad interface is very rich with more than a hundred of functions;
  3. Provides monad transformers for 12 Monads;
  4. A non-restrictive license (MIT).

The Monads library is developed by the BAP Team and is released as a part of the BAP v1.3 release. It can be installed from opam with opam install monads. Please, report any bugs to the BAP issue tracker. Pull request are always welcome!

P.S. If you don’t feel comfortable in the presence of monads, try our tutorial, maybe it will help you to get along with them.

18 Likes

Nice job! I especially like the brief introduction in the documentation.

Would it be possible to separate out monads from BAP? It would be nice to have a separate repo for clarity, issues, PRs, etc.

2 Likes

Sure, that’s the plan. It’s just a temporary measure, in fact they are independent… at least Monads do not depend on BAP.

@ivg This looks great and very helpful! I am going to swap this into a toy project this week! Could you point me towards a simple example of the transformers in action?

1 Like

+1
The introduction is certainly the best I have seen about monads: short, straightforward, to the point (especially for OCamlers, that is people used to functional programming with imperative aspects).

2 Likes

First of all, let me clarify a little bit what a monad transformer is. It looks like, that I didn’t explain thoroughly this concept in the documentation, so I will try to do it here, and then move it to the docs.

A monad transformer of a monad M takes a monad M' as an argument and wraps it into the monad M yielding a new monad that exhibits properties of both M and M'. So transformers are used to create new monads from existing monads. A particular example, that comes to mind is the Couroutine monad, that is usually implemented as a composition of the Continuation monad (that reifies the control flow) with the State monad (that reifies the data flow), giving us a monad that reifies the whole program semantics. I’m not sure whether it is a simple example though, since the Continuation monad is sort of mind-blowing to many people (as well as a concept of the continuation). A real world example, would be BAP’s Primus.Machine monad that is a composition of the Multi State, Result, and Continuation monads, and implements the semantics of the non-deterministic Turing Machine. Moreover, the Primus.Machine monad by itself is also a monad transformer, i.e., it is a functor that takes another monad as an argument and wraps it in the Primus.Machine monad.

In the Monads library, we provide a transformer for each monad, so that you can build your own monads from the twelve base monads that are already in the library. Each monad itself, is actually implemented as an application of its transformer to the Identity monad. This is a common way of building a monad using the transformers - you start with the Identity monad and then wrap it in more and more layers, until you get the satisfactory result.

Given that a transformer is actually a device to create your own monads, and writing a monad is much harder than using a monad, I would suggest to start with implementing a computation (algorithm) that is parametrized by a monad. Then you can start by applying your algorithm to different existing monads, and then to compositions of them. Basically, this is how you should use a monad, you should start with an algorithm, not with a monad.

Also, monads are abstractions, that are so abstract that they can represent several different and orthogonal concepts, i.e.,

  • totality of a computation (whether a computation may diverge)
  • determinism of a computation (whether a computation may yield more or less that one result)
  • data-flow (how a computation handles data effects)
  • control-flow (an order in which computations are evaluated).

So, for a particular generic program it may or may not make sense to parametrize it with one or another concept. The Primus.Machine example is sort of the extreme, as it basically the final object in the caterogy of monads, since it combines all the features of monads: it represents a non-total, non-deterministic computation with reified control and data flow. This is just because the Primus.Machine monad is used to model/study the computations itself, that are the essence of computer science :slight_smile:

In your case, I would start with something more simple. For example, you may try to deal with data structure traversals (i.e., you may find that iter, fold, find and other iterators can be generalized by putting iter into a monad, so that if a user wants to fold over a structure with some state, then the State monad can be used, if it is necessary to short-circuit the traversal, then a totality or a control flow monad can be used. This idea is very essential, when you’re dealing with very complex data structures such as programming languages representations, where instead of using a preprocessor to derive all possible sorts of iterators, we can use one iterator parametrized by a monad).

Later, you may proceed to more complex data structures and implement a computer language interpreter, parametrized by a computation monad. The interpret itself will define the (denotational) semantics of the language. By applying the interpreter to different monads you can build the same language with different flavors, e.g., lazy vs. strict, deterministic vs. non-deterministic, etc. The Bap_primus.Interpreter can be used as a real world example.

7 Likes

Terrific explanation again. Man, you’re good at this.

Since Lwt and Async are commonly used and monadic, were you planning to provide a transformer to combine your monads with them? (Actually I believe they’re really more of an applicative functor, but they have a monadic interface for a subset of their functionality.)

Also, have you benchmarked your monad transformers’ performance? State monads in particular are notoriously slow.

1 Like

Since Lwt and Async are commonly used and monadic, were you planning to provide a transformer to combine your monads with them? (Actually I believe they’re really more of an applicative functor, but they have a monadic interface for a subset of their functionality.)

The Lwt, Async, and other IO monads usually do not provide transformers and they act as an initial monad in the wrap. Since every monad in Monads provides a transformer, you can use it to wrap the IO monad, e.g.,

module Lwt_or_error = Monad.Result.Error.Make(Lwt)

Also, have you benchmarked your monad transformers’ performance? State monads in particular are notoriously slow.

Yes I did, though I didn’t have enough time to publish the results, but with flambda the results are shocking. Basically, in comparison with the legacy compiler the speed up was of factor 20 and more, giving the same overhead as normal fold function with a non-trivial type of state. Basically, if the state type is boxed, then a computation in a state monad is nearly as fast as a hand-written loop. If the state is unboxed or a float, then the hand-written loop usually wins.

The main drawback is the compilation time and the executable, I’ve used -O3 will multiple passes, and high cost of inlining. Also, I had a few issues with stuck compilations and running out of memory or with the stack overflow. So the released library, as of 1.0 will have this overhead. I will later add proper optimizations to the package, as soon as I will find a combination that is robust, relatively fast, and produces the efficient code.

4 Likes

Wow that’s great! So glad to hear we can finally use monads fairly efficiently in OCaml.

Good luck with that – it could be tough due to flambda’s capricious nature. Bear in mind that flambda is also being redesigned from the ground up.

Have you considered to separate them into the independent repository by the way? It is really helpful library, I use them in my project (just copied files for now), would be awesome to have it as an opam dependency instead.

Someone already did it, but it is out of sync, and not “official”. Would be nice to have an official version instead, and keep only one copy.

P.S. Now there is an updated documentation generated with odoc: http://binaryanalysisplatform.github.io/bap/api/odoc/monads/Monads/Std/index.html

1 Like