Ad hoc polymorphism and usability

Having played a lot recently with Rust, which has Haskell-style typeclasses, I’ve rapidly come to the conclusion that ad hoc polymorphism really does make a significant difference in day to day usability of a programming language.

I recognize that the community is currently putting most of its effort into multicore, and that it’s hard to focus on more than one such (enormous) effort at a time, but when multicore is integrated and stable, I’d strongly suggest that modular implicits may be a really important target.

10 Likes

Not that I disagree but thinking on a larger scope can be enlightening :), Ease of use is somewhat subjective and not easily quantified.

How does ad hoc polymorphism such as found in rust and Haskell help? Are there other means to get there?

4 Likes

It helps by making it a lot easier to get your day to day work done. For example, in Rust, print debugging is trivial because if your type implements Debug (which it can always do if any of the things it uses implement Debug) you can just print the thing. You can kind of get this with OCaml with ppx_deriving_show but it’s a pain. This is generally the good bit: you can easily plug new types into existing infrastructure by implementing the interface expected.

modular implicits will do all this for OCaml without having to give up on the beauty of modules and functors.

4 Likes

There’s already ongoing work: Modular explicits by mrmr1993 · Pull Request #9187 · ocaml/ocaml · GitHub

I get the feeling this is the type of work that can’t exactly be rushed through by getting several people on it. It looks like there are still a lot of questions up in the air.

I’m aware. However, having more attention to that work from prominent members of the community may result in it getting earlier and better review etc., and the pull request you point to is only an early step.

OCaml 6.0 HYPE!!! =)

3 Likes

I do see the benefits of ad-hoc polymorphism, but I am a bit concerned that it’s one of those features that’s really nice if you’re writing it but hard for someone else to read the code after. Comparing Haskell to Ocaml, I find picking up an Ocaml codebase much easier.

10 Likes

There are reasons other than ad-hoc polymorphism that Haskell is harder to read. Haskellers tend to like defining operators, doing a lot of type-level computation, etc.

2 Likes

I agree those other reasons don’t help. But that does not mean ad-hoc polymorphism isn’t also a large contributor. It can be a challenge for me to determine what actual code is being executed when evaluating a piece of code. I similarly struggle with object oriented code.

3 Likes

Just to be clarify for other readers of this thread: in order to achieve the kind of usability that is found in Haskell and Rust, you need both mechanisms, type classes/modular implicits and “deriving”, simultaneously (and indeed both Haskell and Rust implement both mechanisms).

The reason is that “modular implicits” will never define new functions for you. It will just make it easier to figure out which existing function to use at a given type. In order to automatically define new functions for user-defined types you need a “deriving”-type mechanism as well.

