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
Thank you for generously sponsoring our project. We have written a paper on our research and submitted it to a conference for review (preprint: https://arxiv.org/abs/2507.10799). Also, because of your funding, we have discovered many new ideas that we plan to explore further in the upcoming year. For example, we've also noticed connections between our work over the summer and other recent work on data processing parallelization and we are currently exploring those connections in the fall semester. Also, we have noticed connections between our work and existing "categorical" models for dataflow programming.