Tyler Hou L&S Math & Physical Sciences
Top-Down Declarative Program Optimization
Optimizing programs makes them run faster and consume less resources. However, implementing program optimizers is difficult for people without specialized expertise.
In recent years, new declarative techniques have made program optimization more accessible to non-experts. However, these techniques lack support for reasoning about programs “top-down.” Top-down reasoning is required to efficiently implement context-sensitive optimizations that are standard in e.g. optimizing compilers and database query planning. For example, we would like to optimize the program ⟦if (x = 1) x (x / x)⟧ to just ⟦1⟧. This requires reasoning that x is equal to 1 within the “then” branch context. In addition, top-down reasoning can make the process of optimization itself more efficient (by intelligently pruning the search space) so that even better programs can be discovered.
The goal of our research is to extend an existing declarative program optimization framework, egglog, to support top-down reasoning in order to both (1) discover better programs and (2) discover those better programs more efficiently. We also intend to develop a theoretical foundation for the extended framework’s semantics.
Message To Sponsor
This is a project that I have been wanting to work on for a while but I haven't had the chance to spend substantial time on it. Because of your sponsorship I now have the opportunity to dedicate my summer to this research. In addition, I want to become a programming languages researcher, and I appreciate your support in helping me to achieve that goal.