Given the recent progress in the Type-V project, I have been working on implementing closures in Type-V, in a way that is non-intruisive to the current bytecode and least possible overhead. This article will cover the current implementation of closures in Type-V.
Regular Functions
Before we dive into the details, allow me to showcase how regular functions are currently implemented in Type-C. First and foremost, a limit of 255 arguments is set for all functions. That is becaues arguments are passed through registers, and no stack is involved. The stack is only used to communicate with the FFI (at this time of writing). Bytecode level, function is only referenced by its address within the code segment. So when a function calls another function, it allocates new execution frame and jumps to the address of the callee function.
Let's review how a function state is modeled:
The idea is that, instead of the classical approach of storing all function context into the stack and popping it back up, we just allocate new "execution context" or "state" and we simply switch between them. This is a very efficient way of handling function calls.
Now let's delve into bytecode: For example:
The following code will result is the following pseudo bytecode:
CLosures
Let's start with a basic example:
Closures requires a lexical analysis, to identify the free variables and to capture them. In the above example, x is a free variable, and it is captured by the closure f. The closure f is then returned by createAdder. Not every variable that is accessible within the closure is captured. Only the needed ones.
When compiling closures to bytecode, the run-time aspect needs to be isolated from the compile-time aspect. The run-time aspect is the environment, which is the value of the free variables. The compile-time aspect is the function itself. The function is compiled to bytecode, and the environment is captured and stored in a separate object.
To model the environment, a new Struct is introduced:
So now, a closure method is converted into the creation of a new TypeV_Closure object. The TypeV_Closure object holds the function pointer and the captured registers. We will need new instructions to allocate this object and to set up the environment.
Before I showcase the new instructions, here is the general idea:
- We create closures in the bytecode
- When we run a closure, it is the same as calling a regular function, except prior to calling it, we set the context of the current function to the closure object.
- Upvalues, while stored as registers, are identified by numbers. The limit is set to be 255, so that the IDs can be read as 1byte.
Here is the list of our new instructions:
| Instruction | Arg 1 | Arg 2 | Arg 3 | Description |
|---|---|---|---|---|
| closure_init | R | I | I | Creates a new closure object of Arg3 number of upvalues, referencing function address Arg 2 and stores the result in the destination register Arg1. |
| closure_capture | R | I | R | Captures a register (Arg3) and stores it in the closure object (Arg1) at index Arg2 |
| mv_reg_upvalue | R | I | I | Moves Arg3 bytes from active closure object index Arg2 to register Arg1. |
| mv_reg_upvalue_ptr | R | I | Moves pointer value stored in index Arg2 of active closure into register Arg1 | |
| mv_upvalue_reg | I | I | R | Moves Arg2 bytes from register Arg3 into active closure upvalue Arg1 |
| mv_upvalue_reg_ptr | I | R | Moves pointer value stored in Arg2 into active closure upvalue Arg1 | |
| fn_call_closure | R | Calls the closure object stored in register Arg 1 |
TypeV_FuncState has been updated to hold the active closure object, as well the methods descriped above are implemented. Now let's review how the bytecode of our closure look like:
Effect on register allocation and spilling
The register allocation algorithm spills registers in a dedicated area spillSlots. When a spilled register is needed for a closure, it will be marked as used by the register allocator, to first unspill the register and then capture it in the closure. The drawback in this approach is that closures will still need to have active registers, meaning if an upvalue x is being used within a closure, it will require a register to be allocated for it as well as the slot in the closure object. This is a trade-off for the sake of simplicity and performance. The overhead certainly tolerable, but nevertheless, this adds some stress on the register allocator.
On the bright side, the register allocator will not worry about closures, since the upvalue registers will just be marked as used and the allocator will take care of the rest.
GC and Closures
Closures, similar to any other dynamic entity in the VM, will have the same life cycle. A closure will be freed when it is no longer marked as reachable.
Conclusion
The effectiveness of this implementation is yet to be determined, will update the article once the implementation is complete and tested.
Until then!