Spring 2015 Dyalog Travelogue (An American Tale: Dyalog Goes West)

Concluding Morten and Gitte’s whistlestop tour round Europe before heading to the US (see parts 1 and 2)

Saturday afternoon feels like Déjà Vu all over again...

Saturday afternoon – Déjà Vu all over again…

On Saturday afternoon we passed through London’s Heathrow airport for the third time in 5 days, this time continuing west to JFK, bringing the total for the week to 8,943km plus 300-odd in 3 different cars, 220 by rail, 25 by bus and 5 on the ferry :-) .

Sunday was spent with some of Dyalog’s North American contingent, co-ordinating and putting the final polish on the coming week’s presentations.

On Monday morning we were ready to start the first Dyalog North America user meeting – DYNA’15. The Princeton Crowne Plaza was our venue – making this our third time there after Dyalog ’07 and Dyalog ’09.

Back at the site of Dyalog ’07 and Dyalog ’09 – the Crowne Plaza in Princeton, New Jersey

Back at the site of Dyalog ’07 and Dyalog ’09 – the Crowne Plaza in Princeton, New Jersey

 

We had 37 visitors on Monday and 25 on Tuesday – a total of 45 different delegates representing about 15 different clients turned up to listen to updated road maps, demonstrations of new tools and four half-day workshops on Recent Language Enhancements, Parallel Programming using Futures and Isolates, Web Application Development and Modern APL Application Architectures. While there were no user presentations this year (the potential presenters seem to be keeping their powder dry for Dyalog ’15 in Sicily in September), we nonetheless had a full schedule.

Woodley Butler of Automatonics, Inc had been due to make a presentation, but had a scheduling problem and was unable to come. Gitte presented his exciting new hosting solution for Dyalog APL: APLCloud.com, during the opening session on Monday.

Monday’s dinner may have been the highlight of the event. We traveled (longer than expected due to the shuttle driver getting lost) to Mimino’s Restaurant for an authentic Georgian meal. The word meal does not do the experience justice – it was a culinary extravaganza – with plate after plate of incredible Georgian food. Imagine everyone’s surprise when we were told that it was now time for the entrees! Good friends, good food and good drink made it a truly special night.

After a meeting in Princeton on Wednesday morning we hit the road, again, this time to the Poconos to spend a few days relaxing and working with the North American Dyaloggers on a variety of projects before wrapping this tour up with visits to clients next Monday and Tuesday.

Spring 2015 Dyalog Travelogue (The Saga Continues)

Continuing Morten and Gitte’s whistlestop tour round Europe before heading to the US for DYNA15

From left to right this time…

From left to right this time…

FH Bingen – must have good student parties?

FH Bingen – must have good student parties?

Day 3: Bramley-Bingen

Job interviews done by lunch-time, and we hopped in the car (without lunch) to Heathrow, flew to Frankfurt and finally arrived at Bingen at sunset, just in time for some Weissbier and Flammkücken with the other early arrivals. Bingen is located west of Frankfurt, where the Rhine leaves the plains and bends north through hills, heading for Köln, Düsseldorf and the North Sea. Separated from the river by a vineyard-covered hill lies Fachhochschule Bingen, where our, host Dieter Kilsch, uses APL with MatLab and other tools to teach students about quality control and other subjects.

Days 4 & 5: APL Germany Spring Meeting in Bingen

We spent the next two days in the company of about 25 German APL enthusiasts. This time we were first up with a 2.5 hour workshop on Futures and Isolates, and we were very pleased to see that all the delegates who had gone to the trouble of installing Dyalog APL were able to perform all the exercises. We’ll have to make them a little harder next time (Tuesday in Princeton) :-) . The afternoon was focused on IBM: News from the Z-series hardware front, and the IBM GSE requirements process, where APL2 users get together and vote on priorities for requests for enhancements. Wouldn’t it be great if our Dyalog users would gang up on us like that and help us to set priorities as a group?

