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;

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.

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

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.)

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)
``````

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.