This is a demo of a toy language with dynamic typing, inline values, stack allocation, interior pointers, single ownership, and a limited form of borrowing – less expressive than rust, but much more expressive than second-class references (eg we can express external iterators).
Since there is no static typing the borrows must be checked dynamically. The interesting part of the demo is that we can do that fairly cheaply and with useful error messages.
The code is here.
background
I’m exploring a style of type-system exemplified by julia and zig. Both languages start with a dynamic type system, enforced by dynamic type-checks, and then layer on a static type system which is capable of proving that the dynamic type-checks are unnecessary. The dynamic type system provides flexibility and easy meta-programming, while the static type system removes the overhead in most of your code.
Julia and zig differ slightly in how they handle code that cannot be statically type-checked. Zig will refuse to compile the code at all, while julia will leave some dynamic type-checks and will run the static type-checks again when more type information is available.
For zest I’m exploring a third option – code can either be dynamically typed (and interpreted), or statically typed (and compiled), but switching between the two requires explicit annotations. The goal is that most of your code can have the assurances of static typing, but you can still opt in to dynamically-typed glue code to handle repls, live code reloading, compile-time metaprogramming, runtime code generation, malleable software etc.
The tricky part is that I also want to enforce mutable value semantics. To date there are two main strategies for doing this:
- Reference-counting and copy-on-write, which imposes an unpleasant performance overhead and is hard to combine with interior pointers / explicit stack allocation.
- Static type systems, which won’t help me with my dynamically-typed language.
So I have to do something new. This is what I’ve come up with:
- The overhead of borrow-checking is limited to some reference-counting operations when creating/dropping/copying references.
- The reference counts themselves are always stored on the stack so the cache impact is low.
- Reference counts are never shared between threads, so we don’t have to use atomic operations to update them.
- The reference counting overhead is only paid in dynamically-typed function frames. Reference counts are never allocated on the heap and statically-typed code never has to see them.
- Whenever a borrow-checking rule is violated, the runtime immediately throws an error which identifies the exact value that is at fault.
And as a bonus, I’m at least 60% certain that this scheme is actually sound 🙂
repl
First a quick note: If you see a green tick below then all the examples are interactive. You can edit the code and hit the eval button to see the result. If you see a red cross instead then probably you have javascript turned off or I didn’t test on your browser, and you’ll have to make do with the offline result at the end of the code box.
✗
values
Our toy language is pretty minimal. We have integers, tuples, functions, and some basic control flow.
let nums = [1, 5];
let inc = fn (i) {i + 1};
while {nums[0] < nums[1]} {
nums[0] = inc(nums[0]);
};
nums
[5, 5]
Every variable is an independent value. Mutating the value in one variable never affects the value in a different variable.
let a = [1, [2, 3]];
// `b` is an independent copy of `a`
let b = a;
b[1][0] = 42;
// `a` is unchanged
[a, b]
[[1, [2, 3]], [1, [42, 3]]]
At the end of each block ({}), for every variable defined in that block we drop the associated value, freeing any memory used by that value.
let a = [1, [2, 3]];
{
let b = [4, 5];
let c = 6;
// c is dropped here
// b is dropped here
};
// a is dropped here
[]
This approach to combining value semantics with mutation is simple and easy to implement.
But it’s also useless. Creating a full copy of every value on every use is infeasible when we want to work with bigger values. We need a way to express sharing between values without breaking value semantics.
references
References let us express the idea of a value that is stored in a different location to its parent value.
One way to make a reference is the box function which stores its contents on the heap. In the example below, the value [2, 3] is stored on the heap and the value [1, box(...)] is stored on the stack.
[1, box([2, 3])]
[1, box([2, 3])]
The dereference operator * is used to reach inside a reference to access its contents.
let a = [1, box([2, 3])];
a[1]*[0]
2
So what should the code below do?
let a = [1, box([2, 3])];
let b = a; // What does this mean?
b*[0] = 42;
a
We could copy the contents of the box, but that’s not a solution that scales to arbitrarily large data-structures. We could end up copying gigabytes of memory!
Or we could just copy the pointer itself and share the heap allocation between a and b. But then the assignment to b*[0] will be visible in a, breaking the illusion of value semantics.
What we actually do, unless you add more explicit annotations, is to just refuse to copy boxes at all.
let a = [1, box([2, 3])];
let b = a[1];
b*[0] = 42;
b*
Error at 2:9
Can't copy an owned reference
To work with references we have to be more specific about what we mean. We have a few options.
The first option is to move the value using ^. This gives us a copy of the reference but destroys the original!
let a = [1, box([2, 3])];
let b = a[1]^;
b*[0] = 42;
b*
[42, 3]
We leave those XXX in the diagram to show that the original reference has been destroyed and nothing has replaced it yet. What exactly the XXX means is a question we’ll leave for later. (We could just pick some zero value that is valid for all types, but that feels like a mistake).
Destroyed values can be overwritten with new values.
let a = [1, box([2, 3])];
let b = a[1]^;
a = [4, box([5, 6])];
a[1]*
[5, 6]
This gives us a (clunky) way to pass references to functions without copying them. We can move the original value, mutate it within the function body, return the mutated value, and assign it back to the original variable.
let inc_first = fn (x) {
x*[0] = {x*[0] + 1};
x^
};
let a = [1, box([2, 3])];
let [a0, a1] = a^;
a = [a0^, inc_first(a1^)];
a^
[1, box([3, 3])]
To make this process less tedious, we provide a second option – we can create a borrowed reference using !. This is just like moving the value into a new box(...), except that when the new reference is dropped we return the value to its original location. (When you borrow things, you’re supposed to give them back!)
let inc_first = fn (x) {
x*[0] = {x*[0] + 1};
// `x` is dropped here and the mutated contents are moved back to `a`
};
let a = [1, box([2, 3])];
inc_first(a[1]*!);
a^
[1, box([3, 3])]
The third and final option is creating a shared reference using &. This behaves like a borrowed reference, but the original owner gets to keep their copy – it isn’t destroyed.
let a = [1, box([2, 3])];
let b = a[1]*&;
[a[1]*, b*]
[[2, 3], [2, 3]]
To maintain the illusion of separate values, we can’t allow you to mutate either copy.
let a = [1, [2, 3]];
let b = a[1]&;
b*[0] = 7;
Error at 3:1
Can't assign through a shared reference
let a = [1, [2, 3]];
let b = a[1]&;
a[1][0] = 7;
Error at 3:1
Can't assign to `a` because it is shared by `b`
closures
Closures are supported, but don’t implicitly capture variables from their scope. So the example below doesn’t work.
let iter_copy = fn (tuple_ref) {
let index = 0;
fn () {
if index < len(tuple_ref*) {
let elem = tuple_ref*[index];
index = {index + 1};
elem
} else {
[]
}
}
};
let a = [1,2];
let next = iter_copy(a&);
[next(), next(), next()]
Error at 4:8
Can't refer to `index` here because it is defined outside this function - try using an explicit capture instead.
(We could support rust-style implicit captures just fine, but explicit captures make it much easier to explain the interaction with borrow-checking.)
Let’s think first about how we could write this example without closures. We can return a tuple with all the essential state, and then call a separate next function on that tuple.
let iter_copy = fn (tuple_ref) {
let index = 0;
[index, tuple_ref]
};
let next = fn (state_ref) {
let [index, tuple_ref] = state_ref^;
if index* < len(tuple_ref**) {
let elem = tuple_ref**[index*];
index* = {index* + 1};
elem
} else {
[]
}
};
let a = [1,2];
let state = iter_copy(a&);
[next(state!), next(state!), next(state!)]
[1, 2, []]
Closures are just syntax sugar for this pattern. We specify what state we want to capture in the closure (index, tuple_ref) and what kind of access we want to that state (!). Then the compiler desugars it to the example above.
let iter_copy = fn (tuple_ref) {
let index = 0;
fn [index, tuple_ref]! () {
if index* < len(tuple_ref**) {
let elem = tuple_ref**[index*];
index* = {index* + 1};
elem
} else {
[]
}
}
};
let a = [1,2];
let next = iter_copy(a&);
[next!(), next!(), next!()]
[1, 2, []]
safety
Under the hood, borrowed and shared references are implemented as pointers to the original value. Those XXXs don’t actually exist in the implementation.
The goal of borrow-checking is to try to have our cake and eat it – we want to provide the simplicity of value semantics while keeping the performance of reference semantics, and never let you get into a situation where you could tell the difference.
Ensuring that moving, borrowing, and sharing don’t break the illusion is surprisingly easy to do with a static type system, and surprisingly hard to do with a dynamic type system, or at least hard to do cheaply. This is the best I’ve managed so far and it’s still quite restrictive compared to rust.
Maybe the easiest way to explain how it works is to first list all the things that it prevents you from doing, and then talk about the implementation afterwards.
The biggest restriction is that owned references (boxes) are not allowed to point to borrowed/shared references. This ensures that borrowed/shared references only live on the stack, which makes many of the other rules easier to enforce dynamically.
let a = 1;
let b = box(a&);
Error at 2:9
Can't box a shared ref
let a = box(box(1));
let b = 2;
a* = b&;
Error at 3:1
Can't assign a value of type `number&` to a location of type `box(number)`
While a borrowed reference points to a value, no more borrowed/shared references to that value can be created.
let a = 1;
let b = a!;
let c = a!;
Error at 3:9
Can't borrow `a` because it is borrowed by `b`
The runtime does track when borrowed references are dropped though.
let a = 1;
{
let b = a!;
// `b` is dropped at the end of this scope
};
let c = a!; // now we can borrow `a` again
[]
let a = 1;
let b = a!;
b^; // `b` is moved here and then dropped
let c = a!; // now we can borrow `a` again
[]
We can create multiple borrowed references to parts of a value by destructuring a borrowed reference.
let a = [1,2];
let [b, c] = a!;
b* = 42;
c* = 101;
b^; c^; // drop `b` and `c`
a
[42, 101]
While a shared reference points to a value, only shared references to that value can be created.
let a = 1;
let b = a&;
let c = a&; // this is allowed, have as many shared references as you want
let d = a!; // this is not allowed, because writing to `d` would also change `b` and `c`
Error at 4:9
Can't borrow `a` because it is shared by `c`
let a = 1;
let b = a&;
let c = a&;
b^; c^; // once we drop all the shared references we can borrow again
let d = a!;
[]
Values can’t be moved out of variables while any borrowed/shared references exist, even if the moved and borrowed/shared parts don’t overlap.
let a = [1,2];
let b = a[0]&;
a[1]^
Error at 3:1
Can't move out of `a` because it is shared by `b`
Once a value has been moved, even partially, it can’t be used at all until the entire value is replaced.
let a = [1,2];
a[0]^;
a[1]
Error at 3:1
Can't refer to `a` because it has been moved
let a = [1,2];
a[0]^;
a[0] = 3; // replacing just the moved part is not enough
Error at 3:1
Can't refer to `a` because it has been moved
let a = [1,2];
a[0]^;
a = [3, 4]; // replacing the entire value works
a
[3, 4]
Variables can only hold borrowed/shared references pointing to variables with longer lifetimes.
let a = 1;
let b = 2;
let c = a&; // this is ok, `a` will be dropped later than `c`
c = b&; // also ok, `b` will be dropped later than `c`
let d = 3;
c = d&; // uh oh, `d` will be dropped before `c`
Error at 6:1
This value can't be owned by `c` because it shares from `d`, which will be destroyed before `c`
Values returned from a block may not contain borrowed/shared references pointing to variables defined in that block.
let a = {
let b = 1;
b&
};
Error at 1:9
This value shares from `b`, but `b` will be destroyed at the end of this block
Although the language is dynamically typed, variables can’t change type once assigned (because their allocation can’t change size).
let a = [1]; // 8 bytes allocated on the stack
a = [1, 2]; // can't change the allocation to 16 bytes
Error at 2:1
Can't assign a value of type `[number, number]` to a location of type `[number]`
Even references can’t change type, although their size would be the same. This lets us avoid having to store type tags for each allocation, because we can always derive the type of a value from the type of the reference pointing to it.
let a = box([1]);
a = box([1, 2]);
a*
Error at 2:1
Can't assign a value of type `box([number, number])` to a location of type `box([number])`
However, like julia, we can opt in to storing type tags just in the places where we want dynamism. The any function takes a reference and returns a dynamically-typed version of that reference.
let a = box([1]); // 8 byte value with type box([number])
let b = any(a^); // 16 byte value with type box(any)
b = any(box([1, 2]));
b*
[1, 2]
We still can’t change the type of the allocation itself though.
let a = any(box([1]));
a* = [1, 2];
a*
Error at 2:1
Can't assign a value of type `[number, number]` to a location of type `[number]`
expressiveness
After all that talk about what we can’t do, let’s look at what we can do that we wouldn’t have been able to do with only second-class references.
References can be placed inside tuples. In a non-toy language, that would mean we could use types like Option<&mut T>.
let a = 1;
let b = 2;
let c = [a!, b!];
c[0]* = 3;
c[1]* = 4;
c^;
[a, b]
[3, 4]
References can be returned from functions. In a non-toy language, that would mean we could use function types like fn(&[T], usize) -> Option<&T>.
let get = fn (tuple, index) {
tuple*[index]&
};
let a = [1, 2, 3];
get(a&, 1)*
2
Even borrowed references can be returned from functions, although there is some subtlety. The example below doesn’t work.
let get = fn (tuple, index) {
tuple*[index]!
};
let a = [1, 2, 3];
get(a!, 1)* = 5;
a
Error at 5:1
This value borrows from `tuple`, but `tuple` will be destroyed at the end of this block
The reason is that tuple*[index]! is borrowed from tuple and will be returned to tuple at the end of its lifetime, so it can’t outlive tuple. If you want to produce a reference that outlives tuple, you have to explicitly consume tuple by using a move.
let get = fn (tuple, index) {
tuple^*[index]!
};
let a = [1, 2, 3];
get(a!, 1)* = 5;
a
[1, 5, 3]
In this comment Alex gives an example that is impossible to handle with second-class references – iterating over a linked list in a loop. We can handle this too. It is a bit clunky because our toy language doesn’t have sum types, but that’s just a lack of implementation effort, not a limitation of the borrow-checker.
let list = any(box([]));
list = any(box([0, list^]));
list = any(box([1, list^]));
list = any(box([2, list^]));
{
let next = list!;
let null = any(box([]));
while {next != null!} {
next**[0] = {next**[0] + 1};
next = next^**[1]!;
};
};
list^
any(box([3, any(box([2, any(box([1, any(box([]))]))]))]))
We already saw a copying iterator in the closures section, but we can also make iterators that return shared or borrowed references.
let iter_borrowed = fn (tuple_ref) {
let index = 0;
fn [index^, tuple_ref^]! () {
if index* < len(tuple_ref**) {
let elem = tuple_ref^**[index*]!;
index* = {index* + 1};
elem^
} else {
[]
}
}
};
let a = [1,2];
{
let next = iter_borrowed(a!);
next!()* = 3;
next!()* = 4;
};
a
[3, 4]
This even correctly assigns the lifetimes of the returned references – the shared version shares from the underlying tuple, while the borrowed version borrows from the iterator itself and so doesn’t allow returning multiple borrowed references at the same time.
let iter_shared = fn (tuple_ref) {
let index = 0;
fn [index^, tuple_ref^]! () {
if index* < len(tuple_ref**) {
let elem = tuple_ref^**[index*]&;
index* = {index* + 1};
elem^
} else {
[]
}
}
};
let a = [1,2];
let next = iter_shared(a&);
let a0 = next!();
let a1 = next!();
[a0*, a1*]
[1, 2]
let iter_borrowed = fn (tuple_ref) {
let index = 0;
fn [index^, tuple_ref^]! () {
if index* < len(tuple_ref**) {
let elem = tuple_ref^**[index*]!;
index* = {index* + 1};
elem^
} else {
[]
}
}
};
let a = [1,2];
let next = iter_borrowed(a!);
let a0 = next!();
let a1 = next!();
[a0*, a1*]
Error at 16:10
Can't borrow `next` because it is borrowed by `a0`
implementation
To enforce these rules we need to store some extra data.
For each variable, we store a ref-count which can be in one of 4 states:
- If
ref_count == INT_MINthen some part of the value in this variable has been moved. - If
INT_MIN < ref_count < 0then this counts the number of references which borrow from this value. - If
ref_count == 0then this variable is available to be borrowed/shared. - If
0 < ref_countthen this counts the number of references which share from this value.
The neat thing is that each safety check only requires a single integer comparison:
const Count = std.math.IntFittingRange(-stack_size, stack_size);
const available = 0;
const moved = std.math.minInt(Count);
fn isMoved(ref_count: RefCount) bool {
return ref_count.count == moved;
}
fn canMove(ref_count: *RefCount) bool {
return ref_count.count == available;
}
fn canBorrow(ref_count: *RefCount) bool {
return ref_count.count == available;
}
fn canShare(ref_count: *RefCount) bool {
return ref_count.count >= available;
}
For each borrowed/shared reference we store:
lease: whether this reference is an owned, borrowed, or shared reference.lender: the variable from which this value was borrowed/shared, and whose reference count we need to decrement when dropping this reference.owner: the variable to which this value originally belonged, and whose lifetime dictates which values are safe to write to this reference.
We can address an 8mb stack with 8-byte alignment using only 20 bits, so all of the above fits into 42 bits per reference. This does mean that each borrowed/shared reference is now 16 bytes in total, but in the crossing stacks section below I’ll show that statically-typed code doesn’t have to pay this overhead.
The only case in which lender and owner differ is when reborrowing from an existing borrow:
let a = 1;
let b = a&;
let c = 2;
let d = b!; // owner: b, lender: b
let e = d*!; // owner: b, lender: d
e* = c&; // this isn't safe because `c` doesn't live as long as the owner `b`
Error at 6:1
This value can't be owned by `b` because it shares from `c`, which will be destroyed before `b`
Both b and d are borrowed from and should not be accessed while e lives. To enforce this, when creating b! we increment the borrow count on b, and when creating d*! we increment the borrow count on d.
The result is that b can’t be accessed while d lives, and d can’t be accessed while e lives. We create a kind of chain of custody of the underlying value so that at any point in time there is at most one reference that can mutate the value.
But the underlying value is still owned by b, which means it is not safe to write e* = c& because c will be dropped before b. So when we safety-check assignment we have to look at the owner of the location, not the lender. That’s why we need to track both the owner and the lender for every reference.
The downside of this scheme is that we can’t return a reference past the lifetime of its lender.
let a = 1;
{
let b = a!; // owner: a, lender: a
let c = b*!; // owner: a, lender: b
c^ // can't return this reference because its lender `b` is about to be dropped
}* = 2;
a
Error at 2:1
This value borrows from `b`, but `b` will be destroyed at the end of this block
We want to return c from this block, but c has lender b and b will be dropped at the end of the block.
The way to make this work is to move b. When evaluating the l-value b^* we notice that b was consumed and is no longer accessible, so we don’t need to record it as the lender.
let a = 1;
{
let b = a!; // owner: a, lender: a
let c = b^*!; // owner: a, lender: a
c^
}* = 2;
a
2
If you scroll back up to the iter_borrowed example in the previous section, you’ll notice this pattern in tuple_ref^**[index*]!. Without the ^, the iterator can’t return that borrowed reference because its lender would be tuple_ref.
error messages
Most of the error messages are pretty easy to produce from the data we already track. For example:
let a = 1;
a&
Error at 1:1
This value shares from `a`, but `a` will be destroyed at the end of this block
The expression a& produces a reference which records a as the lender, so we know exactly who to blame.
There is one kind of error which requires more work though.
let a = 1;
let b = [1, 2, [a!, 3]];
a!
Error at 3:1
Can't borrow `a` because it is borrowed by `b[2][0]`
We know that it’s not safe to borrow a again because the borrow count is already set to 1. But that doesn’t tell us where the borrowed reference is.
We do know that all borrowed/shared references must be on the stack somewhere, and that any reference which borrows a must be on the stack below a. We also know that we’re definitely about to panic, so we can afford to burn some cpu cycles on producing a better error message by scanning the stack to find the reference which is borrowing from a.
fn findLendee(lender: StackIndex, lease: Lease) struct { *StackItem, RefIndex } {
var i = c.stack.len;
while (i > 0) : (i -= 1) {
const item = &c.stack.items[i - 1];
if (item.value.findLendee(lender, lease)) |ref_index|
return .{ item, ref_index };
}
panic("Couldn't find lendee for {}", .{.{ .lender = lender, .lease = lease }});
}
fn findLendee(value: Value, lender: StackIndex, lease: Lease) ?RefIndex {
for (value.type_id.getRefIndexes()) |ref_index| {
const ref = value.getRefAtIndex(ref_index);
if (ref.type_id.getType().ref.lease == lease and
ref.getRefProvenance().lender == lender)
return ref_index;
}
return null;
}
A key function here is getRefIndexes which, for a given type id, returns a pre-computed list of the locations of all the references contained in that type. This saves us from having to recursively drill down through the types. It’s a little like the gc bitmaps used in some garbage collected languages.
crossing stacks
When spawning a new thread, we want to be sure that it doesn’t share refcounts with any other threads. When calling from dynamically-typed code into statically-typed code (or vice versa), we want to be sure that the statically-typed code doesn’t use any references in ways that would break the reference counting in the dynamically-typed code. In both cases the safety requirements are similar.
I haven’t actually implemented threads or static typing, but I have encapsulated the safety requirements in the with_new_stack function, which copies a closure onto a new stack, calls it, and then copies the result back.
let a = 0;
let b = 1;
let c = with_new_stack(fn [a!, b^] () {
a* = 2;
b + 2
});
[a, c]
[2, 3]
The captures may contain borrowed/shared references. After copying these references to the new stack we change the provenance to point to dummy lenders on the new stack so that the function call never has to touch refcounts on the old stack.
We only decrement the refcounts of the original lenders when the function returns (which for threads implies some sort of structured concurrency).
We can’t do this reborrowing recursively, so the targets of those borrowed/shared references must not themselves contain borrowed/shared references.
let a = 0;
let b = a&;
with_new_stack(fn [b] () { b* }); // This is ok - we capture a& - one layer of sharing.
with_new_stack(fn [b&] () { b** }); // This is not ok - we capture a&& - two layers of sharing.
Error at 4:1
The closure passed to `with_new_stack` contains a shared reference to a shared reference.
The result of the function call must not contain any borrowed/shared references.
let a = 0;
with_new_stack(fn [a&] () { a* }); // This is ok - returns 0.
with_new_stack(fn [a&] () { a }); // This is not ok - returns 0&.
Error at 3:1
Can't return a shared reference from `with_new_stack`.
In the case of spawning a thread this last restriction is too strong – we could allow returning borrowed/shared references so long as they live long enough. But for statically-typed code we might not precisely know the owner/lender of the resulting references, so we can’t update the ref-counts correctly when returning to dynamically-typed code.
The function must expect to be called by move, not by borrowed/shared reference.
let a = 0;
with_new_stack(fn [a]! () {})
Error at 2:1
The closure passed to `with_new_stack` should expect to be called by move, not by borrow
Together these restrictions allow safely calling across different stacks, or across partitions on a single stack. They prevent threads from sharing refcounts, and prevent statically-typed code from ever seeing refcounts or provenance at all.
thoughts
On the way to this scheme I tried many, many different schemes with different tradeoffs between cost, expressiveness, and explainability.
The most interesting system that I sketched out and abandoned used invisicap-style shadow allocations for each value to track which elements are borrowed/shared.
This allowed creating multiple borrows against a single value, so long as they are disjoint.
let a = [1,2];
let b = a[0]!;
let c = a[1]!; // This would be safe, because we can check dynamically that a[1] hasn't been borrowed.
It also allowed partial moves.
let a = [1,2];
a[0]^;
a[0] = 2; // This overwrites the value that was moved out, so now `a` would be safe again.
a
It also removed the need to pin values when some child reference has been borrowed, because only the borrowed part itself needs to be changed when the borrow is dropped.
let a = [box(1), box(2)];
let b = a[0]*!;
let c = a^; // This would be safe, because the location that `b` points at doesn't move.
The major problem was that I couldn’t figure out a way to safely transition into statically-typed code. If you can move a value that is currently borrowed from, the only way to be sure that you aren’t passing such a value into statically typed code is to scan the entire value to check if any part of it has been moved.
Error messages were also much worse, because when a safety rule was violated we often had no reasonable way to track down the offender without a full heap scan.
There is a lot of punctuation in these examples. I think much of it could be removed by adding dynamic equivalents to rust’s deref coercion. For example, a**[0] could just be a[0] if the [] operator dereferenced the lhs until it found a tuple. Similarly a** = b could just be a = b if the = operator dereferenced the lhs until it found something that matched the type of the rhs.
If you played with the repl you might have run into this error:
let f = fn () { [2, 3] };
let a = [1, f()!, 4];
Error at 2:13
For annoying stack management reasons, arbitrary expressions are only allowed inside path expressions if they are immediately followed by a dereference operator
The problem is that we have a strict LIFO stack, where every expression is expected to consume its arguments and leave only its result value on the stack. But in f()! the value [2, 3] needs to be allocated somewhere on the stack before being borrowed. In a statically-typed language we could check the size of that value and allocate stack space for it in advance, but that’s not an option in a dynamically-typed language.
The only case that’s easy to handle is when the expression returns a reference and we immediately dereference it.
let get = fn (t, i) { t^*[i]! };
let a = [1, 2, 3];
get(a!, 1)* = 42;
a
[1, 42, 3]
This works out because we can pop the reference from the stack and produce an l-value pointing to its contents.
It might be possible to solve the general problem by having two stacks – one for values that are the results of expressions, and one for values that should live until the end of the current block. Then when we want to allocate a value and immediately borrow it, we can pop it from the first stack and push it to the second.
But there is one advantage to the current setup – it’s currently only possible to share/borrow from named values. This makes it much easier to produce readable error messages. If we allowed f()! we’d have to produce error messages that said things like:
Can't borrow from the stack location produced by the expression at 2:13 because it is already borrowed by the expression at 3:17
The main reason for confining borrowed/shared references to the stack is so that in the assignment a = b we can check the lifetime of b by scanning its stack value, rather than its entire heap value.
But as a bonus, this means that pointers to the stack can only occur on the stack, and we can identify them precisely, which means we can easily grow/shrink the stack.
We have enough unused space in provenance to allow 32-bit stack indexes, which would allow each stack to grow up to 4gb if needed.
It really bugs me that moving a value gives you a value of the same type, but borrowing/sharing a value gives you a reference. But it’s really hard to avoid. I’ve tried:
- Make borrowed/shared references totally second-class, so they can never appear in tuples and their size/type can’t be directly observed.
- Make variables immutable and un-addressable. Only allow mutation through explicitly created
box(...)(like ocaml).
Neither feel particularly ergonomic when I work through examples.
The problem is closely tied to the existence of interior pointers. If you look back in the history of the repo, I made a language with universal layout where there is no need for l-values and dropped values are represented as null pointers. This felt very ergonomic and also easy to explain, but using universal layout limits the potential performance.
Compared to rust, it feels limiting that we have to explicitly drop values to end their lifetime.
let a = 1;
let b = a!;
b^; // If we don't drop `b` here then we can't access `a` below.
a
1
This is fixable though!
It’s not quite as simple as dropping variables after their last direct use, because references to the value could still exist.
let a = 1;
let b = a!;
// No further usages of `a` after this point, but `a` will be used indirectly through `b`.
b* = 2;
// Now it's safe to drop `a`.
[]
Instead, we could mark variables as ‘droppable’ after their last direct use, and then only actually drop them when their ref-count hits zero. This would give a more rust-like feel to the language.
The reason I haven’t done this is that there are cases where this would make the dynamically typed version of a function drop values earlier than the statically typed version, because the static analyis has to approximately track ref-counts that the dynamic version knows precisely.
let a = 1;
let b = 2;
let c = if {a == b} { a! } else { b! };
// The dynamically-typed version knows that `c` only borrows from `b` so it can drop `a` here,
// but the statically-typed version thinks that `c` might borrow from `a` or `b`.
c* = 3;
// The statically-typed version can't know until here that `a` is unreachable.
[]
I’ve been sticking to the principle that static typing only rules out errors and never changes semantics. Dropping later feels a little like changing the semantics, even if it’s not currently directly observable.
I’m really solving two problems at once:
- Support (a limited form of) references while preserving the illusion of value semantics.
- Support interior pointers and (explicit) stack allocation while preserving memory safety.
There is a lot of related work that solves problem 1 or problem 2, but only a few systems that solve both problems at the same time.
Rust solves both, at the cost of a surprising amount of type system complexity. Hylo, mojo, and lately swift also try to solve both while trading off more restricted use of references for a simpler type system.
Hylo is particularly interesting because their references are entirely second-class, which considerably simplifies the mental model, but they’re able to recapture some of the expressiveness of first-class references by allowing interleaved coroutines:
fun f(x: Array<Int>, y: inout Array<Array<String>>) {
// x1 coroutine starts
let x1 = x[1]
// y1 coroutine starts
inout y1 = &y[1]
y1[x1] = "Hello World"
// x1 coroutine ends
print(y1)
// y1 coroutine ends
}
I’m still tempted by this, but it’s a little more restrictive than what I have here (eg no Option<&T>), the codegen seems gnarly, and if coroutines are allowed to perform side-effects then it can be tricky for the reader to figure out when those side-effects happen. Also I can get a similarly simple mental model in my current system by not allowing borrowed/shared refs to appear inside other values.
It’s worth noting that rust does also have a dynamic model in the form of tree borrows, which is used in miri for testing code that uses unsafe escape hatches from the type system. But tree borrows are far too expensive to use as an actual programming model – every read or write to any reference requires checking every other aliased reference in case it must be invalidated.
C# refs and oxcaml modes only aim at solving problem 2, but do so in a way that is easy to extend to problem 1. Both require static typing, but my ref-counting system is very roughly a dynamic version of c# refs and has similar expressiveness.
Cheriot and fil-c solve problem 2 without static typing (albeit by requiring garbage collection). I sketched out a fil-c inspired system that also solves problem 1, as mentioned above, but I couldn’t find a reasonable way to transition between dynamically- and statically-typed code.
R and (a subset of) swift solve problem 1 by using reference counting and copy-on-write. Reference-counting imposes a fairly steep overhead (eg these benchmarks find that just switching from atomic to non-atomic ref-counts can double the performance of some swift programs), and copy-on-write creates the possibility of accidentally and invisibly creating copies of arbitrarily large values. It’s also tricky to combine reference-counting with interior-pointers, and allowing interior pointers to escape is a common source of leaks in eg go. Finally, stack allocation is still only possible via best-effort escape analysis. None of this is compatible with my goal of predictable performance.
Gel/inko is an interesting tweak on the reference-counting formula. Rather than freeing values when the ref-count hits zero, they free values at the end of their scope (like rust or this demo) and throw an error if the ref-count is not zero. This doesn’t solve either of my problems, but did inspire my implementation.
next
I’m not quite sure what’s next. Everything here works, but in usage it feels… fiddly. It’s possible that first-class borrowing works in rust because the type system allows the compiler to fill in a lot of the details (eg autoborrow, deref coercion) and catch the remaining mistakes.
One option would be to move more in the hylo-direction with second-class references and coroutines, if I can figure out how to make that work in a dynamically-typed, interpreted setting.
Another option would be to statically type everything (so that I don’t need dynamic borrow-checking) but focus on the ergonomics of working with values of unknown types in statically-typed code. I can see how zig-like comptime can still work even if the comptime language is also statically-typed, but I can’t guess how much it will hurt the ergonomics of meta-programming.
Anyway, if you want to see more of this language then there is this handy sponsor button you could press. Think of it like your taxes contributing to someone’s phd stipend, but a little more directly 🙂
