APL as a Functional Programming Language

E.E. McDonnell

I.P. Sharp Associates, Inc.
Palo Alto, California
 

Abstract

This paper gives an elementary introduction to the notion of functional programming, and gives examples of how to define APL functions in a functional programming style.
 

Functional programming

The term functional programming has come into use in recent years to describe a style of programming in which the application of functions to arguments is the only permitted form. The interest in functional programming comes from several sources, but one of its chief ones is a dissatisfaction with conventional programming languages, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1. In a key paper [Ref. 1], John Backus, the father of FORTRAN, gave wide exposure to these ideas. These languages are thought to have basic defects in that they essentially processing data one element at a time, and use assignment as a fundamental control form. Backus feels that APL is exempted from the first defect, because of its array orientation, but that it is still imperfect because of its use of assignment. By adhering to certain restrictions, however, it is possible to make a purely functional language out of APL. These restrictions are:

• don’t use assignments
• use the direct definition form of function definition
• don’t use global variables
   

An example

The problem is to make a table which shows all possible ways of choosing M objects from N different objects. For example, if we label the objects a, b, c, d, and e, and want to tabulate all the ways of choosing three of these, we would be satisfied with the result:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

It is often more convenient simply to make a table of the indices which can be use to select the objects, as follows:

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

The idea underlying the functions we will define is to create an incidence matrix (a matrix of ones and zeros) whose rows show the positions of the chosen objects, and to produce the matrix of indices from this incidence matrix. Thus, for our 3-out-of-5 problem we would want the incidence matrix:

1 1 1 0 0
1 1 0 1 0
1 1 0 0 1
1 0 1 1 0
1 0 1 0 1
1 0 0 1 1
0 1 1 1 0
0 1 1 0 1
0 1 0 1 1
0 0 1 1 1

Putting an APL solution together

A programmer might observe that the desired incidence matrix could be extracted from the rows of a complete truth table, as generated by an expression such as ⍉(⍵⍴2)⊤⍳2*⍵ . For example, the truth table of order 3 looks as follows:

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

The incidence matrix for the 2-out-of-3 case could be obtained fron this by selecting those rows which summed to 2, namely the fourth, sixth, and seventh rows:

0 1 1
1 0 1
1 1 0

At this point it might be noticed that using this incidence matrix will not yield the indices in lexical order. Instead of:

1 2
1 3
2 3

we would have instead:

2 3
1 3
1 2

To remedy this, we could do several things. Perhaps the simplist is to complement the truth table before doing the selection, giving us:

1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0

Now when we select the rows summing to 2, they come out in the desired order:

1 1 0
1 0 1
0 1 1

and the corresponding index rows are as we want them, too:

1 2
1 3
2 3

To put this thought together in an APL expression is for the experience APL programmer but the matter of a moment: the truth table is given by ~⍉(⍵⍴2)⊤⍳2*⍵ . (Actually, this truth table, being in 1-origin, has the first row in the last place, but that doesn’t affect our use.) Now, to select the rows which sum to the desired amount, we must perform a sum reduction of the rows of this matrix, and a comparison with the desired value, in order to produce the selector mask. Here we run into a quandary. We would prefer not to have to compute the truth table twice, for aesthetic reasons, as well as from considerations of efficiency. If we were allowed to use assignment we could create a temporary variable t and write something like:

(⍺=+/t)⌿t←~⍉(⍵⍴2)⊤⍳2*⍵ .

Lacking assignment, what can we do? A little thought will reveal that we are dealing with a fnction of ⍺ and our modified truth table. This suggests that we define a function, say k , which takes ⍺ as one argument and the modified truth table as the other. If we then write:

⍺k~⍉(⍵⍴2)⊤⍳2*⍵

it shouldn’t take too long to define:

k ⋄ (⍺=+/⍵)⌿⍵

Having done this, we can try the function out immediately:

      3 k~⍉(5⍴2)⊤⍳2*5
1 1 1 0 0
1 1 0 1 0
1 1 0 0 1
1 0 1 1 0
1 0 1 0 1
1 0 0 1 1
0 1 1 1 0
0 1 1 0 1
0 1 0 1 1
0 0 1 1 1

So far, so good. The next task will be to convert the rows of this incidence matrix, to give the column indices corresponding to the 1’s in each row. There are many different ways to do this, but we’ll choose a method that helps reinforce the point we made before on how to do without assignment.

The essential idea is to generate as many copies of the set of indices as we need, and then select the desired elements using the ravel of the incidence matrix. One way to generate the desired indices is to generate one set of indices (by ⍳⍵), reshape this to the shape of the incidence matrix, and ravel this. Thus, in the 2 out of 3 case, we could write:

      ,3 3⍴⍳3