The watch tower at the top of the hill south of Bingen

The watch tower at the top of the hill south of Bingen

The first session on Friday was an APL Germany “business session” which we were allowed to skip. Morten discovered that the Tourist Information office next to our hotel rented bikes. They were a little shocked that he was willing to spend €13 for on hour on a bike, but he felt that he really needed to burn some carbon off the spark plugs. Seems he can’t see a hill without feeling it is necessary to make an attempt to get to the top of it.

With Morten energised after an hour on the bike, it was time to return to the meeting. A couple of presentations were particularly interesting: before lunch, Jürgen Sauermann spoke about GNU APL, which is now 2 years old and up to version 1.5. It is very encouraging to see open source APL systems thriving and promoting the use of APL.

GNU APL

GNU APL

One of the presentations after lunch can only be described as mind-blowing! Jörg Hudelmaier presented a development environment for JavaScript applications, written in Dyalog APL. Jörg was able to prototype JavaScript applications in Dyalog APL, using the WinForms WebBrowser control to render the User Interface, processing callbacks in APL – using a set of APL functions that emulated enough JavaScript DOM support to make his application work. Once he had finished development, he wrote a translator that generated a stand-alone JavaScript application which could run in a browser.

We rounded the two days off with a presentation on our strategy and selected demos of features from versions 14.0 and 14.1: Key, the new experimental JSON parser/generator and the Compiler, threw ourselves in the rental car and headed to Denmark for 15 hours at home before we set off for JFK and Princeton. The story continues next week, on the other side of the Atlantic!

To be concluded…

Spring 2015 Dyalog Travelogue (Ferries, Trains, Planes and Automobiles)

The journey begins: Kronborg Castle, Helsingør

The journey begins: Kronborg Castle, Helsingør

Göteborg: Läppstiften and Barken

Göteborg: Läppstiften and Barken

One of my favourite times of the year is the period in March/April where we traditionally start with a visit to the FinnAPL Forest Seminar followed by the APL Germany Spring Meeting. This year there are two new stops to make: the Swedish APL Group has started holding meetings twice a year too – and we are running the first Dyalog North America meeting in Princeton.

The FinnAPL meeting was a few weeks ago; this week we are wrapping up the rest in a whirlwind tour of no less than five one-way trips to get us to Princeton late on Saturday.

Day 1: Helsingør to Göteborg

We were off to a beautifully easy start on Monday evening, with the 20-minute ferry ride from Helsingør, where Gitte Christensen and I live, to Helsingborg in Sweden. From here it was 1 hour and 45 minutes by snabbtåg (train) to Göteborg, where we arrived just in time for a run at sundown, over the bridge across the Göta river, from which the second image was taken. Our hotel, the beautiful ship Barken, is on the right, and the conference venue, Läppstiften (the Lipstick), a very short walk away to the left.

Day 2: Göteborg to London

Gitte catching some, er, fresh air outside the Hotel Barken

Gitte catching some, er, fresh air outside the Hotel Barken

After a good night’s rest we were welcomed on the 21st floor of the Lipstick by Lars Wenztel of Aplensia, our host for the day. Lars opened the meeting with a talk about the efficiency of using arrays to do product configuration and production planning at Volvo Car Corporation, which is also located just across the river from the meeting site. He mentioned how his team had been working to improve performance, and I would like to take that opportunity to remind you all to send us benchmarks that are representative of your most performance-critical application components so that we (Dyalog) can help you to speed things up.

I was up next with an updated Road Map presentation and demos of the new JSON parser and external workspaces (spoiler alert: Germans and North Americans will see something very similar later this week :-) ). The afternoon was full of interesting presentations on the use of APL, with Gert Møller from Genokey in Denmark as the last presenter. He brought the day to a close with his presentation of ongoing work on the application of array-based logic to the problem of reducing the cost, increasing the effectiveness of – and reducing the side-effects that patients are likely to experience when using – new drugs. And guess what…he mentioned that performance was important, too.