Concretely: suppose a user-defined type t together with a function show_t : t -> string. Suppose there is also a function show_list : ('a -> string) -> 'a list -> string giving a way to “show” an 'a list given a way to “show” an 'a. Then in order to “show” a value x : t list list list, you need to use show_list (show_list (show_list show_t)) x.

  • Modular implicits will make it possible to simply write show x and the typechecker will figure out the precise combination of show_t and show_list that should be used.

  • “Deriving” will define the functions show_t and show_list for you.

If you only have modular implicits in your language, then you still need to define “show” functions for user-defined types (eg type t = A of int | B of bool, or record types, or …), which is where a big part of the boilerplate is actually found.

Personally I think that a built-in “deriving” mechanism that better integrates with the compiler is more of a missing killer feature than “modular implicits”. But as mentioned above you need both mechanisms to achieve the usability of Haskell/Rust.

Cheers,
Nicolas

14 Likes

Culling features even more, having upstream provide a good runtime type representation would already go a long way as far as usability is concerned.

(Also I slightly share @orbitz’s concern)

4 Likes

Indeed. That was, er, implicit in what I said, but I should have made it explicit. Without the deriving mechanism you still won’t get debugging prints “for free”. You need both. Of course things like debugging prints are not the only use for ad hoc polymorphism; it’s just plain convenient to have it, and one gets used to it just as one gets used to parametric polymorphism.

BTW, Rust is surprisingly interesting. The Rust type system is very nice; it is the first non-functional (though not dysfunctional) language I’ve used that has algebraic data types, pattern matching, parametric polymorphism, and a reasonable ad hoc polymorphism mechanism. It does not have inheritance, and the lack of it is not felt (or at least I have not felt it so far), which increases my conviction that it is usually an antipattern. Rust is not an elegant language, the syntax is clunky and it is not particularly ergonomic overall, but it does have some things to teach almost everyone, including its (unique, in a non-academic language) linear/affine type system.

OCaml probably wouldn’t want to steal very much from Rust (Rust stole many of its more interesting features from OCaml!) but it does have some interesting bits.

A few things I would note that are theft-worthy:

  1. it has an extremely powerful syntax extension mechanisms (in the form of its procedural macro feature) that are dead stable across compiler updates. PPX has proven to be a lot more painful than this because of the instability. Some important “deriving” mechanisms are well integrated into the compiler.
  2. The linear types allow for very high performance memory management, though it’s unclear to me given OCaml’s model if any of this could be stolen.
  3. As noted, I’m very impressed with the utility of the ad hoc polymorphism system, and I find I miss it when I’m dealing with OCaml. I miss having proper modules when working in Rust of course. Modular implicits should give the best of both worlds.
  4. The compiler’s error messages are fantastic. It will literally tell you things like “you accidentally typed || instead of | in this or pattern, fix it here” or “there’s no such function name as “goo” but “foo” seems to have a close name and the right function signature.” I had not realized how amazingly useful very user friendly error messages could be, and indeed, on the occassions when the Rust compiler gives a bad error message it’s shocking and one gets a bit irritable because one is used to so much better. OCaml now uses Menhir for parsing and probably could do a lot better simply by making use of Menhir’s excellent system for creating good error messages.
4 Likes

The way Go does this is pretty similar to the way OCaml does it right now with functors or first-class modules.

Indeed, I think inheritance is usually an anti-pattern because “simple, direct inheritance” appears very rarely is the real world. The most common relationship you get between two concepts is “inheritance mixed with something else”, or diverse kinds of multiple inheritance, and trying to force a static, simple kind of inheritance on those is a case of the cure being worse than the disease.

1 Like

This is one of the places where I think OCaml gets things mostly right in the way its object and class types work. In my experience, you rarely need to resort to using them, and your best option is usually to try to do without them. Use them only when equivalent logic that doesn’t use them is much more complicated.

The thing that is more common, which Rust does not offer and OCaml does offer, and offers it very well, is subtyping. The lack of subtyping in Rust is what we are usually thinking of when we observe that Rust doesn’t have inheritance.

OCaml also has a type system that does not assume subclasses are subtypes. Because, of course, they’re not— but OCaml is the rare language that actually makes the distinction cleanly.

Another problem for introducing ad-hoc polymorphism into OCaml is that implementing the coherence property isn’t compatible with functor module types. So that’s, of course, not a feature of the various proposals that have been put forth so far. I’m actually not sure I agree that the coherence property is desirable, but it’s offered by Rust and Haskell, so there’s a pretty sizable population of programmers who sort of expect it to be there, and OCaml is never going to have it. We don’t talk about that much in these discussions, and I think we should.

2 Likes

It’s even simpler than that, a golang interface is just a simple dictionary of closures. It’s similar to the solution given by @jobjo to the shape design problem. What I did in this thread, or what do RWO, with first-class modules is to make explicit the structure of these closures.

Look at the Golang example for their interface system (interface in golang). When you want to implement an interface for a given type, you just have to define a closure that captures a value of that type:

func (f MyFloat) Abs() float64 {
	if f < 0 {
		return float64(-f)
	}
	return float64(f)
}

in this case Abs is a closure that encapsulates a MyFloat named f. And the system will automatically instantiates the right dictionary when you convert a MyFloat to an Abser (this is the implicit part of modular implicits, that you also find with Haskell’s type classes or Rust’s traits).

They define their interface this way:

type Abser interface {
	Abs() float64
}

In OCaml, we will use this dictionary of closures:

type abser = { abs : unit -> float }

but, since this type will be populated with closures, its values will be be partial applications of closed functions of this following type (I just remove the unit to simplify):

type 'a abser_closed : { abs : 'a -> float }

