Functional Programming in J (Part 2)
Vector 13:2, page 29
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 29
This is Part II 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 (here) demonstrates how to develop the program directly, while characterizing a J programmer’s thinking. Part III (next issue) will continue 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.
Program Development Review¶
As a review of Part I, here we will develop a program for generating prime numbers, from the beginning, in bottom-up style. We will also characterize a J programmer’s thinking along the way, and the reader may notice the fundamental strategies involved (from Part I) which are noted in the text like this [0]:
[0] Think Arrays
[1] Select Primitive Functions
[2] Select Primitive Operators
[3] Use Parallel Processing
[4] Name Utility Functions and Variables
[5] Compose Functions (Define Programs).
The programming task is to generate a list of primes up to (and including) a given integer. To begin with, the programmer might well think: I want to use arrays — especially since the result should be a list of integers. [0] And: what primitive functions (verbs) does J offer which might be immediately useful? [1]
The verb Integers (i.) generates integers from 0 to n-1 for an input n. This is a reasonable first step in computing prime numbers; that is, I know that primes are somewhere in the list of positive integers. But I want positive integers up to and including n. It is easy enough to use the primitive verb Increment (>:) to add 1 to each number, as in >: i. 12 which produces integers from 1 to 12. [3]
Or, I can use the utility verb: [4]
For example:
This list will be useful as a test case. So I’ll name it: [4]
Now the question is how to detect which of these integers are prime. (A prime number is defined mathematically as a positive integer greater than 1 which is divisible only by itself and 1). A useful primitive verb — Remainder (|) — comes to mind because ‘divisible’ means a remainder of 0. [1] And, looking ahead, I also expect to use the primitive verbs Equal (=) and Zero (0:). [1]
Right away, I can compute a list of remainders all at once using J’s built-in parallel processing: [3]
And identify the zero remainders: [3]
(p | 12) = 0 NB. Or 0 = p | 12
1 1 1 1 0 1 0 0 0 0 0 1 NB. 1 means true (divisible)
NB. 0 means false (not divisible)
Now I’ll define a program for this by composing functions in a "fork" (where three verbs in sequence mean that the middle verb uses results of the left verb and the right verb, as introduced in Part I): [5]
So, from now on I can use its name: [4]
Next, I want to get the actual integers — the "divisors" — which are marked with 1s. Recall the utility verb If (from Part I): [4]
Use it to select the divisors from p:
NB. 1 2 3 4 5 6 7 8 9 10 11 12 If
p If p Divides 12 NB. 1 1 1 1 0 1 0 0 0 0 0 1
1 2 3 4 6 12 NB. Divisors
Compose the verbs involved (including Pos which produced p) and give the program a name: [5]
Divisors =. Pos If Pos Divides ] NB. Divisors is Pos If
NB. (Pos Divides Input)
NB. where ] is the input
This program computes the divisors of any given input integer. Examples:
Now I can use this to detect a prime number. Recognizing that a prime has exactly two divisors, I only need to count the divisors! [0] This suggests the primitive verb Tally (# used with one input) which counts the number of items. [1] For example:
Next, ask if these results are equal to two: [1]
(#Divisors 12) = 2 NB. (Tally Divisors 12) Equal 2?
0 NB. No
(#Divisors 13) = 2 NB. (Tally Divisors 13) Equal 2?
1 NB. Yes
Compose verbs and name a program for this: [5]
Prime =. #@Divisors = 2: NB. Prime is
NB. (Tally Atop Divisors)
NB. Equal Two
NB. where 2: returns 2
Examples of its use to detect primes:
Finally, I want to apply this to a list of positive integers, as in Prime p — expecting a list of 0s and 1s which can be used to select primes, as in p If Prime p. So I attempt the final program:
While this initial program development seems correct, there is a subtle bug in the program which will be rectified in the next section (numbered 6 to continue from the strategies presented in Part I).
6. Test and Debug Programs¶
After the initial development of a program, the critical next strategy is to test it and debug it if it doesn’t work properly. This includes trying not only typical inputs but also special cases. (Other debugging strategies are not discussed in this article.)
First, test the Primes program for a typical input:
J reports an error message here indicating that the computation requested cannot be done. Actually, Primes 12 doesn’t work because subprogram Prime was designed for a single integer input but, instead, received a list (Pos 12). That caused subprogram Divisors, its subprogram Pos and Integers (i.) to fail unintentionally because the input list produced a large 12-dimensional array (see end of section 8) beyond the computer’s capacity.
In order to correct this bug, use the Rank operator (") to force Prime to apply to each item in the input separately. [2] For example:
Rank (") is a "conjunction" operator which requires a verb (on the left) and an integer (on the right) which indicates the rank of the items to which the verb will apply. Rank 0 refers to single values; rank 1 refers to lists; rank 2 refers to tables; etc. Here Prime"0 applies the verb Prime to each rank-0 integer in the input list and produces a 0 or 1 for each. This resulting list of 0s and 1s can be used with utility verb If to select the primes from a list of positive integers. Correct the definition of Primes accordingly:
Now test it:
Primes 12 NB. Primes to 12
2 3 5 7 11
Primes 13 NB. Primes to 13
2 3 5 7 11 13
Primes 100 NB. Primes to 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
97
While this programming task is essentially completed, it is wise to test the program further for special cases. For instance, check if an input of 1 works:
According to the definition of a prime, 1 itself is not prime. Since there are no primes up to (and including) 1, an empty list is an appropriate result here. In J, an empty list can be entered as follows:
Both of the above entries print a blank line, but the results may be used in other expressions. For instance, try program Primes with an empty input:
Testing a program for empty input is a strategy often practised by J (and APL) programmers as a precaution. Even though the program itself may not be normally used with such special cases, it is more robust if it returns a (correct) result anyway — instead of an error message — because it may be used in other contexts, perhaps within other programs which don’t constrain its use.
Other special cases here include zero (Primes 0 is empty); a small integer input (Primes 2 is a list of one item); very large integers (results depend on computer limits); negative integers (Primes _13 returns primes in reverse order); decimals (domain error); etc.
7. Modularize Programs¶
A good strategy is to develop programs modularly, that is, create and test each subprogram separately and assemble them into larger programs when needed. An important advantage of this is that any subprogram may be used (as is) at other times in other contexts.
Since the programs developed above are already modularized, here we will just show their structure. First, define a utility verb to display boxes around the parts of a program:
This uses the Foreign conjunction (!:) which controls various aspects of the J system, along with the conjunction Atop (@) and the verb Box (< with one input). See [Ref 1] for details.
Now the structure of each defined program may be displayed:
Boxed 'Primes' NB. Boxed display of Primes program
┌───┬──┬───────────────────┐
│Pos│If│┌───────────┬─┬───┐│
│ │ ││┌─────┬─┬─┐│@│Pos││
│ │ │││Prime│"│0││ │ ││
│ │ ││└─────┴─┴─┘│ │ ││
│ │ │└───────────┴─┴───┘│
└───┴──┴───────────────────┘
Boxed 'Prime' NB. Subprogram Prime
┌──────────────┬─┬──┐
│┌─┬─┬────────┐│=│2:│
││#│@│Divisors││ │ │
│└─┴─┴────────┘│ │ │
└──────────────┴─┴──┘
Boxed 'Divisors' NB. Subprogram Divisors
┌───┬──┬───────────────┐
│Pos│If│┌───┬───────┬─┐│
│ │ ││Pos│Divides│]││
│ │ │└───┴───────┴─┘│
└───┴──┴───────────────┘
Boxed 'Divides' NB. Subprogram Divides
┌─┬─┬──┐
│|│=│0:│
└─┴─┴──┘
Boxed 'Pos' NB. Subprogram Pos
┌──┬─┬──┐
│>:│@│i.│
└──┴─┴──┘
Boxed 'If' NB. Subprogram If
┌─┬─┐
│#│~│
└─┴─┘
Other representations are also available in J. For instance:
This displays a tree structure. For example:
Tree 'Divisors' NB. Tree display of subprograms
┌─ Pos
├─ If
──┤ ┌─ Pos
└─────┼─ Divides NB. Fork within a fork
└─ ]
J also provides an adverb called Fix (f.) which replaces all subprogram names with their primitive definitions. This compilation is particularly advantageous for efficient execution of a program. (See next section.) For instance:
Now its tree structure looks like this:
Tree 'Divisors' NB. Tree display of primitives
┌─ >:
┌─ @ ─┴─ i.
├─ ~ ─ #
──┤ ┌─ >:
│ ┌─ @ ──┴─ i.
└───┤ ┌─ |
├──────┼─ =
│ └─ 0:
└─ ]
And its definition is in terms of primitives:
This linear representation is the default, obtained simply by entering the program name by itself.
Note that you may switch between these representations conveniently via the View menu on a J system.
Reference¶
[1] Iverson, K. E. J Introduction and Dictionary, Iverson Software Inc., Toronto 1995