In this post I'm going to show a small overview of the
J programming language. An example of polynomial multiplication is examined.
J
J is an
array programming language derived from
APL which means is good for manipulating arrays and matrices. Its syntax and semantics are very different from other languages which makes it an interesting topic for studying.
There's a lot of documentation and examples available from the
J software website. Two complete tutorials are
"Learning J" by Roger Stokes and
"J for C programmers" by Henry Rich.
The J distribution also includes examples and tutorials. The examples will be presented using J's REPL called
jconsole.
The example
In order to give an overview of the language I'm going to start from the definition of a function that performs polynomial multiplication and examine how it was constructed.
The function is defined as follows:
polymulti =: dyad : '+/ (((_1 * i. #y) (|. "0 1) ((x (*"_ 0) y) (,"1 1) (((#y) - 1) $ 0))) , 0)'
Writing this example helped me understand some of the J's basic concepts (I'm completely sure there's a better/more efficient way to do this!).
Polynomial multiplication
The basic technique for
polynomial multiplication consists on multiplying each term of one of the polynomials by the order and them simply the result. For example:
(4x3 - 23x2 + x + 1) * (2x2 - x - 3)
= ((4x3 - 23x2 + x + 1) * 2x2) +
((4x3 - 23x2 + x + 1) * -x) +
((4x3 - 23x2 + x + 1) * -3)
= (8x5 - 46x4 + 2x3 + 2x2) +
(-4x4 + 23x3 - x2 - x) +
(-12x3 + 69x2 - 3x - 3)
= (8x5 - 50x4 + 13x3 + 70x2 - 4x - 3)
Now I'll start creating
polymulti from the bottom up to the definition.
1. Defining polynomials
As mentioned above J is a nice language for manipulating arrays. We're going to use J arrays to define polynomials. In fact J supports some
operations on arrays as polynomials which will be described bellow.
In order to write a new array literal containing 1,1, -23 and 4 in J we write (here using jconsole):
1 1 _23 4
1 1 _23 4
As you can see the elements of the array are separated by space. Also negative numbers are prefixed by underscore '_'. This array is going to be used to represent the coefficients of the "(4x
3 - 23x
2 + x + 1)" polynomial.
We're going to define two variables with the polynomials shown above to use them for examples:
p1 =: 1 1 _23 4
p2 =: _3 _1 2
Here the '=:' operator is used to bind the specified arrays with p1 and p2.
2. Multiply each element of one of the polynomials
We can proceed to apply the first step in the process which is multiply each element of the second operand by the first operand.
In J we can operate on arrays easily, for example if we want to multiply each element of the above array by a 2 we write:
1 1 _23 4 * 2
2 2 _46 8
In J the an operation that receives two arguments is called a
dyad and a operation that receives only one is called
monad. Here we're using the '*' dyad to perform the multiplication.
We cannot directly go and type "p1 * p2" because we will get the following error:
p1 * p2
|length error
| p1 *p2
This happens because the length of the two arrays (4 and 3) could not be used to perform the operation. We can apply '*' to a two same size arrays and J will multiply each element. For example:
p1 * p1
1 1 529 16
Now what I want is to multiply each element of 'p2' by 'p1'. In order to do this we can change the behavior of the '*' dyad by specifying its rank (more details on how to do this can be found in
"Verb Execution -- How Rank Is Used (Dyads)") . To change the rank of '*' and say that we want to multiply the complete array on the left for each of the cells of the right array we write
(*"_ 0) .For example:
p1 (*"_ 0) p2
_3 _3 69 _12
_1 _1 23 _4
2 2 _46 8
By specifying
(*"_ 0) we say that the left operand has "infinite rank" (_) which means it will consider the array as single unit.We also say that for the right argument we will consider every cell (by using the 0 rank). Notice that in order to modify the rank we use double quote (") which, in J, doesn't have to paired with another double quote as in most programming languages.
Also you can notice that the result of this operation is an array of arrays, one for each element of the right argument.
2. Sum each element of one of the polynomials
Now that we have an array of polynomials with the result of multiplying the coefficients, we need to change the degree of each of the polynomials. First we need to make more space to increment the degree of the polynomials. We're going to use the ',' dyad which lets you concatenate two arrays. For example:
p1 , 0 0
1 1 _23 4 0 0
We need to append an array that is the size of the second polynomial minus one. In order to create a new array of this size we use '$' which lets you create an array or matrix by specifying the size and the value of the elements of the new array. For example:
10 $ 0
0 0 0 0 0 0 0 0 0 0
The size of the array can be obtained with the '#' monad. For example:
# p1
4
Now we can combine all these elements to resize each array resulting from the multiplication of the coefficients like this:
(p1 (*"_ 0) p2)
_3 _3 69 _12
_1 _1 23 _4
2 2 _46 8
(((#p2) - 1 ) $ 0)
0 0
(p1 (*"_ 0) p2) (,"1 1) ( ((#p2) - 1 ) $ 0)
_3 _3 69 _12 0 0
_1 _1 23 _4 0 0
2 2 _46 8 0 0
Here we use
(((#p2) - 1 ) $ 0) to generate an array of zeros of the desired size. Then we use
(,"1 1) which is the ',' dyad with a modified rank saying that each element of the left matrix (an array) will be concatenated with the second array (since the second argument is a single dimension array we could have said
(,"1 _) ).
With the arrays resized we can change the degree of our polynomial array. In order to do this we're going to use the
'|.' dyad which let's you rotate an array an specified amount of positions. For example:
1 |. 1 2 3
2 3 1
_1 |. 1 2 3
3 1 2
As shown in the example, by specifying a positive number the array will be rotated to the left and a negative number to the right.
Now the question is, how to rotate each element of the polynomial array by a different element count? Before showing that we're going to introduce the 'i.' primitive which lets you create an array of with a sequence of numbers for example, to create an array of 10 numbers (starting with 0) we write:
i. 10
0 1 2 3 4 5 6 7 8 9
We can use this primitive in conjunction with the rotate primitive to say
m =: (p1 (*"_ 0) p2) (,"1 1) ( ((#p2) - 1 ) $ 0)
i. #p2
0 1 2
_1 * i. #p2
0 _1 _2
(_1 * i. #p2) (|."0 1) m
_3 _3 69 _12 0 0
0 _1 _1 23 _4 0
0 0 2 2 _46 8
As you can see we use the array generated by
(_1 * i. #p2) to specify how many positions are we moving. We apply the change the rank of '|.' by saying
(|."0 1) which means apply '|.' for each single cell of the left array to each row of the right array.
The previous step generated an array polynomials to be summed. So the only thing left is to generate the final polynomial. In order to do this we use the '+/' dyad which let's use sum the contents of an array. For example:
+/ 5 3 4 1
13
We can apply +/ to any array and J will do the operation as expected.
+/ (_1 * i. #p2) (|."0 1) m
_3 _4 70 13 _50 8
As a work around I'm appending a zero row to this matrix, just in case the p2 array is a 0 degree polynomial.
+/ ((_1 * i. #p2) (|."0 1) m) , 0
_3 _4 70 13 _50 8
And that's it we have the complete process for multiplying the array.
3. Create the function
Now putting all the elements described above we can put together the polynomial multiplication dyad:
polymulti =: dyad : '+/ (((_1 * i. #y) (|. "0 1) ((x (*"_ 0) y) (,"1 1) (((#y) - 1) $ 0))) , 0)'
The 'x' and 'y' names are the implicit names of the left and right operands.
We can use it with any pair of polynomials. For example:
2 34 3 polymulti 4 3
8 142 114 9
2 34 3 polymulti 4 0 3
8 136 18 102 9
2 34 3 polymulti 1
2 34 3
4. Use the polynomials
J already has support for polynomials inside the library. For example by using the 'p.' we can get an evaluation of a given polynomial.
3 4 5 p. 34
5919
3 + (4*34) + (5*34*34)
5919
_2 p. 34
_2
(5 3 _2 polymulti 3 0 0 _2)
15 9 _6 _10 _6 4
(5 3 _2 polymulti 3 0 0 _2) p. 3
204
Final words
It was very interesting to read about J. It offers a different perspective on programming which is definitely worth studying. I have to admit it was difficult at the beginning because of the number of concepts to learn ( only a couple are presented in this post) and the syntax . For future posts I'm going to try to explore more J features.
