May 26 2014

Lessons from APL, a “lost” language

A few weeks back the forum that I go on often held a obfuscation challenge, and people joked around about submitting a entry that was coded in APL.

APL (A Programming Language) is a programming language that was developed at IBM by mathematician Kenneth Iverson.

It is mainly infamous because of its need to have a separate keyboard installed to code in it:

The challenge involved making a simple program:

You will be provided a random large integer, via stdin.
If the number is prime, print "prime". Otherwise, print "not prime"
Example:
   $ echo 11 | prime
   prime
   $ echo 122 | prime
   not prime

One of the bigger issues with writing this blog post is that most browsers can’t even display a lot of the symbols I need to demo.

Above is what I submitted, and I think its a great idea to go though on what the program and give a small demo on how powerful APL really is.

It’s first worth noting, I used GNU APL. Since most APL interpreters where designed way before i386 was around (Or if they where, for MS-DOS), there is not a great deal of choise.

$ echo "777" | apl --noColor -f prime.apl --noCIN --noCONT --silent
⎕:
not prime

$ echo "7" | apl --noColor -f prime.apl --noCIN --noCONT --silent
⎕:
prime

One of the first things I really got quite annoyed by is the large amount of flags needed to make it function as a “normal” language. --noColor --noCIN --noCONT --silent Though I suspect this is mostly just a GNU APL thing.

Overall though I though it was a nice language, My explanation to the large amount of symbols are below:

So there are 5 major vars,

I l T E X and K

The first three parts are the fairly simple parts of the code:

Hiding the strings

T ← 'eimnoprt '
E ← 4 1 4 9 5 6 0 3 1
X ← 2 5 8 2 6 7 2 2 1

So here we are seeing T being set to a string. this string is “not prime” alphabetically sorted.

The E and X vars are a mask that are used to put T in the correct order.

This is done by running ⌈ over it, that goes though E and X and picks the biggest var of each, so E⌈X == 4 5 8 9 6 7 2 3 1

In that order when you run T[E⌈X] it will equal not prime

Moving on

First we start off a new function by asking ∇K This makes a var that will be turned into a function until ∇ is inputted again.

I ← ⎕ takes a number in from stdin and puts it in I.

l ←(((X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I)∊I)[⍒(((X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I)∊I)][1^(~E[7])] is a complex one but can be simplified a great deal by noticing the repetition.

(X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I is a function that will get a list of all primes leading up to the number in I.

When I is 7 we can get the following vars from it.

   I ← 7

   (X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I
2 3 5 7

2,3,5,7 is prime.

Expanding this more we can notice (((X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I)∊I)

Or in a more easy to read fashion: ( WhatWeSaw )∊I).

This does a check to see if any of them match what put in I.

   I ← 7
   test ← ((X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I)
   test
2 3 5 7
   test ∊ I
0 0 0 1

As can see all of the older vars have been turned into 0’s apart from the 7 that we put in, that was turned into 1.

Next we take the output as an array and try and get a element from it.

l ←((( WhatWeHaveSeen )[⍒(((X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I)∊I)][1^(~E[7])]

As you can note. We have used the same function twice. So I will remove that to make it clear.

l ←((( WhatWeHaveSeen )[⍒( WhatWeSaw )][1^(~E[7])]

The ⍒ function will sort everything to make sure that the highest value element is at the front.

   l ←(((X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I)∊I)[⍒(((X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I)∊I)]
   l
1 0 0 0

The last part is [1^(~E[7])] at the end. You can probably guess at this point what this does.

E[7] is part of the jumble array, the 7th element is 0.

The ~ function inverts. so 0 becomes 1.

We can now simply put this as [1^1], Unsurprisingly this is 1.

To print Prime or not to.

To pick if we should print prime or not prime is handled by (E[1]×l)↓T[E⌈X]

We have already gone through what T[E⌈X] does.

   T[E⌈X]
not prime

the ↓ function will take one off the front, for example.

   1↓T[E⌈X]
ot prime

In this, the amount to chop off the front is dependent on what (E[1]×l) returns.

We can simply this to 4×l. We can already look at see that l is the output (1 or 0).

If it is 1 then that is multiplied by 4 and thus becomes 4.

   4↓T[E⌈X]
prime

or if it isn’t because it is a multiplication by 1 it becomes:

   0↓T[E⌈X]
not prime

Then we end the function using ∇.

All of that function was stored in K. So then we just call K. Then all of the code we have written above runs.

It’s worth noting that there isn’t an exit issue, this is because )OFF (the command to exit) as not working in my tests, So I left it out since the rules didn’t say it has to exit.

But wait you didn’t explain the huge long function. Well now that you have asked…

Note, I have made the var names easier to distinguish going down

Before in this we simplified the long line into a basic component:

((X[1]=+⌿E[7]=(⍳J)∘.|⍳J)/⍳J←I)

First we are going to remove the number fill ins, Like the ones I did last time.

((2=+⌿0=(⍳J)∘.|⍳J)/⍳J←I)

Now we have a zero and two in the mix.

We know that I at the end means the number that the user had inputted.

This function works by assuming that is number A is multiple of another number (B) then the remainder of A divided by B is zero.

The function | gives us remainders.

   7|10
3

We can do this on an array/vector of numbers. So a better way to explain this function is:

   3|1 2 3 4 5 6 7 8 9 10
1 2 0 1 2 0 1 2 0 1

Then we can use ∘. to try this for more than one number at once.

   3 4 5∘.|1 2 3 4 5 6 7 8 9 10      
1 2 0 1 2 0 1 2 0 1
1 2 3 0 1 2 3 0 1 2
1 2 3 4 0 1 2 3 4 0

If this does not make sense (don’t worry it made no sense to me) I would annotate it like this:

   3 4 5∘.|1 2 3 4 5 6 7 8 9 10 

    1 2 3 4 5 6 7 8 9 10     
 %---------------------- 
3|  1 2 0 1 2 0 1 2 0 1
4|  1 2 3 0 1 2 3 0 1 2
5|  1 2 3 4 0 1 2 3 4 0

So we can use this trick to look for primes now:

   X ←10
   ⍳X
1 2 3 4 5 6 7 8 9 10
   (⍳X)∘.|⍳X
0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1 0
1 2 0 1 2 0 1 2 0 1
1 2 3 0 1 2 3 0 1 2
1 2 3 4 0 1 2 3 4 0
1 2 3 4 5 0 1 2 3 4
1 2 3 4 5 6 0 1 2 3
1 2 3 4 5 6 7 0 1 2
1 2 3 4 5 6 7 8 0 1
1 2 3 4 5 6 7 8 9 0

Here we now have a bunch of remainders.

Because we only care about 0 and 1 remainders in this case, I will be adding 0= to the beginning.

   0=(⍳X)∘.|⍳X      
1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1
0 0 1 0 0 1 0 0 1 0
0 0 0 1 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1

Now adding +⌿ to the beginning means that we will add everything in the 2D array upwards.

   +⌿0=(⍳X)∘.|⍳X
1 2 2 3 2 4 2 4 3 4

(Observe that the first number is 1 because all but one row is 1 in that col).

Now we can finally spot what we are looking for. We are only looking for where the results are 2

   2=+⌿0=(⍳X)∘.|⍳X
0 1 1 0 1 0 1 0 0 0

Then we compress the array down:

   (2=+⌿0=(⍳X)∘.|⍳X)/⍳X
2 3 5 7

Oh look. Prime numbers!

The downside of this way is that its really really slow. But then again, this wasn’t a speed showdown.