Problem with generics and bare functions

[brson]

fn main() {
    fn# foo<T>() { }

    // This wants to build a closure over type int,
    // but there's no way to do that while still being a bare function
    let f: fn#() = foo::<int>;
}

As a result we can't do bare-fn spawn for generic functions, which is pretty important:

#[test]
fn spawn_polymorphic() {
    fn# foo<~T>(x: T) { log_err x; }

    task::spawn2(true, foo);
    task::spawn2(42, foo);
}

[marijnh]

(I'm assuming safe spawning is the primary motivation for bare functions. If it is actually 'saving a word of storage', ignore what comes after---)

What if we support 'unique functions' (terrible term) instead of bare functions? They'd be closures that own all the values in their environment (the environment being a unique pointer as well). They'd be more compatible with regular blocks (you could pass a fn~ to a function expecting a block), and for real bare functions the environment field can simply be a null pointer, so no extra malloc is required.

[brson]

Spawning is the primary motivation for having some sort of typesafe function that can cross tasks.

The reasons for preferring bare functions to unique functions are somewhat murky to me, but pcwalton and dherman have both expressed doubts. One tangible issue is that type descriptors are not unique-kinded so putting them into unique closures and passing them between tasks presents obstacles.

I'm going to make it so you can't take the value of generic bare functions. It doesn't bring me joy.

For reference, graydon's notes on function types are here: https://github.com/graydon/rust/wiki/Function-types

[brson]

Also, the plan is to turn function items into bare functions, which means that anywhere we are taking the value of a generic function currently will have to become a bind.

[pcwalton]

We've discussed this before and I agree that it's a severe problem.

As far as I can tell we have to do one of these things:

1. Monomorphize.
2. Implement unique closures. Remove the "type descriptors on the stack" feature. Move the type descriptor store (used in upcall_get_type_desc) to a shared arena. Add locks around upcall_get_type_desc.
3. Implement unique closures. When creating a type-parametric unique closure, copy the type descriptors into the exchange heap. (Note that this must be a recursive copy, because of derived tydescs. So it has to use the shape glue.)

All of these are painful. #2 is especially bad for performance, but it's probably the easiest to implement.

In any case, I think that sending is the nail in the coffin for type-passing. The only option that's acceptable for production is #1.

[Yoric]

Fwiw, we have experimented #1 and something that looks like #2 in Opa, with the added difficulties that we had to pass types between (untrusted) computers and that our type system allowed (possibly recursive) open sums and open products.

The results were unfortunately unimpressive with either solution. Both solutions caused our binaries to grow enormously. #1 because of the sheer number of polymorphic calls in our code, #2 because of the size of the type descriptor store, despite our optimizations. Solution #2 considerably slowed down communication. Solution #1 was largely incompatible with separate compilation and caused surprising bugs (e.g. with mutable cells that were somehow monomorphized as a side-effect of the monomorphization of something else).

I personally believe that #2 is the least fragile. I am really not sure how you would go about #1 without a quite complex linking phase.

[graydon]

I don't accept the assertion that #2 is unacceptable for performance. This is hypothetical. Many tydescs are static and if the dynamic cases are really so bad in practice, there are options:

• Interprocedural type-escape analysis to stack-ify all those that don't escape
• Make tydescs sufficiently self-describing (in terms of their size, memory contents) that you can deep-copy them out of the stack and into the heap when they're escaping a task like this (keep in mind, a tydesc term is necessarily an acyclic graph, and probably pretty small)

[pcwalton]

For #1 we basically have to do something like serializing ASTs.

Interprocedural tydesc escape analysis seems complex, but we might be able to get away with something simpler: just dynamically (shallowly) copy a type descriptor into the new type descriptor whenever we're creating a derived type descriptor.

The latter option is #3 above. It'd be tricky to get working but should be possible. I'd be worried about slowing down communication though.

[graydon]

Ah right. Ok. Yeah, I'd try #3 then if your gut says #2 will be costly if done systematically. I don't think "most" communication will require forming unique closures; I'd bet most channels will be carrying more-plain data, rather than closures, most of the time.

[marijnh]

Is seems #3 requires yet another function type. That's unfortunate, of course.

[graydon]

If you mean "unique closure", this is necessarily the case (always was) to get the kind-based control of closures working, to prevent accidentally racing on captured environments between tasks.

[nikomatsakis]

Unique closures have been implemented. The current semantics are that closed over type descriptors are cloned into the shared heap as needed.