Add garbage-collected references and reference types.

[elucent]

Basil is planned to be a garbage-collected language, whereas most types in the language are value types (with the exceptions of strings, lists, and closures). In order to support more desirable semantics for certain types of objects, such as arbitrarily-long lifetimes and minimal copying, Basil should have an easy-to-use reference type that allows the allocation and management of arbitrary values.

I propose introducing a new type kind to Basil, "Reference". We'll refer to a reference to some type T as a T ref. Overall, the semantics of references are rather similar to those of raw pointers (#30), but since references are safer and fall quite naturally out of any GC, we'll be prioritizing their development. At minimum, references should support a few unique operations:

• ref : Type -> Type: to construct a reference type value, i.e. Int ref is the type of a reference to an integer.
• new : T? -> ref T?: allocates a value of type T on the heap and returns a managed reference to it.
• deref : ref T? -> T?: dereferences a managed reference and returns the pointed-to value. This pattern also functions as an lvalue!

Some open questions:

• While pointer arithmetic is distinctly not a goal of reference types, we might want similar syntax for managed and non-managed pointers: perhaps deref foo could be represented as *foo or foo.* for brevity's sake?
• Should references be nullable? While it would be relatively easy to represent this on a value level, nullability has famous downsides. Perhaps we can require the use of optional types or unions, and optimize out tags when possible.
• Since reference types don't change the semantics of a value too greatly, we might want their use to be as seamless as possible. Some features that would fall into this category would be syntactic sugar to define implicit reference types (such as ref Foo = Int for an automatically-boxed integer), or perhaps automatic dereference via type coercion (T <: T ref?).

[dumblob]

Just a note that not all references has to be garbage collected - some (and practice in programming in V shows there'll be many - incl. smaller arrays & strings with statically known sizes - i.e. not just "value types") are referencing stack structures.

This makes a huge difference in performance according to measurements done on V apps.

[elucent]

I'm a bit dubious of any result coming from V...but yes, Basil will remain unboxed by default. These will behave primarily like OCaml's ref types - a means of boxing an otherwise value-type explicitly (although OCaml overuses GC a bit last I checked...). For passing around arrays and such I'm tentatively thinking about doing a copy-on-write optimization but I'm not set on it quite yet.

[dumblob]

I'm a bit dubious of any result coming from V...

🤣

but yes, Basil will remain unboxed by default.

👍 This is important.

These will behave primarily like OCaml's ref types - a means of boxing an otherwise value-type explicitly (although OCaml overuses GC a bit last I checked...).

Yep.

For passing around arrays and such I'm tentatively thinking about doing a copy-on-write optimization but I'm not set on it quite yet.

Only measurements (both complexity & performance) can show.

[dumblob]

https://github.com/matthieu-m/static-rc - yet another small step towards lower reference counting pressure.

[elucent]

Lobster uses a similar approach. Basil's garbage collector is not reference-counting so I'm not sure it's as applicable or useful (RC needs optimization really bad due to poor locality and slow allocation speed, whereas Basil's current tracing copying collector takes like half a dozen cycles per allocation and is always compact), but I'd like to explore some sophisticated escape analysis in the future. Lifetime analysis during optimization and potentially some alternative kinds of dynamic allocation (like on-stack mini-arenas) are potentially in the cards but aren't priorities at the moment.

[dumblob]

but I'd like to explore some sophisticated escape analysis in the future. Lifetime analysis during optimization and potentially some alternative kinds of dynamic allocation (like on-stack mini-arenas) are potentially in the cards...

That makes a lot of sense (most allocations are tiny - see https://github.com/nadavrot/memset_benchmark ).

All in all the best approach is combination of direct register/stack allocation (for compile-time analyzed tiny values) and garbage collection for everything else. Which is what Basil seems to aim for which is great!

[dumblob]

Just saw an interesting take on reference counting with less than half the overhead of "traditional" optimized RC.

https://verdagon.dev/blog/generational-references
https://verdagon.dev/blog/hybrid-generational-memory

Might be interesting to explore in the context of Basil.