Algorithms for functional programming: the premise
Algorithms for functional programming is a textbook on algorithms and data structures, presented in a purely functional style and exemplifying the functional programmer's approach to algorithm design and implementation.
The building blocks of programs created in this style are functions, in the mathematical sense of the word: well-defined formal entities that receive values as arguments and yield values as results. Functions have no internal state. Given the same arguments, therefore, a function always yields the same results, regardless of the context in which it is applied. This invariant behavior simplifies many algorithms and makes it easier to determine their preconditions and postconditions exactly, to prove their correctness, and to analyze their resource use.
A second characteristic of the functional programming style is the treatment of functions as values that can be transmitted as arguments to other functions, yielded as results by other functions, and constructed and invoked during program execution. Programming languages that support this style provide convenient and concise ways of expressing such operations.
Algorithms for functional programming uses Scheme as its implementation language. Scheme supports functions as values within its “procedure” type. (This type also includes entities that receive arguments and yield results, but do not qualify as pure functions because they have internal states, and their results can depend on those states as well as on the arguments that the procedure receives.)
Scheme is defined by a de facto standard, the Revised6 report on the algorithmic language Scheme. This standard defines a base language and a set of standard libraries that make it exceptionally easy to specify extensions, subsets, and variants that are tailored to specific projects. The language variant used in Algorithms for functional programming is designed to exclude many of Scheme's non-functional constructions and to supplement the Scheme base and standard library with additional operations that support the functional style.
Algorithms for functional programming currently exists as an incomplete draft, which I developed during previous leaves from my job as a teacher of computer science and system and network administrator at Grinnell College. Initially, this blog will follow the development of this draft into a finished book. After that, my intention is to announce here any supplements and extensions to the book, or other news related to it, and perhaps more generally to report and discuss discoveries and events in this field.