Borrow-checking without type-checking

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.

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.

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, 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.

values

Every variable is an independent value. Mutating the value in one variable never affects the value in a different variable. 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.

references

References let us express the idea of a value that is stored in a different location to its parent value.

• Move (^): Gives a copy of the reference but destroys the original.
• Borrow (!): Creates a borrowed reference; when dropped, the value returns to its original location.
• Shared (&): Behaves like a borrowed reference, but the original owner keeps their copy. To maintain value semantics, mutation is disallowed through shared references.