OCaml Weekly News

Online, (Scala/Java) and Haskell-specific tutorials on existential types seem to be dominant. Because I wouldn't get stuck too much on notation, I went with Haskell tutorials, and they all seem to imply that existentials that are unconstrained are useless.

The usual example for existentials is information (but not trait) hiding, in which for example you can have a definition like so (with some syntax parallels for those unfamiliar with haskell):

{-
ocaml: ~type gadt = Constr : typexpr~
haskell: ~data Gadt where Constr :: typexpr~
-}

data Hidden where
  Hide :: Show a => a -> Hidden

{-
ocaml: iter (fun (Hide x) -> ...) [Hide 1; Hide ...]
-}

main :: IO ()
main =
  mapM_ (\(Hide x) -> print x) [Hide 1, Hide "a", Hide 4.2]

The problem with such implication is that I can't find a usage for an existential introduced by an OCaml GADT because I don't know how I'd express the Show a => a constraint.

type hidden = Hide : 'a -> hidden

Would simply completely cloak 'a, and any attempt at interacting with it would produce a type scope escaping error.

That considered, since Show a => a is best emulated now with passing a first-class module, that was the vector I was walking in with my existentials experiments, but I have a feeling there's better, more valid, usage of those type variables that isn't reliant on constraining.

So my question is, have you ever come across a pattern where an existential type variable is the solution?

Your showable example can be written as:

type showable = Show: 'a * ('a -> string) -> showable

And there is fact many similar way to constraint existential types, either using type constructors: if you have an 'a. 'a t, you may still be able to write useful functions, or coupling various producers or consumers of the existential types.

The showable example is a little artificial here but that are many examples where existential types are useful for:

• representing internal types.
• hiding some type information at an abstraction barrier.

I can offer one examples that combines the two to implement a zipper through mutually recursive trees. Starting from a simplified data structure

type a_tree =
  | Leaf of int
  | Node_A of b_tree * b_tree
and b_tree =
  | Leaf of float
  | Node_B of a_tree * a_tree

Then zipper over a binary tree would be simply:

type dir = Left | Right
type zipper = { value: tree; path: (dir * tree) list }

but here our problem is that we have alternatively a_tree and b_tree. We can use existential types to keep a similar representation as the simpler zipper described above. The first step is to describe a step in the data structure as

type ('a,'b) step =
  | A: dir * b_tree -> (b_tree,a_tree) step
  | B: dir * a_tree -> (a_tree,b_tree) step

Then we can connect the step using an existential types to describe that if we have a path from nodes of type top to a node of type bottom, we don't necessarily know the intermediary types

type ('bottom,'top) path =
  | []: ('top,'top) path
  | (::):
  ('bottom , 'previous_bottom) step * ('previous_bottom,'top) path ->
    ('bottom,'top) path

Then a zipper is simply:

type ('bottom,'top) zipper = { value: 'bottom; path:('bottom,'top) path }

However, sometime we don't care if we don't know where we are in the tree, thus we may need to erase the bottom information from the zipper:

type 'top any_zipper = Any: ('bottom, 'top) zipper -> 'top any_zipper

and we can still use this any_zipper type to write an up function for instance:

let up (type top) (Any z: top any_zipper) =
  match z.path with
  | [] -> Any z
  | A (Left,r) :: rest ->
    Any { path=rest; value = Node_A(z.value,r) }
  | B (Left,r) :: rest ->
    Any { path=rest; value = Node_B(z.value,r) }
  | A (Right,l) :: rest ->
    Any { path=rest; value = Node_A(l, z.value) }
  | B (Right,l) :: rest ->
    Any { path=rest; value = Node_B(l, z.value) }

Any time you have useful functions of type 'a. 'a t -> .., you can quantify existentially that type parameter and still retain some functionality. For instance, I can compute a length for an any_list:

type any_list = Any_list : 'a list -> any_list
let len (Any_list l) = List.length l

then there is also the possibility to use type witnesses to recover the quantified type at a later date:

 type 'a num_ty =
| Int: int num
| Float: float num
type num = Num: 'a num_ty * 'a -> num
type num_array = Narray: 'a num_ty * 'a array -> num_array
let sum (Narray (witness, array)) = match witness with
| Int -> Num(Int, Array.fold_left (+) 0 array)
| Float -> Num(Float, Array.fold_left (+.) 0. array)

@octachron's examples are very good. For variety, here is a small example of a slightly different flavor that we use in ocamlformat to wrap Cmdliner: (from here)

include Cmdliner

(** existential package of a Term and a setter for a ref to receive the
    parsed value *)
type arg = Arg : 'a Term.t * ('a -> unit) -> arg