And now, to complete the closure, we need a partial application and hence a value to apply the closed function. So the original abser type is near to this one:

type 'a abser_closure = 'a abser_closed * 'a

And since the type of the value encapsulated in the closure is unknown to the user, we need to wrap this in an existential:

type abser = Abser : 'a abser_closure

We could also have use first-class modules, since the parametric dictionary 'a abser_closed is equivalent to this one:

module type Abser = sig
  type t
  val abs : t -> float
end

type 'a abser_closed_with_module = (module Abser with type t = 'a)

The interest of first-class module is that we can divide the code in clear and separate compilation units, and then create easily a closures dictionary from them as illustrated in the chapter about first-class module in RWO.

By the way, that’s also how works ad hoc polymorphism in OOP : an object is just a dictionary of closures that shared the same environment (the instance variables).

Nevertheless, with simple closures, you will end up with problem as soon as you do not only consume your value but you also produce them, like in this interface:

module type Abser_extended = sig
  include Abser
  val double : t -> t
end

Here, you can still use the solution with first-class module and existential GADT. But, as soon as you want to add binary operator (for instance overloading the addition) you’re stuck with this solution and you need to rely on the highest solution for ad hoc polymorphism in OCaml: functor or first-class functor (but without existential GADT).

Geometrically, the solution with GADT can be seen with this cone:

the circular base of the cone represent all the types of the language that can implement the abser interface (each point is a type) and the top or apex A of the cone is precisely the type abser. You can see it as a directed graph where each edge (that goes from the base to the apex) is labelled with the dictionary (the first-class module) that shows how a type can be viewed as an abser. Now, when you want to use an asber value, you have to reverse the direction of the graph: the edges go from the apex to the circular base, and the purpose of such a value is to dispatch the right dictionary to the right type. I guess that the dispatching mechanism at the heart of some form of ad hoc polymorphism can be well seen with the shape of the cone.

To conclude, there is something that we don’t see with the cone: in the two previous examples (Abser and Abser_extended) the apex also belongs to the base circle (an abser value also satisfies the asber interface), but it’s not the case when we have binary operators and that’s why we need the full power of functors (the implicit part is just here to reduce boilerplate).

4 Likes

There’s a bit of a chicken and egg problem here. Method dispatch is known to be pretty slow in OCaml. I imagine that few people want the automatic performance penalty in many cases. As for myself, I would at least consider using them more often if the performance was more competitive with records and functions.

Yawar,

I don’t want to derail, but I thought it should be noted that Golang interfaces have massive problems, specifically with equality. At least, they did back in … 2016. Maybe it’s all been fixed. I would feel uncomfortable looking to those as any sort of positive example.

3 Likes

I tend to view this in reverse. The performance advantage of using functions and module functors with concrete record and tuple types and no subtyping or inheritance is a reason to prefer them over classes and objects. Use object types instead of records when you really need subtyping. Use class types instead of module types when you really need inheritance rather than mixins. That’s the lesson I think OCaml wants you to take, and I’m generally happy with the results of looking at it that way.

2 Likes

My experience programming with STL these days is that subtyping/inheritance is less necessary than in the past, and most of the time the reason I want it is for coding up discriminated unions. STL seems strong evidence that subtyping was mostly needed for building those core libraries.