Return-Position Borrows in Felt

Felt Context

Feel free to skip this section if you’ve been following my little PL project.

I’ve been working on a programming language called “Felt”^[1] for the past couple years. I last wrote about it during my batch at the Recurse Center, and that blog post remains a good overview of the general vibe of the project.

One of my goals with Felt is to create a simple programming language that enforces “shared XOR mutable”. That is, at no point in a valid program can there be a shared reference and a mutable reference to the same value, at the same time. I think that “shared XOR mutable” is a hugely beneficial innovation in Rust^[2], and has broad benefits beyond maximum-performance systems programming.

Sort of as a proof of that theory, I’ve set out to make a simple, imperative, high-level language that gives similar guarantees around aliasing. I’m pretty serious about keeping things simple—partially because I have to implement whatever I design. This whole project is for fun, so designing something super complex means I have to implement something super complex… No thanks.

Plus, I feel like there might be a niche for a PL shaped like Go, but designed with niceties like sum types.

Basics of Borrowing in Felt

If you’re familiar with Rust, you can mentally replace Felt’s ref keyword with & and its unique keyword with &mut and skip this section.

Felt’s references are pointers that encode whether they are shared (copyable and immutable) or unique (non-copyable and mutable). They also must always point to a valid object, which may not be changed, destroyed, or moved while there are any active references. The latter obviously has some memory safety benefits, but it’s the former that is more interesting to me. It eliminates a class of annoying, spooky-action-at-a-distance bugs like iterator invalidation^[3], concurrent race conditions, and unknown writers clobbering data in deeply-nested function calls.

Taking a reference (or “borrowing”) looks like this:

let x = 5;
do_something_immutable(ref x);
do_something_mutable(unique x);

And produces types with names like unique i32 and ref i32.

Borrow Limitations

My original design for borrowed references to values was very constrained: borrows exist only in the syntactical scope where they’re created. There’s no way to assign a borrowed value to a new name. That way the entire problem of borrow-lifetime-checking is essentially avoided: it’s impossible to define a borrow that lives longer than the thing it’s borrowing, because references may only ever have a narrower scope than what they are borrowing. I implemented this borrow checker, wrote a couple tests, and saw that it worked. Life is good.

let x = list[1, 2, 3];
{
    borrow y = unique x;
    // y can't possible outlive x - it's stuck inside this scope
    // its value can't be re-assigned to other borrows, and it
    // cannot change its value.
}

Life is good… unless you want to return a reference to something. At first I said to myself “bleh, you just can’t return references! Write your program a different way.” This lets you get pretty far. I wrote a tiny game as a demo at RC, pretty much entirely in Felt! At that point my language design seemed validated.

Then I decided I wanted to write a collection in Felt. It’s a pretty simple one, that I tend to implement each time I write a game: a spatial map of tiles for a game world. It’s indexed by world-space coordinates and returns the tile at that location, backed by a one-dimensional array. Nice and efficient. I wrote it in Felt:

union Tile {
    Empty,
    Block,
}

struct Tilemap: Resource {
    tiles: list[Tile],
    width: i32,
    height: i32,
    tile_size: i32,

    fn index(ref self, x: f32, y: f32): i32 {
        let tile_x = math.truncate(x) / self.tile_size;
        let tile_y = math.truncate(y) / self.tile_size;
        return tile_x * self.height + tile_y;
    }

    fn at(ref self, x: f32, y: f32): Tile {
        let tile_x = math.truncate(x) / self.tile_size;
        let tile_y = math.truncate(y) / self.tile_size;

        if x < 0.0 or y < 0.0 or tile_x >= self.width or tile_y >= self.height {
            Tile.Block
        } else {
            self.tiles[tile_x * self.height + tile_y]
        }
    }

    fn free(ref self, x: f32, y: f32): bool {
        case self.at(x, y) {
            Empty => true,
            Block => false,
        }
    }
}

Then I thought “it would be nice to take a mutable reference to a Tile, so I can both get the value and set it without having to round-trip through the Tilemap.” Ah, crap. That requires the ability to return references. Maybe it’s not sustainable to have the collections in the language hard-coded in the compiler after all.

Returning References from Functions

I sat on the problem for the next two and a half months. A couple times I doodled ideas on the back of a bill or hopefully-unimportant tax document. Various solutions came to mind with various issues, including “implement full Rust-style borrow checking” (which I know I don’t want to do) or “give up” (which I also don’t really wanna do).

The solution ended up requiring 20% of the effort to get 80% of what I want, which is sort of the Felt project’s motto. You are now permitted to return a reference from a function—as long as it only borrows from the function’s parameters. References returned from a function are assumed to be constrained by the lifetime of the shortest-lived parameter.

We know all parameters must outlive the current function (because their lifetime originates in the caller). There’s still no way to return a reference that borrows a local value, because those values will go out of scope when the function returns. Without any kind of annotation syntax to pick which parameters constrain the lifetime of the return value, we’re forced to assume they all do. Whichever argument has the shortest lifetime will determine the lifetime of the returned value.

This is now legal:

fn ref_max(x: ref i32, y: ref i32): ref i32 {
    if *x > *y {
        x
    } else {
        y
    }
}
let a = 10;
let b = 20;
borrow c = ref_max(ref a, ref b);
*c

because the lifetime of ref_max’s return value is constrained to be the lifetime of its parameters (in this case, a and b).

but unfortunately this is not:

fn lookup(dict: ref Dictionary, key: ref Key): ref Value {
    /* ... implementation ... */
}
fn mutate(key: unique Key) {
    /* ... implementation ... */
}
fn examine_value(value: ref Value) {
    /* ... implementation ... */
}

let dict = Dictionary.create();
let key = Key.create();
borrow value = lookup(ref dict, ref key);
mutate(unique key);     // mutably borrowing key invalidates
                        // all prior references,
                        // including `value`

examine_value(value);   // this is now a compile error

value’s lifetime is the the intersection of dict and key. The immutable borrow of key must end on the next line, when key is mutably borrowed. Because a value can never be mutable and immutably borrowed at the same time, the previous immutable borrow to key is invalidated at this point which transitively invalidates value. Thus attempting to use value on the next line is a compiler error.

The latter case isn’t a hard limitation; I could introduce something like Rust’s lifetime annotations to solve it. It’s definitely overly strict. In the above example, it’s almost certainly safe to mutate value while observing key, but we can’t express that to the compiler. Maybe I’ll change that at some point, but for now I’m happy with my “barely good enough” solution.

The Next Problem: Optional References

At some point, I know I’m going to want to express “this function takes either a reference or some null-value” or “this function returns a reference or an error” or something similar. Right now… you super can’t do that. There are two reasons:

1. Nullability is a language-level construct that has sorta jank semantics. I’m planning to replace it with Felt’s union mechanism, but I don’t have type parameters yet. (Look out out for that later this year, I hope).
2. Including a reference inside another type is expressly forbidden (to make borrow checking easier).

Even if I introduce some kind of limited lifetime annotation syntax to make that dictionary lookup example work well, it won’t solve problem #2. Currently I don’t know how I’ll solve this. Maybe type parameters will help? That’s the next thing on the docket either way, so maybe look out for a blog post on basic type parameters in a few months.nths.

Thanks to Max Bernstein and Nate Lane for quick feedback on a draft of this post.