Using obscure graph theory to solve programming languages problems

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: + g expensive expensive 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 = exp ... Read full article.