(** convert a list of arg packages to a term for the tuple of all the arg
    terms, and apply it to a function that sets all the receiver refs *)
let tuple args =
  let pair (Arg (trm_x, set_x)) (Arg (trm_y, set_y)) =
    let trm_xy = Term.(const (fun a b -> (a, b)) $ trm_x $ trm_y) in
    let set_xy (a, b) = set_x a ; set_y b in
    Arg (trm_xy, set_xy)
  in
  let init = Arg (Term.const (), fun () -> ()) in
  let (Arg (trm, set)) = Base.List.fold_right ~f:pair args ~init in
  Term.app (Term.const set) trm

let args : arg list ref = ref []

let mk ~default arg =
  let var = ref default in
  let set x = var := x in
  args := Arg (arg, set) :: !args ;
  var

let parse info validate =
  Term.eval (Term.(ret (const validate $ tuple !args)), info)

The idea here is similar to an "any list", where an existential around a pair of an 'a Cmdliner.Term.t representing a command-line argument yielding an 'a value, and a function of type 'a -> unit to set a ref to the parsed value. Then a list of such packages can be built using mk and then converted with tuple to a single Cmdliner.Term for the list as a tuple.

I don't think this example needs anything more from the type system, but is an almost minimal example of packaging a value with the interesting operations over it into an existentially-typed value.

I have made my own futures library and one of the features is futures are connected to each other creating a dependency tree. This is done so that you can do Future.abort fut and it will abort that future and everything connected to it. I accomplish this by each future storing a list of those futures that depend on it. But those futures do not necessarily have the same type. So I hide the type in an existential so I can still perform actions on the future that do not depend on the type.

Note, I stole this from @dbuenzli 's futures library which I used to start mine.

Here is the code from my library:

(* The concrete type of a future.  Future's are mutable, but once they are
   determined they become immutable.  A future has a state which starts as
   undetermined, can become determined or an alias.  An alias is a future that
   needs to exist because some unknown computation will eventually become its
   value, and once that computation is found out, we set the future to an
   alias to that future. *)
type 'a u = { mutable state : 'a state }

and 'a state =
  [ 'a Abb_intf.Future.Set.t
  | `Undet of 'a undet
  | `Alias of 'a u
  ]

(* An undetermined has an optional function, which is some work to be
   executed, watchers are executed when this undetermined future becomes
   determined, deps are futures that are not required to be executed before
   this future is determined but in some meaningful way connected to it, the
   abort function is what to do if this future is aborted, and finally num_ops
   is how many operations have been performed on this future.  The definition
   of an "operation" is kind of vague but basically it corresponds to mutating
   this undetermined future in some way. *)
and 'a undet = {
  mutable f : (State.t -> State.t) option;
  mutable watchers : 'a Watcher.t list;
  mutable deps : dep list;
  abort : abort;
  mutable num_ops : int;
}

(* A dependency can be any future and it will not have the same type as this
   future, so we have to hide the actual type in an existential so we can
   reference any future as a dependency. *)
and dep = Dep : 'a u -> dep

Welcome to the September 2021 Multicore OCaml monthly report! This month's update along with the previous updates have been compiled by me, @ctk21, @kayceesrk and @shakthimaan. The team has been working over the past few months to finish the last few features necessary to reach feature parity with stock OCaml. We also worked closely with the core OCaml team to develop the timeline for upstreaming Multicore OCaml to stock OCaml, and have now agreed that:

