Affiliations: Departamento de Informática, Universidade do
Minho, Campus de Gualtar, 4710-057 Braga, Portugal. [email protected];
[email protected]
Note: [] Address for correspondence: Departamento de Informática,
Universidade do Minho, Campus de Gualtar, 4710-057 Braga, Portugal
Abstract: Functional programs are particularly well suited to formal
manipulation by equational reasoning. In particular, it is straightforward to
use calculational methods for program transformation. Well-known transformation
techniques, like tupling or the introduction of accumulating parameters, can be
implemented using calculation through the use of the fusion (or promotion)
strategy. In this paper we revisit this transformation method, but, unlike most
of the previous work on this subject, we adhere to a pure point-free calculus
that emphasizes the advantages of equational reasoning. We focus on the
accumulation strategy initially proposed by Bird, where the transformed
programs are seen as higher-order folds calculated systematically from a
specification. The machinery of the calculus is expanded with higher-order
point-free operators that simplify the calculations. A substantial number of
examples (both classic and new) are fully developed, and we introduce several
shortcut optimization rules that capture typical transformation patterns.
Keywords: Functional Programming, Program Transformation, Program Calculation, Point-free Programming, Accumulation Strategy
