Value Oriented Programming Needs Implicits?

[turbolent]

@matklad wrote a very interesting blog post about mutable value semantics: https://matklad.github.io/2023/05/02/implicits-for-mvs.html

I was wondering about the ergonomics around second-class references myself, so this is very timely.

What would an "idiomatic" implementation of a sort function in (a future version of) Val look like?

[dabrahams]

We think implicits might make some kinds of code more ergonomic, but I think "needs" is overstating the case. You can do value-oriented programming in Swift no problem, and there are no implicits. I'm out of time to write it out right now but an idiomatic implementation in Val would be similar to an idiomatic implementation in Swift, which is pretty straightforward. A Quicksort will be more elegant in Val than what Swift people will mostly recommend you do because mutating slices in Swift is inefficient (choose a pivot, partition on it, quicksort both partitions as slices, swap the pivot into place).

[kyouko-taiga]

@matklad, I think your statement adds unnecessary qualification to the approaches that get harder to express with MVS.

The "certain (type-class based) approaches to generic programming" that you mention aren't approaches suitable to MVS before even considering generic programming. If you want to use MVS, then you cannot store references to parts that confer access to their whole, even if you're writing programs that only manipulate Ints and arrays thereof.

So I think a more accurate statement should be "value semantics makes certain (type-class based) approaches harder", to which @dabrahams answered "which is no more than one should expect: all disciplines that have safety/local reasoning benefits create similar effects on the programming model".

Hope that clarifies a possible misunderstanding, or at the very least doesn't bring any more confusion.

[matklad]

Thanks @kyouko-taiga! This indeed seems like a specific misunderstanding which is consistent with the comments so far! Let me elaborate this angle then!

It is true that value semantics makes everything a bit more complicated as you don't have references. That's an "obvious point" which isn't mentioned in the post explicitly. For non-generic code, this is not a big deal: you just add a ctx: Context parameter to various concrete functions and that's it. It can get a bit tedious if you have different kinds of contexts or need nested lookups or both. Pulling this example from one value-oriented codebase of mine:

// Indexes:
store.names.lookup(store.fun[*callee].name)
// Direct references:
callee.name

But even in complex concrete cases, this all is fairly straightforward, you just add parameters to function declarations and fix call-sites.

For generic code, the situation is meaningfully more interesting. Even in simple generic cases, you can not "just" add a context parameter, because the generic signature is fixed upstream. You can work-around that by having two copies of generic API, one that works based on type-level traits, and one that takes value-level context, but having two copies of generic API means that the API is not actually maximally generic!

So, the two distinct difficulties arising from the forgoing of references are:

• you need to add context parameters to concrete functions (tedious, but straightforward)
• you need to add context parameters to generic functions (requires some imagination, as signatures are fixed)

[kyouko-taiga]

I think I understand what you mean.

I suppose higher-order functions can help tremendously here. sort(by:) is a good example that can be derived for many other generic algorithms:

let x = callees.first(where: fun(c) { store.fun[c].name == "abc" })
let y = callees.filter(where: fun(c) { store.fun[c].name == "abc" })
let z = callees.map(fun(c) { store.fun[c].name.count() })
...

You'll probably have multiple versions of these algorithms, but only for convenience. There's one maximally generic signature, which is the one that takes a lambda. That's because callees.contains(x) is sugar for callees.contains(where: fun(c) { c == x }), regardless of the type of callees's elements.

[kyouko-taiga]

The next challenge is mutation, because the maximally generic variant of some algorithms will also have to consider effects as parameters. We plan on using polymorphic effects to address this need, but this feature probably won't land before the first release of the language.

extension Collection {
  public fun for_each<E, a: access>(_ action: [E](a Element) -> Void) a { ... }
}

In this example, for_each(_:) is generic over the mutability of the elements that it passes to action. If the latter takes let parameters, for_each is instantiated as a let (i.e., non-mutating) method. If it takes inout parameters, then for_each is instantiated as a inout (i.e., mutating) method.

