Goodbye

At the end of May 2019 I am leaving Dyalog, so it seems like a good time to reflect on my time here and what I’ve learned from APL and the APL community.

When I joined Dyalog in 2010 I knew nothing about APL, so there was a really steep learning curve as I got to grips with both the language and its implementation. I was using some of my previous experience with compilers to improve the performance of the implementation, and thinking about ways to compile APL. This is a tough problem, and one that many people have worked on over the years (see for example Timothy Budd’s 1988 book An APL Compiler). My own ideas have shifted as I’ve gained more experience with APL and the way it is used. At first I thought “writing a compiler” was an obvious thing to do; now I think that hybrid compiler/interpreter techniques are much more promising, and Dyalog’s recent experiments with deferred execution and thunks are a good step in that direction.

At the same time, there was a lot of excitement around the APL language itself. Dyalog was working on APL#, a new .NET-based APL dialect (sadly abandoned as Microsoft’s own commitment to .NET waned). And Dyalog APL itself was starting to borrow more language features from the SharpAPL/J branch of the family tree, starting with the Rank operator and continuing over many years. This prompted me to delve more into the history of APL, to try to understand some of the fundamental differences between different implementations, so that we could reconcile those differences in Dyalog APL and provide, as far as possible, the best of both worlds. I think we’ve done pretty well in that, as evidenced by the fact that many APLers are happily using Rank, Key, function trains et al in an APL2-based language, something that seemed unthinkable a decade ago.

One of the most gratifying developments in the time I’ve been working with APL is the rapid growth of new APL implementations, open source projects and grass-roots enthusiasm. In particular, the open source movement has made it much easier for anyone with a good idea about language design to implement it, and share it with the world. We’ve seen a wide variety of new APLs and APL-inspired languages popping up over the years, ranging from full-featured to highly experimental, including but not limited to (in roughly the order I remember hearing about them): ELI, ngn/apl, GNU APL, Ivy, Aprildzaima/APL and APL\iv.

And speaking of new APLs, of course there is Co-dfns, a compiled APL implementation that tries to solve another tough problem: harnessing the power of GPUs and other massively parallel hardware in a way that makes it accessible to the end user. This is something that many people are trying to do, in a wide variety of languages, but as far as I can tell no-one has quite succeeded yet. The state of the art is still that, in order to get good performance, you need quite a lot of mechanical sympathy for the underlying hardware. But Co-dfns has come a long way, and if any language is well-suited to run on parallel array processors then surely it is APL!

This brings me on neatly to my next job: I’ll be working on compilers for GPUs, the parallel computers that render 3D graphics. They are closely related to their “general purpose” cousins the GPGPUs, which are used for pure number crunching, and to so-called tensor processing units (TPUs) that simulate neural networks for use in machine learning and artificial intelligence. “Tensor” here just means an array of arbitrary rank, or as we would say: an array. For programming TPUs there is a Python-based framework called TensorFlow. But, look closely at the APIs for some of the core TensorFlow libraries, and you’ll see operations like reshape, reverse and transpose, which are eerily similar to their APL equivalents. There truly is nothing new under the sun!

With fond regards to all APLers,
Jay.

A message from the CTO

Hello! Further to Morten’s kind words of introduction, I’d like to take this opportunity to introduce myself as the new CTO of Dyalog Ltd.

About me

I’m a newcomer to APL. When I started working for Dyalog in 2010 I had only seen the Game of Life video, an intriguing but baffling glimpse into a world of squiggles. But I soon got the opportunity to learn from some giants of the language, and came to appreciate the power and beauty of the notation. Later I learned that, despite its venerable history, the language is not set in stone; with care and attention we can develop and extend it to increase its power, relevance and performance, without sacrificing its elegance and simplicity.

We — not just Dyalog, but the wider APL community — are guardians of a rare thing: a language born more than 50 years ago that is not just relevant and useful today, but groundbreaking in the way it embodies data parallelism from the ground up in a simple, consistent notation.

Before working at Dyalog I spent 13 years developing compilers, optimisers and debuggers for more mainstream programming languages, including C and Java. This has given me a good insight into how to get the best performance out of modern computer hardware, and I’ve made it my continuing mission to help bring that level of performance to APL!

My rôle

As CTO I’ll be responsible for day-to-day management of the core interpreter development team, and for the overall technical strategy of the company. This strategy must include getting the maximum performance out of current and future hardware, but also:

  • Keeping the quality of the product as high as possible.
  • Embracing new platforms and attracting new users.
  • Improving our development tools, and making it easier to create and deploy new applications.
  • Ensuring that Dyalog APL can interoperate smoothly with modern frameworks and services.
  • Continuing to look at new ways of (carefully!) extending and improving the core APL language.

