Statement about value oriented programming seems incorrect

[dabrahams]

This style of programming doesn’t work with cyclic data structures (values are always trees), so indexes are often used to express auxiliary relations. This, however, gets in a way of type-based generic programming — a T is no longer Comparable, only T + Context is.

I think you're conflating a bunch of things with this statement. The use of indices for extrinsic relations is unrelated to the feasibility of type-based generic programming, IMO. We have plenty of Ts that are Comparable in value-based programming. The issue you're pointing at is that you can't store a reference to additional data inside your T, but if you have many Ts you probably don't want to do that anyhow. If you really, really want to you can store a reference to data that's immutable while you're sorting (the name table) along with T inside your U then sort Us. The classic (Stepanov) generic programming approach to these things is to have a parameterless sort function for Comparable Ts and another sort function that takes a comparison function as a parameter. You want this anyway, because even simple types shouldn't always be sorted the same way (sort your integers in descending order for example).

[matklad]

I think my statement is fairly precise. With MVS, you use indexes more often. If you indexes, then your T is not Comparable without context, and that does get in way of generic programming, as you now forced to provide two flavors of APIs:

A bounded-quantification based one:

fn transmogrify<T: Frobnicatable>(t: T)

And a universal-quantification based one:

fn transmogrify_by<T>(frobnicate: fn (T), t: T)

This is fairly standard for sort, but usually is not done for things like hash or to_string. Indeed, doing this throughout the API means that you essentially have two separate parallel infrastructures for generic programming. Luckily, the _by versions are more general, and can be delegated to. But then the question arises why not to keep only the more general version?

Does it quantitatively matter? Not sure! For me anecdotally, "printing index-based stuff" is a fairly common point of friction.

Does it qualitatively exist? Yes, absolutely! value semantics makes generic programming easier, because everything is a value, but it also makes certain (type-class based) approaches to generic programming harder, because values more often can't reach elsewhere without runtime context, and there's no direct support for threading runtime context through type classes.

Is it fixable in theory? Probably! This feels very similar to what the "modular implicits" paper says in 3.8:

In Haskell, which lacks both local instances and a way of explicitly instantiating type class dictionary arguments, neither option is available, and programmers are advised to define library functions in pairs, with one function (such as sort) that uses type classes to instantiate arguments automatically, and one function (such as sortBy) that accepts a regular argument in place of a dictionary:

sort :: Ord a = > [ a ] -> [ a ] 
sortBy :: ( a -> a -> Ordering ) -> [ a ] -> [ a ]

And it does feel like module-based approach solves this.

Is it worth fixing? Damned if I know! My general feelings towards non-trivial parametric polymorphism are close to https://github.com/fsharp/fslang-suggestions/issues/243#issuecomment-916079347. But at the same time, I like printing things generically, even if things are indices...

[dabrahams]

If you use indices (or rather, don’t use references) and you were previously willing to pay the space cost of storing a reference in T to mutable context needed for comparisons, then that T that would have been Comparable without (separate access to) context, is not Comparable without separate access to context. Perhaps it wasn't your intention, but your phrasing in the blog post and here makes it sound like you are claiming that no Ts are Comparable in a world using indices, which is definitely not the case.

You may mean something special by “generic programming,” but the discipline I know by that name is not harmed by the existence of algorithms parameterized by functions that tune details of the algorithm's behavior. Indeed, the need for such algorithms is fundamental to the practice. You can always wrap a type in something that provides a particular hashing behavior, and in Val you can even use “scoped conformances” to have a type conform to Hashable differently in different regions of code, but driving all behaviors via types is simply not always appropriate. I may need an ascending sort of integers in one branch of an if and a descending sort in another.

As for why you don't see this kind of parameterization for hashing in practice, I think there are several reasons: first, the two operations of hashing and equality have interdependent semantics and need to be customized together, which would complicate the relevant APIs, second, the stability of hash functions is almost invariably tied to the integrity of important data structures, and last, the use cases for it are simply rare enough that wrapping a type is not burdensome. The discipline I know as generic programming is always driven by real use-cases. And that probably accounts for the reasons that I do not have the experience of needing "two separate parallel infrastructures for generic programming" even though I've been practicing generic programming since around 1996.

You are right that the API for sorting that uses Comparable is dispensable. The only reason to have it is that it considerably simplifies and improves the readability of many common use-cases. Different generic library authors can reasonably make different choices about that.

For me anecdotally, "printing index-based stuff" is a fairly common point of friction

My experience is that, indices or not, one often wants to choose among several string representations for a thing (the one for debugging, the one for end-user consumption, the one that summarizes long arrays with “...”, the one that deduplicates large repeated values), and that demands threading some context because printing a thing always involves printing its parts.

