About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ACM Transactions on Programming Languages and Systems (TOPLAS)
Paper
On the Development of the Algebra of Functional Programs
Abstract
The development of the algebraic approach to reasoning about functional programs that was introduced by Backus in his Turing Award Lecture is furthered. Precise definitions for the foundations on which the algebra is based are given, and some new expansion theorems that broaden the class of functions for which this approach is applicable are proved. In particular, the class of “overruntolerant” forms, nonlinear forms that include some of the familiar divide-and-conquer program schemes, are defined; an expansion theorem for such forms is proved; and that theorem is used to show how to derive expansions for some programs deemed by nonlinear forms. © 1982, ACM. All rights reserved.