Removing polymorphic compare from Core


#1

OCaml’s polymorphic comparison operators are a useful but highly problematic feature of the language. I wrote a blog post about this some years ago, and the basic gist of it is: OCaml’s polymorphic comparison functions are lightweight and convenient, but have occasionally crazy semantics which make them error prone. To add insult to injury, the performance is also not great.

For this reason, we decided that we wanted to remove polymorphic comparison from the namespaced exposed by Base from the very beginning. As a result, once you open Base, you’ll discover that operators like = only work on integers, and that you’ll need to use type-specific comparison functions when dealing with other types. You can do this manually, i.e.:

open Base

let  b = List.equal Int.equal [1;2;3] [4;5;6]

Or you can do it using a syntax extension:

let b = [%compare.equal: int list] [1;2;3] [4;5;6]

Note that polymorphic comparison is still available, and can brought back in scope by opening Base.Poly.

I’m writing this email because we are planning on doing the same thing to Core and Core_kernel, to make them consistent with Base. Given that this is a serious breaking change, we wanted to give some advance warning and get some feedback.

Note that this is a relatively easy change to adopt. Internally, we’re going to mechanically replace open Core with open Core open Core.Poly, and similarly with Core_kernel. It’s a fairly simple textual change, so it’s not clear that an upgrade tool is worthwhile, but that is something worth discussing.

Anyway, feedback on all of this is welcome.

y


The Base Module and Polymorphic Functions
#2

I’m sure that fundamental design choices about JS stdlib replacement are good as already discussed (no exceptions and Options/return type, tail recursion, optimized computation, additional useful functions that one should not reinvent).
This improves OCaml natural safety.

Another good thing would be to accomplish the following architecture and documentation decisions:

  • definitively get rid of ALL “unsafe” OCaml legacy, making impossible to use them (e.g. polymorphic compare);
    so no more chance to trap newcomers with cryptic mechanisms and no more need to discuss about that

  • use only ONE library called Core (Base and Core and even Kernel have more or less the same meaning, i.e. something fundamental we can build on) ;
    so open Core should and must be enough to start working with Core (with no silent shadowing mechanisms)

  • put all possibly very advanced stuff in a so-called Core.Advanced or Core.Extended sub module (not experimental stuff but industrial stuff that solves very particular problems and that also requires some time to learn)

  • stabilize the Core module signature to offer a reference to all users.

  • offer a migration tool for users of the stdlib (Stdlib function -> Core function)

  • improve the documentation with a “minimum number of clicks” access and with 2 levels of information when on, say, the Core.List module :
    1/ a category if necessary
    2/ the signature and a clear example
    Option: some very short additional information such as useful pointers to reference papers or blog posts.
    With a single Core module architecture, the documentation should automatically simplify without any references to Base/Core_kernel//Core_hyper_kernel/Core_Giga.
    And please NO more expand/collapse widgets with hyperlinks to other main sub/upper modules with useless unsafe functions or slightly different functions.
    This should be calm and straightforward (as when reading OCaml refman in pdf: there are some signatures, some examples and your brain to understand).

These are some minimum ingredients for getting a real industrial-strength OCaml library.


#3

This seems like a topic for another thread. (or maybe several other threads!) I’d like to focus this thread on the particular topic of the deprecation of polymorphic comparison from Core and Core_kernel.

y


#4

Deprecate ASAP!
:joy:

Putting it in Core.Poly is a kind of pre-deprecation.

Don’t you think it’s enough to make it disappear?


#5

Yet more reason to feel like Modular Implicits would be a wonderful thing if they were finished someday…


#6

Yet more reason to feel like Modular Implicits would be a wonderful thing if they were finished someday…

Wishing for a better time is legitimate but likely not productive to answer short term decisions.

Regarding core, i think it makes sense even if i like polymorphic compare more than average devs those days for two reasons :

  • both base and containers have monomorphic operators by default, so consitency is indeed a good argument.
  • 4.07 prefixed stdlib makes it less costly to override stuffs. If someone is really against this change it’s easy to reimport everything back
