This article exists to showcase my APL programs and explain how they work in detail, particularly to those who may not be familiar with APL, although a light familiarity is required. Most of the APL I write is for solving simple mathematical problems or other such things posed to me, in a single line of code. As opposed to documenting a single APL program, I decided to collect some of that APL I've written over these years and document it. The APL language is very fun, given its quite concise and carefree nature: every loop, with few exceptions, is implicit; programs are written purely for their results, rather than caring precisely how that result is arrived at or transformed; and memory usage and storage exhaustion aren't a concern. APL is proof that good notation goes a long way.
This article contains many code fragments and some of these are already under the GNU Affero General Public License version three; therefore these programs are all licensed under the GNU Affero General Public License version three.
I will firstly be documenting pieces of my Masturbation interpreter written in APL, relating to that 2017-02-02 article. The first fragment is the searching routine, for brackets:
⍝ This is a searching routine for [ and ]; it returns the index of the corresponding bracket. ∇ z←search x;⎕IO ⎕IO←0◊z←0⍳⍨+\(-x=convert'[')+x=convert']' ∇
My convert function merely coerces the character argument into an integer, as x is an integer array. The ⎕IO is set to zero for zero-based indexing. So, using dyadic = and unary negation, that x array is used to produce two arrays, where the open brackets are negative one and the closing brackets are one, and both are then summed to result in a single array consisting of negative one, zero, and one. The array is then scanned over to produce sums of the elements at each step and then the location of the first zero is located to finish the routine; the execution looks as so, with two nested brackets and some characters inside of them:
¯1 0 ¯1 0 0 1 0 1 ⍝ This is the joined array, reducing each element to its integer. ¯1 ¯1 ¯2 ¯2 ¯2 ¯1 ¯1 0 ⍝ This is the scanned array, see how the nesting is shown. ^ ⍝ This is that first zero, which for this is past the outer nesting.
The next fragment is a predicate for determining if the program uses brackets properly, meaning in a balanced and ordered fashion:
⍝ This predicate determines whether [ and ] are balanced properly or not. ∇ z←balanced x;⎕IO;t ⎕IO←0◊t←0=+/(-x=convert'[')+x=convert']'◊z←t∧~∨/1=+\(-x=convert'[')+x=convert']' ∇
Note APL executes right-to-left, yet pieces separated by the diamond are executed left-to-right; the ⎕IO is again set to zero here. To simplify the predicate this executes in two parts, performing the same trick as my search function, but reducing addition across instead of scanning and so leading to a single sum, which is then compared to zero. Another similar process is then used to scan addition across this same result array, seek out any ones, reduce that to a single value with an or, and then see if the first test was true and this test is false; if a single one was found, that indicates the use of a closing bracket before a corresponding opening bracket, which is incorrect. This execution looks as so, with an improperly nested example this time:
¯1 0 ¯1 0 1 1 0 1 ⍝ This is the joined array, reducing each element to its integer. 1 ⍝ This is the sum thereof, it's not zero, so it's not balanced. ¯1 ¯1 ¯2 ¯2 ¯1 0 0 1 ⍝ This is the scanned array, notice it doesn't end with zero. 0 0 0 0 0 0 0 1 ⍝ These are the elements that equal one. 1 ⍝ This is the result of reducing or; it's negation is zero, false.
This is a simple line that produces ever more accurate values of e for larger values of n:
All this does is generate an array of integers, beginning from ⎕IO, adjust it so that it begins from zero, obtain the factorial of each integer, have each factorial replaced by its reciprocal, and then reduce this to a single sum.
This solves a trivial math problem I came across while skulking around:
This solves the problem of, given array of N distinct numbers from zero to N, determining which lone number is missing from the sequence; a solution can be given in linear time and constant space. The solution is trivial, as it can be determined what the sum should be if all numbers were present, and so that is arrived at, the difference with the sum of that array given is found, and then the answer is known. The execution looks as so, for N being 10:
0 6 1 5 3 2 9 7 8 ⍝ This is an example array missing four. 41 ⍝ This is the sum thereof. 1 2 3 4 5 6 7 8 9 ⍝ This is the complete array, sans zero. 45 ⍝ This is the sum thereof. 4 ⍝ This is the difference of the sums, four, the answer.
This solves a simple problem which was posed to me in a discussion and was that most brief solution:
This produces a checkerboard pattern of X rows and Y columns. This is simple to perform in the case of odd columns and reshaping an even pattern, as it naturally staggers, however that even case poses issues. What is done is checking if the number is even, incrementing it by one if so and so to that larger odd number, and the reshape is performed. Then in the even case, all but that last column is taken to get the result, with the odd case taking that full result. This is then rather simple code to produce an X by Y checkerboard in all cases. Follows is an example for the odd case.
The following is produced when Y is ten and X three; the value of X is largely irrelevant:
# # # # # # # # # # # # # # # #
This pattern is actually eleven-by-three, note. Removing the final column produces this:
# # # # # # # # # # # # # # #
The following APL program accepts a one-dimensional pattern and transforms it into a two-dimensional pattern where the first row and column are the source pattern and the remainder is spaces; this is a common programming challenge and I've never seen any APL solution. I'm not pleased with how long my program is and believe it could be shorter. The value N is the pattern and M is the result:
Follows is an example usage of this program, showing the intermediate steps:
N←'VERISI' M←N⍴⍨2⍴⍴N◊M VERISI VERISI VERISI VERISI VERISI VERISI M[;⎕IO]←N◊M VERISI EERISI RERISI IERISI SERISI IERISI M[1↓⍳⍴N;1↓⍳⍴N]←' '◊M VERISI E R I S I
Spurred by my other implementations, this is the Rule 30 cellular automaton in one line:
N←(1 1,~N)=(0,N,0)∨N,0 0
Here, N is a bit vector; this R30 function is defined for convenience; with another line the IR30 is defined to make calling more convenient:
∇ R←R30 N R←(1 1,~N)=(0,N,0)∨N,0 0 ∇ ∇ L IR30 R ⍝ The L is the repetition count and R the pattern. R◊→0↓⍨0≠0⌈L←L-1◊R←(-~¯1↑R)↓(~↑R)↓R←R30 R◊→1 ∇
Rule 30 is a simple, one-dimensional cellular automaton in which new values for cells are found with Left XOR (Current OR Right). My first attempt in this was to transform a one-dimensional pattern to a vector of compressed three-length-vectors, interpret those as binary numbers, and index these with a table to determine the next cell value, but this was arduous and so I sought a different approach. My second attempt involved reshaping the array and then modifying each row before reducing along the second axis, but this was similarly fruitless, although it led to the third and successful approach. The contiguous pattern can grow by two cells, at most, in any generation and this fits well with the shifting approach. While APL provides bit OR, bit XOR is built with negation and equality; a proper set of examples will make the inner workings clear:
N←1 N,0 0 1 0 0 0,N,0 0 1 0 (0,N,0)∨N,0 0 1 1 0 1 1,~N ⍝ The ones are an optimization. 1 1 0 0 0 N ⍝ This is what that is before negation. 0 0 1 N←(1 1,~N)=(0,N,0)∨N,0 0 ⍝ Negation and equality make for XOR. N 1 1 1 N,0 0 1 1 1 0 0 0,N,0 0 1 1 1 0 (0,N,0)∨N,0 0 1 1 1 1 0 1 1,~N 1 1 0 0 0 (1 1,~N)=(0,N,0)∨N,0 0 1 1 0 0 1
As I wrote this, the finished function seemed reversed, at least concerning how I expected it to be, but reversing everything in the logic is superior to explicitly using ⌽. Follows is a basic example using the functions; notice how IR30 array size is trimmed where possible to make display more nice:
R30 R30 R30 1 1 1 0 1 1 1 1 5 IR30 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 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0
This accepts the ``Look and Say sequence'' or a sequence which resembles it and reverses it; I wrote this in my head while trying to sleep one morning and when I later gave it to the machine I realized I'd actually written a reverser, not a generator for the sequence. The N holds the vector:
The mechanism is simple, as it merely splits that vector into even and odd indexed sets, and repeats them appropriately. Follows is an example showing the intermediate steps:
N←3 1 2 2 1 1 ⍝ This is three ones, two twos, and one one. (~2|⍳⍴N)/N ⍝ These are the even elements to be repeated. 1 2 1 (2|⍳⍴N)/N ⍝ These are the odd elements providing the counts. 3 2 1 ((2|⍳⍴N)/N)/(~2|⍳⍴N)/N 1 1 1 2 2 1
Follows are more examples using the previous value of N:
N←((2|⍳⍴N)/N)/(~2|⍳⍴N)/N◊N 1 1 1 2 2 1 N←((2|⍳⍴N)/N)/(~2|⍳⍴N)/N◊N 1 2 1 1 N←((2|⍳⍴N)/N)/(~2|⍳⍴N)/N◊N 2 1 N←((2|⍳⍴N)/N)/(~2|⍳⍴N)/N◊N 1 1 N←((2|⍳⍴N)/N)/(~2|⍳⍴N)/N◊N 1
Observe the invariant of an even vector length, which the starting value doesn't fulfill.
I entertained thoughts of lower systems which are nicely suited to use from higher systems. Logical count is such a lower system and I realized I'd never written it in APL before. This behaves nicely as any monadic primitive scalar function would in that it accepts any shape of arguments and behaves identically for each element, returning a similarly-shaped answer. The N holds the vector:
This collects the base two representation of each element of N by determining the largest integer in the set, collecting the ceiling of its base two logarithm, and then using that to determine how many bits are necessary for the representation function to use. As this adds a new dimension, I can then simply reduce along this new first dimension to collect the sum of the bits and so the logical count for each element. A one is added to the largest of the set to prevent errors in the case of zero or other powers of two. This function operates correctly on the empty set as well, although in fashion rather inefficient; reduction of the empty set returns the smallest representable negative number of the system and this results in an unnecessarily large set of twos being created to achieve an answer that's empty; in any case, the empty set is uncommon for this and it's hardly an issue. Follows are some examples:
N←3 3⍴⍳9◊N 1 2 3 4 5 6 7 8 9 +⌿N⊤⍨2⍴⍨⌈2⍟1+⌈/,N 1 1 2 1 2 2 3 1 2 N←⍳9◊N 1 2 3 4 5 6 7 8 9 +⌿N⊤⍨2⍴⍨⌈2⍟1+⌈/,N 1 1 2 1 2 2 3 1 2 N←⍳0 ⌈/,N ⍝ This APL system uses negative infinity for this negative limit. ¯∞ ⌈2⍟1+⌈/,N ⍝ Only the real part will be used for the reshaping, making a large vector. 1024J5 +⌿N⊤⍨2⍴⍨⌈2⍟1+⌈/,N ⍝ Ultimately, you get nothing in the summing. N←10 +⌿N⊤⍨2⍴⍨⌈2⍟1+⌈/,N 2