Higher Order Functions Considered Unnecessary for Higher Order Programming

Joseph A. Goguen, Higher Order Functions Considered Unnecessary for Higher Order Programming (1987).

It is often claimed that the essence of functional programming is the use of functions as values, i.e., of higher order functions, and many interesting examples have been given showing the power of this approach. Unfortunately, the logic of higher order functions is di�cult, and in particular, higher order unication is undecidable. Moreover (and closely related), higher order expressions are notoriously di�cult for humans to read and write correctly. However, this paper shows that typical higher order programming examples can be captured with just rst order functions, by the systematic use of parameterized modules, in a style that we call parameterized programming. This has the advantages that correctness proofs can be done entirely within rst order logic, and that interpreters and compilers can be simpler and more e�cient. Moreover, it is natural to impose semantic requirements on modules, and hence on functions. A more subtle point is that higher order logic does not always mix well with subsorts, which can nonetheless be very useful in functional programming by supporting the clean and rigorous treatment of partially dened functions, exceptions, overloading, multiple representation, and coercion. Although higher order logic cannot always be avoided in specication and verication, it should be avoided wherever possible, for the same reasons as in programming. This paper contains several examples, including one in hardware verication. An appendix shows how to extend standard equational logic with quantication over functions, and justies a perhaps surprising technique for proving such equations using only ground term reduction.

This (old paper) proposes an interesting approach for formulating functional programs. But can this truly subsume all uses of higher order functions? I don't see the paper address how the uses of higher order functions in general can be replaced (not that I have a counterexample in mind).

Anyone familiar with the OBJ language? Do other languages share this notion of 'modules', 'theories'?