module IReallyWantPolymorphism = struct 
  open Stdlib.Pervasives
  let (=) = (=)
  let (<>) = (<>)
  let compare = compare
  let (>=) = (>=)
end

open IReallyWantPolymorphism

#7

I’m hoping we can come up with some better way to solve this problem.

There must be a better middle-ground between cannot use = for anything except ints and overcomplicated and exception prone polymorphic compare.

When really needing polymorphic compare, I think it’s good being able to get back the behaviour by using open Poly.

But it would be much much better if users could use the comparison operators with variables/lists/arrays/tuples of primitive types.

If hacking the OCaml compiler would be an option, how realistic would it be to fix this problem?

The error message is also not very user-friendly:

utop # "foo" = "foo";;
Error: This expression has type string but an expression was expected of type
         int

For inspiration on how string comparison is solved in other languages:

https://rosettacode.org/wiki/String_comparison

Haskell:

> "abc" == "abc"
True
> "abc" /= "abc"
False

Rust:

let a: &str = "abc";
let b: String = "Bac".to_owned();
if a == b { println!("The strings are equal") }
if a != b { println!("The strings are not equal") }

F#:

if a =  b then printfn "%s is equal to %s" a b

#8

There is no easy fix. This is a major part of OCaml’s basic architecture, that is, there is no type-based dispatch for data, which is essential for polymorphic comparison to be safe. You would need to design a whole new part of the language to allow this to work. When F# essentially forked OCaml, this is one of the things they added.

Personally, given the fact that modular implicits is so far away, I wouldn’t mind having an interim solution created for basic type-based dispatch. But it is by no means an easy task.


#9

Seriously: if we want a fully safe OCaml (or more and more safe OCaml), what is the problem with really getting rid of polymorphic functions that “have occasionally crazy semantics which make them error prone (…) and which performance is also not great.”?
Putting it in some Poly submodule is somehow hiding the problem.

Why don’t you fully clean up Core by putting out all the “more or less unsafe stuff”?

The Base module is a place for them (where “unsafe” labels would be even more explicit).
This would contribute to focus on a safe Core module (only one, easy to grasp; no Core_kernel or whatever).


#10

Re: Base/Core_kernel/Core: our plan is over time to get down to just two: Base and Core, with both being portable, and Base remaining focused on being very lightweight.

I don’t really see your point about Poly. Putting it in a sub-module does effectively hide it, so that people don’t stumble upon it unless they explicitly want to include it in their code. It seems like an adequate solution to me, especially in a world where occasionally, the lack of polymorphic compare can be highly inconvenient.

Polymorphic compare may eventually be removed fully from the language, but only after modular implicits lands, I would guess.

y


#11

Regarding the proposal: I’m strongly in favor. Polymorphic compare is one of the few corners where OCaml’s type system can really let you down. And this actually happens in practice. I just recently ran into a bug caused by polymorphic compare in ocamlgraph. This is one of the most popular packages on opam! So you can see that this is a real issue. In that instance I got lucky and OCaml threw a runtime exception. Alas, you don’t always get that lucky, and then things can be extremely tough to debug.

Regarding polymorphic compare more generally:
Rejecting programs that use = on expression that are not guaranteed to be of suitable base type, as suggested by @joelj, does seem doable. One could imagine a “-safe-compare” flag that enables this stricter behavior. It seems like this shouldn’t be hard to implement as an additional pass on the typed AST. Maybe someone with deeper knowledge of the compiler, like @gasche, could comment on this?


#12

Yes, this shouldn’t be too hard. A few things to watch for:

  • Abstract types can make it impossible to know from the typedtree whether a type is comparable. We have a syntax to declare through an abstraction boundary that a type is “immediate” (represented by an integer), but not the corresponding “comparable” or “eqtype” restriction. Either you extend the signature language, or you have to reject certain programs.

  • (=) or compare can be passed as argument to a function expecting an instance (List.sort compare : string list -> string list), so you have to check the instantiation sites of polymorphic operators, rather than just application sites.

  • Polymorphic comparison operators can be rebound, in a module or across module boundaries. In theory you should just warn on any operator at the type forall 'a. 'a -> 'a -> {int,bool}, they are either silly or non-parametric. In practice I’m not sure that rebinding polymorphic comparisons (rather than specialized instances) is a common practice.

