OCaml Weekly News

We are pleased to announce several minor releases: opam 2.0.10, opam 2.1.1, and opam-depext 1.2.

The opam releases consist of backported fixes, while opam-depext has been adapted to be compatible with opam 2.1, to allow for workflows which need to maintain compatibility with opam 2.0. With opam 2.1.1, if you export OPAMCLI=2.0 into your environment then workflows expecting opam 2.0 should now behave even more equivalently.

You'll find more information in the blog post .

A new 0.9.3 relase is available. Still not 1.0.0 just in case. The change I'm most glad I managed to make is that the lexer is now re-entrant and doesn't use any mutable state. Where can I apply for the "Designed for multicore OCaml" certification sticker? ;)

I am pleased to announce a new release of Fix, with several new modules contribued by Frédéric Bour (thanks!).

In short, Fix is a toolkit that helps perform memoization and fixed point computations (including data flow analyses). More generally, it offers a number of basic algorithmic building blocks that can be useful in many circumstances.

opam update
opam install fix.20211125

Documentation can be found here:

• https://gitlab.inria.fr/fpottier/fix/-/blob/master/README.md
• http://cambium.inria.fr/~fpottier/fix/doc/fix/Fix/index.html

Enjoy,

François Pottier
francois.pottier@inria.fr
http://cambium.inria.fr/~fpottier/

I am pleased to announce a new release of Menhir, with an exciting contribution by Frédéric Bour: a groundbreaking performance improvement in menhir --list-errors. This is made possible by an entirely new reachability algorithm, which has been designed and implemented by Frédéric, and which is described in our paper "Faster Reachability Analysis for LR(1) Parsers". This is the link to the paper:

http://cambium.inria.fr/~fpottier/publis/bour-pottier-reachability.pdf

To install the new release, just type

opam update
opam install menhir.20211125

Enjoy!

François Pottier
Francois.Pottier@inria.fr
http://cambium.inria.fr/~fpottier/

• The command menhir --list-errors has been sped up by a factor of up to x100, and requires up to x1000 less memory, thanks to a new LR(1) reachability algorithm, which has been designed and implemented by Frédéric Bour.
• Better document the restricted way in which the error token must be used when using --strategy simplified. Menhir now checks that this token is used only at the end of a production, and warns if this is not the case. (Better yet, our suggestion is to not use the error token at all!)
• The $syntaxerror keyword is now forbidden when using --strategy simplified. This keyword will be entirely removed in the next release. Incidentally, we have just found out that it behaves differently under the code back-end and under the table back-end.
• Disable OCaml warning 39 (unused rec flag) in the OCaml code produced by Menhir's code back-end. This does not affect the table back-end. (Reported by Armaël Guéneau.)
• Fix a bug in --random-* which could cause Menhir to diverge if the grammar uses the error token.
• Warn if a terminal symbol is named Error. This creates a name clash in the public interface of the generated parser.
• Menhir now requires OCaml 4.03.0 (instead of 4.02.3) and Dune 2.8.0 (instead of 2.0.0).

It is my pleasure to announce the release of Lwt version 5.5.0, Lwt_domain version 0.1.0, Lwt_react version 1.1.5, Lwt_ppx version 2.0.3 and Lwt_ppx_let version 5.5.0.

https://github.com/ocsigen/lwt/releases/tag/5.5.0

All those packages can be installed via opam as usual.

The OCaml team started switching to GitHub Actions last year for some of the official OCaml repositories. Also, we have released some CI related stuff, such as setup-ocaml, to the community. Some OCaml hackers also know that CI in the OCaml community is gradually switching to GitHub Actions nowadays.

However, what gradually became a problem when we started switching was that the number of concurrent jobs that could run in a free account on GitHub was not enough for our activeness.

One of the major pain points for compiler contributors is that the wait time for CI to complete, which is unrelated to the actual build, is too long. However, this has been a pain point in all services, even before GitHub Actions.

The GitHub team did their best to help us make it better. As a result, they offered to upgrade the OCaml organization's plan to the team plan for free, which means that we can now benefit from a range of features, including access to 3x more concurrent runners than before.

• About team plan: https://docs.github.com/en/actions/learn-github-actions/usage-limits-billing-and-administration
• Concurrency/plan: https://docs.github.com/en/get-started/learning-about-github/githubs-products#github-team

We would like to thank GitHub for supporting our team and Ahmed Bilal, who supported this effort.