Front row: Gitte Christensen, Conrad Helgesson, Joakim Hårsman, Jens Andersson, Tina Leijding, Lars Wentzel. Second: Gilgamesh Athoraya, Ewa Svensson, Radha Jayabalan, Jonas Stensiö. Third: Peter Simonsson, Keerthi Thadikamalla, Per Ericsson, Erik Häggblom and feet of Ole Johansen. Off screen: Paul Grosvenor and Morten Kromberg

Tuesday was a wonderful day in the company of some very lively Swedish APL Users. It is wonderful to see how they have put APL to use in important production planning applications at some of Sweden’s largest manufacturing operations, and the rapidly-growing bio-informatics sector was also well represented. We ended the day deciding to meet again on November 11th, with a target focus of web servers and services. Nearly everyone present had either experience of or plans to implement web-based solutions in APL; there will be code reviews and perhaps even have some hands-on coding sessions next time!

spring2015pt1_6The original plan was to take the train and ferry again and have a night in our own beds, but an opportunity to interview two potential candidates for our current job opening had appeared and, since it would be 2-3 weeks before we were back in the UK, we decide to grasp it. One of the benefits of having a large collection of air miles is that you can spend them on last-minute one-way trips that would otherwise cost a fortune. So instead of hopping on the train, we found ourselves on the airport bus and then a BA flight to Heathrow.

To be continued…

Exploring Key

In ⍺ f⌸ ⍵, major cells of specify keys for the corresponding major cells of , and f applies to each unique major cell of and the major cells of having that key. The monadic case f⌸⍵ is equivalent to ⍵ f⌸ ⍳≢⍵. Key is similar to the GROUP BY clause in SQL.

For example:

   ⎕io←0

   (⍳11) ,[¯0.5] 'Mississippi'
0 1 2 3 4 5 6 7 8 9 10
M i s s i s s i p p  i

   {⍺}⌸'Mississippi'                 {⍺⍵}⌸'Mississippi'
Misp                              ┌─┬────────┐
                                  │M│0       │
   {⊂⍵}⌸'Mississippi'             ├─┼────────┤
┌─┬────────┬───────┬───┐          │i│1 4 7 10│
│0│1 4 7 10│2 3 5 6│8 9│          ├─┼────────┤
└─┴────────┴───────┴───┘          │s│2 3 5 6 │
                                  ├─┼────────┤
   {≢⍵}⌸'Mississippi'             │p│8 9     │
1 4 4 2                           └─┴────────┘

We illustrate key by using it to model some APL primitives and to motivate and solve a programming puzzle.

Index-Of and Friends

Since key is defined in terms of unique and indices, we expect to be able to effect members of the index-of family. And so we can.

The specifications say that f applies to each unique major cell of . Therefore, {⍺}⌸ and equivalently ⊣⌸ computes unique. Since the specifications are for unique major cells, these are what ∪⍵ would be if it were extended to non-vector arguments, analagous to the way was extended to non-vector left arguments.

   x←↑'Aspen' 'John' 'Susan' 'Roger' 'Opal' 'John' 'Aspen'
   x
Aspen
John 
Susan
Roger
Opal 
John 
Aspen

   {⍺}⌸x                  ⊣⌸x
Aspen                  Aspen
John                   John 
Susan                  Susan
Roger                  Roger
Opal                   Opal 

A little surprisingly, key can also be used to model extended index-of and extended membership. For reasons which will become clear, we model (AKA ∊⍨) instead of . Both models use the merge operator, whimsically denoted here by .

