Functional Programming in J (Part 3)
Vector 13:3, page 22
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 22
This is Part III 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. Part II demonstrated how to develop the program directly, while characterizing a J programmer’s thinking. Part III continues development of the same program with higher-level strategies. Part IV will consider alternative algorithms for iterative, recursive, and array-processing programs and will end with meta-strategies for packaging and documentation.
8. Simplify, Optimize, Generalize Programs¶
An often overlooked strategy involves looking back at a program after its development and rethinking it. This is an opportunity to simplify or optimize or generalize the program (and subprograms). To ‘simplify’ here means to make a program shorter and/or more readable. To ‘optimize’ means to increase speed and/or reduce space required for computations; that is, improve efficiency. To ‘generalize’ means to design the program to apply to many (preferably all) cases and/or higher dimensional arrays.
Simplify¶
First, consider some ways to simplify the programs developed previously. For instance, the Primes program (from section 6):
One way to simplify this definition is to enter a list of integers as input, thereby removing the need to generate them (twice, using Pos) within the program. Thus:
Example of its use:
Another slight simplification involves using another form of composition in J — called a "hook" — where two verbs are written together in an isolated sequence. The (dyad) verb on the left uses the input and the result of the (monad) verb on the right. For example, (* >:) is a hook for the input Times (*) the Increment (>:) of the input. Give this hook a name:
Test it with one input:
In general, for one input y, a hook (verb1 verb2) y is equivalent to y verb1 (verb2 y), as shown in the diagram:
A hook may be given two inputs. For example:
In general, for two inputs x and y, a hook x (verb1 verb2) y is x verb1 (verb2 y). Diagram:
Now simplify the definition of Primes by removing one symbol (]) and forming a hook of the two verbs If and Prime"0 like this:
The example of its use is the same as before:
Another more substantial simplification can be achieved by noticing that the actual divisors aren’t needed to detect a prime. Just count them. So, create a simpler subprogram to return 1s marking the divisors (as shown earlier in the first section):
And revise subprogram Prime accordingly to Sum (+/) the 1s:
Main program Primes gives the same result as before. A further simplification arises by noticing that the input integer is always a divisor of itself. Instead of Pos producing 1 to n, use Integers (i.) to produce 0 to n-1 for the list to divide the input. Don’t worry about the 0 — for instance, 0 Divides 12 is 0 (false) because the remainder 0|12 is 12).
So, revise Dividors:
And revise Prime to use 1: (which returns the constant 1) instead of 2: :
Similarly, notice that 1 is always a divisor of the input integer. Another simplification could remove 1 (and 0 as well) from the list generated by i. in Dividors and then replace 1: with 0: in Prime. But this definition (not shown here) admits 1 as a prime incorrectly, so it would have to disallow 1 in the input items. In either case, the main program should be used like this:
This suggests defining another utility verb to produce a list of any consecutive positive integers such as 2 to 13. Thus:
This definition is a hook (introduced above) of two verbs. The first verb, called Drop (}.), removes items from a list; it uses two inputs — the left input is how many items to drop and the right input is the list of items. The second verb is a composition of Integers (i.) Atop (@) Increment (>:), producing integers from 0 to its input. So, x To y drops x items from the list of integers from 0 to y — in effect, listing the integers from x to y. For example:
From now on, use this for convenience like this:
Optimize¶
All these simplifications made the programs more efficient as well. J offers helpful tools for measuring such optimization efforts. For instance:
Now the time and space required to execute a program (or any expression) can be determined:
Benchmarks for a larger number of primes:
Comparing these results with Time 'Primes 1000' and Space 'Primes 1000' for the earlier developmental definition of Primes (in section 6) reveals a factor of about 2 speedup as well as a reduction in space of about 9%. Note: These benchmarks were obtained on a 486 PC running JFW (J Freeware for Windows) Release 3.
Further, optimize the program by replacing subprograms with primitives (as shown in section 7):
Now compare benchmarks:
This optimized program performs faster in the same space. (See Part IV for more optimization efforts for alternative algorithms.)
Generalize¶
J programs often generalize easily — sometimes without revision. Although the programming task here does not lend itself to significant generalization, note that program Primes will work (as is) for a list of integers (greater than 1) input in any order. For example:
The result can be ordered — at additional expense — using the primitive /: (called Sort) embodied in a utility verb as follows:
Sort =. /: ] NB. Sort is Input Sort Input
Sort Primes 6 3 8 2 7 11 10 4 12 5 13 9
2 3 5 7 11 13 NB. Ordered primes
Further, consider using program Primes with a table or a 3-D array of integers input (although this is admittedly unusual). First, here are some ways to create such higher dimensional arrays. J’s primitive verb Shape ($) can be used to create an array of any shape (given on the left) made up of any items (on the right). For example:
And:
2 3 4 $ 2 To 25 NB. 2 by 3 by 4 array
2 3 4 5
6 7 8 9 NB. (Two 3 by 4 tables)
10 11 12 13
NB. Blank line between
14 15 16 17
18 19 20 21
22 23 24 25
Note that (even though these examples do not illustrate it) items may be in any order, are repeated cyclically if there are too few, and are truncated if there are too many. Another way to create ordered arrays (such as above) uses the Integers primitive verb (i.) with a list input. For example:
Other verbs may be applied to this table, such as:
A 3-D array would be expressed similarly: 2 + i.2 3 4. Note that longer lists input to Integers (i.) may create higher dimensional arrays beyond the computer’s limits (as encountered in beginning of section 6 where i.1 2 3 4 5 6 7 8 9 10 11 12 created a 12-dimensional array with 479001600 items).
The primitive verb Ravel (, used with one input) makes any such array into a list:
So, to use an array with the Primes program, Ravel the input first:
So there is no need to change the program.
Next, in Part IV, we will consider alternative algorithms for generating prime numbers in recursive, iterative, and array-processing programs.
Reference¶
[1] Iverson, K. E. J Introduction and Dictionary, Iverson Software Inc., Toronto 1995