Dr Jekyll & Mr Hyde

This may come as a surprise, but I will today write about a programming language for which no Free Software implementation exists, the J programming language. J does not stand for the J dirty word (Java), but is the full name of the language.

I first heard about J while solving some problems on the Project Euler challenge. One of the problems to be solved was “given that C(n,p) is the number of ways to take p items amongst m items, find the number of C(n,p) greater than one million for n between 1 and 100 inclusive.”

This was a very easy problem. I coded my solution using Python and, by curiosity, looked at how other people did it. I saw someone mentionning its J solution:

+/1e6< ,!/~>:i.100

Wow, 17 characters! As I was in disbelief, I gave it a try and installed a copy of J on my GNU/Linux laptop. I cut and pasted the expression, and it gave me 4075, the expected solution. Let me describe how it works.

First of all, expressions are evaluated from right to left.

i.100

will generate a list of all integers from 0 to 99 (the 100 first non-negative integers). Then, the increment operator is used, so the part

>:i.100

leads to the list of numbers from 1 to 100. The rank of the increment operator is zero, which means that it operates on individual items, not on lists. Since we give it a list as argument, each member of the list will be incremented, and give the new 1 to 100 list.

The C(n,p) operator in J is written as

p ! n

However, we want to apply it for every p and n in 1 to 100. The tilde (~) modifier means that we want the left argument of the ! function to be the same as the right argument. The slash (/) modifier means that we want to build a table. Without it, the ! operator would be applied to the first item of the left argument and the first item of the right argument, then to the second item of the left argument and the second item of the right argument and so on. Here, it is applied to every combination of its left and right arguments, meaning that the result is a 100×100 table:

!/~>:i.100

Now, the coma (,) transforms the 100×100 table into a 10000 elements flat list:

,!/~>:i.100

Now, we want to select all the elements greater than one million. For that, we will compare each element to 1e6 (one million in scientific notation). Since the left argument is a plain number and the right argument is a list (the 10000 long list we obtained), the result will be a 10000 items list containing either 0 (false) or 1 (true):

1e6< ,!/~>:i.100

Ok, so we now have a 10000 items list containing 0 (smaller than one million) or one (greater than one million). To find out the number of ones, we only have to sum up the items. Using the plus (+) operator and the slash (/) modifier, an addition will be inserted between every item of the list:

+/1e6< ,!/~>:i.100

That’s it.

To the computer literate people, it looks a lot like APL without the special characters and the need for a special keyboard. No surprise, J and APL have both been designed by Kenneth E. Iverson.

J is very efficient while working on large sets of data. Its table operator and its rank analysis almost entirely obliviates the need for explicit loops. For example, if you want to multiply the 100 first prime numbers, you can use the p: operator which returns the n\super{th} prime number (starting with 0, which returns 2, 1 returns 3, 2 returns 5, 3 returns 7 and so on):

*/p:i.100x

The x modified asks for extended (read unlimited) integer precision. You want to know what the solution is? Install your copy of J and try it yourself.

This entry was posted on Wednesday, February 8th, 2006 at 11:38 and is tagged with English, J, Languages, Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

8 Responses to “The J programming language”

Gregor Lingl Says:
February 27th, 2006 at 13:41
During my first encounter with J I succeeded in shortening the

+/1e6< ,!/~>:i.100

program by more than 10%.

+/1e6<,!/~i.101

Please notice, that !/~>:i.100 doesn’t use the
complete table of binomial coefficients (i. e. Pascals’s triangle)
Example:

!/~>:i.10
1 2 3 4 5 6 7 8 9 10
0 1 3 6 10 15 21 28 36 45
0 0 1 4 10 20 35 56 84 120
0 0 0 1 5 15 35 70 126 210
0 0 0 0 1 6 21 56 126 252
0 0 0 0 0 1 7 28 84 210
0 0 0 0 0 0 1 8 36 120
0 0 0 0 0 0 0 1 9 45
0 0 0 0 0 0 0 0 1 10
0 0 0 0 0 0 0 0 0 1

in contrast to:

!/~i.11
1 1 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 10
0 0 1 3 6 10 15 21 28 36 45
0 0 0 1 4 10 20 35 56 84 120
0 0 0 0 1 5 15 35 70 126 210
0 0 0 0 0 1 6 21 56 126 252
0 0 0 0 0 0 1 7 28 84 210
0 0 0 0 0 0 0 1 8 36 120
0 0 0 0 0 0 0 0 1 9 45
0 0 0 0 0 0 0 0 0 1 10
0 0 0 0 0 0 0 0 0 0 1

regards
Gregor Lingl
Aidan Says:
March 9th, 2007 at 14:35
Hi i am having a bit of trouble with a program i am working on. Basically i have 2 function getInxSmallest and getInxLargest they take in an array on numbers and reutrn the position of the largest or lowest depending on which function you use. Now i must must create a function that returns the position of the smallest number in the array when a 0 is entered and the largest when a 1 is entered.
for example lets say you create an array v1 =: 5 2 1 3 when 0 FUNCTIONNAME v1 is entered the answer should return 2 as the smallest number 1 is in position 2. Can you please help i would greatly appreciate it.
Samuel Tardieu Says:
March 9th, 2007 at 15:22
You can define it as an adverb easily: (which does what you ask, including embed your getInxSmallest and getInxLargest functions)
```
   f =: 1 : ']i.<.`(>.)@.x/'
   0 f 10 20 5 30 15
2
   1 f 10 20 5 30 15
3
```
I’ll let you analyze the adverb.
Aidan Says:
March 12th, 2007 at 11:51
Thank you very much you’re a life saver.
Aidan Says:
March 27th, 2007 at 16:26
Hi I am back again. Just one small question, in order for me to muliply a column i change it to a row using |: as i want to use them all at once. So my column 1
0
2
4
is changed to 1 0 2 4. It works but I am just wondering is there not another way to do this? Given that I am only a novice with J I am sure there is. Can you please help I would really appreciate it.
Aidan Says:
April 28th, 2007 at 17:15
Hi Samuel Thanks for all your advice so far. My project is due shortly on J but i an having one last error. The folllowing line returns a domain error and i cannot understand why.
getIHW =: ( (0 {:: NetParams) ,&> (1 {:: NetParams)) $ ((0 {:: NetParams) * (1 {:: NetParams)) {.!.0 [

Can you please offer some advice for one last time i would grateful.
Harry Reed Says:
May 25th, 2007 at 18:53
Hi, I discovered J a few years ago and am quite impressed. Sadly, as is mentioned, “…no Free Software implementation exists.” I am contemplating writing an open source version of J. However, before I start this Herculean task, does anybody know if an effort to produce an open source J has already been started?
Elmer Fittery Says:
April 12th, 2008 at 1:55
According to:

http://www.byte.com/art/9603/sec11/art10.htm

The public-domain version 7 of the J programming language. BYTEmark is a collection of 10 tests that exercises the CPU, FPU, cache, and system memory; J is a complete interpreter that is the last public-domain release of the J language’s source code prior to J’s becoming a commercial package.

The J programming language

8 Responses to “The J programming language”

Leave a Reply