Monday, August 27, 2012

Rank Part I

For a multidimensional array, we can say the shape of the array is the 1D array made from concatenating the lengths of each axis. For example:


a =: i. 3 3 2
   a
 0  1
 2  3
 4  5
 6  7
 8  9
10 11
12 13
14 15
16 17

Here "a" is a 3 dimensional array with axes of length 3, 3 and 2. We can get the shape of the array by using the "$" monadic verb.
  $a3 3 2


The rank of an array is essentially the dimensionality of the array. For example, still using "a":


#$a
3

Here we used the "#" verb to get the size of the array. Of course, it is 3 dimensional.

The rank is very important as it determines how verbs act on an array.
But not only arrays (nouns) can have ranks. Verbs (operators) also have rank.

In part II we will look at verb ranks.







Sunday, August 19, 2012

Some primitives...

I will briefly go through some of the primitive verbs used in J. These are some of the inbuilt functions (both dyadic and monadic) that seem to be pretty ubiquitous in J code.

Arithmetic Dyadic Verbs
Addition: 2 + 5 6 7  
Subtraction: 4 - 6 
Multiplication: 2 * 4 6 8 
Division: 5 % 6
Exponent: 8 ^ 9
Logarithm: 8 ^. 64 ( = 2)Root: 3 %: 27 ( =3)
Greater: 5 >. 20 ( =20)
Lesser: 9 <. 21 ( =9)GCD:  3 +. 7 ( =1)LCM: 4 *. 10 ( =20)

Arithmetic Monadic Verbs 
Floor: <. 6.1   ( = 6) 
Ceiling: >. 6.1 ( =7) 
Sign: * _4 ( =_1) 
Factorial: ! 5 
Random Integer: ? 7 ( = random int from 0,...,6) 
Random Real: ? 0 ( = random real from 0 to 1)
Comparisons, producing 1 or 0, for true and false, respectively
Equality: 2 = 1 ( = 0) 
Greater than: 1 > 2  
Greater than or equal to: 1 >: 2  Note - don't confuse with dyadic >. 
Less than: 3 < 4 
Less than or equal to: 3 <: 4 Note - don't confuse with dyadic <. 
Inequality: 3 ~: 4
Boolean Operations
OR: +.NOR: +: AND: *.NAND: *:XOR: ~:XNOR: =  
Monadic: 
NOT: -. 


Some boolean examples:

   1 +. 0 (OR)
1
   1 *. 0 (AND)
0
 
   1 0 1 0 0 1 *: 1 (NAND)
0 1 0 1 1 0
Some Binary:

We can also do bit shifting. Here we will shift the number 1 by 3 bits (left rotate):

3 (32 b.)18
 Of course, the output is 8. We can also display the output as a binary value:


#: 4 (32 b.) 31 1 0 0 0 0


Here we used the verb "#:" to change from a decimal number into its binary form.
We can change it back:

#.1 1 0 0 0 0
48


Perhaps in another post I will look into using hexadecimal representations.

Take and Drop List Verbs:

 Take - here the left operand is the index and we take the elements from the list with index less than this.


       1 {. 2 3 5 7  
2    
   5 {. 3 4 6 7 7 8 9 2 1 3 
3 4 6 7 7    
   6 {. i.20 
0 1 2 3 4 5



Drop - same as take but we drop these elements from the original list.


   3 }. i.10
3 4 5 6 7 8 9
 
   6 }. 'A long time ago in a galaxy far, far away...'
 time ago in a galaxy far, far away...
 
   _10 }. 'A long time ago in a galaxy far, far away...'
A long time ago in a galaxy far, f

Well those are some of the basic operations. You can see more here: http://www.jsoftware.com/jwiki/HenryRich?action=AttachFile&do=get&target=J602_RefCard_color_letter_current.pdf







Saturday, August 18, 2012

Boxes

We have seen 1D arrays and multi-dimensional numerical arrays. But what if we want a structure to hold different types of data? For example, we can create a structure, a box, containing both numeric and charcter data.
First we will have a quick introduction to character data.

      charlist =: 'Hello world!'