Indices or not, there are sometimes reasons not to store references to context in your objects (e.g. if you have a large collection of them you waste storage, and if you want to use two different contexts on that collection you waste time updating the references). Implicits can potentially make some of this context-threading nicer, for sure. That's not an argument you really lay out in the blog post though; we have to infer it—implicits are barely mentioned. There's a class of applications where all the context you need can appropriately be stored by reference, and the context threading issue goes away, sure, but it's not the case in general. This also has nothing to do with generic programming as far as I can tell.

[matklad]

but your phrasing in the blog post and here makes it sound like you are claiming that no Ts are Comparable in a world using indices, which is definitely not the case.

It could be read that way, yeah! The "this = using indexes to express cyclic relations" is load bearing, but is easy to miss!

You can always wrap a type in something that provides a particular hashing behavior.

I believe this is not true. Newtype wrapping works in the common case where the behavior depends only on a compile-time type, but there are cases (particularly around using indexes), where the hashing behavior depends on a certain runtime value. A good example here is an interner puzzle. Here's how you can implement an interner using a sorted vec as a lookup data structure. This works because sorted vec provides a _by version of the API:

#[derive(Clone, Copy)]
struct InternedString {
    index: usize,
}

struct Interner {
    vec: Vec<String>,
    set: Vec<InternedString>,
}

impl Interner {
    fn lookup(&self, i: InternedString) -> &String {
        &self.vec[i.index]
    }

    fn intern(&mut self, s: String) -> InternedString {
        match self.set.binary_search_by(|i| self.vec[i.index].cmp(&s)) {
            Ok(insertion_point) => self.set[insertion_point],
            Err(insertion_point) => {
                let i = InternedString {
                    index: self.vec.len(),
                };
                self.vec.push(s);
                self.set.insert(insertion_point, i);
                i
            }
        }
    }
}

If we replace sorted vec with a hash set, which doesn't have a closure-taking API, we find ourselves unable to write the correct Hash+Eq impl:

#[derive(Clone, Copy)]
struct InternedString {
    index: usize,
}

struct Interner {
    vec: Vec<String>,
    set: HashSet<InternedString>,
}

impl Interner {
    fn lookup(&self, i: InternedString) -> &String {
        &self.vec[i.index]
    }

    fn intern(&mut self, s: String) -> InternedString {
        match self.set.entry(/* can't write corretc impl Hash */) {
            OccupiedEntry(entry) => *entry.get(),
            VacantEntry(entry) => {
                let i = InternedString {
                    index: self.vec.len(),
                };
                *entry.insert(i)
            }
        }
    }
}

[matklad]

You may mean something special by “generic programming,” but the discipline I know by that name is not harmed by the existence of algorithms parameterized by functions that tune details of the algorithm's behavior.

I think another load bearing word got missing here. I am talking specifically about type-based generic programming, where genericness comes from properties of a compile-time type (so, Haskell type classes or C++ ADL). It is contrasted with value based generic programming, where customization is achieved by passing in runtime values.

[dabrahams]

"this = using indexes to express cyclic relations" is load bearing, but is easy to miss!

I didn't miss it. I read your statement as, “in a world where indices are used to express cyclic relations, no Ts are Comparable.” If your intention is to say that “Ts using indices that way are not Comparable” (which is only true for some such Ts), and you want people to understand you, I suggest you rephrase.

You can always wrap a type in something that provides a particular hashing behavior.

I believe this is not true. Newtype wrapping works in the common case where the behavior depends only on a compile-time type, but there are cases (particularly around using indexes), where the hashing behavior depends on a certain runtime value.

It is true. You can embed the "certain runtime value” (or a reference to the immutable value, or a CoW'd reference to the value) in the wrapper.

But though the statement is true, I acknowledge it may not be appropriate for many use cases, including the interning case. It has costs that not everyone wants to pay.

I am talking specifically about type-based generic programming

OK, but as a practical matter nobody tries to do generic algorithm/data structure customization and adaptation exclusively with types and no lambdas/closures. The world needs both anyway, that's my point, so pushing a few cases into the category of needing values doesn't change the nature of generic library construction.

I don't know what point you're making with the interning example (there are lots of ways to build such a thing exclusively with value semantics; I can build an interner with a hash-based dictionary) and no "by" method—but it seems to prove my point that exclusively type-based generic programming is insufficient in the real world, e.g. if you want to use a sorted vector.

[matklad]

You can embed the "certain runtime value” (or a reference to the immutable value, or a CoW'd reference to the value) in the wrapper.

My understanding is that it's not always possible. In particular, it's not possible in the above interner example, because you'll need to close over mutable value, and that runs into borrow checker / mutable value semantics. This is different from languages with C++/Java semantics of unrestricted aliasing, where indeed such wrappers work.

It's interesting that even closures don't automatically fix this. Eg, in C++, it's customary to parametrise hashing behavior by supplying a collection-specific hashing function at construction time. But this doesn't work for this example if you forbig aliasing, because the closure would have to close over mutable data. One needs to supply closures at the point where collection is used, not at the point where it is constructed.