Generic Variables: simple implicity context passing

language design
1

Hello everyone

I have an idea for a new language feature to solve the problem of types that depend on runtime context to be meaningful. I also made a post about this on Zulip [1], but it isn't getting much traction so I want to share the idea here as well to get more feedback, and check if there was something obvious (or subtle) that I missed.

To avoid restating the problem and bloating this post, check out @tmandry excellent explainer on the issues that arrise when using types that depend on runtime context, and his solutions to them [2].

There is seemingly quite a lot of prior disscussion around this issue, but everyone seems to have differing ideas about just how exactly runtime variable data should influence how types and functions work, if at all [3], [4].

Of cause, I have my own solution. I have thought about it a lot, so to explain its intricacies properly, I needed more words then is allowed for a single post. It's not complicated, just a tough concept to explain without introducing it in small peices seperated by examples. You can read the full explanation (as a pdf) :backhand_index_pointing_right: here, what follows is a high level summery of the idea.

Summary

My solution to this problem is to extend the type system to include a new kind of generic, generic variables. Generic variables would allow types to depend on runtime variables without duplicating references to those variables across every instance of the type or explicitly passing references to them as arguments to all its functions/methods. References to generic variables are implicitly passed to all methods on types that use those variables, making them in scope for the method body. Generic variables are simple in their construction, and work seemlessly with methods, traits, lifetimes, and generic code.

To support this I also propose introducing a new kind of variable whose name can't be shadowed so it can be used in type signature as a concrete subsitution for a generic variable.

2

I've been working on what is essentially this proposal, which I came up with independently (and other people have come up with very similar things too). My early version of it is in this blog post. There's certainly room for improvement for the syntax (my placeholder syntax there is pretty ugly and probably a more ergonomic syntax should be selected before stablising it), but getting the semantics right is hard enough as it is.

I do think that something like this is extremely important; basically every Rust program I've ever written would benefit from it (and the lack of this sort of feature in Rust is actually making me seriously consider changing to a different language). In particular, Rust would greatly benefit from the ability to statically prove that programs cannot panic (as this would guarantee the absence of certain types of bugs, just like the memory safety does), but there are lots of situations where you need a type system feature like this to prove the absence of panics. As you mention, allocators are also a significant use case (programs are most efficient if they use special-purpose local allocators for just about everything, but you need a feature like this to be able to write code using such allocators without memory bloat and without unsafe).

There are a few significant obstacles. As you mentioned in your post (and I mentioned in mine), one of them is dyn. There are some subtle requirements for mixing dyn with this sort of generic to even be sound. (Notably, the variable has to be Sync (assuming that the type of the dyn references it rather than copying a value); this is because existing unsafe code, including in the standard library, assumes that it is sound to send a lifetime from one thread to another, in the sense of "if you have a reference to a Sync value with lifetime 'a on thread 1 you can reborrow it as a reference to a Sync value with lifetime 'a on thread 2", but this would not be true if you could create a non-Sync generic variable.) Actually implementing such a dyn is also nontrivial, because the dyn metadata ends up changing in size as you add more of these generics into it; there is a fairly simple solution by allocating memory, and a much more complicated solution that involves a whole-program analysis, neither of which is really ideal. (All this said, I consider this feature important enough that I would rather use a Rust without dyn rather than a Rust without this feature.)