I’m looking forward to working on this alongside the “new” CXO, Morten. At Dyalog we take a lot of care in the design of new features, and I firmly believe that a lively discussion between CXO (representing the needs of the customer) and CTO (representing the language designers and implementers) will only improve the quality of the designs we come up with.

On the road

In the future I expect to spend a bit more time out and about, showing off Dyalog APL, and talking to all of you about your own needs and expectations of the product. In particular, this year I’ll be at DYNA16 in Princeton in April, and the Dyalog ’16 User Meeting in Glasgow in October. I look forward to seeing, or meeting, all of you soon!

Posted in CTO

Solving the 2014 APL Problem Solving Competition – Cryptography Problem 3

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. In this post we’ll conclude looking at the cryptography problems from Phase II that we started looking at in a previous blog post and continued in a further blog post.

Cryptography Problem 3 – Playfair Cipher

Task 1 – Squaring Off

The first task is to convert a string into a 5×5 Playfair table. The solution makes straightforward use of APL primitives:

  • Unique () to remove duplicate characters from the string.
  • Without (~) to find the rest of the alphabetic characters that are not mentioned in the string, and again to remove the character J.
PlayfairTable←{
    k←∪⍵
    5 5⍴(k,⎕A~k)~'J'
}

Here it is in action:

      ⊢table←PlayfairTable'KENNETHEIVERSON'
KENTH
IVRSO
ABCDF
GLMPQ
UWXYZ

Task 2 – Encryption

To encrypt a message we need to take two characters at a time, find their coordinates in the 5×5 Playfair table, swap their column coordinates and look up the letters at the new coordinates. There are lots of tricks in the code below of which we’ll describe just a few:

  • To process the message two characters at a time, appending to the result as we go, we use a tail-recursive dfn whose left argument accumulates the result. For an introduction to this technique see this implementation of the Fibonacci function.
  • To find letters in the Playfair table we first look them up in the ravel (i.e. the linearised form) of the table, and then use Encode () to convert this linear index into a pair of coordinates. Decode () does the opposite, converting a pair of coordinates back into a linear index.
  • Mix () and Split () are used to convert between two different representations of the coordinates of the two characters we’re encoding: either as a flat 2×2 matrix, or as a nested 2-vector of 2-vectors. The choice of representation is largely a matter of taste, and it might be fun to play with this part of the code. You could tweak it to work entirely with the flat representation, or entirely with the nested representation, rather than converting back and forth between them.
PlayfairEncrypt←{
    ⎕IO←0                       ⍝ To aid arithmetic modulo 5.
    t←⍺                         ⍝ The Playfair table.
    m←⍵,(2|≢⍵)/'Z'              ⍝ Add a Z if the message length is odd.
    ((m='J')/m)←'I'             ⍝ Convert J to I in the message.
    ''{                         ⍝ Start with an empty accumulator.
        0=≢⍵:⍺                  ⍝ Finished: return the accumulated encrypt.
        1=≢⍵:⍺ ∇ ⍵,'X'          ⍝ Only one character left: add an X.
        p←2↑⍵
        =/p:⍺ ∇(⊃⍵),'X',1↓⍵     ⍝ Duplicate character: insert an X.
        c←(⍴t)⊤(,t)⍳p           ⍝ Coords of each letter in the table.
        c←{
            =/1↑⍵:↑(⍴t)|0 1+↓⍵  ⍝ Same row: move to the right.
            =/1↓⍵:↑(⍴t)|1 0+↓⍵  ⍝ Same column: move down.
            0 1⌽⍵               ⍝ Else swap column coords.
        }c
        p←(,t)[(⍴t)⊥c]          ⍝ Look up new coords in table.
        (⍺,p)∇ 2↓⍵              ⍝ Tail recursion.
    }m
}

Here it is in action:

      ⊢cipher←table PlayfairEncrypt'HELLOWORLD'
KNMWQVZVVMCY

(Note that this result is slightly different from that given in the original problem description, because of some confusion about the rules for handling duplicate letters and odd message lengths, which were clarified later in the student competition forums.)

Task 3 – Decryption

Decryption is very similar to encryption. The differences are:

  • Letters found in the same row of the table need to move left instead of right, and letters in the same column need to move up instead of down.
  • We don’t need to worry about the input having an odd length, or containing the letter J.

Hence the code for PlayfairDecrypt is shorter than but very similar to PlayfairEncrypt:

