Functional Programming in J (Part 4)
Vector 13:4, page 23
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 23
This is the last part of a four-part article. Part I (in Vector 13.1) presented fundamentals of J in a framework of functional programming strategies, with examples expressly aimed toward developing an illustrative program to generate prime numbers. Parts II and III (in Vector 13.2 and 13.3) demonstrated how to develop the program directly, while characterizing a J programmer’s thinking, and continued development of the same program with higher-level strategies. Part IV (here) presents alternative algorithms for iterative, recursive, and array-processing programs, then ends with meta-strategies for packaging and documentation.
Parts I – III presented these functional programming strategies:
- Think Arrays
- Select Primitive Functions
- Select Primitive Operators
- Use Parallel Processing
- Name Utility Functions and Variables
- Compose Functions (Define Programs)
- Test and Debug Programs
- Modularize Programs
- Simplify, Optimize, and Generalize Programs
We continue with two final programming strategies for the same programming task of generating prime numbers.
9. Consider Alternative Algorithms¶
It is wise to consider alternative algorithms as a strategy for improving on a programming task — even after completing a working program. Developing different programs may lead to new or better ideas. In any case, the programs may be compared and the best one selected.
J offers iteration, recursion, and array processing — three possible approaches for developing programs. We will present programs for each of these approaches and compare them.
Array Processing¶
First, consider generating primes by array processing. (The following algorithm is an alternative to the one developed in Parts I – III.) Begin with a list of consecutive integers greater than 1 (using utility verb To =. }. i.@>: from Part II):
Then create a table of products of all pairs of these integers:
p */ p NB. p Times-Table p
4 6 8 10 12 14 16 18 20 22 24 26
6 9 12 15 18 21 24 27 30 33 36 39
8 12 16 20 24 28 32 36 40 44 48 52
10 15 20 25 30 35 40 45 50 55 60 65
12 18 24 30 36 42 48 54 60 66 72 78
14 21 28 35 42 49 56 63 70 77 84 91
16 24 32 40 48 56 64 72 80 88 96 104
18 27 36 45 54 63 72 81 90 99 108 117
20 30 40 50 60 70 80 90 100 110 120 130
22 33 44 55 66 77 88 99 110 121 132 143
24 36 48 60 72 84 96 108 120 132 144 156
26 39 52 65 78 91 104 117 130 143 156 169
Here the adverb / uses * (Times) to produce a new verb */ (called Times-Table when used with two inputs) which then multiplies every item in p (on the left) by every item in p (on the right) in pairs. Define a verb for this:
Composites p produces the table above. To get the primes, remove the composites from the list p:
The verb -. (called Less when used with two inputs) removes the items on the right from the items on the left. Now define the main program:
An example of its use:
Since excessive space is required to create the table of composites, this program can certainly be improved by truncating the inputs to */ in about half. First, define a utility verb to obtain the last item in an input list:
And define a subprogram:
Half =. 2: To <.@-:@Last NB. Half is Two To
NB. ((Floor Atop Halve)
NB. Atop Last)
NB. where <. is Floor
NB. and -: is Halve
This generates integers from 2 to the integer part of half of the last item in the input list. For example:
Then revise program Composites accordingly:
This computes the composites needed (with much less excess). For example:
Composites 2 To 13
4 6 8 10 12 NB. 2 * 2 3 4 5 6
6 9 12 15 18 NB. 3 * 2 3 4 5 6
8 12 16 20 24 NB. 4 * 2 3 4 5 6
10 15 20 25 30 NB. 5 * 2 3 4 5 6
12 18 24 30 36 NB. 6 * 2 3 4 5 6
The main program works the same as before:
This program is quite efficient for such small input lists. However, for longer lists, the space required to to create such a table of composites can push a microcomputer’s limits. We can do somewhat better by truncating one side of the */ table with SquareRoot (%:) instead of Halve (-:). Thus:
Root =. 2: To <.@%:@Last NB. Root is Two To
NB. ((Floor Atop SquareRoot)
NB. Atop Last)
Composites =. Root */ Half NB. Composites is
NB. Root Times-Table Half
This uses less space and is faster. Let’s obtain actual benchmarks. First, replace the subprograms with their primitives, using Fix (as shown in Part III):
Then use the utility verbs Time =. 6!:2 and Space =. 7!:2 (introduced in Part III):
These benchmarks were obtained on a 486 PC running JFW (J Freeware for Windows) Release 3. Although this program is significantly (about 11 times) faster than the previous array-processing program (optimized in Part III), space is a growing problem.
Recursion¶
As an alternative, now consider a recursive approach. The overall structure of a recursive program in J is:
where Recurse is a composed verb which uses the defined Program itself (and other verbs); Default is a verb which returns a result for the degenerate case; and Else is a conjunction which ties the two verbs together. When is a conjunction which executes the first verb (Recurse) if Test returns 0 (false) or the next verb (Default) if Test returns 1 (true). This is J’s version of a "case structure" (see [1] for details). First, be sure to define the utility conjunctions in order to use names for J primitives ` (called Tie) and @. (called Agenda):
Then the common introductory example of computing a factorial recursively can be defined as follows:
Fac =. (] * Fac@<:) Else 1: When (] = 1:)
NB. Fac is ((Input Times (Fac Atop Decrement))
NB. Else One) When (Input Equal One)
NB. where verb 1: returns the constant 1
NB. and Decrement (<:) subtracts one
In other words, for positive integer input n, Fac(n) is n*Fac(n-1) recursively until n=1, when it defaults to 1. For example:
This result is computed as follows: Fac 5 is 5*Fac 4. Fac 4 is 4*Fac 3. Fac 3 is 3*Fac 2. Fac 2 is 2*Fac 1. Fac 1 is 1. So, Fac 2 is 2*1. Fac 3 is 3*2*1. Fac 4 is 4*3*2*1. And Fac 5 is 5*4*3*2*1 or 120.
Incidentally, Factorial (!) is a primitive verb in J:
Another classic example of (double) recursion is computing the nth number in the Fibonacci sequence (1 1 2 3 5 8 13 21 34 55 …) defined in J as follows:
Fib =. (Fib@<: + Fib@<:@<:) Else 1: When (] < 3:)
NB. Fib is (((Fib Atop Decrement) Plus
NB. ((Fib Atop Decrement) Atop Decrement))
NB. Else One) When (Input LessThan Three)
NB. where verb 3: returns 3
For a positive integer input n, Fib(n) is Fib(n-1) plus Fib(n-2) recursively until n<3, when the default is 1. For example:
Now let’s return to the task of generating prime numbers and develop (top down) a recursive program using the well-known algorithm called "Sieve of Eratosthenes": given a list of consecutive integers beginning with 2, take the first number, remove all its multiples, and repeat, taking the next remaining number, removing its multiples, etc. Begin with definition of a verb, named Primes, which will call itself:
Primes =. (First , Primes@Sieve) Else ] When Done
NB. Primes is ((First Append
NB. (Primes Atop Sieve))
NB. Else Input) When Done
NB. where Append (,) joins items
For an input list of integers, Primes returns the first integer followed by the primes remaining after doing Sieve, recursively until Done, when the default is the (successively reduced) input list.
First is a utility verb to get the first item in an input list:
Sieve is defined as follows, using If =. #~ and Divides =. | = 0: (subprograms from Part I):
Not is a utility verb named for the primitive verb Not (-.) which converts every 1 to 0 and every 0 to 1:
In other words, Sieve selects from its input those integers which are not divisible by the first integer. For example:
Doing Sieve again on that result:
Note that sieving twice is sufficient to get all primes up to 13: 2 (the first integer in the first Sieve), 3 (the first integer in the second Sieve), and 5 7 11 13 (the integers remaining). It is not necessary to do Sieve again if the first number remaining in the list exceeds the square root of the last number; that is, it is not possible to eliminate any more. This suggests how to define subprogram Done to stop the recursion:
In other words, Done compares the first number in its input list with the square root of the last number and returns a 1 (true) if it is greater, otherwise a 0 (false). For example:
Done 3 5 7 9 11 13 NB. Test after first recursion
0 NB. 3 > %:13 is false
Done 5 7 11 13 NB. Test after second recursion
1 NB. 5 > %:13 is true
A simpler definition of Done =. # = 0: would stop the recursion when the list input to Primes becomes empty, but this is far less efficient — increasingly so for longer lists. Now execute the main program:
Benchmarks:
Primes =. Primes f. NB. Primes Fixed in primitives
Time 'Primes 2 To 1000'
0.097
Space 'Primes 2 To 1000'
49492
This is much faster and more economical on space than the previous array-processing program, but still requires a stack of program calls which would betray its efficiency for longer input lists. (Also see [2] for an alternative recursive definition.)
Iteration¶
Iteration is a common approach. In J, there are several ways to apply a verb repeatedly. To begin with, iteration is implicit in "parallel processing"; that is, the same verb can be performed on all items in an array — without looping and counters — as shown in previous examples (from Part I) such as:
3 | 9 10 11 12 NB. Remainders of a list
0 1 2 0 NB. Result is a list
1 2 3 4 + 9 10 11 12 NB. (1+9),(2+10),(3+11),(4+12)
10 12 14 16 NB. Parallel sums
Another way to iterate in J uses the adverb / (Insert) which applies a given verb between items of an array (one input). (See Part I for introduction.) For example, +/ adds up a list of numbers:
J also permits explicit iteration of a verb on its own results. A function to a power such as f4(x) or f(f(f(f(x)))) in conventional mathematical notation would be f^:4 x in J. The conjunction ^: (called Power) requires two inputs: a verb (on the left) and the number of times to repeat it (on the right). For instance, consider iterating cosine:
The primitive verb o. (called Circle when used with two inputs) contains a family of trigonometric functions (see [1]), including cosine. For example:
Iterate this on itself four times — Cos(Cos(Cos(Cos 1))):
Or use a list to show the sequence of iterations:
We could iterate further, seeking convergence to a fixed point, but J offers a symbol (_) called Infinity which will cause Power to iterate as many times as needed until the result doesn’t change:
In effect, this solves the equation cos(x)=x (in conventional notation).
Now let’s address the task of generating prime numbers iteratively, based on "Eratosthenes’ Sieve" algorithm. Here we will use the Power conjunction (^:) with two verbs — where the verb on the right calculates how many times to repeat the verb on the left — to define the main program:
Here the verb on the left of ^: is a composition of three verbs called a "fork" (see Part I for introduction) which appends the first item in the input onto the end of the list resulting from doing subprogram Sieve. The definition of Sieve is the same as earlier (in Recursion):
Now we need to compute how many times to iterate, given any input list. So, define Repeat based on the (whole) number of primes needed to sieve the list up to the square root of the largest integer (given last) in the input list — when it’s not possible to eliminate any more:
Repeat =. Round @ Nprimes @ %: @ Last
NB. Repeat is ((Round Atop Nprimes
NB. Atop SquareRoot) Atop Lat
NB. where Last =. {: (from earlier)
Utility program Round assures that the result is a whole number by adding 0.5 and then taking the integer part:
Now we need to estimate the number of primes. First, consider the following simple program (based on the famous prime number theorem [3]):
Unfortunately, this underestimates (badly) the number of primes for inputs over 4. (See [3] for a better heuristic based on the celebrated Riemann zeta function which is too computationally intense for our purposes here.) Np can, however, be used in the following program to compute a good upper bound (together with Round) for inputs from 2 to at least 10 billion:
Examples of its use with Repeat:
Repeat 2 To 13
2 NB. 2 primes up to SquareRoot 13
Repeat 2 To 25
3 NB. 3 primes up to SquareRoot 25
Repeat 2 To 1000
11 NB. 11 primes up to SquareRoot 1000
NB. (2 3 5 7 11 13 17 19 23 29 31)
Examples of the main program:
Note that while the primes are not in the usual ascending order, the results reveal where sieving stopped. It is easy enough (although more expensive) to re-order the result using the utility verb Sort =. /: ] (from Part III):
Better yet, simply rotate the smaller primes on the end of the list to the front using the primitive verb |. (called Rotate). For example:
Benchmarks for the Primes program (by itself) are as follows:
Primes =. Primes f. NB. Primes Fixed in primitives
Time 'Primes 2 To 1000'
0.06
Space 'Primes 2 To 1000'
47900
Compared with the previous optimized recursive Primes program for the same input, this program is more efficient in time and space.
Finally, here is an additional alternative which uses J’s control structures to define a multi-line iterative program explicitly (using variables):
Primes =. 3 : 0 NB. Open definition
input =. y. NB. Initial input
list =. i.0 NB. Initial list (empty)
while. Not Done input NB. While true (1)
do. list =. list , First input NB. Do reassign list
input =. Sieve input NB. reassign input
end. list , input NB. End result
) NB. Close definition
This explicit definition is initiated by the : conjunction with 3 (indicating that the program will be a verb) and a 0 (indicating that it will be entered at the keyboard). (See [1] for other options.) The first line assigns a (local) variable — called input — to be the initial input (y.) given to the program. The second line assigns another (local) variable — called list — to be an empty list (see Part II for introduction). The next line begins a loop using a while. – do. control structure. (See [1] for other control structures.) The expression following the while. controls the execution of what follows do.. Here, the expression is Not Done input (see program definitions earlier). Done input produces a 0 and Not Done input becomes a 1 when the first number in input is not greater than the
square root of the last number. In other words, while the program is not done processing the input, it does the next two lines: reassign list to become the list of primes found so far with the first number in input appended on the end; and reassign input to be the result of Sieve (which removes all multiples of the first number in input). The end. indicates the end of the control structure, and the result is the following expression — here, the list of primes appended to those remaining in the input. A final right parenthesis closes the definition. Now it can be used:
Benchmarks for this program reveal that it is slow for the example inputs here but increasingly fast for larger inputs and more economical on space than all other programs here:
Primes =. Primes f. NB. (No effect here)
Time 'Primes 2 To 1000'
0.326
Space 'Primes 2 To 1000'
17952
Comparisons¶
Here are benchmarks for all the optimized Primes programs presented above:
| Time | Space (for Primes 2 To 1000) | |
|---|---|---|
| Array-processing | 0.389 | 265896 |
| Recursive | 0.097 | 49492 |
| Iterative | 0.061 | 47900 |
| Iterative (multi-line) | 0.326 | 17952 |
Comparing these programs in general terms, the iterative program is the fastest (for the limited example here); the multi-line iterative program is the most economical in space (and the fastest for larger inputs); the recursive program is competitive in speed (more so for larger inputs); and the array-processing program is simplest in its definition yet impractical.
10. Package and Document Programs¶
The last programming strategy is to package and document programs so that they may be used productively by users and/or other programmers. J offers a facility for recording a "script". This captures all J expressions, including (program) definitions, (variable) assignments and any comments. Fundamental procedures are outlined below. (More convenient procedures are available via menus under Windows.)
First, assign a script (here, an arbitrary name):
This uses the : conjunction to define a variable (indicated by the first 0) entered from the keyboard (indicated by the second 0). From here on, everything you enter will be recorded. In order to abbreviate this illustration here, suppose you enter several lines, as indicated below:
When you are finished, enter a right parenthesis:
Now you have assigned a script.
You may also want to save the script, as follows:
When you wish to retrieve this file (here arbitrarily named 'WORK'), the script may be reconstructed and executed, as follows:
Load =. 0!:11 & < NB. Define utility verb
Load 'WORK' NB. Load 'WORK' file
NB. J expressions
NB. ...
Now all your J expressions are there — just as if you had entered them. (See [1] for more options.) You may want to check the names of programs, etc. Use another utility verb:
For example, list the names of programs (verbs) here in this article (Part IV):
Names 3 NB. Names of programs (boxed)
┌──────────┬───┬───────┬────┬───┬───┬─────┬────┬──┬────┬────┐
│Composites│Cos│Divides│Done│Fac│Fib│First│Half│If│Last│Load│
└──────────┴───┴───────┴────┴───┴───┴─────┴────┴──┴────┴────┘
┌─────┬───┬───────┬──────┬──────┬────┬────┬─────┬────┬─────┐
│Names│Not│NPrimes│Primes│Repeat│Root│Save│Sieve│Sort│Space│
└─────┴───┴───────┴──────┴──────┴────┴────┴─────┴────┴─────┘
┌────┬──┐
│Time│To│
└────┴──┘
Other names are accessible similarly (see [1]). Other inputs for the Foreign conjunction (!:) manage files; communicate with the host system; report storage types, time, and space; display representations; control font and screen attributes; query and set global parameters; offer information for debugging; etc. (See [1])
Finally, suppose you want to save just the optimized Primes programs (and subprograms) with documentation (using NB.). You can cut and paste selected lines, include comments as needed and record it all in a script. For instance:
script =. 0 : 0 NB. Begin script
NB. One input: Program (y)
NB. Two inputs: (x) Program (y)
NB. Utilities:
First =. {. NB. First item of y
Last =. {: NB. Last item of y
To =. }. i.@>: NB. Integers x to y
NB. Array-processing approach:
Primes =. ] -. Composites NB. Primes in list y
Composites =. Root */ Half NB. Table of products
Half =. 2: To <.@-:@Last NB. First half of list y
Root =. 2: To <.@%:@Last NB. Squareroot half of list y
NB. Recursive approach:
Primes=.(First,Primes@Sieve)`]@.Done NB. Primes in list y
Sieve =. ] If First Not@Divides ] NB. Items y notdivisible by y1
If =. #~ NB. Select x where 1s in y
Not =. -. NB. Change 1s to 0s, 0s to 1s
Divides =. | = 0: NB. 1s where x divides y evenly
Done =. First > %:@Last NB. 1 (true) when y1 > sqrt yn
NB. Iterative approach:
Primes =. (Sieve,First)^:Repeat NB. Primes in list y
Repeat =. >.@Nprimes@%:@Last NB. Integer Nprimes to sqrt yn
Nprimes =. <: % (2: * 10&^.) + % NB. Approx # of primes to y
NB. Multi-line iteration:
Primes =. 3 : 0 NB. Open definition
input =. y. NB. input is y
list =. i.0 NB. list is empty
while. Not Done input NB. Loop while Not Done is 1
do. list =. list,First input NB. Append next prime
input =. Sieve input NB. Remove multiples of input1
end. list,input NB. Result
) NB. Close definition;End script
This script provides a succinct package of the programs developed here in this article (comments could be expanded, of course). It may be saved and retrieved (as shown above), and individual programs may be selected for use at any time.
Note, however, that J now provides a primitive verb p: (called Primes) which generates the nth prime number. This obviates the above programs. For example:
J also provides a companion primitive verb q: (called Factors) which produces prime factors. For example:
Conclusion¶
This (four-part) article has presented functional programming strategies in J:
- Think Array
- Select Primitive Functions
- Select Primitive Operators
- Use Parallel Processing
- Name Utility Functions and Variables
- Compose Functions (Define Programs)
- Test and Debug Programs
- Modularize Programs
- Simplify, Optimize, Generalize Programs
- Consider Alternative Algorithms
- Package and Document Programs
These strategies can guide a programmer in tackling tasks well beyond the one illustrated here (generating prime numbers). A J programmer can thereby develop programs and subprograms rapidly in order to build a "toolbox" for solving problems, prototyping projects, and designing applications.
References¶
[1] Iverson, K. E. J Introduction and Dictionary, Iverson Software Inc., Toronto 1995
[2] Hui, Roger K.W. An Exchange on Primes, Vector, Vol.9, No.4, April 1993 pp.130-4