Borrow-Checking Without Type-Checking

In the landscape of programming language design, a fascinating tension exists between the flexibility of dynamic typing and the safety guarantees of static systems. Rust has demonstrated how sophisticated compile-time borrow-checking can enable memory-safe reference manipulation, but at the cost of significant type system complexity. What if we could achieve similar safety guarantees in a dynamically-typed language? This article examines an innovative approach that implements borrow-checking through runtime reference counting, creating a system that balances flexibility with safety.

The Challenge: Value Semantics with Performance

The author begins by exploring a style of type system exemplified by Julia and Zig—languages that start with dynamic typing and layer on static type systems capable of proving that dynamic checks are unnecessary. For their experimental language called "Zest," they propose a third option: code can be either dynamically typed (interpreted) or statically typed (compiled), with explicit annotations switching between the two modes.

The core challenge is enforcing mutable value semantics without traditional approaches:

• Reference-counting and copy-on-write impose performance overhead
• Static type systems don't work in dynamically-typed contexts
• Interior pointers and explicit stack allocation complicate memory management

The solution involves a novel reference-counting scheme where the overhead is limited to operations when creating, dropping, or copying references. Crucially, reference counts are stored on the stack rather than the heap, minimizing cache impact. The system ensures reference counts are never shared between threads, avoiding atomic operations, and this mechanism only applies to dynamically-typed function frames.

Reference Types in a Dynamic World

The language introduces three distinct reference types:

1. Owned references (boxes) - Created with the ^ operator, these give exclusive ownership of a value. When moved, the original reference is destroyed.

2. Borrowed references - Created with the ! operator, these provide temporary access to a value that must be returned to its original location when dropped.

3. Shared references - Created with the & operator, these allow multiple read-only views of a value without destroying the original.

Each reference type enforces different safety rules. For example, while a borrowed reference points to a value, no additional borrowed or shared references to that value can be created. Once a value has been moved, even partially, it cannot be used until entirely replaced. These rules are enforced dynamically through the reference counting system.

Implementation Details: Tracking Provenance

The cleverness of this system lies in how it tracks reference provenance with minimal overhead. For each variable, a reference count tracks one of four states:

• INT_MIN: Some part of the value has been moved
• Negative: Number of references borrowing from this value
• 0: Available to be borrowed/shared
• Positive: Number of references sharing from this value

Each borrowed/shared reference stores metadata including:

• Lease type (owned, borrowed, or shared)
• Lender variable (where the value was borrowed from)
• Owner variable (which originally owned the value)

This dual tracking of lender and owner enables precise lifetime management. When creating a borrowed reference from an existing borrow, the system creates a chain of custody ensuring that at any point, at most one reference can mutate the value.

Error Messages and Debugging

One of the system's strengths is its ability to provide precise error messages. When borrow-checking rules are violated, the runtime identifies the exact value at fault. For complex cases where a reference is borrowing from a variable buried in the stack, the system can scan the stack to locate the offender.

The author notes a deliberate design choice: confining borrowed/shared references to the stack. This restriction enables readable error messages (referencing named variables rather than ephemeral stack locations) and simplifies lifetime checking during assignment operations.

Expressiveness Beyond Second-Class References

Despite being more restrictive than Rust, this system demonstrates greater expressiveness than second-class reference systems. Key capabilities include:

1. References in tuples: Supporting types like Option<&mut T>
2. Returning references from functions: Enabling types like fn(&[T], usize) -> Option<&T>
3. Complex iterators: Implementing both copying and non-copying iterators
4. Linked list traversal: Solving problems impossible with second-class references

The system demonstrates particularly elegant iterator implementations that return shared or borrowed references with proper lifetime management.

Crossing Stacks: Safe Interoperability

A critical challenge is ensuring safety when crossing between different execution contexts—whether spawning threads or transitioning between dynamically-typed and statically-typed code. The with_new_stack function encapsulates these safety requirements:

• Copies closures to new stacks with modified provenance
• Prevents sharing reference counts between threads
• Ensures statically-typed code never sees reference counts
• Restricts what can be returned across stack boundaries

These restrictions prevent dangerous sharing while enabling interoperability between different execution contexts.

Trade-offs and Design Decisions

The author candidly discusses the trade-offs of their approach:

1. Verbosity: The explicit reference annotations (^, !, &) make code more verbose than systems with implicit borrowing.

2. Performance: While reference counting overhead is minimized, it still exists in dynamically-typed contexts.

3. Restrictions: The system is less expressive than Rust, particularly around reborrowing and lifetimes.

Several design decisions reflect careful consideration of these trade-offs:

• Variables can't change type after assignment (preserving stack layout)
• References can't be created from arbitrary expressions (simplifying stack management)
• Moving a value requires explicit destruction before reuse

Comparison with Related Work

This approach stands in interesting contrast to several existing systems:

• Rust: Solves similar problems with static typing at the cost of complexity
• Hylo/ Mojo/Swift: Similar goals with more restricted reference usage
• C# refs/OCaml: Solve only the interior pointer problem with static typing
• R/Swift: Use reference counting with copy-on-write overhead
• Gel/Inko: Free values at scope end rather than when ref-count hits zero

The author's system uniquely combines dynamic typing with sophisticated borrow-checking, offering a different set of trade-offs than existing approaches.

Future Directions and Open Questions

The author concludes by considering potential improvements:

1. Ergonomics: Reducing the verbosity of reference annotations
2. Second-class references: Exploring approaches like Hylo's coroutines
3. Static typing focus: Improving ergonomics for working with unknown types
4. Lifetime management: Implementing more Rust-like automatic dropping

Several open questions remain about the long-term viability and expressiveness of this approach. The system demonstrates that sophisticated memory safety is possible without static typing, but whether the trade-offs will appeal to mainstream developers remains to be seen.

The author's work represents an important contribution to programming language design, showing that the space between dynamic flexibility and static safety contains unexplored territory worth investigating. By implementing borrow-checking through runtime reference counting, they've created a system that challenges conventional wisdom about the relationship between typing and memory safety.