OCaml Weekly News

• #9856, #9857: Prevent polymorphic type annotations from generalizing weak polymorphic variables. (Leo White, report by Thierry Martinez, review by Jacques Garrigue)
• #9859, #9862: Remove an erroneous assertion when inferred function types appear in the right hand side of an explicit :> coercion (Florian Angeletti, report by Jerry James, review by Thomas Refis)

Given a type Bigstring.t (1 dimensional byte arrays) there now exist functions such as -

val cmpeq_i8 : (t * int) -> (t * int) -> (t * int) -> unit

So cmpeq_i8 (x,o1) (y,o2) (z,03) will compare 32 bytes starting at o1 and o2 from x and y respectively and store the result in z at o3.

This was mainly an exercise in curiosity. I just wanted to learn whether something like this is viable. I also want to see if adding some type-directed magic + ppx spells can let us write data parallel code much more naturally similar to what lwt / async did for async code.

At the same time, you might ask - why not use something like Owl (which already has good support for data-parallel operations)? Apart from the fact that such libraries are oriented towards numerical code, I would also like to explore if we can operate directly on OCaml types and cast them into data parallel algorithms. Like how simdjson pushed the boundaries of JSON parsing, it would be nice to port idiomatic code to data-parallel versions in OCaml. Can we, at some point, have generic traversals of data-types, which are actually carried out in a data-parallel fashion?

Given the limitation of the current implementation (due to foreign function calls into C), I still found some preliminary results to be interesting! Implementing the String.index function, which returns the first occurence of a char, the runtime for finding an element at the n-1 position in an array with 320000000 elements is -

serial: 1.12 seconds
simd: 0.72 seconds (1.5x)

