Remembering Professor Susan B. Horwitz

[Guest poster Thomas Ball of Microsoft Research remembers his Ph.D. advisor, Professor and programming languages researcher Susan Horwitz, who recently passed away. –Mike]

Remembering Professor Susan B. Horwitz

By Thomas Ball, Microsoft Research 

Susan B. Horwitz

I graduated from Cornell University in the spring of 1987 with a B.A. in Computer Science, having worked with Professor Tim Teitelbaum on the Synthesizer Generator project. Tim had recommended that I apply to the University of Wisconsin – Madison for graduate school, where his Ph.D. advisees Susan Horwitz and Thomas Reps were professors. I arrived Madison in the fall of 1987 and loaded up on graduate courses.

Based on my familiarity with the Synthesizer Generator, Susan generously offered me a research internship for the summer of 1988. Now I don’t remember much of what I accomplished technically that summer, as I had just started dating the woman who would become my wife.

The first piece of recorded technical work I did with Susan was to prove correct an algorithm that she and Tom had designed as part of the Wisconsin Program Integration System (WPIS, now known as the Wisconsin Program-Slicing Project). This was a lot of fun, as I learned tons from Susan about dataflow analysis, program slicing, the program dependence graph (PDG), and proving algorithms correct.  The proof effort paid off – I found a bug in their algorithm!

As a result of this work, Susan offered me a research assistantship working on WPIS, which supported me from 1990-1993.  Working on the project was a great experience, especially as it offered a front row seat during Susan and Tom’s spirited technical discussions. It was an intense immersion into things program analysis – every WPIS graduate student had two advisors for the price of one!  Susan and I worked together on the problem of slicing programs with arbitrary intra-procedural control-flow. I presented our paper in Sweden at the 1993 Algorithm and Automated Debugging Workshop, where this work won a best paper award.

Another problem in program slicing that Susan worked on was interprocedural program slicing.  Using the PDG, one computes a program slice via a backwards transitive closure or reachability operation on the PDG. For a program with multiple procedures, such an approach yields slices much larger than necessary because when the backwards reachability descends into procedure bar from caller foo it doesn’t “remember” this context and then can ascend to different callers of bar other than foo.  The solution to this problem was to use an attribute grammar to place restrictions on the reachability so that it properly follows the call/return structure of a program.  Susan’s PLDI 1988 paper on the topic, “Interprocedural Slicing using Dependence Graphs”, with Tom and Dave Binkley, was selected in 2003 as one of the 50 best papers to appear in the PLDI conference in the last 20 years.

Later on, Susan, Tom and Mooly Sagiv realized that this idea of grammar-restricted reachability (now called context-free language reachability) had applications to program analysis.  Their POPL 1995 paper “Precise Interprocedural Dataflow Analysis via Graph Reachability”, also known as the RHS algorithm, showed how interprocedural, finite, distributive, subset problems can be solved efficiently by transforming them into the problem of graph reachability along interprocedurally realizable paths.  At Microsoft Research in 2000, Sriram Rajamani and I created a symbolic version of the RHS algorithm, using binary decision diagrams, as part of the SLAM software model checking project, which gave rise to the Static Driver Verifier tool.   At the same time, Manuvir Das created the ESP static analyzer using a different variant of the RHS algorithm.  Both tools are still in active use at Microsoft today.

Friedrich Nietzsche famously said: “Without music, life would be a mistake.” Music was a huge part of Susan’s life – she minored in music as a graduate student at Cornell, which was lucky for me, as I planned to minor in music history at Wisconsin. Many professors counseled their students to minor in a subject that would aid them more directly in their dissertation work.  Susan appreciated the connection between the arts and science and how each gives inspiration to the other. She was an excellent pianist and loved playing music with others. In emails we exchanged during her last months, she told me of a piece for flute and piano four-hand that Tom recently had found for her and that she played with her family and friends. Susan supported many arts organizations and recently served on the Board of Directors of the Bach Dancing and Dynamite Society.

Susan was a devoted and inspirational educator (see the number of awards she received for teaching on her home page). Over the last decade, Susan focused on increasing the number of underrepresented students in Computer Science. Among other activities, she designed and launched the Wisconsin Emerging Scholars-Computer Science program (WES-CS) to attract students at Wisconsin to Computer Science. This program uses student-led group meetings to work on problems specifically designed to help them understand and enjoy the topics taught in the introductory programming class.

If you wish to celebrate Susan’s life and achievements, please consider making a donation to the Susan B. Horwitz WES-CS Endowment at the University of Wisconsin Foundation (http://bit.ly/wes-cs) or the Bach Dancing and Dynamite Society (P.O. Box 2348; Madison, WI 53701).