ix  ← {(≢⍺) ↓ (0⍴⍨(≢⍺)+≢⍵) ((∊i)→)⍨ (≢¨i)/(≢⍺)⌊⊃¨i←{⊂⍵}⌸⍺⍪⍵}
has ← {(≢⍺) ↓ (0⍴⍨(≢⍺)+≢⍵) ((∊i)→)⍨ (≢¨i)/(≢⍺)>⊃¨i←{⊂⍵}⌸⍺⍪⍵}

   y←↑'China' 'Susan' 'John' 'John' 'Anne' 'Roger'
   y
China
Susan
John 
John 
Anne 
Roger

   x ix y
7 2 1 1 7 3

   x has y
0 1 1 1 0 1

To focus on essentials, ix and has do not directly handle the case where the right argument has higher rank than the left argument (the principal argument). Such higher rank arguments can be handled by pre-application of {↑,⊂⍤(¯1+⍴⍴⍺)⊢⍵} and post-application of ((1-⍴⍴⍺)↓⍴⍵)⍴.

Partition

Since key can effect non-contiguous partitions, we expect to be able to use it to effect contiguous partitions, a special case of the former. And so we can:

   part ← {(+\b/⍺){⊂⍵}⌸b⌿⍵⊣b←∨\⍺}

   x
Aspen
John 
Susan
Roger
Opal 
John 
Aspen
   0 1 0 1 0 0 1 part x
┌─────┬─────┬─────┐
│John │Roger│Aspen│
│Susan│Opal │     │
│     │John │     │
└─────┴─────┴─────┘
   0 1 0 1 0 0 1 (⊂[0] ≡ part) x
1
   (7⍴0) (⊂[0] ≡ part) x
1

Sort and Grade

sort  ← {⍺⌿⍨¯1+{≢⍵}⌸⍺⍪⍵}
grade ← {(≢⍺)-⍨∊1↓¨{⊂⍵}⌸⍺⍪⍵}

If is an array from a small “alphabet” , then ⍺ sort ⍵ sorts and ⍺ grade ⍵ grades it. For example:

   x←?1e6⍴256                        a←⎕a[?1e6⍴26]

   (⍋x)  ≡ (⍳256) grade x            (⍋a)  ≡ ⎕a grade a
1                                 1
   x[⍋x] ≡ (⍳256) sort  x            a[⍋a] ≡ ⎕a sort  a
1                                 1

The Maximum of a Vector

In Dyalog ’13 session D11, I included a slide giving relative timings on the then new key operator:

x←?1e6⍴1000

a. ¯1+{≢⍵}⌸(⍳1000),x     1.00
b. ¯1+{≢⍵}⌸(⍳1+⌈/x),x    1.62
c. ...

The timings show that key with tally takes less than a factor of 2 over finding the maximum. This is fast; unbelievably fast even. The following puzzle arose from investigations into this timing: Find the maximum of a vector of unsigned 1-byte integers without using multicore, vector instructions, loop unrolling, etc. Can you do it faster in C than the following?

max=*x++; 
for(i=1;i<n;++i){if(max<*x)max=*x; ++x;}

I posed the puzzle to some expert C programmers, and they failed to solve it. An “obvious” solution obtains by considering an obvious implementation of {≢⍵}⌸x in C:

M=256;
memset(c,0,M*4);              // initialize table of counts
for(i=0;i<n;++i)c[*x++]++;    // analoguous to c[x]+←1 in APL

Therefore, one way to find the maximum of x is to have an M-element (byte) Boolean table b, and:

memset(b,0,M);
for(i=0;i<n;++i)b[*x++]=1;    // analoguous to b[x]←1 in APL
c=b+M;                        // scan from the back
for(i=0;i<M;++i)if(*--c){max=c-b; break;}

Timing show that the table method is faster than the comparison method by a factor of 1.5 for 1-byte integers and 1.3 for 2-byte integers. The table method requires more code, but the main n-loop, the time for which dominates the overall time, is simpler for the table method.

Jay Foad countered that finding the maximum (and the minimum) is much faster still with the vector instructions available in modern CPUs. Dyalog has now (version 14.1) implemented such finding, with performance benefits for key, the index-of family, grade, and sort.