OCaml 5.0 will support shared-memory parallelism through domains and direct-style concurrency through effect handlers (without syntactic support).

• The Domain mechanism permits OCaml programmers to speed up OCaml code by taking advantage of parallel processing via multiple cores available on modern processors.
• Effect handlers allow OCaml programmers to write high-performance concurrent programs in direct-style, without the use of monadic concurrency as is the case today with the Lwt and Async libraries. Effect handlers also serve as a useful abstraction to build other non-local control-flow abstractions such as generators, lightweight threads, etc. OCaml will be one of the first industrial-strength languages to support effect handlers.

The new code will have to go through the usual rigorous review process of contributions to upstream OCaml, but we expect to advance the review process over the next few months.

What is the upcoming OCaml debugging story? Firing up the native executable and debugging using gdb/rr is going to be difficult because all you will see is low level stuff.

We've gone to some effort to preserve DWARF unwinding correctly in multicore OCaml (see the effects paper for more details). You may also want to check the debugging tips and tricks in the OCaml multicore wiki which has info on how to use gdb and rr. You do get your functions back as mangled names, but it's pretty easy to visually map those back to their original OCaml function names by inspection.

Avec plus de 4 millions de membres et 7 milliards d'individus référencés, Geneanet est leader sur le marché de la généalogie. Dans le cadre de notre croissance, nous recherchons un(e) développeur(euse) OCaml afin de renforcer nos équipes de développement.

DESCRIPTION DU POSTE

Vous intégrerez une équipe SCRUM et prendrez part au développement du logiciel OpenSource GeneWeb, qui est au coeur de l’architecture des outils de saisie et de présentation des généalogies sur Geneanet.

Vous pourrez participer à de nombreux projets d’évolution sur les arbres généalogiques (saisie, calculs de parenté, exports, recherche d’informations), apporter vos idées et votre créativité lors de semaines de labs et prendre en charge des sujets plus large d’évolution de la plateforme technique.

PROFIL REQUIS

• Vous promouvez et partagez les valeurs de l'Open Source.
• Vous avez une réelle expérience sur l’utilisation du langage OCaml.
• Une connaissance des technologies du web (PHP, Mysql, HTML, CSS, Javascript) est requise.
• Vous avez le souci de la maintenabilité du code et du service rendu à l’utilisateur final.
• Vous aimez travailler en équipe.
• Vous êtes éventuellement intéressé(e) par la généalogie, l’Histoire ou les jeux de société à la pause de midi…

Si vous vous reconnaissez dans ce qui précède, envoyez nous votre CV à recrutement-tech@geneanet.org ! Poste basé à Paris, possibilité de télétravail 3j/semaine.

We have discovered a regression within OCaml 4.13.0 that make the compiler crash on classes named row

module M = struct
   class row = object end
end

due to a collision between two families of internal identifiers.

To restore your freedom to name classes however you want, we have released OCaml 4.13.1 as an early bug-fix release.

This new version is available as a set of OPAM switches with

opam update
opam switch create 4.13.1

and as a source download here:

https://caml.inria.fr/pub/distrib/ocaml-4.13

It with great excitement and some ~2 years of anticipation that we have now the pleasure to announce the release of Liquidsoap 2.0.0!

The release is currently being deployed to opam and should be available through their main repository shortly. If you need to install it right away you can do:

git clone https://github.com/savonet/liquidsoap.git
cd liquidsoap && git checkout v2.0.0
opam install -y .

The release also includes binary packages for a bunch of platforms/OSes.

The idea is quite simple. There are many people lurking here that wish to write an OCaml book or tutorial or blogpost, however :

• either they miss the most illustrative ocaml code snippet
• or they know what the best code is but there is a (potential) Statement of Rights violation

I want to help these people, starting with @dmbaturin and OCaml From the Ground Up. I will publish here my own code as CC-BY-SA 4.0. Also i will link to resources that are known to be CC-BY-SA 4.0-compatible. And i invite you to post your own code as CC-BY-SA 4.0 so that it can be inspiring and used in educational material.

Editor’s note: this message was followed by many code snippets. Please follow the archive link above to read them.