I still have to do the analysis what the overhead of the function call into C is (even with [@@noalloc]!

It would be interesting to see, if we can create a representation which encapsulates the various SIMD ISA's such as AVX2, AVX512, NEON, SVE etc. Further more, it would be really interesting to see if we can use ppx to automatically widen `map` functions to operate on blocks of code, or automatically cast data types in a data parallel representation.

This was mostly a hobby project, so I cannot promise completing any milestones or taking feature requests etc. I definitely do not recommend using this in production, because of the lack of testing etc.

Based on camlp5 and the pa_ppx PPX rewriters, I've written a new one, pa_deriving_plugins.rewrite, that automates almost all the work of writing a migration from one version of OCaml's AST to another.

1. It took a few days (b/c of laziness) to write the initial PPX rewriter
2. A day to get 4.02->4.03 AST migration working
3. a couple of hours to get 4.03->4.02 working
4. and a few more hours to get 4.03<->4.04 and 4.04<->4.05 working

At this point, I fully expect that the other version-pairs will not be difficult.

You can find this code [warning: very much a work-in-progress] at https://github.com/chetmurthy/pa_ppx/tree/migrate-parsetree-hacking

The file pa_deriving.plugins/pa_deriving_rewrite.ml contains the source for the PPX rewriter.

The directory pa_omp contains the migrations, typically named rewrite_NNN_MMM.ml.

If you think about it, ppx_deriving.map isn't so different from what we need for ocaml-migrate-parsetree. ppx_deriving.map, from a type definition for ~ 'a t~, will automatically generate a function

map_t : ('a -> 'b) -> 'a t -> 'b t

If you think about it, if we could just substitute our own type for the second occurrence of t (somehow …. yeah grin) then it would be almost like what we want for o-m-p, yes?

With 11 versions of the Ocaml AST so far, maybe it's worth thinking about how to automate more of the migration task. Also, since so much of it is type-structure-driven, one would think that it would be an excellent opportunity to apply PPX rewriting technology. Indeed, one might think that a good test of PPX rewriting, is the ability to automate precisely such tasks.

So what's hard about this migration task? Here are some issues (maybe there are more):

1. the types are slightly differently-organized in different versions of the AST. Types might move from one module to another.
2. sometimes new types are introduced and old ones disappear
3. constructor data-types may get new branches, or lose them
4. record-types may get new fields, or lose them
5. sometimes the analogous types in two consecutive versions are just really, really different [but this is rare]: we need to supply the code directly
6. when mapping from one version to another, sometimes features are simply not mappable, and an error needs to be raised; that error ought to contain an indication of where in the source that offending feature was found
7. And finally, when all else fails, we might need to hack on the migration code directly

But morally, the task is really straightforward (with problems listed in-line):

1. use ppx_import to copy over types from each of the AST times of each Ocaml version
   • ppx_import works on .cmi files, and those have different formats in different versions of Ocaml. Wouldn't it be nice if it worked on .mli files, whose syntax (b/c OCaml is well-managed) doesn't change much?
2. build a single OCaml module that has all the AST types in it (from all the versions of OCaml)

   • but without the form

     type t = M.t = A of .. | B of ....
     

     that is, without the "type equation" that allows for a new type-definition to precisely repeat a previous one.

3. Then use ppx_import against this single module to construct a recursive type-declaration list of all the AST types for a particular version of OCaml, and apply a "souped-up" version of ppx_deriving.map to it, to map the types to another version of the AST types.
   • but ppx_deriving.map doesn't do this today, and besides, it would have to provide a bunch of "escape hatches" for all the special-cases I mentioned above.

But this is in principle doable, and it has the nice feature that all the tedious boilerplate is mechanically-generated from type-definitions, hence likely to not contain errors (assuming the PPX rewriter isn't buggy).

So I decided to do it, and this little post is a result.

I think this is a quite viable approach to writing ocaml-migrate-parsetree, and I would encourage the PPX community to consider it. One of the nice things about this approach, is that it relies heavily on PPX rewriting itself, to get the job done. I think one of the important things we've learned in programming languages research, is that our tools need to be largely sufficient to allow us to comfortably implement those same tools. It's a good test of the PPX infrastructure, to see if you can take tedious tasks and automate them away.

I'm not going to describe anymore of how this works, b/c I'd rather get the rest of the migrations working, start figuring out how to test, and get this code integrated with camlp5.

But for anybody who's interested, I'd be happy to interactively describe the code and walk them thru how it works.

"Hm, I wonder what years have Febuary 29th?"

$ telltime search --time-slots 5 --years 100 "feb 29 00:00"
Searching in time zone offset (seconds)            : 36000
Search by default starts from (in above time zone) : 2020 Sep 03 19:24:15

Matching time slots (in above time zone):
[2024 Feb 29 00:00:00, 2024 Feb 29 00:00:01)
[2028 Feb 29 00:00:00, 2028 Feb 29 00:00:01)
[2032 Feb 29 00:00:00, 2032 Feb 29 00:00:01)
[2036 Feb 29 00:00:00, 2036 Feb 29 00:00:01)
[2040 Feb 29 00:00:00, 2040 Feb 29 00:00:01)

"Would be handy to know what this cron expression refers to"

$ telltime search --time-slots 5 "0 4 8-14 * *"
Searching in time zone offset (seconds)            : 36000
Search by default starts from (in above time zone) : 2020 Sep 06 17:39:56

Matching time slots (in above time zone):
[2020 Sep 08 04:00:00, 2020 Sep 08 04:01:00)
[2020 Sep 09 04:00:00, 2020 Sep 09 04:01:00)
[2020 Sep 10 04:00:00, 2020 Sep 10 04:01:00)
[2020 Sep 11 04:00:00, 2020 Sep 11 04:01:00)
[2020 Sep 12 04:00:00, 2020 Sep 12 04:01:00)

"I have a bunch of time ranges, but some of them overlap, and they are not in the right order. If only there is a way to combine and sort them easily."

$ telltime search --time-slots 1000 "2020 . jan . 1, 10, 20 . 13:00 to 14:00 \
  || 2019 dec 25 13:00 \
  || 2019 dec 25 10am to 17:00 \
  || 2020 jan 5 10am to 1:30pm \
  || 2020 . jan . 7 to 12 . 9:15am to 2:45pm"
Searching in time zone offset (seconds)            : 36000
Search by default starts from (in above time zone) : 2020 Sep 06 18:01:12

Matching time slots (in above time zone):
[2019 Dec 25 10:00:00, 2019 Dec 25 17:00:00)
[2020 Jan 01 13:00:00, 2020 Jan 01 14:00:00)
[2020 Jan 05 10:00:00, 2020 Jan 05 13:30:00)
[2020 Jan 07 09:15:00, 2020 Jan 07 14:45:00)
[2020 Jan 08 09:15:00, 2020 Jan 08 14:45:00)
[2020 Jan 09 09:15:00, 2020 Jan 09 14:45:00)
[2020 Jan 10 09:15:00, 2020 Jan 10 14:45:00)
[2020 Jan 11 09:15:00, 2020 Jan 11 14:45:00)
[2020 Jan 12 09:15:00, 2020 Jan 12 14:45:00)
[2020 Jan 20 13:00:00, 2020 Jan 20 14:00:00)

$ telltime from-now "1 hour"
Now                   : 2020-09-03 15:53:29
Duration (original)   : 1 hour
Duration (normalized) : 1 hours 0 mins 0 secs
Now + duration        : 2020-09-03 16:53:29

$ telltime from-now "1.5 days 2.7 hours 0.5 minutes"
Now                   : 2020-09-03 15:55:43
Duration (original)   : 1.5 days 2.7 hours 0.5 minutes
Duration (normalized) : 1 days 14 hours 42 mins 30 secs
Now + duration        : 2020-09-05 06:38:13

s1 >> s2 is similar to s1 || s2, but >> picks between s1 and s2 in a round robin fashion, instead of just picking the smallest between two.

One specific differing case would be when the search starts at 4pm today, 3pm || 5pm would return 5pm today and 3pm tomorrow, and so on, while 3pm >> 5pm would return 3pm tomorrow and 5pm tomorrow (a 5pm is only picked after a 3pm has been picked already).