Dromedary and a half - The little type that could too much
The little type that could too much
Part<br>1: Hashtbl, Mashtbl, Smashtbl, Slashtbl, Clashtbl, Crashtbl
The Hashtbl module of the OCaml’s Stdlib<br>exposes a parametric type ('a, 'b) t. As the<br>documentation explains, they are used as mutable key-value stores in<br>imperative code.
However, the module doesn’t expose just a “hashed association table”.<br>Instead, the module exposes a data-structure and functions meant to<br>model the notion of “environments” in the programming-language and<br>compiler domains. Specifically: it’s a one-to-ordered-list association<br>table with some helpers to work on the head of the ordered list. This<br>only becomes clearer further down in the documentation:
The add<br>function contains a warning: adding a binding doesn’t remove the<br>previous bindings, it just shadows them.
The remove<br>function “restores the previous binding”.
The find_all<br>function returns “the list of all data associated with [the<br>key]”.
etc.
(The same behaviour exists for specialised hash tables obtained via<br>Hashtbl.Make. I’ll only discuss the Hashtbl<br>module for brevity.)
This behaviour is somewhat surprising because the semantics differs<br>from other languages’ stdlibs: Python’s<br>dict, Rust’s<br>HashMap. This behaviour is also arguably less intuitive<br>and more complex: the state of the Hashtbl after you call<br>remove is not known.
It is possible to use the Hashtbl in a way that corresponds to the<br>other languages’ semantics: just use replace instead of<br>add. You can find such uses in the wild publicly<br>released packages of opam repository. For example, dream’s<br>graphql’s subscriptions and ringo’s<br>resource cache tables.
The issue is that you have to do it consistently. Mixing and matching<br>is a possible source of bugs or memory leak. There are no guardrails.<br>All you get is a Hashtbl.t and you are left to determine<br>whether you should call add or replace,<br>whether find_all is relevant or not.
At Ahrefs, we’ve taken to linting<br>out the use of Hashtbl.add and enforcing the arguably<br>simpler Hashtbl.replace semantic. That’s our guardrail.<br>Just a linter. In the rare cases that we do want to maintain bindings to<br>a growable list of values, we have a dedicated module implementing just<br>this. And it seems we’re not the only ones: ocaml-uri’s<br>config exposes a hashtbl_add_list function to<br>accumulate values into a list explicitly.
Ideally, the multiple uses of a Hashtbl would be exposed<br>as different modules. One module to manage environments exposing<br>add a find_opt and find_all; one<br>module to manage one-to-one association tables exposing<br>replace and find_opt.
module HashEnvTbl : sig<br>type ('a, 'b) t
(* equivalent to Hashtbl.add *)<br>val push : ('a, 'b) t -> 'a -> 'b -> unit
(* equivalent to Hashtbl.find_opt *)<br>val peek: ('a, 'b) t -> 'a -> 'b option
(* equivalent to Hashtbl.find_and_remove *)<br>val pop: ('a, 'b) t -> 'a -> 'b option
[… some other functions …]
end
module Hash1to1Tbl : sig<br>type ('a, 'b) t
(* set the value bound to the given key *)<br>val set : ('a, 'b) t -> 'a -> 'b -> unit
(* equivalent to Hashtbl.find_opt *)<br>val get: ('a, 'b) t -> 'a -> 'b option
(* remove the binding for the given key *)<br>val unset: ('a, 'b) t -> 'a -> 'b option
[… some other functions …]
end<br>I don’t know that it is worth changing the Stdlib. It would open a<br>can of worm of design with backwards compatibility considerations. And<br>it would place the burden of maintenance on a team which already handles<br>a lot of work. (Maybe I’ll make a patch to the documentation, mentioning<br>the quirk earlier on.) But I think it’s an important consideration for<br>altlibs.
More importantly, this Hashtbl quirk is small and interesting example<br>for the rest of this post.
Part 2: Lwt_stream,<br>one type to rule them all
The Lwt_stream module of the Lwt library exposes a<br>parametric type 'a t. The documentation doesn’t state any<br>intended uses. It simply states somewhat tautologically that a<br>'a Lwt_stream.t is “a stream holding values of type<br>'a”.
In practice, a Lwt_stream is a sequence of values which<br>become available at different times in the life of the program. The only<br>guarantee of the data-structure is that the ordered is preserved inside<br>the stream: values added in a given ordered are processed in the same<br>order.
Part 2a: 推, 拉 and so much<br>more
There aren’t really many guarantees about the data-structure because<br>it supports many different uses with many different requirements. Common<br>uses include:
Lwt stream for push-based pipelines. You can use Lwt<br>streams to hold and transport values which are added as they become<br>available (e.g., read from a pipe). Each addition triggers a cascade of<br>computations. The rhythm of the processing pipeline is dictated by the<br>uses of the push function.
(* reimplementing `Lwt_io.read_lines` for the sake of example *)<br>let lines_of_ic ic =<br>let s, push = Lwt_stream.create () in<br>let rec feed () =<br>match Lwt_io.read_line_opt ic with<br>| None -> push None; Lwt.return ()<br>| Some l -> push Some l; feed...