Using Obscure Graph Theory to Solve Programming Languages Problems

Summary

Usually I write about solutions to problems I’ve worked out, but I’ve found myself increasingly becoming interesting in where solutions come from. Maybe it’s because I’ve been reading Boorstin’s excellent The Discoverers, which I’d strongly recommend. Regardless of why, I thought I’d switch up the usual dance step today, and discuss what solving my most-recent-big-problem actually looked like, in terms of what I tried, where I looked, and what the timeline was. The Problem The problem is to serialize a program graph into a series of let-bindings. For example, given the following graph: + / \ f ---> g | / \ a \ / expensive which represents the program: f a (g expensive expensive) + g expensive expensive Unfortunately, this is a naive representation of the program, since it duplicates the work required to compute expensive four times, and g expensive expensive twice. Instead, we would prefer to generate the equivalent-but-more-efficient program: let $0 = expensive $1 = g $0 $0 in f a $1 + $1 This transformation is affectionately known as sharing, since it shares the computed answer whenever there is repeated work to be done. So this is what we’re trying to do. Given the original graph, determine the best place to insert these let-bindings, for some reasonable definition of “best.” We can assume there are no side effects involved, so any place that an expression is well-scoped is an acceptable solution. In order to understand some of my attempted solutions, it’s worth noting that our final solution should build something of type Expr, and the original graph is represented as a IntMap (ExprF Int). ExprF is the Base functor of Expr, with all of its self-references replaced by some type variable, in this case Int. Thus, the graph above looks much more like: _ : IntMap (ExprF Int) _ = IM.fromList [ (0, Apply "+" [1, 3]) , (1, Apply "f" [2, 3] , (2, ...) -- a , (3, Apply "g" [4, 4]) , (4, ...) -- expensive ] The Original Solution I spent over a year trying to solve this pro...