PlayfairDecrypt←{
    ⎕IO←0                       ⍝ To aid arithmetic modulo 5.
    t←⍺                         ⍝ The Playfair table.
    ''{                         ⍝ Start with an empty accumulator.
        0=≢⍵:⍺                  ⍝ Finished: return the accumulated encrypt.
        p←2↑⍵
        c←(⍴t)⊤(,t)⍳p           ⍝ Coords of each letter in the table.
        c←{
            =/1↑⍵:↑(⍴t)|0 ¯1+↓⍵ ⍝ Same row: move to the left.
            =/1↓⍵:↑(⍴t)|¯1 0+↓⍵ ⍝ Same column: move up.
            0 1⌽⍵               ⍝ Else swap column coords.
        }c
        p←(,t)[(⍴t)⊥c]          ⍝ Look up new coords in table.
        (⍺,p)∇ 2↓⍵              ⍝ Tail recursion.
    }⍵
}

Here it is in action:

      table PlayfairDecrypt cipher
HELXLOWORLDX

Solving the 2014 APL Problem Solving Competition – Cryptography Problem 2

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. In this post we’ll continue looking at the cryptography problems from Phase II that we started looking at in a previous blog post.

Cryptography Problem 2 – Book Cipher Variation

Task 1 – Let’s Get Normal

The first task is to normalise some text by weeding out non-alphabetic characters, collapsing consecutive spaces and converting to upper case. It’s possible to do this all by hand with APL, but it’s much easier to use the ⎕R operator to search for and replace regular expressions.

Taking the transformations in turn, here’s how to convert non-alphabetic characters in message to spaces:

('[^[:alpha:]]'⎕R' ')⍵

Here’s how to convert multiple consecutive spaces to a single space:

(' +'⎕R' ')⍵

And here’s how to convert every alphabetic character to upper case:

('.'⎕R'\u&')⍵

We can combine the first two of these, by converting any sequence of one or more non-alphabetic characters to a single space, giving the following implementation:

Normalise←{
    text←⎕SE.UnicodeFile.ReadText ⍵
    ('[^[:alpha:]]+' '.'⎕R' ' '\u&'⍠'Mode' 'D')text
}

The option 'Mode' 'D' tells ⎕R to operate in Document mode, which processes the whole file at once instead of line by line, as we are not interested in preserving the original line breaks. Here it is in action:

      70↑bor←Normalise'/home/jay/Desktop/BillOfRights.txt'
THE PREAMBLE TO THE BILL OF RIGHTS CONGRESS OF THE UNITED STATES BEGUN

Task 2 – Encryption

In this cipher there are lots of different ways of encoding each character of the message, and we are free to pick any of them. In order to try to “minimise the number of duplicated pairs in the result”, we simply pick randomly whenever we have a free choice. The function pickone helps with this. Given a boolean vector, it first uses {⍵/⍳⍴⍵} to get a vector of the indices of all the 1 bits, and then uses {⍵[?≢⍵]} to choose one of these indices at random.

In this coding of BookEncrypt, the anonymous inner dfn encodes a single character of the message into a (word offset) pair. These pairs are joined together with ⊃,/, a common pattern for catenating strings. The Disclose is required because, in Dyalog, reduction always reduces the rank of its argument, so ,/ on a vector of strings returns a scalar: the enclose of the catenated strings.

BookEncrypt←{
    pickone←{⍵[?≢⍵]}∘{⍵/⍳⍴⍵}
    b←' ',⍺                     ⍝ b has a space wherever a word starts in the key.
    s←{⍵/⍳⍴⍵}b=' '              ⍝ Get the indices of all the word starts.
    ⊃,/{
         p←pickone b=⍵          ⍝ Choose a random occurrence of letter ⍵
         p-←s                   ⍝ and get its offset within each word.
         w←pickone{(0<⍵)∧⍵≤20}p ⍝ Choose a word with a reasonable offset
         w(p[w])                ⍝ and return the (word offset) pair.
    }¨⍵                         ⍝ ... for each letter in the message.
}

Here it is in action:

      ⊢cipher←bor BookEncrypt 'MYSECRETMESSAGE'
480 11 523 11 440 6 115 5 78 16 579 18 696 20 330 16 544 4 658 17 400 9 661 11
      246 18 186 4 482 13

Task 3 – Decryption

Decryption is simpler then encryption, because there is no need to make random choices. All we have to do is:

  • Find the index of the start of each word in the key, as before.
  • Split the input into pairs of numbers.
  • For each pair, find the character in the key at the specified offset from the start of the specified word.

There are various ways to split the input into pairs of numbers. Here, we do it with the Rank operator (). Encrypting an N-character message gives a vector of 2×N numbers. To split it into pairs we first reshape it into a matrix with N rows and 2 columns; and then use f⍤1 to apply f to the rank-1 subarrays of this matrix, which are its row vectors.