The monads library provides the transformers for some well-known monads. All these monads have a more or less standard implementation, offering the same performance as any other monadic library can offer. Like there is no better way of implementing the state monad other than a function. We have experimented a lot with different performance optimizations, such as boxing and unboxing it and inlining various operators, and keep experimenting to get the maximum from the current compiler. In BAP, we heavily use the monads library, first of all for our knowledge representation and reasoning engine, which is the foundation for all BAP analyses. We also use it for emulating binary programs. The rich interface is here to make our life easier and more comfortable when we use monads. It definitely comes for free¹ as the number of functions doesn't affect the performance of the underlying monad.

But… there is always a but :) Stacking monads using a transformer does have a price. Even with the flambda compiler. The latter is doing an excellent job of unstacking them and eliminating the overhead of having a chain of monads. But our latest experiments show that a custom-made monad (still with the monads library) performs better under either branch of the compiler. We have rewritten our main monads that were relying on transformers and got from 20% to 50% performance improvement. But that is not to say that the monads library itself is slow or that we're not using it, it is to say that there are other options to transformers that might work in some cases. See the linked PR if you want to learn the trick.

¹⁾ Provided that we ignore the size of the executable, e.g., linking the core_kernel library results in a quite large binary, which may increase the startup time. Insignificantly, but in some use cases, it might be a significant factor.

As it was already suggested, you can use monad transformers, to compose several monads into a single monad. As a show-case, we will use the monads library (disclaimer, I am an author of this library), which you can install with

opam install monads

It offers most of the well-known monads in a form of a monad transformer, which in terms of OCaml, is a functor that takes a monad and returns a new monad that enriches it with some new behavior. For example, to make a non-deterministic error monad, we can do Monad.List.Make(Monad.Result.Error) and get a monadic structure (i.e., a module that implements the Monad.S interface) that is both a list monad and an error monad. The small caveat is that the operations of the wrapped monad, the error monad in our case, are not available directly, so we have to lift them, e.g.,

let fail p = lift @@ Monad.Result.Error.fail p

So that in the end, the full implementation of the transformed monad still requires some boilerplate code,

module ListE = struct
  type 'a t = 'a list Monad.Result.Error.t
  include Monad.List.Make(Monad.Result.Error)
  let fail p = lift@@Monad.Result.Error.fail p
  (* and so on for each operation that is specific to the wrapped monad *)
end

Now, let's try wrapping the Lwt monad into the state. We don't want to add the Error monad because Lwt is already the error monad and adding an extra layer of errors monad is not what we want. First of all, we need to adapt the Lwt monad to the Monad.S interface, e.g.,

module LwtM = struct
  type 'a t = 'a Lwt.t
  include Monad.Make(struct
      type 'a t = 'a Lwt.t
      let return = Lwt.return
      let bind = Lwt.bind
      let map x ~f = Lwt.map f x
      let map = `Custom map
    end)
end

If we want to keep the state type monomorphic, then we will need a module for it. Suppose your state is represented as,

module State = struct
  type t = string Map.M(String).t
end

Now, we can use it to build our State(Lwt) Russian doll,

module IO = struct
  include Monad.State.T1(State)(LwtM)
  include Monad.State.Make(State)(LwtM)

  (* let's lift [read] as an example *)
  let read fd buf ofs len =
    lift (Lwt_unix.read fd buf ofs len)
end

The Monad.State.T1 functor is used to create the types for the generated monad. You can write them manually, of course, like as we did in the List(Error) example, but the type generating modules are here for the convenience¹

Now, let's get back to the problem of the lifting. It looks tedious to impossible to lift every operation from Lwt. Commonly, we try to put the smaller monad inside, to minimize the work, but it doesn't work with Lwt as the latter is not a transformer. So what is the solution? For me, the solution is to not lift the operations at all, but instead, define your IO abstraction and hide that it is using Lwt underneath the hood. This will make the code that uses this new abstraction more generic and less error-prone so that it can focus on the business logic and the implementation details could be hidden inside the monad implementation. This is what the monads are for, anyway.

¹⁾ We omit the types from the output of the Make functor since for a long time OCaml didn't allow the repetition of types in a structure so having the types in it will prevent us from composing various flavors of monads using include. It is also a long-time convention widely used in many OCaml libraries, including Core and Async. A convention that we probably don't need anymore.