[matklad]

I suppose higher-order functions can help tremendously here. sort(by:) is a good example that can be derived for many other generic algorithms:

Exactly! And then you start imagining a by version for something like printing a Collection<Collection<IAmAnIndex>>, and end up writing an article about implicits :)

[muscar]

That's a great explanation @kyouko-taiga. The blog post had an interesting example with a name table with strings in it where the external API exposes int handles. The problem posed was to sort a vector of such handles but in the lexicographic order given by the elements they represent. How would that look in Val?

By the way, I find Val very interesting, great work :)

[kyouko-taiga]

That's a great explanation @kyouko-taiga.

Thanks.

The blog post had an interesting example with a name table with strings in it where the external API exposes int handles. The problem posed was to sort a vector of such handles but in the lexicographic order given by the elements they represent. How would that look in Val?

That's the situation I mentioned (was probably still editing when you answered; concurrency is hard). When an operation on a whole needs access to the contents of other data structures, APIs tend to get messier.

I think implicits are a very solid response to this problem. There are alternative approaches. The simplest is of course to use a lambda to sort the vector of handles:

let table: Array = ["durian", "apple", "mango"]

public fun main() {
  var s = name_table.indices()
  &s.sort(comparing_with: fun(a, b) { table[a].lexicographically_precedes(table[b]) })
}

Another approach would be to "bundle" a projection of the table together with each individual handle. That would be similar to iterator in C++, but guaranteed safe. Rust can do it out of the box if I'm not mistaken. It's a little trickier to express in Val because we can't store projections in containers (at least currently). You could use the unsafe API though:

extension Array {
  public type BundledIndex {
    let b: Pointer<Element>
    let i: Array.Index
    property element: Element { unsafe b.advanced_by(i).pointee }
  }
  public with_bundled_indices<T>(_ do action: (Array<BundledIndex>) -> T) -> T {
    unsafe with_buffer_pointer(fun(b) {
      action(self.indices.map(fun(i) { BundledIndex(b, i) ))
    })
  }
}

Note that since Array.BundledIndex is not Sinkable nor Copyable, it cannot escape the lambda we pass to Array.with_bundled_indices.

[turbolent]

Thank you for the great explanation and the illustrative examples 👍

[turbolent]

@kyouko-taiga

Note that since Array.BundledIndex is not Sinkable nor Copyable, it cannot escape the lambda we pass to Array.with_bundled_indices.

I looked at https://forums.swift.org/t/template-for-a-possible-future-object-model/59823#the-copyable-and-sinkable-traits-14 to understand Sinkable a bit more.

So is the call of action not a problem, because action is effectively let, so that is not considered a sink, but if the closure passed to action would then e.g. try to bind it (or return it?), that would be a sink and fail?

[kyouko-taiga]

Because Array<BundledIndex> is not Sinkable, action cannot return it or store it anywhere. Let's try to break those assumptions:

let table: Array = ["durian", "apple", "mango"]
public fun main() {
  // error: cannot return `x`; `Array<BundledIndex>` does not conform to `Sinkable`
  let esc0 = table.with_bundled_indices(fun(x) { x })

  // error: `Array<BundledIndex>` has no method `copy`
  let esc1 = table.with_bundled_indices(fun(x) { x.copy() })

  // error: cannot assign `esc2`; `Array<BundledIndex>` does not conform to `Sinkable`
  var esc2: Array<BundledIndex>
  table.with_bundled_indices(fun(x) { &esc2 = x })
}

Note: I've been recently thinking about the interaction between sink and Sinkable and came to the conclusion that "sinking" an argument might not necessarily mean to move it, which is what the trait Sinkable actually represent. Perhaps we should revisit our name choices.

[tjammer]

Since C++ iterators were mentioned:
There is a related discussion on how such things can be represented in Val https://github.com/val-lang/val-lang.github.io/discussions/44
At the end, implicit parameter (like Scala's implicits) are even mentioned as a possible solution.