Here’s the code:

BookDecrypt←{
    b←' ',¯1↓⍺                  ⍝ b has a space wherever a word starts in the key.
    s←{⍵/⍳⍴⍵}b=' '              ⍝ Get the indices of all the word starts.
    {
        (w o)←⍵                 ⍝ Get word number and offset
        b[s[w]+o]               ⍝ and find the character at that position
    }⍤1⊢(0.5×≢⍵)2⍴⍵             ⍝ ... for each pair of numbers in the input.
}

And here it is in action:

      bor BookDecrypt cipher
MYSECRETMESSAGE

To be continued…

Solving the 2014 APL Problem Solving Competition – Cryptography Problem 1

This post is a continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. I’ll start by looking at the cryptography problems from Phase II.

Cryptography Problem 1 – Vigenère Cipher

The cipher is described using a large table of letters, but you don’t need to create this table in APL. Instead, you can convert each letter of the key and the corresponding letter of the message to numbers; add them together; and then convert the result back to a letter. Some subtleties:

  • We want the result of the addition to “wrap around” at the end of the alphabet, so 25 + 1 = 26 (Z) but 25 + 2 = 27 which should wrap round to 1 (A). This is called modular arithmetic.
  • We can implement modular arithmetic easily using APL’s Residue primitive, but this works most naturally when the alphabet is numbered from 0 to 25, rather than from 1 to 26. To use 0-based numbering, I’ll set ⎕IO←0 in the code below.
  • An idiomatic way of converting letters to numbers is to look them up in the ⎕A, the upper case alphabet: ⎕A⍳⍵. To convert the other way we can simply index into ⎕A: ⎕A[⍵]. (For more comprehensive conversions between characters and numbers see the ⎕UCS system function.)

The code is then straightforward:

VigEncrypt←{
    ⎕IO←0                       ⍝ use 0-based numbering
    key←(⍴⍵)⍴⎕A⍳⍺               ⍝ convert key to numbers and expand to length of message
    ⎕A[26|(⎕A⍳⍵)+key]           ⍝ add key to message and convert back to characters
}

To encrypt the message we added the key (modulo 26). To decrypt, we need to subtract the key (modulo 26) instead, so we can go from VigEncrypt to VigDecrypt just by changing one character in the code. Note that the result of the subtraction might be negative, but Residue (unlike the remainder or modulo operations in some other programming languages you may have used) will still give us the correct result in the range 0 to 25. For example, 26|¯3 is 23.

VigDecrypt←{
    ⎕IO←0                       ⍝ use 0-based numbering
    key←(⍴⍵)⍴⎕A⍳⍺               ⍝ convert key to numbers and expand to length of message
    ⎕A[26|(⎕A⍳⍵)-key]           ⍝ subtract key from message and convert back to characters
}

Here are the functions in action:

      key←'KEIVERSON'
      key VigEncrypt'APLISFUNTOUSE'
KTTDWWMBGYYAZ
      key VigDecrypt key VigEncrypt'APLISFUNTOUSE'
APLISFUNTOUSE

To be continued…

Three-and-a-bit

The most obvious expression for computing π in APL is ○1. But what if you can’t remember how works, or your O key is broken, or you feel like taking the road less travelled? With thanks to Wikipedia’s excellent list of Approximations of π, here are some short sweet APL expressions for three-and-a-bit:

      3                                 ⍝ very short
3
      4                                 ⍝ not so sweet
4
      s←*∘0.5                           ⍝ let's allow ourselves some square roots
      +/s 2 3
3.14626436994197234232913506571557
      31*÷3
3.141380652391393004493075896462748
      +/1.8*1 0.5                       ⍝ Ramanujan
3.141640786499873817845504201238766
      s 7+s 6+s 5
3.141632544503617840472137945142766
      ÷/7 4*7 9
3.141567230224609375
      9⍟995
3.141573605337628094187009177086444
      355÷113
3.141592920353982300884955752212389
      s s 2143÷22                       ⍝ Ramanujan again
3.141592652582646125206037179644022
      +∘÷/3 7 15 1 292                  ⍝ continued fraction
3.14159265301190260407226149477373
      ÷/63 25×17 7+15×s 5
3.14159265380568820189839000630151
      (1E100÷11222.11122)*÷193
3.141592653643822210363178893440074
      (⍟744+640320*3)÷s 163             ⍝ Ramanujan yet again
3.141592653589793238462643383279727

This last one is accurate to more places than I ever learned in my youth!

Technical note: to get plenty of precision, these examples were evaluated with 128-bit decimal floating-point, by setting ⎕FR←1287 and ⎕PP←34.

For more on continued fractions, see cfract in the dfns workspace.