Functional Programming in J (Part 1)
Vector 13:1, page 20
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 20
This is the first of a three-part article. Part I presents fundamentals of J in a framework of functional programming strategies, with examples aimed toward developing an illustrative program to generate prime numbers. Part II (to appear in the next issue) will demonstrate how to develop the program directly, characterizing a J programmer’s thinking along the way, and will continue development of the same program with higher-level strategies. Part III (in a following issue) will present alternative algorithms for iterative, recursive, and array-processing programs and will end with meta-strategies for packaging and documentation.
0. Think Arrays¶
As an a priori programming strategy, a programmer must decide how to represent data for a particular task. (This strategy is numbered 0 to indicate that it may well occur before actual programming begins.) It involves thinking ahead about what structures are best suited for processing the given data and for reporting results. In J, data structures are "arrays" — that is, single values (scalars), lists (vectors), tables (matrices), 3-D and higher-dimensional arrays. To ‘think arrays’ means to plan to process data as a whole array where possible. In this article we will use lists primarily.
A list of numbers is represented with a space between each number. For example:
Other kinds of numbers (not needed in this article) are represented as follows: Negative numbers are preceded by an underbar, as in _3. Real numbers use a decimal point and leading zero, if necessary, as in 0.5. Very small and large numbers are represented in scientific notation, as in 1e6 for one million. Complex numbers use engineering notation, as in 3j4 for 3 plus 4 times the square root of negative 1.
Note that comments (following NB.) can be used for explanation.
A list of characters is represented within single quote marks. For example:
A table is represented in rectangular rows and columns. For example:
(Ways to create tables will be presented in Part II and Part III.) Note that no declarations and no data typing are necessary in J. Different data types may be mixed together in a "boxed" array. For example:
┌──────┬──────────┐ NB. A list of two boxed items
│primes│2 3 5 7 11│ NB. each containing items
└──────┴──────────┘
This enables representation of non-rectangular arrays. (See [1] for an introduction to boxed arrays, which are not needed in this article.)
1. Select Primitive Functions¶
A first strategy for programming in J is to select primitive functions appropriate for the task at hand. J provides over a hundred mathematical functions as primitives, that is, symbols on the keyboard. Included are: arithmetic functions Plus, Minus, Times, Divide, and Power; relational functions Equal, NotEqual, LessThan, GreaterThan, etc.; logical functions And, Or, Not, etc.; standard functions such as SquareRoot, random numbers, and greatest integer part; handy functions such as Square, Increment, Halve, and Factorial; powerful functions such as Matrix Inverse and Matrix Divide for linear algebra and statistical regression; permutation and sorting functions; trigonometric and circular functions; and many other functions for manipulating arrays, formatting output, complex arithmetic, etc.
Only a dozen or so primitive J functions are introduced here in this article. (See [1] for a complete list.) Note that symbols can be utilized alone or with a dot (.) or a colon (:) as a suffix to denote different functions, as in * (Times) or *. (And) or *: (Square).
In J, functions are called "verbs", and they use "nouns" (data) or "pronouns" (variables) for arguments (inputs). A student may explore the behaviour of any verb by entering expressions interactively, where an expression is indented automatically and the computer prints the result on the next line. For instance, consider the Remainder verb (|) which uses a noun on the left and on the right:
3 | 9 NB. 3 Remainder 9
0 NB. Result is 0
3 | 10 NB. 3 Remainder 10
1 NB. Result is 1
3 | 11 NB. 3 Remainder 11
2 NB. Result is 2
3 | 12 NB. 3 Remainder 12
0 NB. 3 goes into 12 evenly
These expressions may be combined using a list:
A longer list reveals more of a pattern:
The primitive verb i. (called Integers) is convenient here:
Substituting this illustrates how verbs may be used together:
Note that here | is a "dyad" verb (binary function) which — like Plus (+) — uses two inputs (here a single number on the left and a list on the right); whereas Integers (i.) is a "monad" verb (unary function) which uses one input on the right — like -4 and √4 and f(x) in conventional notation. All verbs in J are either monadic or dyadic. Many use the same symbol for both a monad and a dyad, which can be distinguished by use (with one input or two inputs), as in 7--4 which is 7 Minus Negate 4.
Further, note that the rightmost verb is executed first in order to produce the right input for the next verb. For instance, above, Negate before Minus, as in 7-(-4) and, earlier, Integers (i.) before Remainder (|), as in 3|(i.13). Indeed, J adopts the following general rule: every verb uses the (noun) result of the entire expression on its right. This eliminates the need for a hierarchy (such as exponentiation before multiplication and division before addition and subtraction) but appears controversial (see [2] for discussion of maths teachers’ reactions to learning J notation). Nevertheless, the issue can be avoided by using parentheses redundantly to indicate order of operations (in the normal way), as shown in this article.
2. Select Primitive Operators¶
In addition to primitive functions (verbs), J provides operators which modify verbs. Operators effectively create new verbs which often enable programming tasks to be accomplished more directly. For instance, Insert (/) is an "adverb" operator which inserts a verb between successive items of an array. It requires a verb as an input (on its left). For example:
Here the verb + (Plus) is the input for / (Insert). The two symbols +/ together produce a new verb (called Sum) which then applies to the given numbers, in effect producing 2+3+5+7+11, which is 28. Programmers might compare this with how it is done in other programming languages and note that J allows direct use of an operator instead of iteration with explicit control structures. (See forthcoming Part III for more discussion.)
Other dyadic verbs may be used with Insert, so the programmer can produce more new verbs. For example:
In effect, this repeats * as many times as needed to insert it between all items in the input, and then 2*3*5*7*11 is evaluated as 2*(3*(5*(7*11))). Other operators will be introduced, as needed, in the following sections. (See [1] for a complete list and note that all operators are performed before functions.)
3. Use Parallel Processing¶
A natural programming strategy in J uses "parallel processing", where a verb applies automatically to every item in an array. Recall the example of Remainder (|) from Section 1: 3 | 9 10 11 12 is equivalent to (3|9), (3|10), (3|11), (3|12) where a single number on the left is used with each number on the right. In general, the verb applies every item on the left in one-to-one correspondence with every item on the right — in parallel. For example, when both inputs have the same number of items:
This pertains to other primitive verbs as well, such as:
1 2 3 4 + 9 10 11 12 NB. (1+9),(2+10),(3+11),(4+12)
10 12 14 16 NB. Parallel sums
1 2 3 4 # 9 10 11 12 NB. (1#9),(2#10),(3#11),(4#12)
9 10 10 11 11 11 12 12 12 12 NB. Parallel copies
Here the verb # (called Copy) makes copies of each item respectively. It is also particularly useful for selecting items:
Each 1 selects its corresponding item, and each 0 eliminates an item. (This is often called a "bit mask".) Another example:
4. Name Utility Functions and Variables¶
Programmers often enter or retrieve utility functions (programs) and variables they need as tools for tackling a programming task. J uses =. for local assignment and =: for global assignment of variables (called "pronouns"). For example:
To print out the contents of a pronoun, simply type its name:
A pronoun may be changed, of course. For example, use the primitive verb Increment (>:) to add 1 to each item in the list:
Asking for the value of a pronoun which has not been assigned results in an error message. For example, note that J is case sensitive:
This is one of about a dozen possible error messages, including "domain error", "syntax error" etc. J reports an error message whenever it cannot interpret an expression but lets you enter another expression immediately.
New functions ("pro-verbs") in J are defined just as easily using =. or =: which can be read as ‘is’. For instance, suppose you want to use a name instead of a symbol for a verb:
Now this name can be used instead of the | symbol. For example:
It can be used as a function in any expression. For example:
Note that the result of Equal (=) is either 1 (representing "true") or 0 ("false"). Other relational functions, such as LessThan (<) and GreaterThan (>), return Boolean results also. See [1].
Since some programmers may prefer using the name "mod" (short for "modulo") with the inputs switched (as in 12 modulo 3), a slightly different verb could be defined:
The symbol ~ is an adverb (called Passive or Commute) which switches the inputs of a verb. For example:
Recall the Copy verb (#) from the previous section, which used 0s and 1s on the left to select items from an array. We may use #~ to select items, where 0s and 1s are given on the right side instead:
It is convenient to give this verb a name:
Now you can use the name as a utility function:
5. Compose Functions (Define Programs)¶
J provides facilities for defining traditional multi-line programs with variables and control structures (see Part III). But these are not needed here since we can define short (one-line) programs without control structures by composing functions. This is a quintessential strategy in J programming. Furthermore, J allows definition of a program ("pro-verb") without explicit reference to inputs or variables. This is sometimes called "pure functional programming".
J offers several kinds of functional compositions. To begin with, the operator @ (called Atop) composes one verb after another — like function composition in mathematics. For example, let’s define a simple utility verb to generate positive integers:
Atop (@) is a "conjunction" operator which requires two verb inputs. It causes the verb on the left (here >:) to be done after the verb immediately on the right (here i.), that is, Increment after Integers. Now execute this new verb with an input:
Another convenient form of composition — called a "fork" in J — occurs when three verbs are written in an isolated sequence. The verb in the middle uses the results of the verb on the left and the verb on the right. For example, (>: * <:) is a fork which executes Times with the results of Increment and Decrement. (<: is the primitive verb Decrement which subtracts one from its input.) Give this fork a name:
Test it with one input:
In general, for one input y, a fork (verb0 verb1 verb2) y is equivalent to (verb0 y) verb1 (verb2 y), as seen in the following diagram:
A fork may be given two inputs. For example:
In general, for two inputs x and y, fork x (verb0 verb1 verb2) y is equivalent to (x verb0 y) verb1 (x verb2 y). Diagram:
Now consider the fork (| = 0:) which executes Equal with the results of Remainder and Zero. (0: is a constant verb which returns a 0 result.) Give this fork a name:
This program uses two inputs. For example:
It also works with a list input — by parallel processing — to test the divisibility of each item:
(Pos 12) Divides 12 NB. (1 2 3...12 | 12) = 0
1 1 1 1 0 1 0 0 0 0 0 1 NB. 1s indicate divisible items
This suggests defining another program using a fork within a fork:
Note that ] is a primitive verb which returns the input itself. This program uses one input:
Forks may be composed into increasingly complex sequences. This next program uses another fork:
This is equivalent to the following definition, where the rightmost sequence of three verbs is composed first:
(See Part II for how to display the structure of such a program.) Examples of its use:
Divisors 12 NB. (Pos 12) If ((Pos 12) Divides 12)
1 2 3 4 6 12 NB. Divisors of 12
Divisors 13 NB. (Pos 13) If ((Pos 13) Divides 13)
1 13 NB. Divisors of 13
This program is a new verb which may be combined usefully with other verbs. For instance, the primitive verb Tally (# used with one input) counts the number of items:
Now compare the results with two:
(#Divisors 12) = 2 NB. Is (Tally Divisors 12) Equal 2?
0 NB. No
(#Divisors 13) = 2 NB. Is (Tally Divisors 13) Equal 2?
1 NB. Yes
Let’s compose the verbs and define a program to detect a prime number (which has exactly two divisors):
Prime =. #@Divisors = 2: NB. Prime is
NB. (Tally Atop Divisors) Equal Two
NB. where verb 2: returns 2
Examples of its use:
Now we are ready to develop a program for generating a list of primes. This will be presented (from the start) in Part II, along with higher-level programming strategies: testing, debugging, modularizing, simplifying, optimizing, and generalizing.
References¶
[1] Iverson, K. E. J Introduction and Dictionary, Iverson Software Inc., Toronto 1995
[2] Peelle, H. A. "Teaching a Computer Notation for Secondary Mathematics" submitted to Journal of Computing in Teacher Education, International Society for Technology in Education, Eugene, OR
Professor Howard A. Peelle
University of Massachusetts
Amherst, MA 01003