Implicit Parallelism Due to Lack of Anti-dependences
In functional languages, there is no such thing as a variable whose value can change during the computation. Rather, a variable behaves like a mathematical variable, having a unique value that is computed (or "solved") by the program.

Multiple definitions of a variable are simply not allowed and all computations are expressed in terms of computing new values from old. For example, given A, a vector of numbers, suppose we want to scale it by 5; that is, the result should be a vector whose i'th component should be 5A(i). In Fortran, we might say:

do i = 1,N
        A(i) = 5 * A(i)
end do

and A itself contains the result. Further, the old value of A is no longer available. In functional languages, such a concept does not exist; instead, we define a new vector based on the old. For example, in pH

b = array (1,n)
        [(i, 5 * a!i) | i <- [1..n]]

(In Haskell, array indexing is denoted by the infix "!" operator.) This defines b, a new vector with index range 1 to n, such that b(i) = 5a(i). Nothing has happened to a-it still means exactly what it used to mean. For example, we could now produce a third vector c that is the vector-sum of a and b:

c = array (1,n)
            [(i, a!i +b!i) | i <- [1..n]]

Matrix multiplication may be expressed in pH as follows:

matmult a b =
    matrix ((1,1), (n,n))
                [((i,j), ip A i B j) | i <- [1..n], j <- [1..n]]

ip A i B j =
    let
        s = a!(i,l) * b!(l,j)
    in
        for k <- [2..n] do
            next s = s + a!(i,k) * b!(k,j)
        finally s

The first part defines the function matmult, which takes two arguments-the matrices a and b. It produces a new n x n matrix whose (i,j)'th component is the inner product of the i'th row of a with the j'th column of b.

(pH permits us to extract size information from a matrix, but since this representation choice is orthogonal to whether a language is functional or not, and since we want to keep the example simple, we assume that a and b are n x n matrices.)

The second part defines the inner product function ip. The let statement binds the value of a(i,1) x b(1,j) to a variable s. Although the loop may superficially look like the corresponding Fortran loop, it is fundamentally different-it expresses the idea of n separate and concurrent computations:

sl = a!(i,j) * b!(1,j)
s2 = s1 + a!(i,2) * b!(2,j)
s3 = s2 + a!(i,3) * b!(3,j)

sn = s(n-1) + a!(i,n) * b!(n,j)

The first computation is the one outside the loop (the let-binding), and sn, the final s, is the value of the entire loop. In other words, there are n different values of s; the next notation simply relates each sk to its corresponding s(k-1); and the finally term just specifies which s is returned as the result value of the whole loop (and, in turn, the function).

The statements of a loop are all executed concurrently, limited only by data dependencies (although the data dependencies in this particular loop do not admit much parallelism other than doing the multiplications in parallel). Thus, it is not the case that s is a variable that is being updated, as in the Fortran loop-each variable still has a unique definition.

The pH program for matrix multiplication directly expresses the structures in original figures at the start of this series of articles, illustrating the mathematical definition. In particular, it takes no position on the order in which computations are done, beyond the natural ordering of data dependencies.

Since variables never change, there cannot ever be any antidependencies. It is for this reason that functional languages are considered to be "naturally parallel" languages.