What should be the role of the standard library?

[nojb]

This question (having a lean standard library vs a "batteries-included" one) has and continues to come up frequently whenever new additions to the standard library are considered. Not having a clear (and consensual) answer to this question amounts to a lack of strategic direction for the standard library, and it greatly hampers its evolution.

Recently the question came up again in the context of #11098.

@gasche opined:

We would try to focus on functions that are clearly things we need, instead of functions that might potentially maybe someday be useful. I am sure there are parts of the stdlib function that are frustrating to use because basic stuff is missing. Let's focus on that basic stuff instead of adding the next Array.fold_mapi_inplace function.

Doing (2) well may require some advance thinking on what parts we wish to develop (and maybe which part are better forgotten for good and replaced by third-party libraries), instead of gliding along PRs submitted on random parts of the stdlib.

And @c-cube followed up with:

I think this is a great remark. But even before asking how and where to improve the stdlib, the first thing to do is ask what the role of the stdlib is, and what its scope is.

Obviously OCaml's stdlib will never be as expansive as Python's (or even Go's, I guess). But, there needs to be a clear philosophy and clear design goals: should it remain, like it is currently, a quite minimalistic algorithmic package with an approximately posix-equivalent layer of IO capabilities? Or, should it provide a set of features that will be useful in most programs (which, in this day and age, I'd argue must include json, base64, better IOs, crypto hashes, and lots of other network related basics)?

I think this question is important. Answering it is a prerequisite to figuring out what is the "basic stuff" that @gasche alludes to in his comment.

---

