Mars assembly: Replace parcall with closure-variable functions

[Matt Giuca]

In order to support clean implementation of closures across multiple backends, the internal representation should change. Currently, the instructions parcall and parcall_global are specified as currying arguments into any function, and returning the resulting function. This instruction by itself is very difficult to implement in all planned backends (LLVM, as well as a hypothetical JVM or JavaScript backend, which would have similar difficulties). This is because the implementation of closures requires that the compiler knows in advance how many arguments will need to be curried into a function.

Another problem is that it is currently difficult to implement a 'lambda expression' feature in Mars, because it would have to compile down to a separate function with a parcall (which would be implemented inefficiently, as the parcall would need to generate another wrapper function on any backend).

Therefore, remove these two instructions and make the internal representation of closures lower level. Rather than allowing any number of arguments to be curried into any function, force the IR to specify, for each function, a set of arguments that MUST be curried, and the remaining arguments CANNOT be curried.

- Introduce a new type of function, a "closure-variable function". (Much like how CGCs differ from normal functions.)
- Normal (non-closure-variable) functions may not be partially applied. If they are called, all arguments must be supplied. BUT they may still be "lifted" (ld_func) without any arguments being applied.
- Closure-variable functions take "closure variables" as well as arguments. These are similar concepts, except that such functions MUST be called in two stages: first pass all of the closure variables, constructing a closure object, then pass all of the remaining arguments to the closure object. It will not be possible to call such functions without first creating a closure object, and it will not be possible to "lift" such functions without supplying all of the closure variables.
- Note that closure-variable functions are static only. There is no such thing as a local variable which is a closure-variable function. All local variable functions are normal functions (so the call instruction only deals with normal function objects).
- ld_func and call_global do not work on closure-variable functions, just as they do not work on CGCs. They only work on normal functions.
- Remove the parcall and parcall_global instructions.
- Add a new instruction, new_closure, which takes a closure-variable function and values for all of its closure-variables. It is required that all closure-variables have a supplied value. This instruction creates a closure object, containing the supplied values, which may be called by the call instruction to supply the non-closure-variable arguments to the function.

Partial application is compiled to Mars assembly by creating a new closure-variable function with all of the curried parameters as closure-variables (as well as the callee, if it is a function variable), and all of the remaining parameters as normal parameters. The body of the function simply calls the wrapped function with all arguments. The partial application expression is replaced by a new_closure instruction which loads all of the curried arguments into the closure.

This also allows the easy implementation of lambda expressions. The lambda function is simply compiled into a separate closure-variable function (assuming it refers to free variables), and the lambda expression is replaced by a new_closure instruction that loads all of the free variables into the closure.

[Matt Giuca (mgiuca)]

Closure templates and the new_closure instruction are implemented. But ast_cfg currently never generates either of them.

Therefore, the remaining work is to have ast_cfg generate a closure template for each partial application, and a corresponding new_closure instruction. Then we can remove parcall, parcall_ctor and parcall_global.

Also needs a review of the typedict code. (Both the whole notion of prepending typedict arguments to closure templates, and also the type dict augmentation of the new_closure instruction.) In particular, in typedict.augment_instr_globalrefs, I am not sure what to do about ArgTypes, which should correspond to the types of the cvars. Do these need to be unified and have type dicts augmented? I wrote some unification code, but didn't commit it, since it currently only does a typecheck (and that isn't the role of typedict):

        % Unify the cvar types with ArgTypes
        ( tables.lookup_function(PT, Name, Func) ->
            ( Func ^ func_cvars = yes(CVars) ->
                CVarTypes = map(func({_,T}) = T, CVars),
                list.foldl_corresponding(...?, CVarTypes, ArgTypes, Varset, _),
            ;
                error("augment_instr_globalrefs: new_closure on non_CT: "
                      ++ Name)
            )
        ;
            error("augment_instr_globalrefs: not a global: " ++ Name)
        ),

[Matt Giuca (mgiuca)]

To answer the above question, see closure-templates r1254. Yes, they do need to be unified, in order to know the actual types of CVar parameters. This was fixed in that revision.

[Matt Giuca (mgiuca)]

Fixed in trunk r1224.