Open myreen opened 6 years ago
This optimisation ought to be implemented on the type+module-update
branch in order to future-proof the development.
Chatting with @zapashcanon, doing this as a flatLang -> flatLang pass has the advantage that the global variables are obviously separate from the locals. This is nice, because the Lambda lifting algorithms start by making all of the names unique, and we don't want to mess with the names of globals. Also, for the proofs, the closure environments only contain local variables.
Introducing more globals shouldn't be difficult in a flat->flat pass.
The CakeML compiler currently lacks a lambda lifting optimisation. Such an optimisation pass could be beneficial because it makes functions closed (not have free variables) which allows optimisations such as
clos_call
to run.When lambda lifting has been discussed, the implicit assumption has been that it should be done in ClosLang. However, implementing it in ClosLang is made awkward by ClosLang's use of dB indices for variables (one would have to shift indices), it would have to remap the globals (the compiler would maintain an injective function), and ClosLang's
max_app
might get in the way when adding new arguments to functions.I propose that lambda lifting is to be done as a source-to-source transformation, because:
The explicit names of the source language allows the optimisation to avoid the need to shift names in dB style.
One avoids the complication of ClosLang's multi-argument functions and
max_app
.By doing this before globals are introduced (in
source_to_flat
), we leavesource_to_flat
as the only place that introduces globals.A source-to-source optimisation is easy to test and debug before verification starts because one can use
process_topdecs
to generate test cases and one can useastPP
to produce output that is readable.Example
For this issue to be considered finished. There needs to be a compiler phase that can (at the very least) optimise functions such as the following:
The optimisation should produce something along the lines of the following.
Note that
insert
andinsert_all
are still defined inisort
just to make the lambda-lifting optimisation easy to verify (not too smart). One could remove these useless bindings in a separate optimisation pass that only targets such unused bindings of partially applied functions.This issue could be the basis of a 5-month Masters project or similar.