1 2 3 1 2 3 1 2 3

We can then use the ravelled incidence matrix to select the desired index elements from this. We would get:

      1 1 0 1 0 1 0 1 1/1 2 3 1 2 3 1 2 3
1 2 1 3 2 3

Since the number of elements selected from each row is the same, this last result can be reshaped easily into the final result:

      3 2⍴1 2 1 3 2 3
1 2 
1 3 
2 3

However, we have the same problem again that we had before, because we want to use the incidence matrix as an argument to compression, and also want to use the shape of the incidence matrix as an argument to reshape.

The function we would have if we used assignment would look like this:

u ⋄ ((⍺!⍵),⍺)⍴(,s)/,(⍴s←(⍺=+/t)⌿t←~⍉(⍵⍴2)⊤⍳2*⍵)⍴⍳⍵

In this, the incidence matrix is given the name s , and then we use its shape and its ravel. Since we don’t want to use assignment, we must create another function, say i , which uses the incidence matrix as one argument, and the set of indices as another. The function i looks like this:

i ⋄ (,⍺)/,(⍴⍺)⍴⍵

We could then write:

(⍺k~⍉(⍵⍴2)⊤⍳2*⍵)i⍳⍵

which, when used with the arguments 3 and 5, would yield:

1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

It is a simple matter to reshape this: the number of rows is ⍺!⍵ and the number of columns is ⍺ . The entire comb function now would look like this:

comb ⋄ ((⍺!⍵),⍺)⍴(⍺k~⍉(⍵⍴2)⊤⍳2*⍵)i⍳⍵

and

      3 comb 5
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

The set of functions we have now preduces its result without using assignment, and without variables. In practice, we would find that the generation of the entire truth table produces an intermediate value which uses a fair amount of workspace, first because the rows which are generated only to be discarded, and second because the ⍺⊤⍵ function produces an integer result when used with integer arguments, and so, even though all the elements of the result are 1’s and 0’s, these are stored as integers, not Boolean values. Some experimentation may convince you that the function j below produces an incidence matrix of the desired kind which has only the required rows, and which is stored as a Boolean matrix:

j ⋄ (1,(⍺-1)j⍵-1),[1]0,⍺j⍵-1 ⋄ ⍺∊0,⍵ ⋄ (1,⍵)⍴⍺=⍵

This doubly-recursive function does its work by dividing the problem into two parts, and catenating the first part result on top of the second part result. The first part is obtained by catenating a 1 in front of the matrix which has ⍺-1 1’s out of a total of ⍵-1 , and the second part is obtained by catenating a 0 in front of the matrix which has ⍺ 1’s, also out of a total of ⍵-1 . The terminating condition for the function is given if ⍺ is 0 or if it is equal to ⍵ , and the result in that case is a 1 by ⍵ matrix which is either all 0’s (if ⍺ and ⍵ are unequal), or all 1’s (if ⍺ and ⍵ are equal).

A further improvement could be made to the comb function if we notice that the desired set of indices could be obtained without reference to the incidence matrix by an expression such as (⍵×⍺!⍵)⍴⍳⍵ . For example:

   (3×2!3)⍴⍳3
1 2 3 1 2 3 1 2 3

This would allow us to eliminate the function i . Putting these two thoughts together gives us the function comb and j as follows:

comb ⋄ ((⍺!⍵),⍺)⍴(,⍺j⍵)/(⍵×⍺!⍵)⍴⍳⍵
j ⋄ (1,(⍺-1)j⍵-1),[1]0,⍺j⍵-1 ⋄ ⍺∊0,⍵ ⋄ (1,⍵)⍴⍺=⍵

A more elaborate use of APL in a functional programming style may be found in reference [2].
 

Function programming enhancements to APL

Several of the additions proposed for APL would increase its suitability as a functional programming language. Among these are many new operators and an indexing function.

Backus writes that a proper set of operators is required in a functional programming language. He claims that APL, which only has four operators of reduction, inner product, outer product, and axis, doesn’t have enough of these forms. However, the principal thrust of the work of K.E. Iverson over the last several years has been in the direction of increasing the number of operators in the language. Already, in SHARP APL the three composition operators ¨ ⍤ ⍥ have been introduced, in a limited fashion, and several more have been discussed and will undoubtedly be implemented one day. For details of these operators, see references [3 4 5 6].

Indexed assignment is frequently used to make modifications to a part of an array. If assignment is not permitted in functional programming, some alternative method of achieving this would be necessary. One proposal [Ref. 3] to do this uses a new Indexing-function, together with one of the composition operators. Thus, to replace with New-values the elements in an Array selected by an Index, one would write:

New-values Index¨Indexing-function Array