C++Next

[please see the preface post for information on getting starting with this study group. Also see Sean Parent's introductory post on this chapter.]
There are two threads running through this chapter: One is the mathematical structure of regularity and associativity, the other are the applications and “engineering” aspects related to optimizing functions.

Definitions:

BinaryOperation

An operation that takes two arguments

Associativity

BinaryOperations that have the associativity property may be freely regrouped without altering the result. More formally, for all a,b,c in Domain(Op) op(op(a,b),c) = op(a,op(b,c,))

Linear Recurrence

Informally, a linear recurrence is an equational representation of a sequence. A linear recurrence can be expressed as a function where the kth element is equal to a polynomial (expressed as an inner product between coefficients a, and the k-1…k-n-1 preceding terms).

Computing Powers

A binary operation that is associative may be applied repeatedly and this repeated application of the function can be viewed as raising the operation to a power. With this knowledge and the framework of transformations and orbits that was introduced in Chapter 2 the authors prove Theorem 3.1 that an element of finite order has an idempotent power.

Program Transformation

Starting with a recursive definition of the power function that implements a binary (“egyptian”) exponentiation routine, the authors apply several strategies to optimize the power function. The strategies employed are to eliminate common sub-expressions, convert the function to tail recursive form using an accumulation variable, and finally transform the function from a tail-recursive to an iterative implementation that computes the nth power of a function in logarithmic time.

Special Case Procedures

In addition to the techniques employed above, the authors discuss the strategy of building in optimized algorithms into to “computational basis” of the type. The example given is for an Integer type.

Parameterized Algorithms

Once the power function has been optimized in terms of minimizing operations performed the authors turn to making the algorithm more general (i.e., abstract). This was partially achieved in the preceding section by altering the Integer type, in addition they take a functor as a parameter to apply different operations.

Linear Recurrence

Using the foundation built up in this chapter the authors demonstrate a very surprising algorithm to compute the nth term in a linear recurrence (in this case the Fibonacci sequence) in logarithmic time.

Accumulation variables

The last section returns to the idea of accumulation variables that act somewhat like a reduce operation in that they change the state of an object (and accumulate the result) by combining binary ops (e.g., x = op(x,y))