Another problem is related to how the type captures the variable (which I don't think you mentioned in your proposal?). Capturing it by shared reference is by far the simplest case: it gives you useful guarantees (that the captured variable won't change in ways other than would be possible through a shared reference), it doesn't put a significant burden on the type checker because shared references are Copy, and it is powerful enough to do a lot of useful things. There have been various suggestions by other people to capture it in other ways (e.g. I was experimenting with allowing captures by mutable reference), but they're both harder to type-check than they look and less useful than they look. (In particular, if you have a mutable reference to something you can swap that thing out, so you end up with no useful guarantees from the type system. You end up being able to implement Cell in safe code, but it isn't useful for implementing anything other than cells.) As such, I would definitely recommend sticking with shared-reference capture, at least initially.

I'm also interested in the theoretical basis, and relationship to other features. Lifetimes are a special case of this feature (a lifetime 'a is equivalent to a variable of type () captured in a generic, except that lifetimes support variance, and for simplicity, variables captured in generics are generally taken not to). It's been commonly proposed to let people pass in their own trait implementations to generic functions (i.e. calling a fn foo<T: Trait>(&T) with a T that doesn't actually implement Trait, by providing an implementation of Trait for T in a generic-like way); I currently believe that that is equivalent to this feature (by providing an implementation that captures a variable as though it were an associated constant), and it can also be used to implement lifetimes (which would make sense if it's equivalent to this feature).

Some existing work, for people interested in reading more (and as a list of references that may be useful for any eventual RFC):

For Rust:

Prior art in other languages:

Other related posts:

3

I'm surprised there no mention of dependent types in neither this post nor in the blog post. They are the first concept I would think of when proposing to allow generic parameters to depend on variables.

2 Likes
4

I'm aware of dependent types (in fact I used to work with a co-worker who was an expert in them, and picked up some dependent types knowledge indirectly like that), but a full dependent-types system isn't at all reasonable as something to add to Rust (they are very complicated both to implement and to work with), and are also much more powerful than is necessary to solve the problems discussed in this thread.

I was planning to mention them if I ever came up with an RFC, but only along the lines of "this is sort-of like dependent types, but much simpler and with only a fraction of the mathematical problems".

1 Like
5

The auto traits, including Sync, would interact with generic variables like have a PhantomData<(&'x0 X0...&'xn XN)> as part of the type, where for the generic variable 0..N, X0..XN are the types of those generic variables, and 'x0..'xn are their lifetimes. So if the generic variables are not Sync, then neither would the type using them be.

Implimenting dyn is non-trivial, and there are trade offs to be made with the way dyn is handled. But I have already thought about it and have a solution. Maybe the not the best solution, but it shows this is possible: We could monomorphise each vtable for each function with generic variables. This allows passing the generic variables through registers and is more flexible in terms of the ABI then some of more dynamic options I've considered. We can point to this monomorphised vtable depending on which function we are in when the dyn pointer is created. This has the issue of some binary bloat and increased compile times, but means the dyn pointer can remaing its current size.

I've got other ideas as well, the design space is huge and there's so many possible solutions at least a couple of them must be good enough.

In my conception of the feature, it's interior mutability/immutability only. As such, capturing works in the obvious way. We could extend the feature in the future to allow mutability of some kind, but I really struggle to imagine why that would be useful, you might as well just store the mutable reference directly on the type, since there can only be one at a time.

6

This probably isn't sound because you can call a method that can name a type without having an instance of that type. For example, FnOnce::call_once() can create a value out of nothing (and is dyn-compatible). This means that you can take a FnOnce which outputs a T that captures a non-Sync variable, send that FnOnce to a different thread, and call it; inside the body of the FnOnce you would probably be able to access the variable because it's mentioned in the type, but you're now accessing it from the wrong thread. The FnOnce can be Sync even if its return type isn't.

I think it's possible that there might be some sort of variance-like analysis that you could use to exclude such cases, but I'm not sure, and it would likely be extremely subtle and hard to get right.

7

But if the variable is non-Sync, and it is captured by reference in the FnOnce, then the FnOnce won't be Send, so you could never send it to a different thread. Because T captures the variable, so does the closure. The only way that wouldn't happen would be if you put T as the return type, but the closure just immediatley calls unreachable! or something. In that case it doesn't matter because the reference is never read from. But in my mental model, the whole system is based soley on type signitures, so even in that case the FnOnce would get conservitively label as non-Send.

8

I'm thinking about something like this:

struct Creator<T: Default + Debug>(PhantomData<fn() -> T>);
impl<T: Default + Debug> FnOnce() for Creator<T> {
    type Output = ();
    extern "rust_call" fn call_once(self) { dbg!(<T as Default>::default()); }
}

pub fn convert_creator<T: Default + Debug>() -> Box<dyn FnOnce + Send> {
    Box::new(Creator::<T>(PhantomData))
}

In current Rust, Creator is unconditionally Sync and Send, regardless of what T is. So convert_creator typechecks in current Rust, and you cannot choose for it to not typecheck without breaking backwards compatibility. (If I had used a FnOnce-like trait that could be implemented stably rather than FnOnce itself, you could write the above code in current stable Rust.)

Now, if you choose T to be a type that captures a non-Sync variable, you get undefined behaviour (because you could send the resulting Box<dyn FnOnce + Send> to another thread and that could potentially lead to trying to debug-print two Ts simultaneously from different threads, that had captured the same non-Sync variable).

9

(And indeed there is such a T: Rc<u32>. || Rc::<u32>::default() is Send and Sync, its return value is not. That doesn't quite seem to include the "capture" step though.)

10

To solve this, there would need to be a new auto trait FnSend, which is applied to a type when all of its generic variables impliment Sync. Now, fn() -> T only impliments Send and Sync if T impliments FnSend.

To keep this backwards compatible, in the same addition this rule is added, all generic and trait delcerations in all previous additions now have an implicit FnSend bound added by the compiler, this bound could be relaxed with ?FnSend. In a future addition, after a sufficant portion of the ecosystem has migrated, the default FnSend bound could be removed in all future additions, and a lint added to warn against using ?FnSend.

FnSend could even be added before the feature itself to give ample time to migrate.

11

Although a new autotrait would work (although the autotrait should probably just be "captures no variables"), there's a pretty high bar for adding those. I suspect it would be easier to just require captured variables to be Sync.

(My experiments in provisional implementations of this suggest that Sync is the only autotrait that is problematic. This is because the soundness requirements on variables captured in types are essentially the same as those on global variables, as both support shared-reference-only access from potentially arbitrary locations in the code; global variables are required to be Sync, so variables captured in types also have to be, but the only other autotrait they require is Sized which is not a problem if you're capturing via shared reference as shared references have a known size.)

12

Is this another formulation of implicit arguments?

Anyway you need to show at least pseudocode, and be more specific on details

13

This feels like a hack to work around the fact that you would like to treat these generic variables like the current generic arguments. IMO they are different, with different semantics, and thus should be treated differently. For example if you intend to implement these by storing a copy/reference of the generic variable on the type, then you should treat that as a hidden field and have it behave like other fields, including affecting Send/Sync.

1 Like