implement lambda blocks

[graydon]

Should produce an alias to a non-copyable, non-sendable (resource) type, capturing the environment but not escaping.

[graydon]

Shifted to rustc.

[marijnh]

We just discussed this here in Toronto. The approach we settled on is:

• bind will go, maybe to be restored later in the form of a macro
• Function types will fall into three categories, @fn, ~fn (both boxed), and plain fn, with the latter only being allowed as a function argument that's passed by alias.
• fn values are noncopyable. Thus, you never have a raw fn value on your hand. Boxes of functions are copyable.
• There will be @fn(args...){body...} and ~fn(){} expressions to create boxed function values. They will close over their environment by copying the closed-over values into their environment.
• Functions passed by alias to another function can be written as plain fn(...){...} expressions. These 'fully' close over their environment (the resulting alias holds the frame pointer). These must never outlive the function call they are passed to.
• Function boxes can transparently be passed to a function that expects a function alias. (Or maybe require an explicit dereference with * if that causes ambiguities.)
• As a form of syntactic sugar, a function that takes a function alias as its last argument can be called like f(args) { block }, causing the given block to become a function. If this function needs to take arguments, it becomes f(args) { |arg1, arg2| ...} (this syntax is not set in stone).
• Function values take the form of a single-word code pointer followed by an environment (of any size). @fn and ~fn create a box of the right size and copy in the code pointer and closed-over values. Stack-allocated functions that are passed by alias have their code pointer plus a frame pointer allocated on-stack, and the address of the code pointer passed.

The issue of returning/breaking out of blocks has not been addressed yet, I'll try to bring that up later.

[msullivan]

What is the status of named nested functions? Do those capture? Do you write things like "@fn foo(...) -> ... {...}"?

[marijnh]

We didn't discuss in depth, but off-the-cuff, Graydon, Dave, and I agree that they probably shouldn't. That's slightly un-obvious but has the advantage of giving these function boxes a definite lifetime. If you need the equivalent of a closing local function, just assign a `~fn' to a local variable. Sounds sane?

[marijnh]

Also, I forgot to mention, taking the name of a normally defined function with ~ or @ in front of it should result in a function box being created for that function. They can also be passed by alias. How type specialization of taking the value of a type-parametric function works wasn't discussed, but I guess we'll want to generate a specialized version of it (as bind currently does) and use that as the function value.

[msullivan]

I understand the reasoning, but it seems inelegant to give lambdas and explicitly named functions fundamentally different semantics.

My proposal is that a nested function declared as "fn foo(args) -> t { body }" does not capture but one declared as "@fn foo(args) -> t {body }" does.

I think function boxing of normally defined functions already exists?

[msullivan]

So, my plan for implementing this involves adding a field to fn_decl saying what form of environment capture the function does (no capture, copying capture, alias capture).

Does anybody have any thoughts on what the right way to detect what sort of capture a function needs? Can/should it be done at parse time?

[marijnh]

Definitely don't do it at parse time. A pass that gathers free variables and puts them in a table is probably the best approach. Various stages of compilation need this information.

[msullivan]

You misunderstand my question. Finding the free variables certainly shouldn't be done at parse time. I mean, figuring out which "flavor" of capture a function has (because the current plan seems to be to have three: no capture, copying capture, aliasing capture). Which it is depends on what context the lambda occurs in (if it is being put in a box it should capture the environment by copying it; if it is being passed by as a function argument then it's by alias). So I'm wondering when the best time to decide on that is.

[marijnh]

Ah, I see what you mean now. I'm actually coming around to having local 'item' functions capture. You'll have to leave something in blocks or regular fn expressions to disambiguate during parsing, yes.

[msullivan]

Capturing by default or only with an @ glyph in front or something?

[marijnh]

Capturing by copying in the case of @fn and ~fn, capturing by storing the frame pointer in other cases.

[msullivan]

So there wouldn't be a "don't capture at all" mode, even for item functions?

[marijnh]

I can't make the final decision on that. Try implementing it like that, we can see how well it works.

[graydon]

the thing is, fn types are to be non movable (nor copyable) so you can only ever really pass a "bare" function as an alias-mode parameter. how you get one ... yeah, it'll have to be an item (inner or otherwise) or a lambda-block.

I don't see a lot of harm in permitting such inner items to capture the frame, the same way a lambda-block will.

[marijnh]

I don't see a lot of harm in permitting such inner items to capture the frame, the same way a lambda-block will.

That's pretty much what my original write up says too.

[msullivan]

the thing is, fn types are to be non movable (nor copyable) so you can only ever really pass a "bare" function as an alias-mode parameter.

OK. As it stands now, you can pass bare function types as non alias parameters and it works right.

[marijnh]

(Because they do not close yet.)

[msullivan]

Also, with regard to capturing the environment by passing the frame pointer:

For each loops are currently not done like that. For each loops are built by constructing an environment with pointers to all of the local upvars and then packaging that as the function's environment. Is LLVM smart enough to magic that into just passing a frame pointer. If not, is there a way to explicitly tell LLVM to just pass a frame pointer? Does the LLVM IR know about things like frame pointers?

Also, passing frame pointers doesn't directly extend to multiple nested lambdas. Pass multiple frame pointers in that case?

[msullivan]

(Because they do not close yet.)

You can pass functions created with bind too, though, which do have an environment...

[msullivan]

Function types will fall into three categories, @fn, ~fn (both boxed), and plain fn, with the latter only being allowed as a function argument that's passed by alias.

Is this intended to mean that @fn should be a different type than a fn type with the @ type constructor applied to it...? (I think that probably doesn't need to be the case)

[msullivan]

I think we might want to have autoderef on the function in function application.

[msullivan]

A quick progress update:

• I've made functions autoderef, and that has landed.
• I have a mostly working implementation of alias capture semantics for that is missing typestate checking and safety checking for aliases. I am deferring finishing this up and landing it until functions are non-copyable, because trying to copy alias-capturing functions will crash.
• I'm working on making functions "mostly" non-copyable. That is, I am making them non-copyable except for putting them into boxes. I am in the process of eliminating function copying from rustc, which is taking longer than I expected and is fairly painful.
• The process of converting rustc to not copy functions has given me some concerns/questions about our planned system that'll I'll be writing up soon.

[msullivan]

There has been a lot of yak shaving.

[msullivan]

The big decision that has been made is that blocks are a separate type but other types of fns can be silently coerced to them. Graydon wrote up his ideas but I'm not sure where that is.

I've also landed alias capturing blocks, although there are still some missing things in typestate.

[msullivan]

Copy capturing blocks landed, although they still allow you to write to the closed over variables, which is a surprising behavior.

[msullivan]

Fixed mutability of copied upvars a while back.

[msullivan]

Inferred lambda-blocks have landed. I think it is probably time to close #6. I'll start filing remaining issues in new bugs.