Origami Programming for Fun and Profit

Abstract

Tony Hoare famously observed in his Notes on Data Structuring in 1972 that “there are certain close analogies between the methods used for structuring data and the methods for structuring a program which processes that data”. A few years later in 1975, Fred Brooks wrote in The Mythical Man-Month: “Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.” In the same year, Michael Jackson wrote in Principles of Program Design that “data provides a model of the problem environment, and by basing our program structures on data structures we ensure that our programs will be intelligible and easy to maintain.” This may be old news, but it is still good news. Today, we see it in higher-order functions that capture the structured program schemes associated with recursive datatypes - the maps, folds, unfolds, and traversals of modern functional programming. Hoare’s “close analogies” reveal themselves through beautiful programs, perfectly adapted to the data they consume and produce, functions following form. I will explain how this works, and show a bunch of pretty examples.