[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
In the virtual code fragment shown below, f
should be
regarded as the virtual code for a binary operator, and k
is a constant.
[[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.
k
is the
result.
x
and the
second being y
, then the result is f
(x,y)
.
f
with each pair.
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.
reduce
is neither.
k
is never used at all unless
the argument is the empty list.
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.
([[reduce
]] (f,k)
) nil
= k
([[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.
([[pairwise
]] f
) nil
= nil
([[pairwise
]] f
) (x,nil)
= (x,nil)
([[pairwise
]] f
) (x,(y,z))
=
(f (x,y),
([[pairwise
]] f
) z)
For the long version, see Pairwise.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This document was generated on December 10, 2012 using texi2html 1.82.