The dynamic program improvement system (dyna-pi) is an interactive tool for
analyzing and improving dynamic programming algorithms. We developed this tool
because Finding a correct program with the optimal asymptotic runtime can be
unintuitive, time-consuming, and error-prone. dyna-pi aims to automate this
laborious process.
Key features:
- Dyna language: A high-level, domain-specific language for clear and concise dynamic program specification.
- Efficient solvers: General-purpose solvers to execute Dyna programs, including agenda-based fixpoint iteration and semiring Newton's method.
- Static analysis: Type analysis and worst-case time/space complexity analyses.
- Program transformations: Meaning-preserving Dyna-to-Dyna transformations, which systematizes the repeated insights of numerous authors when speeding up algorithms.
- Optimizer: A search algorithm for identifying a sequence of transformations that reduce the runtime complexity given an initial, correct program.
- Visualization and debugging: Tools to aid in the development of correct programs, including integration with Jupyter.
The dyna-pi system is based on Tim Vieira's 2023
PhD dissertation
(see also defense video and
slides).
It is also part of the broader Dyna project.
Notice. This code release is in its early stages and might have some rough edges. We welcome feedback and contributions through pull requests, email, and our issue tracker.
For a quick start, check out our demo notebook 
To install dyna-pi using pip run:
pip install -U "git+https://github.com/timvieira/dyna-pi"
This project is licensed under the MIT License - see the LICENSE file for details.
For more information about dyna-pi please refer to:
-
Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing. Tim Vieira. PhD Dissertation. Johns Hopkins University. 2023
-
Searching for More Efficient Dynamic Programs. Tim Vieira, Ryan Cotterell, and Jason Eisner. Findings of EMNLP. 2021