Design Patterns as Higher−Order Datatype−Generic Programs

Abstract

The purpose of this tutorial is to draw together ideas from the Design Patterns community (the Gang of Four: Gamma, Helm, Johnson, Vlissides) and the Functional Programming world (eg Bird, Meertens, Hughes). In particular, the thesis is that whereas design patterns must be expressed extra-linguistically (as prose, diagrams, examples) in object-oriented languages, they may be captured directly as abstractions using higher-order operators in functional programming languages. Therefore, they may be reasoned about, type-checked, applied and reused, just as any other abstractions may be. \par We argue this case by developing the idea of higher-order operators, specifically for capturing patterns of computation in programs. We then build on this to show how the intentions behind a number of the Gang of Four patterns—such as Composite, Visitor, Iterator, and Builder—have higher-order operators as their analogues in functional languages. Specifically, the structure of these patterns is determined essentially by the structure of the data involved, and they can be captured as generic programs parametrized by that datatype. \par The aim is to give greater insight into and understanding of already-familiar patterns.