Solving the 2014 APL Problem Solving Competition – How Tweet It Is

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition.

The problems presented in Phase 1 of the competition were selected because they could be solved succinctly, generally in a single line of APL code. This makes them well suited for experimentation on TryAPL.org.

Problem 2 of Phase 1, entitled “How tweet it is” reads

“Twitter messages have a 140 character limit – what if the limit was even shorter? One way to shorten the message yet retain most readability is to remove interior vowels from its words. Write a dfn which takes a character vector and removes the interior vowels from each word.”

Test cases:
      {your_solution} 'if you can read this, it worked!'
if yu cn rd ths, it wrkd!
      {your_solution} 'APL is REALLY cool'
APL is RLLY cl
      {your_solution} '' ⍝ an empty vector argument should return an empty vector

      {your_solution} 'a' ⍝ your solution should work with a single character message
a

We’ll examine a couple of approaches to this problem – one that’s more “traditional APL” code, and another that makes use of a really helpful Dyalog feature.

This problem could be restated as “find and remove the vowels that aren’t at the beginning or end of a word”. To start with, we need to determine where the words are and where the vowels are. A word is a contiguous set of letters; multiple words are separated by spaces or punctuation. For simplicity’s sake, we’ll ignore contractions and possessives.

The “Traditional APL” Approach

This approach employs a technique that is not commonly found outside of APL and its brethren – using a Boolean vector to determine which elements to remove or keep. First, let’s find where all the vowels are:

      string←'If you can read this, it worked!'
      vowels←{⍵∊'aeiouAEIOU'}
      vowels string
1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0

To help illustrate what’s happening, I’ll write a little operator called “show” to compactly display the string, the Boolean vector, and the elements that would be selected by applying the Boolean to the string.

      show←{⍵⍪⍵{↑(1 0⍕ ⍵)(⍵\⍵/⍺)}⍺⍺ ⍵}
      vowels show string
If you can read this, it worked!
10001100100011000010001000100100
I   ou  a   ea    i   i   o  e

Next we want to remove vowels that aren’t at either end of a word. First, find where the words are by finding where the letters are.  There are several ways to do this; the most obvious may be to use a character vector constant:

      letters←{⍵∊'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'}

Long character constants seem a bit awkward to me.  So, another technique uses the Unicode Conversion system function to return the 26 characters starting at the code points for each of ‘a’ and ‘A’:

      letters←{⍵∊⎕UCS (⍳26)∘.+¯1+⎕UCS'aA'}

Yet another way might be to use the code point values directly and do numerical operations:

      letters←{{((⍵≥65)∧⍵≤90)∨(⍵≥97)∧⍵≤122}⎕UCS ⍵}

Which technique you choose is largely a matter of taste and style. All three return the same result and have comparable performance. My personal preference is the second one – it has fewer characters for me to mistype :)

      letters show string
If you can read this, it worked!
11011101110111101111001101111110
If you can read this  it worked 

So now let’s mark the interior letters of the words. This employs a technique known as shift and compare that I learned in the early 1980s when I was privileged to work with Bob Smith. Among Bob’s many contributions to the APL world was a book on Boolean Functions and Techniques. To mark the interior letters, we’ll do both a right and left shift:

      interior←{⍵∧(¯1↓0,⍵)∧1↓⍵,0}
      {interior letters ⍵} show string
If you can read this, it worked!
00001000100011000110000000111100
    o   a   ea   hi       orke  

The last step is to find interior vowels and negate:

      {(vowels ⍵)∧interior letters ⍵} show string
If you can read this, it worked!
00001000100011000010000000100100
    o   a   ea    i       o  e  

      {(vowels ⍵)⍲interior letters ⍵} show string
If you can read this, it worked!
11110111011100111101111111011011
If y u c n r  d th s, it w rk d!

