2.7.13.3 Reduce

In the virtual code fragment shown below, f should be regarded as the virtual code for a binary operator, and k is a constant.

T24

[[reduce]] (f,k) = ((nil,nil),((f,k),nil))

By constructing a tree in the form shown, the silly mnemonic reduce effectively constructs the code for a function operating on lists in a particular way.

The effect of evaluating an application in this form with an argument representing a list can be broken down into several cases.

• If the list is empty, then the value of k is the result.
• If the list has only one item, then that item is the result.
• if the list has exactly two items, the first being x and the second being y, then the result is f (x,y).
• If the list has more than two items and an even number of them, the result is that of evaluating the application with the list of values obtained by partitioning the list into pairs of adjacent items, and evaluating f with each pair.
• If the list has more than two items and an odd number of them, the result is that of evaluating the application with the list of values obtained by partitioning the list into pairs of adjacent items excluding the last one, evaluating f with each pair, and then appending the last item to the list of values.

In the last two cases, evaluation of the application is not necessarily finished after just one traversal of the list, because it has to carry on until the list is reduced to a single item.

Some care has been taken to describe this operation in detail because it differs from comparable operations common to functional programming languages, variously known as fold or reduce. All of these operations could be used, for example, to compute the summation of a list of numbers. The crucial differences are as follows.

• Whereas a fold or a reduce is conventionally either of the left or right variety, this reduce is neither.
• The vacuous case result k is never used at all unless the argument is the empty list.
• This reduce is not very useful if the operator f is not associative.

The reason for defining the semantics of reduce in this way instead of the normal way is that a distributed implementation of this one could work in logarithmic time, so it’s worth making it easy for a language processor to detect the pattern in case the virtual code is ever going to be targeted to such an implementation. Of course, nothing prevents the conventional left or right reduction semantics from being translated to virtual code by explicit recursion.

The precise semantics of this operation are as follows, where f is not nil, k is unconstrained, and pairwise represents a function to be explained presently.

P29

([[reduce]] (f,k)) nil = k

P30

([[reduce]] (f,k)) (x,y) =
[[left]] ([[bu(iterate,right)]] [[pairwise]] f) (x,y)

The latter property leverages off some virtual machine features and silly code that has been defined already. The function implemented by [[pairwise]] f is the one that partitions its argument into pairs and evaluates f with each pair as described above. The combination of that with bu(iterate,right) results in an application that repeatedly performs [[pairwise]] f while the resulting list still has a tail (i.e., a right side), and stops when the list has only a single item (i.e., when right is false). The left operation then extracts the item.

For the sake of completeness, it is tedious but straightforward to give an exact definition for pairwise. The short version is that it can be anything that satisfies these three equations.

E1

([[pairwise]] f) nil = nil

E2

([[pairwise]] f) (x,nil) = (x,nil)

E3

([[pairwise]] f) (x,(y,z)) = (f (x,y),([[pairwise]] f) z)

For the long version, see Pairwise.

This document was generated on November 8, 2012 using texi2html 1.82.