This creates a D character array. We can use the indexing verbs "{" and "}" to find sublists.

      1{charlist
      e

1} asks for the element of charlist at position 1, similar to C's charlist[1].

      1 2 3{ charlist
      ell

Here we took the 1st, 2nd and 3rd elements of the char array.
We can combine two lists thus.

   charlist =: ' Hello ' , 'world!'

where "," is the verb for concatenating elements.

OK. So what if I try to concat a character list with a numerical list?

    somelist =: 'A phrase', 1 2 3
    | domain error
    |   somelist=:'A phrase'    ,1 2 3

Uh oh. Big problem. The interpreter doesn't want us to do that.
But we can make a "box" to hold both numeric and character data. Here is how:

     char =: 'some important info'
   num =: 1924 1945 1986 1998
   box =: (<char),(<num)
   
   box
┌───────────────────┬───────────────────┐
│some important info│1924 1945 1986 1998│

So the box, which is a scalar object, i.e. it has no size (check $#box), contains one element of char data and one of numerical.

We can search the box to find the data:

         >num
        1924 1945 1986 1998

finds the data corresponding to "num".
We can also go further and make tables of data. For example:


       char1 =: 'important dates'
     char2 =: 'notes'
     num1 =: 15 2
     num2 =: 17 5
     num3 =: 25 12
                        
     note1 =: 'birthday'
     note2 =: 'anniversary'
     note3 =: 'Christmas'


     datebox =: (<char1),<char2
     dates1=: (<num1),<note1
     dates2=: (<num2),<note2
     dates3=: (<num3),<note3

     ((datebox,:dates1),dates2),dates3
┌───────────────┬───────────┐
│important dates│notes      │
├───────────────┼───────────┤
│15 2           │birthday   │
├───────────────┼───────────┤
│17 5           │anniversary│
├───────────────┼───────────┤
│22 11          │Christmas  │
└───────────────┴───────────┘


Here we used the useful dyadic verb ",:", "laminate" which sticks one array on top of another.
An example:

    a1 =: 1 2 3 4
    a2 =: 2 4 6 8
    
    a1,:a2

   1 2 3 4
   2 4 6 8

What about:

    a1 =: 1 2 3 
    a2 =: 2 4 6 8
    
    a1,:a2
    1 2 3 0
    2 4 6 8

The interpreter appends a zero to the top array, as it sees there are too few elements.







Friday, August 17, 2012

Is it prime?

I will write a function (verb) to find if a given integer is prime or not. I'm sure there are much better ways to do this in J than the one I am using, but I wanted to do it for myself. In C style languages it is easy to find if an integer is prime. Just follow the following steps:

  1. Make a loop through all positive integers less than the (floor of) the square root of the given integer. i.e if we want to find if 48 is prime, then we just need to check to see if  2 3 4 5 or 6 divide it.
  2. Loop through the numbers. Use "%" to check the remainder on division. If remainder is zero, break out of the loop and declare our number not prime.
  3. If we reach the end of the loop, we know our number is prime.

In J, there isn't really looping. I had a good think how to do the primality test and the only way I found (without looking at anyone else's code) was to create two functions (verbs). One is a dyadic verb, and the other monadic.

The first verb shall be called ISDIV (meaning "is divisible"):

         ISDIV=:    dyad :'0=x|y'

I think this function is pretty clear. It checks if y divided by x leaves remainder zero. Or checks if y is divisible by x.

          2 ISDIV 4
    1

because 4 is divisible by 2. Here one equates to true, 0 to false.
Now we do the dyadic verb, which is a little more complicated:

       ISPRIME =: monad : '1=#((1+i.>.y^0.5) ISDIV y) #(1+i.(>.y^0.5))'

What's going on here? Well, we check if y ISDIV by all the values up to >.y^0.5, that is, up to the square root of y. This will give us a list of 0's and 1's, corresponding to divisible and not divisible. In teh case of zero 
     
     0 ISDIV y

outputs zero. With our list we now use the dyadic verb "#" (not to be confused with monadic "#", which is tally). This verb copies the 1's form the left operand to the list, which is the right operand. In effect it gives us only those numbers which divide y. More importantly, it gives us the length of the list of those numbers. This is what the monadic "#" at the front means. It gives us the length of the list of divisors of y. We already know that 1 is in the list. So we check to see if the length of this list equals 1, "1=#...". If it does the output is 1 (true), else output is 0 (false).
    
For example:

      ISPRIME 13
      1
      ISPRIME 70
      0
  
Well that was my first attempt at a primality test. I would have liked to have written it with only one function. But my J powers are still weak. I can also already see slight flaws. There is no need to test if 1 is a divisor of a number, so the test of this is wasted. Not a big problem, but...

The verb ISPRIME could easily be modified to not only give us the primality of y, but to output the list of proper divisors.

            DIVLIST =: monad : '((1+i.>.y%2) ISDIV y) #(1+i.>.y%2)'
     DIVLIST 6
     1 2 3 

We could go even further, and calculate sigma(y). That is, the sum of all the proper divisors.

           SIG=: monad : '+/((1+i.>.y%2) ISDIV y) #(1+i.>.y%2)'

All we did was append the +/ on the front. Wait, so now we can test if y is perfect.
           
         ISPERFECT =: monad : 'Y = SIG y'
     ISPERFECT 6
     1

     ISPERFECT 28
     1

     ISPERFECT 18
     0

Beginning Matrices

This topic is all about matrices.
First of all I will show a few ways to make a simple 1D list:

          list=: 3 5 2 66 7 8 90 6 5
or
    list=: i.8
or
    list=: 7 ? 5

The last method is interesting as it uses a new verb "?" (taking a left and right operand, making it dyadic) which, in the above case, means "randomly select 7 integers from 0 to 4. 
To select one random integer only, we can leave off the left operand, using the monadic verb ?:
  
     ? 5

This is similar to Java's:

    Random r = new Random();
    int x = r.nextInt(5);

Let's make a random 2x2 matrix:

    matrix=: 2 2 $ 4 ? 2

Giving output (obviously random so your's may be different):
   
    1 0
    0 1

That was fun. What did we do? We created a matrix, declared it to be 2x2 (declaring the shape of the matrix, using the left operand(s) of "$") and we filled it with 4 random integers of possible values 0 or 1.

Let's do another example. This time, non-random.

       matrix=: 2 3 $ 0 1 2 3 4 5 

This gives output:

    0 1 2 
    3 4 5 

This is a 2x3 matrix filled with values from 0 to 5. You can see it fills the rows before the columns. This may be important to note.
We could have equally written this:

   matrix=: 2 3 $ i.6

because i.6 creates a list 0 1 2 3 4 5.

Anyway, let's do some stuff with matrices. First, let's add two matrices.

       ma=: 2 2 $ 0 1 2 1
   mb=: 2 2 $ 1 2 0 1

   ma+mb

The result is:

       1 3
   2 2
 
as we might expect. How about multiplying two matrices?
   
      ma*mb
      
   1 3
   2 2

Wait, that's not right. That is because * multiplies the corresponding elements of ma and mb. In fact, we can only use this function (verb) like this if the two matrices have the same shape.

If we try:

      mc =: 2 3 $ 1 3 4 5 2 3
      mc
     1 3 4
     5 2 3
     mc*ma

We get

   |length error
   |   mc    *ma

The J interpreter didn't like that. Because it doesn't know what we are trying to do. What does the last column of mc get multiplied by?

We want to do matrix multiplication now. How can we do this? Well, we have to use inbuilt J operations:

    ma +/ *. mb
  0 1
  2 5

We can similarly calculate 

     mb +/ *. ma

and

  ma +/ .* mc

which gives:

  5 2  3
  7 8 11

What about determinants? Inverses?
Well, if we have a square matrix, then we can get the determinant:

  det=: -/ .* ma

Which gives:

  _2

i.e. -2. 

How about inverses?

  inverse=: %. ma
  _0.5 0.5
   1   0

That looks about right. What if the matrix is singular?

  singular=: 2 2 $ 1 2 2 4
  -/ .* singular
  0

OK, so the determinant is zero. So what happens if we try to invert the matrix/

   %.singular
   |domain error
   |       %.singular

Oh. The interpreter did not like that.

OK. One last thing is this:

       ma %. mb
    _4 _1
    2  1

Here %. is used in the dyadic sense, with two operands, ma and mb. This result is the same as doing:

      (%.mb)+/ .*ma
    _4 _1
    2  1

i.e. the inverse of mb multiplied by ma.


Thursday, August 16, 2012

Mean of a list

This blog is here for me to share to the world my own personal struggles with the J language. I have only been programming in this language for less than two days, so forgive my incompetence.
I intend this blog to give examples of common and perhaps uncommon functions using J. The purpose is for my own learning more than anything.

The first post will be the easiest function of all, finding the mean of some set of data.
Suppose I want to find the average (mean) age of a collection of adults.

          data=: 20 21 23 23 24 25 27 30 33 34 45 50 56 63
    mean=: +/data%#data

And the answer is... 33.8571. That's it. Easy. Now just a quick explanation:

  • As you might guess + means "plus". 
  • +/ indicates that we are to plus through the list, i.e. 20+21+23+... Forward slash is a special operator that can be used with functions, or "verbs".
  • % is "divide" in J. 
  • # is a special function called "tally" which gives the size of the list.

But what if the answer is too precise? I don't need to know the mean age to 6 significant digits. How about I round it up to three?

        mean=: 3": +/data%#data
or two:
   mean=: 2": +/data%#data

or just round it up to the next integer (i.e. ceiling):
        mean=: >. +/data%#data 

(naturally, <. is the floor function)

We can also turn our function into a more general use function:
         mean=: monad : '3": +/y%#y ' 

Here, we have changed three things. We stuck a "monad" in the middle of the code, and we changed "data" to "y". And then we wrapped the code in single quotes.

Monad - indicates the function is monadic, i.e. takes one argument, on the right side. The other option (that I'm aware of) is Dyadic, which takes two arguments - one on the left, one on the right.
"y" is just a general variable to indicate the list which we will use as the argument. In C related languages it would look something like this:
       float mean(int[] y){
     ...
   }

Finally, the single quotes (never double) wraps the actual code of the function (or verb as they're called).