AutoDP

Inspiration

The algorithms students asked, and AutoDP answered: AutoDP is a never-seen-before python program that turns a clumsy naive recursive function from the user, and runs it as the appropriate dynamic programming solution to gain a healthy boost in execution speed.

Dynamic programming is an algorithm technique that can dramatically speeds up the asymptotic running time of certain recursive functions by reducing the number of duplicate recursive calls. Although the steps required to apply DP to a function is relatively mechanical, it's easy to make mistakes and it can be challenging for students unfamiliar with algorithms. While I was working through the frequently repetitive DP problems in the algorithms class, I wondered if there is a way to automate this process. This wish has now become reality!

How it works

AutoDP uses the python ast library to produce and manipulate the parse tree of the code input by the user in the following steps:

• Parse user code into python abstract syntax tree
• Extract base cases and dependency of the input function
• Construct the function call dependency graph
• Perform topological sort on the dependency graph to produce the optimal evaluation order (a.k.a. the order in which the dynamic programming table should be filled out)
• Rearrange user code to refer to the DP table instead of recursive calls
• Run the user code in the optimal order, and print the result!

*Note that AutoDP implements true dynamic programming, which is strictly more powerful and frequently faster than simple memoization implemented through python decorators. Memoization does not obtain the optimal evaluation order, but simply stores previously encountered recursive calls.

Challenges I ran into

• I needed to gain a deep understanding of an unfamiliar python library.
• I had to keep track of interactions between two different scopes: the scope of the code of AutoDP and the user input code. The two sets of code needed to interact closely together without clobbering each other.
• The python ast library was not designed to handle extensive code revision and massaging demanded by AutoDP. I was definitely pushing the boundary of the library's capabilities.

Accomplishments that I'm proud of

• The code works on several examples, including a relatively complex two-dimensional recursive function that solves the longest common subsequence problem!
• Metaprogramming: who needs to write code when your code writes itself?

Built With

• ast
• python