Looking at how [@@immediate] is computed/checked/used in the compiler codebase could be a good entry point to get an idea of how to do this.


#13

Sounds good it shouldn’t be too hard.
I had a look at the @@immediate code, but my OCaml skills are not good enough yet to take on the challenge.

Seems like Bucklescript has solved this already. Maybe the native OCaml compiler could take inspiration from it:


#14

As a Core user I am also in favor of removing polymorphic compare from Core. For once, I would like for Core to be a proper superset of Base, so it is easier to move code “down” to Base where I don’t need the full set of things provided by Core without being confronted by a death by a thousand cuts of small, insignificant differences. This would make it easier to separate parts of our code out into smaller and more portable libraries. Currently we try to use Core_kernel, but the wins are not as big.

I don’t see much purpose of the Poly modules except for uhm, compatibility with existing code without having to update it (and I am not sure this is a sustainable way). If I wanted to use polymorphic compare, I could just as well use Caml.(=), thus getting the existing semantics.


#15

Core.Poly. means that it’s polymorphic whereas the point is to explicitly mark it as unsafe (and put it out of the safe place that Core should/must be)
Pls. think also about a newcomer facing that Core.Poly submodule : he shouldn’t be exposed to this risk (today, he is already exposed to the silent behaviour or to weird error messages from the Base/Core_kernel/Core layers (and other libs), to the discovery of opam, OCaml editing tools… which all make first contact with OCaml not very soft).

Base.Unsafe.Poly. or Base.Poly. or whatever could be a fine place.
In fact, Caml.(=) is probably the simplest solution as suggested by @Leonidas.

The experience evoked by @smolkaj and @Leonidas are very valuable.

I believe that Core should/must be totally safe, which means “no hidden unsafe stuff in Core” (hidding is not removing).


#16

In Core parlance, we use “unsafe” to mean “memory unsafe”, which polymorphic compare is not. So the naming convention “Base.Unsafe.Poly” is confusing, I think.

Following @Leonidas’s observation, I think the primary purpose of Poly is to ease migration, with a secondary one being for people who are using OCaml in a quick-and-dirty context where polymorphic compare is a better tradeoff. I think those are both legitimate uses, but the first (easing migration) seems like an absolute necessity.

y


#17

Thanks for the precision. Yes, Caml.(=) is the simplest solution.
Regarding safety, how do you qualify a “OCaml runtime exception” such as the one described by @smolkaj?
I understand that it’s an internal “migration” of the polymorphic compare within Core. Correct?
Do you intend to let people capable of doing some quick-and-dirty code with Core? (I already told how important I believe it is to get a "fully safe" industrial grade Core).


#18

Thanks for all the great info in this thread. I hope it’s okay to ask a few newbie questions that I have arising from this thread:

  • Really newbie one: I’ve noticed using utop that available are Stdlib.= and Stdlib.Pervasives.= . Both are the same apparently, so why are they both in there? Is one just a reexport of the other?

  • Is there a way to turn off the (seemingly) automatic import of Stdlib and/or Stdlib.Pervasives? In Haskell, for example, I normally set the option -XNoImplicitPrelude, which of course doesn’t guarantee that any library I use won’t make use of these unsafe functions, but at least it prevents me from making that problem worse.

Thanks :slight_smile:


#19

There is the compiler option -nopervasives, which ought to do the same thing. (I have not tested it.)


#20

It’s a result of the following change from OCaml 4.07:

GPR#1010: pack all standard library modules into a single module Stdlib which is the default opened module ( Stdlib itself includes Pervasives ) to free up the global namespace for other standard libraries, while still allowing any OCaml standard library module to be referred to as Stdlib.Module). This is implemented efficiently using module aliases (prefixing all modules with Stdlib__ , e.g. Stdlib__string ). (Jérémie Dimino, David Allsopp and Florian Angeletti, review by David Allsopp and Gabriel Radanne)