Putting it all together…

      tweet←{⍵/⍨~(⍵∊'aeiouAEIOU')∧{(1↓⍵,0)∧¯1↓0,⍵}⍵∊⎕UCS(⍳26)∘.+¯1+⎕UCS'aA'}
      tweet string
If yu cn rd ths, it wrkd!

The Other Technique – Using Regular Expressions

In version 13.0, Dyalog introduced the system functions ⎕S and ⎕R as interfaces to the PCRE (Perl Compatible Regular Expression) library. Like APL, regular expressions may seem a bit alien at first, but in the years since their incorporation into Dyalog, I’ve grown to appreciate their power and flexibility – they can frequently accomplish complex string manipulations more succinctly than their APL equivalents thus furthering Dyalog’s power as a tool of thought, notation and execution.

      tweet←{('\B[AEIOU]\B' ⎕R '' ⍠ 1) ⍵}
      tweet string
If yu cn rd ths, it wrkd!

The expression above replaces any vowel (⍠ 1means case-insensitive) that is not at the beginning or end of a word with the empty vector, effectively removing the interior vowels. A blog post is not enough space to give an adequate overview of regular expressions. But I hope the expression above piques your interest and encourages you to experiment with ⎕S and ⎕R on TryAPL.org or with a Dyalog system of your own.

Unforgettable Numbers

Professor Kip Murray asked on the J Forum for the “unforgettable” times seen on a 24-hour digital clock.

The problem is that every number has something notable about it, so that each number is “unforgettable” and consequently it’s hard to remember any single one of them.

0000 all zeros
0001 first counting number
0002 first prime number
0003 first odd prime number
0004 first composite number
...

      ⎕rl←7*5 ⋄ 24 60⊤¯1+?×/24 60
6 59

0659 the time I wake up if the alarm was set at 0700 ☺

You may have heard of the following story about Hardy and Ramanujan. One day Hardy took a taxi to visit Ramanujan. On arriving, Hardy told Ramanujan that the taxi had the thoroughly unremarkable 4-digit number n on its licence plate. Ramanujan immediately remarked that n is the first number that … . I forget what n or the property was, something like n is the first number that can be written as the sum of two perfect cubes in two different ways, something typically Ramanujanian.

Yes, that was it:

      c←3*⍨⍳200           ⍝ cubes of numbers 1..200
      t←(∘.≤⍨⍳≢c) × ∘.+⍨c  
           ⍝ upper triangle of the addition table of these cubes

      e←(,t){⍺⍵}⌸,⍳⍴t     ⍝ unique sums and their indices
      e←(2=≢¨e[;2])⌿e     ⍝ sums that derive two different ways
      e
┌───────┬─────────────────┐
│1729   │┌────┬────┐      │
│       ││1 12│9 10│      │
│       │└────┴────┘      │
├───────┼─────────────────┤
│1092728│┌─────┬─────┐    │
│       ││1 103│64 94│    │
│       │└─────┴─────┘    │
├───────┼─────────────────┤
     ...
├───────┼─────────────────┤
│5472152│┌───────┬───────┐│
│       ││102 164│128 150││
│       │└───────┴───────┘│
└───────┴─────────────────┘

      e⌷⍨(⊢⍳⌊/)e[;1]      ⍝ the row with the smallest sum
┌────┬───────────┐
│1729│┌────┬────┐│
│    ││1 12│9 10││
│    │└────┴────┘│
└────┴───────────┘
      +/ 1 12 * 3         ⍝ check the sums
1729
      +/ 9 10 * 3
1729

Now that I have worked out the number I can find the story on the net. On hearing the story, J.E. Littlewood remarked that “every positive integer is one of Ramanujan’s personal friends”.

P.S. In my youth, when I needed to remember a (5-digit) number for a time, I computed its largest prime factor by mental calculation. Try it and you’ll see why it works.

Translated and updated from a J Wiki essay which first appeared on 2009-08-22.