The API Problem as a Particular Recurrence Problem
Vector 14:1, page 140
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 140
The problem discussed in Robert Bernecky’s letter in Vector 13.4 p.7 concerns the inconvenience of programming recurrence and iteration algorithms in APL. This problem is critical for APL for the following reason: a major advantage of APL is its conciseness, but the better part of recurrence and iteration algorithms must be coded in FORTRAN style, e.g. by loops. You must do this not on account of impossibility in principle, but because the concise APL expressions process the work extremely slowly or are extremely expansive in memory usage.
For example, you can solve the API problem, mentioned in the last three Vectors, with the following APL expressions (in DyalogAPL):
or
where k is 0.5 and p is 1 2 3 4 in Roger Stokes’ example, but they are only quasi-solutions, because they give WS FULL or work too slowly if p is rather long.
I have faced this problem in teaching computational methods to students of applied mathematics. On the one hand APL is convenient for showing the essence of some method, to code it rapidly and to make experiments with it. On the other hand, if we use loops, the program runs slowly. And very often we can program the method in APL style, without loops, by using "each" or "scan"; such solutions are elegant, but they work extremely ineffectively!
For example, the Euler solution of differential equations can be programmed in modern APL as Euler\N/x0, where N is the number of points in the solution, x0 is the initial point (it can be a vector) and Euler is a simple function, which describes one step of the solution. This solution works, but is extremely slow! (As well as Robert Bernecky I had made some timing experiments for optimal loop organization; really the best is using the "pre-allocation" practice — this result was distressing for me).
Moreover, I have seen that all recurrent problems of type
can be solved by the scan operator F\N/⊂x1 x2 … xk (even in the case when x is an arbitrary array)! Function F depends on function f and has dummy left argument. But unfortunately, in practice the expression F\x is calculated as F/¨x except in the cases when F is a associative primitive function. You can see that in the case where the function F is associative, the resulting elements of F\ can be calculated recurrently. The other case is where the function F does not depend on the left argument. But in the general case the resulting elements cannot be calculated recurrently because of APL conventions about the sequence of calculations and the Scan Operator.
A more general form of recurrent (and iteration) calculations is
where \(a\) is the set of parameters, \(i\) is the index (or multi-index). The API problem is one example; in the API problem k=1 and a = k p (here k and k differ). What is very important, is that almost all classical computational methods can be represented in such form (\(x\) can be a nested array).
The problem that is discussed in Vector is that we can not avoid loops in some recurrence problems and that loops work slowly in APL. Robert Bernecky says that "It is time for APLers to admit that iteration has its place in a programmer’s toolkit". I don’t think so.
Really, why is looping not usual for APLers? The reason is that many cycles are hidden into assembler codes automatically by the interpreter. The history of APL is the history of cycle-hiding (at first reduction, scan, inner and outer product, then each). Why must we make an exception for recurrence? It is inconsistent to have the eclectic mixture of styles in APL. And it is quite impossible to expect that any sober-minded person will credit that he must solve the recurrence (iteration) problem with APL.
If the function \(f\) in (2) is "compilable" (that is if it can be represented as an executive module), then the recurrent cycle, which calculates the recurrent sequence can also be written in computer codes — it is quite a simple cycle (it is the nested cycle if \(i\) is multi-index). Robert Bernecky proposes to make it in three steps: at first you write cycle in APL, then APEX translates the APL code into C, then compile it into an executive module. I think this procedure should be automated. My proposition is to introduce into APL a new operator — the recurrence operator.
I published this proposition in our Russian-language journal "APL¨Club" in January 1997 and I hope to report it in Toronto. The main idea is to introduce a new primitive operator, for example, with the name "recurrence" (I suppose it can be a new symbol "⊢" like ⊥ swinging 90 degrees clockwise), with operand \(f\). The arguments of the derived function are \(a, x_1,x_2,\ldots,x_k\). The structure of these arguments characterises the dependence or independence of \(i\). Such an operator, not primitive but defined, is presented in my paper. It contains the cyclic analogues to Robert Bernecky’s "api3", but in general form. Note that my recurrence operator is ideologically close to Norman Thomson’s operators for iterative computations (see, for example, APL Quote Quad 25.1).
The solution of the API problem would be the following:
where Api is defined as follows:
When I use my defined operator RecIt instead of "recurrence", the time of solution is 19 seconds for 10000 elements of p (on my 486/DX2-66). If the recurrence operator were realized internally we should solve the API problem (and all other recurrence/iteration problems) in APL-style and with a speed no slower than in FORTRAN.
Andrei Buzin
RusAPL
Calculating Centre of Russian AcSc.