4   Identification of Scans

4.1   An Operator to Denote Scans

The sum of the elements of a vector v can be computed by the mere expression sum(v(1:n)). With our operator the syntax is a bit more complex :

Scan({ i | 0 <= i <= n }, ( [1] ), +, v, 0)

This operator is described in more details later but one can note that the binary operation to be applied (here the + operation) is given as a parameter. The first two parameters (the accumulation domain and the direction) state that the reduction takes into account the elements of v from subscript 1 to n with a step of 1. Subscript 0 is for the initial value which is the last parameter. Moreover the Scan operator computes the whole set of partial results. In the example, only the last value of the resulting vector is needed:

Scan({ i | 0 <= i <= n }, ( [1] ), +, v, 0) [n]  

• an array a of values to be reduced;
• an array b of initial values;
• a set of arrays x₁,...,x_n with the same shape as a and where n is the dimension of b. These arrays determine the place where each value in a is to be accumulated.

The classical example of a multi-directional scan is the sum of the elements of a matrix:

s=0
DO i=1,n
 DO j=1,n
   s=s+a(i,j)
 END DO
END DO

In the equivalent system of equations, the piecewise rectilinear path appears clearly:

v2[i,j] =
   case
    { i,j | i=1, j=1 }        : a[i,j] ;
    { i,j | 2<=i<=n, j=1 }    : v2[i-1,n] + a[i,j] ;
    { i,j | 1<=i<=n, 2<=j<=n }: v2[i,j-1] + a[i,j] ;
   esac ;

This path may be defined by two vectors (the two directions of the multi-directional scan) (

1

0

) and (

0

1

). The second direction is used until the last element of a row and then the first direction is used to skip to the next row which must be scanned from the beginning to the end, and so on. Since the path iterates the whole array, only one scan is defined here (and not an array of scans). Hence, the domain of the initial value is the single point (1,1). To summarize, the Scan expression to compute the sum of the elements of a matrix a is:

Scan( { i,j | 1<=i<=n, 1<=j<=n }, ( [1 0] [0 1] ), +, a, a[1,1])

4.2   Scan Recognition

1. A basic term is a term.
2. If t₁, ..., t_n are terms, and if w is an operator with ¶(w) = n, then w(t₁, ..., t_n) is a term. w is the head of this new term, and t₁, ..., t_n are its arguments.
3. There are no other terms.

4.2.1   Simple pattern matching

4.2.2   Partial Normalization

Let us take as O the set {+, -, *} with the usual properties: associativity and commutativity of + and *, the rule of signs, distributivity of * with respect to +, and the familiar rules of arithmetic (2 + 2 = 4 and so on). If t is tractable for this set of operators, its normal form is a polynomial in v_i-1 whose coefficients are combinations of its elementary terms. As we have seen earlier, such a polynomial is associated to a scan if it is linear:

v_i = a_i v_i-1 + b_i .

There are two simple cases : a_i = 1, which gives a sum, and b_i = 0, which gives a product. In the general case, we may compose two linear functions and show that the result is still linear:

a(cx + d) + b = (ac) x + (ad + b) .

This gives the associative companion function:

lin

æ è

æ è

a b

ö ø

,

æ è

c d

ö ø

ö ø

=

æ è

ac ad + b

ö ø

.

In fact, since linear functions are a subfamily of the homographic functions which is closed under composition, this is a special case of an earlier observation.

4.2.3   Recurrences on finite domains

1. Compute the tables associated to each f_i.
2. Combine these tables by any tree reduction scheme to get the functions g_i of (8).
3. The results of the scan are given by:
   v_i = g_i(v₀) .

    do i = 1,n
      f3(i) = f2(f1(i))
    end do

4.2.4   A possible organization for a scan recognizer