Should the standard library remain, like it is currently, a quite minimalistic algorithmic package with an approximately POSIX-equivalent layer of IO capabilities? Or, should it provide a set of features that will be useful in most programs (which, in this day and age, I'd argue must include json, base64, better IOs, crypto hashes, and lots of other network related basics)?

[dbuenzli]

Taking this from what I once wrote elsewhere. My take on this would be:

The stdlib provides the minimal infrastructure to allow the batteries included of today and tomorrow to be defined in a lean, interoperable and distributed way outside of the language distribution – assuming a minimal amount of cooperation among the external actors.

This means providing datatypes and essential functions so that when you try to build an application with the bazaar, you don’t end with two different concurrency monads, three different modules of string convenience functions and four incompatible definitions of file descriptors.

This is not to say that the line is easy to draw but it should allow to guide some decisions. For example rather than the language or stdlib enshrining and providing support for the serialization format du moment, it’s likely a better idea for the stdlib to provide infrastructure for the serialization problem.

[gasche]

Another thing you mentioned somewhere that I found interesting, and relevant to the conversation, is that you are unconvinced by the current system-programming modules offered by the stdlib (Sys and then Unix). Maybe we should consider deprecating their active uses (besides "shared building block exposing portable runtime capabilities" and "what makes our compiler-writing life easier") and seriously think about advertising third-party libraries for that problem domain.

[dbuenzli]

I'm not unconvinced by Unix, it provides thin bindings to POSIX system calls + a nice compatibility layer for Windows. I think it's a good set of primitives on top of which nicer and more ergonomic stuff can be provided.

I'm unconvinced by Sys because some of its functions have bad usability (e.g. Sys.file_exists that turns permission errors into false) and more importantly because it adds dependencies on system calls to the runtime system that are not needed for it to provide its service. As such I don't think it's a good idea to add more to Sys.

[gasche]

Personally my usual comment regarding extending the scope of the stdlib quite a bit is that there are few benefits compared to using a third-party package. I have the impression that, for the OCaml community, having specialized packages to do this or that tends to work better than having large, integrated libraries that try to cover a lot of ground. The main effort in the direction of "let's cover a lot of ground" I was involved in was Batteries, and it suffered a lot from its own weight.

I could see ourselves doing more in terms of data-exchange formats for interoperability purposes, and I remain supportive of efforts to make FFI-types more standard (yes, unsigned integers). But getting a HTTP client library in the stdlib sounds like too much of a commitment for no clear gain compared to having it developed and maintained outside.

On the other hand, we actually have a decent track record of exploring state-of-the-art options for PRNG, compression lately, and hashing, thanks to @xavierleroy's interest in this corner of the algorithm toolbox. One thing that works well for the stdlib is that we can expose these capabilities without being too explicit about which specific algorithm we chose, and so we can evolve in the future in a mostly backward-compatible way.
Crypto works in a specific problem domain, but there people actually rely precisely on which algorithm/protocol is exported for interoperation with other systems, and people's needs move fast, sometimes with urgency. I am skeptical that we could cover that to satisfying quality standards. (I mean, we are still using md5 in various places.)

In summary: I would personally push back on growing the scope of the stdlib in very different problem domain, and rather try to foster a vibrant ecosystem of third-party packages to cover those needs. I think there is room for new modules that are small and require little maintenance, typically simple, common data structures (I am working on dynamic arrays, we mentioned priority queues, maybe there are other ideas but no need to hurry). I could see us adding some transversal aspects to many modules (for example a non-trusted serialization / data exchange format). Maybe some concurrency-related structures as well?

[c-cube]

I kind of agree with you about the scope of the stdlib remaining smallish. However, there are some true upsides to something being in the stdlib as opposed to an opam package:

• you don't have to worry about versioning constraints, conflicts with other libraries that want a different version, etc.
• everybody will agree on the types and API since it's the standard one, so interoperability is better

However, I think it's currently still too minimal. An example of a good minimal stdlib, to me, is rust's (even though it doesn't have some of the things I listed in my earlier post). A few things that rust, with 20+ years of hindsight, did better imho:

• a standard derive mechanism with some derivers present in the stdlib (more or less, the equivalent of ppx_deriving.std). This is tremendously useful, since it means most types will have a printer, an equality and comparison function, etc.
• traits for IO (Read, Write, BufRead, BufWrite), so that IOs can be composed
• a heap implemented on top of the dynamic arrays
• a modular hashing interface (via a trait that's generic on the hash algorithm itself), so that can be used with cheap hashes such as FNV, or with cryptographic hashes, all the same. You only derive it once.
• basic time functions, basic subprocess functions (these are kind of served by Unix, but not too well. In practice I always have to reach for ptime/mtime and redo my own layer on top of Unix for subprocesses).

Let's note that rust also has this philosophy of at least providing some common ground in the ecosystem, even for features it doesn't implement itself: the Future trait is an example. If you want async IO and all that, you typically use tokio.rs, but at least everyone agrees on what futures are.

edit: I think, for the stdlib, good steps forward would be to have more standard types for interoperability. It's not the first time I suggest this but well. Having cstruct, sexp, json (even if it's just types) and improving channels would go a long way. I know adding ppx_deriving.std to the stdlib will sadly never happen.

[L1-42]

I think there is room for new modules that are small and require little maintenance, typically simple, common data structures (I am working on dynamic arrays, we mentioned priority queues, maybe there are other ideas but no need to hurry). I could see us adding some transversal aspects to many modules (for example a non-trusted serialization / data exchange format). Maybe some concurrency-related structures as well?

From a user point of view, an implementation of simple data types would be really useful. Some other types that come to mind : binary trees (which I am working on, and I would gladly share my code), binary search trees (AVL or B-trees), Heap (close to Priority Queue), Mat_Graph (with an adjacency matrix implementation), List_Graph (same with an adjacency list), with implementations of classic algorithm such as Dijkstra's algorithm, TSP, traversal, (strongly) connected components, etc.

[c-cube]

That sounds a lot like containers ;-). Joke aside, the stdlib already has AVL trees in Map and Set. Heaps are a big missing feature, idk why. Graph algorithms are harder to do satisfactorily without more abstraction, which is why most people use ocamlgraph and its functors that can work with one's own data structure. I personally almost never have "a graph", I always have something that can also behave like a graph.

…

-- Simon Cruanes

[L1-42]

I don't think Containers has a binary tree nor a graph module... They could however be added to Containers rather than Stdlib.
As for graphs, I am not familiar with ocamlgraph at all, but it still seems like only a few algorithms are implemented... A*, Kosaraju's algorithm, Prim and Kruskal algorithms, etc. are still missing... (Although having those algorithms would definitely be better in a Containers style library)
Another data type I just thought of, which may already exists (but not to my knowledge), is UnionFind

[c-cube]

On Mon, 27 Mar 2023, L1-42 wrote: I don't think Containers has a binary tree nor a graph module...

https://c-cube.github.io/ocaml-containers/dev/containers-data/CCGraph/index.html :-) As far as binary trees are concerned, I don't know what interesting operations you can provide on them. I've never used "just" a binary tree, and it's just simpler to define your own?

As for graphs, I am not familiar with ocamlgraph at all, but it still seems like only a few algorithms are implemented... A*, Kosaraju's algorithm, Prim and Kruskal algorithms, etc. are still missing... (Although having those algorithms would definitely be better in a Containers style library)

Tbh that sounds like a graph library, not a standard library :-). Who needs all that in most of their projects? They would make good contributions to ocamlgraph I suppose.

…

-- Simon Cruanes

[jhwoodyatt]

At the risk of being "that person" in the discussion, I'd like to say that the word standard in the phrase "standard library" is where the trouble begins. In my view, a standard is something promulgated by something with the power to mount a campaign. In the realm of technology, that usually means some kind of standards body or an organization that can function like one. Otherwise, what you have is not really a standard, but rather at best a convention, a best current practice, or perhaps merely a popular alternative.

The OCaml "standard" library is not really the standard, so much as it is the general purpose library distributed with the compiler, which is among several alternatives competing for recognition as a standard. The organization that might be in the best position to facilitate the promulgation of a proper standard is OCaml Software Foundation, but as near as I can tell from reading its web site, that's not in its charter. Perhaps that should be up for reconsideration?