Value Oriented Programming Needs Implicits?

An amateur note on language design which explores two important questions:

Lets start with the second question. What is the basic stuff that everything else is made of?

Not so long ago, the most popular answer to that question was objects blobs of mutable state with references to other blobs. This turned out to be problematic local mutation of an object might accidentally cause unwanted changes elsewhere. Defensive copying of collections at the API boundary was a common pattern.

Another answer to the question of basic stuff is immutable values, as exemplified by functional programming. This fixes the ability to reason about programs locally at the cost of developer ergonomics and expressiveness. A lot of code is naturally formulated in terms of lets mutate this little thing, and functionally threading the update through all the layers is tiresome.

The C answer is that everything is made of memory (*). It is almost as if memory is an array of bytes. Almost, but not quite to write portable programs amenable to optimization, certain restrictions must be placed on the ways memory is accessed and manipulated, hence (*). These restrictions not being checked by the compiler (and not even visible in the source code) create a fertile ground for subtle bugs.

Rust takes this basic C model and:

Curiously, this approach allows rust to have an immutable values feel, without requiring the user to thread updates manually, In Rust, Ordinary Vectors are Values. But the cognitive cost for this approach is pretty high, as the universe of values is now forked by different flavors of owning/referencing.

Lets go back to the pure FP model. Can we just locally fix it? Lets take a look at an example:

let xs1 = get_items() in
let xs2  = modify_items(xs1) in
let xs3 = sort_items(xs2) in

It is pretty clear that we can allow mutation of local variables via a simple rewrite, as that wont compromise local reasoning:

var xs = get_items()
xs = modify_items(xs)
xs = sort_items(xs)

Similarly, we can introduce a rewrite rule for the ubiquitous x = f(x) pattern, such that the code looks like this:

var xs = get_items()

Does this actually work? Yes, it does, as popularized by Swift and distilled in its pure form by Val.

Formalizing the rewriting reasoning, we introduce second-class references, which can only appear in function arguments (inout parameters), but, eg, cant be stored as fields. With these restrictions, borrow checking becomes fairly simple at each function call it suffices to check that no two inout arguments overlap.

Now, lets switch gears and explore the second question polymorphism.

Starting again with OOP, you can use subtyping with its familiar class Dog extends Triangle, but that is not very flexible. In particular, expressing something like sorting a list of items with pure subtyping is not too natural. What works better is parametric polymorphism, where you add type parameters to your data structures:

fn sort<T>(items: &mut Vec<T>)

Except that it doesnt quite work as, as we also need to specify how to sort the Ts. One approach here would be to introduce some sort of type-of-types, to group types with similar traits into a class:

fn sort<T: Comparable>(items: &mut Vec<T>)

A somewhat simpler approach is to just explicitly pass in a comparison function:

fn sort<T>(
    compare: fn(T, T) -> bool,
    items: &mut Vec<T>,

How does this relate to value oriented programming? It happens that, when programming with values, a very common pattern is to use indexes to express relationships. For example, to model parent-child relations (or arbitrary graphs), the following setup works:

type Tree = Vec<Node>;
struct Node {
    parent: usize,
    children: Vec<usize>,

Using direct references hits language limitations:

struct Node {
    parent: Node, // Who owns that?
    children: Vec<Node>,

Another good use-case is interning, where you have something like this:

struct NameTable {
    strings: Vec<String>,

struct Name(u32);

How do we sort a Vec<Name>? We cant use the type class approach here, as knowing the type of Name isnt enough to sort names lexicographically, an instance of NameTable is also required to fetch the actual string data. The approach with just passing in comparison function works, as it can close over the correct NameTable in scope.

The problem with just pass a function is that it gets tedious quickly. Rather than xs.print() you now need to say xs.print(Int::print). Luckily, similarly to how the compiler infers the type parameter T by default, we can allow limited inference of value parameters, which should remove most of the boilerplate. So, something which looks like names.print() would desugar to Vec::print_vec(self.name_table.print, names).

This could also synergize well with compile-time evaluation. If (as is the common case), the value of the implicit function table is known at compile time, no table needs to be passed in at runtime (and we dont have to repeatedly evaluate the table itself). We can even compile-time partially evaluate things within the compilation unit, and use runtime parameters at the module boundaries, just like Swift does.

And thats basically it! TL;DR: value oriented programming / mutable value semantics is an interesting everything is X approach to get the benefits of functional purity without giving up on mutable hash tables. This style of programming doesnt 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. A potential fix for that is to base generic programming on explicit dictionary passing combined with implicit value parameter inference.

Is there a language like this already?