Dyalog ’17: Day 2 (Monday 11 September)

by Vibeke Ulmann

Focus on Dyalog APL the language – Monday 11th September 2017

Where Sunday is traditionally filled with workshops and hands-on experiences – the first proper day of the annual user meeting is Monday – and this year was no different.

CEO, Gitte Christensen opened the meeting and emphasised a few of the major new things that have been achieved since last year, namely:

  • RIDE Version 4
  • Embedded HMTL Rendering Engine and – as always –
  • Performance enhancements.

She highlighted the fact that Version 16.0 was the beginning of a tool chain for developing distributed applications – including Cloud computing.

The licence for the SyncFusion library has been renewed for another 5 years. So, for those working with SyncFusion, you will have the usual widgets for dashboarding and graphing to hand.

A new multi-platform developer licence is now available allowing for development on all platforms; Windows, Linux, Mac, and soon, Android.

The Tools Group has been expanded, and they are producing more and more examples and templates.

Dyalog is now producing live content (outside of the user meeting) in the form of webcasts – currently one a month – and Podcasts are also planned.

CXO Morten Kromberg gave us a look at the next generation APL.

Authors note: if you are wondering what the X in CXO stands for it is ‘Experience’.

Morten established that there is a general ‘climate change’ in the world of computing especially as cloud computing is now ‘THERE’. This means that performance once again becomes key, as the true cost of cloud computing is measured in Watts – meaning CPU and memory consumption. So, if you can reduce the footprint of your application, you can reduce the costs of cloud hosting. Another point made is that Cloud computing generally means Linux – as it uses less memory and, therefore, fewer Watts. Whereas macOS and Androids can be considered UNIXes.

Morten focused on the demand for a new generation of APL developers and more to the point, managers who are comfortable using APL, and APL programmers. There are a number of criteria that both groups need; the developer need a modern set of libraries to build upon and to be able to find them easily for example using Git. Whereas managers need test driven development, source code management, and continuous development cycles.

Not everyone is a familiar with Git, and some are even a tad intimidated by it. But there is much good to be said for Git. You can have a private area, as well as a public shared area. Dyalog currently has 25 public repositories on Git. More will follow over time.

CTO Jay Foad proceeded to outline how we can make some of the Dyalog dreams for the future come true.

Version 16.0 of Dyalog APL was released in June this year, and work on version 17.0 continues apace. Speculatively Jay highlighted some of the key areas in version 17.0 to be: scripting, language, performance, and bridges to Python, Julia, MATLAB and Haskell. More work on RIDE, GPUs (and Xion Phi), portability and Android, the Cloud, shuffle testing and PQA.

The Key Note speech before Lunch was presented by Aaron Hsu from Indiana University (USA). Aaron went through how you can escape the beginner’s plateau when starting to work with APL.

The key takeaways for yours truly was that Aaron has observed two attitudes to APL

1)     Never in my life

2)     Can’t imagine life without it

He also observed that there seems to be a ‘learning wall’ which we need to find a way to overcome.

A directory of best practices can give insight into why computer scientists, or those trained in traditional programming methods, often find APL jarring and difficult, whereas those with no prior training fall in love with APL and take to it like ducks to water.

Watch his presentation in which he walks through 8 patterns, he considers to be key for newbie APL programmers. We will announce when the presentation is available on Dyalog’s YouTube Channel later in the autumn.

After lunch, most of the afternoon was dedicated to looking deeper into some of the new feature/functionality and topics many APL programmers find of particular interest.

In the interest of enticing you to watch the presentations online when they’re posted on Dyalog’s YouTube Channel, this blog only touches the basics on a couple of the presentations.

John Scholes went through re-coding from procedural to denotative style and showed us how pure functions opens for code reduction when implemented. ‘Massaging’ the code was the new expression I came away with.

Roger Hui showed us how he has now managed to solve a 20-year-old problem: ‘Index-of’ on Multiple Floats. After having initially established – to much hilarity – that the best way of solving the problem at hand was to not introduce it in the first place in your code, Roger proceeded to show how it can now be solved. Intentionally I am not giving away what Rogers 20-year-old ‘Problem’ was. Let me just briefly mention: it has to do with X and Y.

The afternoon was rounded off with a user presentation by Kostas Blekos from the University of Patras (Greece), where a group of physicists have used APL for the research they did for a paper.

His initial premise was that Physicists + Programming = Disaster. On the other hand, physicists need to do a lot of programming, so when they were developing the basis for the paper, they wanted to find a (new) language that made it easier to do better (and faster) prototyping.

Lots of Kostas’ and his colleagues’ previous work had been done in FORTRAN and, as he said, we needed something a bit easier to work with and the choice was Dyalog APL. Outside of the ability to do fast prototyping, the terseness of the language was attractive, as were the close mathematical relations, which made it easy to understand.

What they learned was that APL is GREAT, suitable for fast prototyping, and for avoiding making mistakes. The quote of the day surely must be

In FORTRAN I could spend a whole day trying to find a missing comma……..

Asked if there were any downsides to APL, Kostas said no, not really, except it is difficult to convince people to use it.

Dyalog ’17: Day 1 (Sunday 10 September)

by Vibeke Ulmann

SharpPlot and SharpLeaf – the graphics and publication tools included with Dyalog on all platforms

(Workshop SA4)

A lot of work has gone into SharpPlot and SharpLeaf over the past couple of years*. The workshop on Sunday 10th September was run by Nicolas Delcros, the Dyalog software programmer behind the work.

SharpPlot:

The documentation has been significantly improved, comes across as comprehensive, and is available on right-click anywhere when you use the tool. It is also available on www.SharpPlot.com and can be downloaded as a PDF. Nic strongly recommends that you walk through the documentation and tutorials and familiarise yourself with the capabilities and the different graph types that are available for automatic graphical representation of data before you start using SharpPlot. That way you will save yourself a lot of time when you start working with the tool, and you will also quickly discover which types of graphs are ‘best’ to show your particular data.

It’s possible to click on the graph widget within a Dyalog Session to immediately see how the data displays graphically. If it doesn’t work to your satisfaction, or clearly show the data the way you want in one type of graph, you can right-click on the data and choose the graph wizard.

Output can be Raster or Vector format, and you can publish to the Web or UI (User Interface).

Chart types are 2D and 3D. There are also a number of miscellaneous charts such as Gantt, Triangle, Table and Venn diagrams.

There are obviously a lot of options you can tweak for each graph and the graph wizard presents them to you and lets you see the effects immediately. Once you are happy with the graph you can turn the specs into a script which can be incorporated in your program.

All in all, SharpPlot now comes across as highly intuitive and easy to use.

We recommend you review the blogpost on www.dyalog.com from April 2017 where Nic explains some of the concepts further: https://www.dyalog.com/blog/2017/04/displaying-cross-references-with-sharpplot-2/

SharpLeaf:

SharpLeaf is an automated publication tool, which comes in extremely handy if, for example, you have to create the same report on a regular basis, but have to use/show different data from the previous report. A good example could be Board reports with varying data from Finance and/or Product Sales.

A lot of people will be pleased to find that their standard multi page report – which hitherto they have had to develop for example in Word and Excel each month – can now be generated automatically, with changes made to the embedded graphs and tables, based on data accrued since the previous month.

If you want this level of automation, you will have need to swap to SharpLeaf, develop your standard report, and then carry on from there. Importing an old report developed in, for example, Word or Excel is, unfortunately, not an option (but cutting and pasting text is).

* Author’s note: The original software programming work on SharpPlot and SharpLeaf was done by Causeway. Causeway was acquired by Dyalog Ltd in May 2007.

Stencil Lives

⎕io←0 throughout. ⎕io delenda est.

Stencil

A stencil operator is available with Dyalog version 16.0. In brief, stencil is a dyadic operator f⌺s which applies f to (possibly overlapping) rectangles. The size of the rectangle and its movement are controlled by s. For example, enclosing 3-by-3 rectangles with default movements of 1:

   ⊢ a←4 5⍴⎕a
ABCDE
FGHIJ
KLMNO
PQRST
   {⊂⍵}⌺3 3 ⊢a
┌───┬───┬───┬───┬───┐
│   │   │   │   │   │
│ AB│ABC│BCD│CDE│DE │
│ FG│FGH│GHI│HIJ│IJ │
├───┼───┼───┼───┼───┤
│ AB│ABC│BCD│CDE│DE │
│ FG│FGH│GHI│HIJ│IJ │
│ KL│KLM│LMN│MNO│NO │
├───┼───┼───┼───┼───┤
│ FG│FGH│GHI│HIJ│IJ │
│ KL│KLM│LMN│MNO│NO │
│ PQ│PQR│QRS│RST│ST │
├───┼───┼───┼───┼───┤
│ KL│KLM│LMN│MNO│NO │
│ PQ│PQR│QRS│RST│ST │
│   │   │   │   │   │
└───┴───┴───┴───┴───┘

Stencil is also known as stencil code, tile, tessellation, and cut. It has applications in artificial neural networks, computational fluid dynamics, cellular automata, etc., and of course in Conway’s Game of Life.

The Rules of Life

Each cell of a boolean matrix has 8 neighbors adjacent to it horizontally, vertically, or diagonally. The Game of Life concerns the computation of the next generation boolean matrix.

(0) A 0-cell with 3 neighboring 1-cells becomes a 1.

(1) A 1-cell with 2 or 3 neighboring 1-cells remains at 1.

(2) All other cells remain or become a 0.

There are two main variations on the treatment of cells on the edges of the matrix: (a) the matrix is surrounded by a border of 0s; or (b) cells on an edge are adjacent to cells on the opposite edge, as on a torus.

There is an implementation of life in the dfns workspace and explained in a YouTube video. It assumes a toroidal topology.

   life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}    ⍝ John Scholes

   ⊢ glider←5 5⍴0 0 1 0 0 1 0 1 0 0 0 1 1,12⍴0
0 0 1 0 0
1 0 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0
   life glider
0 1 0 0 0
0 0 1 1 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0

   {'.⍟'[⍵]}¨ (⍳8) {life⍣⍺⊢⍵}¨ ⊂glider
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│..⍟..│.⍟...│..⍟..│.....│.....│.....│.....│.....│
│⍟.⍟..│..⍟⍟.│...⍟.│.⍟.⍟.│...⍟.│..⍟..│...⍟.│.....│
│.⍟⍟..│.⍟⍟..│.⍟⍟⍟.│..⍟⍟.│.⍟.⍟.│...⍟⍟│....⍟│..⍟.⍟│
│.....│.....│.....│..⍟..│..⍟⍟.│..⍟⍟.│..⍟⍟⍟│...⍟⍟│
│.....│.....│.....│.....│.....│.....│.....│...⍟.│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

Stencil Lives

It has long been known that stencil facilitates Game of Life computations. Eugene McDonnell explored the question in the APL88 paper Life: Nasty, Brutish, and Short [Ho51]. The shortest of the solutions derive as follows.

By hook or by crook, find all the 3-by-3 boolean matrices U which lead to a middle 1. A succinct Game of Life then obtains.

   B ← {1 1⌷life 3 3⍴(9⍴2)⊤⍵}¨ ⍳2*9
   U ← {3 3⍴(9⍴2)⊤⍵}¨ ⍸B  ⍝ ⍸ ←→ {⍵/⍳⍴⍵}

   life1 ← {U ∊⍨ {⊂⍵}⌺3 3⊢⍵}    ⍝ Eugene McDonnell

Comparing life and life1, and also illustrating that the toroidal and 0-border computations can be expressed one with the other.

   b←1=?97 103⍴3

   x←1 1↓¯1 ¯1↓ life 0,0,⍨0⍪0⍪⍨b
   y←life1 b
   x≡y
1

   g←{(¯1↑⍵)⍪⍵⍪1↑⍵}
   p←life b
   q←1 1↓¯1 ¯1↓ life1 (g b[;102]),(g b),(g b[;0])
   p≡q
1

Adám Brudzewsky points out that life can be terser as a train (fork):

   life1a ← U ∊⍨ ⊢∘⊂⌺3 3    ⍝ Adám Brudzewsky
   life1b ← U ∊⍨ {⊂⍵}⌺3 3

   (life1 ≡ life1a) b
1
   (life1 ≡ life1b) b
1

life1 is an example of implementing a calculation by look-up rather than by a more conventional computation, discussed in a recent blog post. There is a variation which is more efficient because the look-up is effected with integers rather than boolean matrices:

   A←3 3⍴2*⌽⍳9
   life2 ← {B[{+/,A×⍵}⌺3 3⊢⍵]}

   (life1 ≡ life1b) b
1

Jay Foad offers another stencil life, translating an algorithm in k by Arthur Whitney:

   life3 ← {3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}    ⍝ Jay Foad

   (life1 ≡ life3) b
1

The algorithm combines the life rules into a single expression, wherein s←{+/,⍵}⌺3 3 ⊢⍵

(0) for 0-cells s is the number of neighbors; and
(1) for 1-cells s is the number of neighbors plus 1, and the plus 1 only matters if s is 4.

The same idea can be retrofit into the toroidal life:

   lifea←{3=s-⍵∧4=s←⊃+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

   (life ≡ lifea) b
1

Collected Definitions and Timings

life   ← {↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
lifea  ← {3=s-⍵∧4=s←⊃+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

  B←{1 1⌷life 3 3⍴(9⍴2)⊤⍵}¨ ⍳2*9
  U←{3 3⍴(9⍴2)⊤⍵}¨ ⍸ B
  A←3 3⍴2*⌽⍳9

life1  ← {U ∊⍨ {⊂⍵}⌺3 3⊢⍵}
life1a ← U ∊⍨ ⊢∘⊂⌺3 3
life1b ← U ∊⍨ {⊂⍵}⌺3 3
life2  ← {B[{+/,A×⍵}⌺3 3⊢⍵]}
life3  ← {3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}

   cmpx (⊂'life') ,¨ '1' '1a' '1b' '2' '3' '' 'a' ,¨ ⊂' b'
  life1 b  → 2.98E¯3 |    0% ⎕⎕⎕⎕⎕
  life1a b → 1.97E¯2 | +561% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  life1b b → 2.99E¯3 |    0% ⎕⎕⎕⎕⎕
  life2 b  → 2.71E¯4 |  -91%
  life3 b  → 6.05E¯5 |  -98%
* life b   → 1.50E¯4 |  -95%
* lifea b  → 1.41E¯4 |  -96%

The * indicate that life and lifea give a different result (toroidal v 0-border).

life1a is much slower than the others because ⊢∘⊂⌺ is not implemented by special code.

{+/,⍵}⌺ is the fastest of the special codes because the computation has mathematical properties absent from {⊂⍵}⌺ and {+/,A×⍵}⌺.

The effect of special code v not, can be observed (for example) by use of redundant parentheses:

   cmpx '{+/,⍵}⌺3 3⊢b' '{+/,(⍵)}⌺3 3⊢b'
  {+/,⍵}⌺3 3⊢b   → 3.13E¯5  |      0%
  {+/,(⍵)}⌺3 3⊢b → 2.63E¯2  | +83900% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '{+/,A×⍵}⌺3 3⊢b' '{+/,A×(⍵)}⌺3 3⊢b'
  {+/,A×⍵}⌺3 3⊢b   → 2.42E¯4 |      0%
  {+/,A×(⍵)}⌺3 3⊢b → 2.98E¯2 | +12216% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   ⍝ no special code in either of the following expressions
   cmpx '{+/,2×⍵}⌺3 3⊢b' '{+/,2×(⍵)}⌺3 3⊢b'
  {+/,2×⍵}⌺3 3⊢b   → 2.92E¯2 |      0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
  {+/,2×(⍵)}⌺3 3⊢b → 3.03E¯2 |     +3% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

That life and lifea do not use stencil and yet are competitive, illustrates the efficacy of boolean operations and of letting primitives “see” large arguments.

Finally, if you wish to play with stencil a description and a hi-fi model of it can be found here.

Krypto

In the 2016 Year Game, the task was to generate the numbers 0 to 100 using APL primitives and the digits 2 0 1 6 in that order. For example,

   20=16
   ×2016
   2⌊016
   2+×016
   …

This “puzzle of the year” brings to mind Krypto, a game I played many years ago while in grade school.

Krypto

Krypto is a mathematical card game. The Krypto deck has 56 cards: 3 each of numbers 1-6, 4 each of the numbers 7-10, 2 each of 11-17, 1 each of 18-25.

   ⎕io←0
   DECK ← (3/1+⍳6),(4/7+⍳4),(2/11+⍳7),18+⍳8

Six cards are dealt: an objective card and five other cards. A player must use all five of the latter cards’ numbers exactly once, using any combination of arithmetic operations (+, -, ×, and ÷) to form the objective card’s number. The first player to come up with a correct formula is the winner. The stricter “International Rules” specify the use of non-negative integers only; fractional or negative intermediate results are not permitted.

For example, if the objective card were 17 and the other cards were 2, 8, 14, 19, and 21, then a Krypto solution can be as follows. Without loss of generality, we use APL notation and syntax.

   8 - 19 + 14 - 2 × 21

In this article we present functions to find all solutions to a Krypto hand.

A Solution

There are a maximum of !5 permutations of the 5 cards and 4 possibilities in each of the 4 places where an operation can be put, for (!5)×4*4 or 30720 total possibilities. This number is small enough for an exhaustive approach.

deal←{DECK ⌷⍨⊂ 6?≢DECK}

Krypto←{
  perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}
  a←256⌿5 0⍕⍵[perm 5]
  a[;6+5×⍳4]←'+-×÷'[((256×!5),4)⍴⍉(4⍴4)⊤⍳256]
  ⊣⌸ a ⌿⍨ ⍺ = ⍎⍤1 ⊢a
}

   deal ⍬
17 8 19 14 2 21

   ⊢ t← 17 Krypto 8 19 14 2 21
    8 - 19 + 14 -  2 × 21
    8 - 19 + 14 - 21 ×  2
    8 - 19 - 21 + 14 ÷  2
    8 - 14 + 19 -  2 × 21
        ...
   21 +  8 - 19 - 14 ÷  2
   21 - 19 -  8 + 14 ÷  2

   ⍴ t
24 25

Intermediate Steps

The function perm is from the Dyalog blog post Permutations, 2015-07-20. perm n generates the sorted table of all permutations of ⍳n.

The local variable a in Krypto is a 30720-row character matrix computed from the 5 non-objective numbers. It consists of all !5 permutations of the 5 numbers interspersed with all 4*4 arrangements of the four operations + - × ÷.

Executing the rows of a produces a 30720-element numeric vector. Comparison of this vector with the objective yields a boolean vector that selects the rows of a which are correct formulas.

   ⍴ a
30720 25

   8↑a
    8 + 19 + 14 +  2 + 21
    8 + 19 + 14 +  2 - 21
    8 + 19 + 14 +  2 × 21
    8 + 19 + 14 +  2 ÷ 21
    8 + 19 + 14 -  2 + 21
    8 + 19 + 14 -  2 - 21
    8 + 19 + 14 -  2 × 21
    8 + 19 + 14 -  2 ÷ 21
   ¯5↑a
   21 ÷  2 ÷ 14 × 19 ÷  8
   21 ÷  2 ÷ 14 ÷ 19 +  8
   21 ÷  2 ÷ 14 ÷ 19 -  8
   21 ÷  2 ÷ 14 ÷ 19 ×  8
   21 ÷  2 ÷ 14 ÷ 19 ÷  8

   +/ b ← 17 = ⍎⍤1 ⊢a
24

   t ≡ b⌿a
1

We note that use of the @ operator, new to Dyalog version 16.0, obviates the need to name intermediate results for reasons for syntax. Instead, names are only used to break the code down into more comprehensible components.

Krypto1←{
  perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}
  ⊣⌸ ⍺ (⊢(⌿⍨)=∘(⍎⍤1)) '+-×÷'[((256×!5),4)⍴⍉(4⍴4)⊤⍳256]⊣@(6+5×⍳4)⍤1 ⊢256⌿5 0⍕⍵[perm 5]
}

Krypto2←{
  perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}
  fns  ← '+-×÷'[((256×!5),4)⍴⍉(4⍴4)⊤⍳256]
  nums ← 256⌿5 0⍕⍵[perm 5]
  ⊣⌸ ⍺ (⊢(⌿⍨)=∘(⍎⍤1)) fns ⊣@(6+5×⍳4)⍤1 ⊢nums
}

   17 (Krypto ≡ Krypto1) 8 19 14 2 21
1

   17 (Krypto ≡ Krypto2) 8 19 14 2 21
1

International Rules

The international rules (intermediate results must be non-negative integers) can be enforced readily:

irules←{⍵⌿⍨∧/(i=⌊i)∧0≤i←8 13 18{⍎¨⍺↓¨⊂⍵}⍤1⊢⍵}

   irules 17 Krypto 8 19 14 2 21
    8 +  2 + 14 ÷ 21 - 19
    8 + 21 - 19 - 14 ÷  2
   19 -  2 ×  8 - 21 - 14
   19 -  2 ÷  8 - 21 - 14
   19 -  2 × 14 - 21 -  8
   19 -  2 ÷ 14 - 21 -  8
    2 +  8 + 14 ÷ 21 - 19
   21 - 19 -  8 + 14 ÷  2

It is instructive to look at how the local variable i in irules is formed:

   ⊢ t←17 Krypto 8 19 14 2 21
    8 - 19 + 14 -  2 × 21
    8 - 19 + 14 - 21 ×  2
    8 - 19 - 21 + 14 ÷  2
    8 - 14 + 19 -  2 × 21
        ...
   21 +  8 - 19 - 14 ÷  2
   21 - 19 -  8 + 14 ÷  2

   8 13 18 {⍺↓¨⊂⍵}⍤1 ⊢t
┌─────────────────┬────────────┬───────┐
│19 + 14 -  2 × 21│14 -  2 × 21│ 2 × 21│
├─────────────────┼────────────┼───────┤
│19 + 14 - 21 ×  2│14 - 21 ×  2│21 ×  2│
├─────────────────┼────────────┼───────┤
│19 - 21 + 14 ÷  2│21 + 14 ÷  2│14 ÷  2│
├─────────────────┼────────────┼───────┤
│14 + 19 -  2 × 21│19 -  2 × 21│ 2 × 21│
├─────────────────┼────────────┼───────┤
            ...
├─────────────────┼────────────┼───────┤
│ 8 - 19 - 14 ÷  2│19 - 14 ÷  2│14 ÷  2│
├─────────────────┼────────────┼───────┤
│19 -  8 + 14 ÷  2│ 8 + 14 ÷  2│14 ÷  2│
└─────────────────┴────────────┴───────┘

      ⍎¨ 8 13 18 {⍺↓¨⊂⍵}⍤1 ⊢t
¯9 ¯28  42
¯9 ¯28  42
¯9  28   7
¯9 ¯23  42
   ...
¯4  12   7
 4  15   7

(An earlier version of the text appeared as the Jwiki essay Krypto, 2013-07-04.)

Stencil Maneuvers

Introduction

The e-mail arrived in the early afternoon from Morten, in Finland attending the FinnAPL Forest Seminar.

How do I speed this up and impress the Finns?

0 cmpx 'e←⊃∨/0.2 edges¨r g b'
6.4E¯1
edges
{⍺←0.7 ⋄ 1 1↓¯1 ¯1↓⍺<(|EdgeDetect apply ⍵)÷1⌈(+⌿÷≢),⍵}
apply
{stencil←⍺ ⋄ {+/,⍵×stencil}⌺(⍴stencil)⊢⍵}
EdgeDetect
¯1 ¯1 ¯1
¯1 8 ¯1
¯1 ¯1 ¯1

(r g b in the attached ws)

Background

is stencil, a new dyadic operator which will be available in version 16.0. In brief, f⌺s applies the operand function f to windows of size s. The window is moved over the argument centered over every possible position. The size is commonly odd and the movement commonly 1. For example:

   {⊂⍵}⌺5 3⊢6 5⍴⍳30
┌───────┬────────┬────────┬────────┬───────┐
│0  0  0│ 0  0  0│ 0  0  0│ 0  0  0│ 0  0 0│
│0  0  0│ 0  0  0│ 0  0  0│ 0  0  0│ 0  0 0│
│0  1  2│ 1  2  3│ 2  3  4│ 3  4  5│ 4  5 0│
│0  6  7│ 6  7  8│ 7  8  9│ 8  9 10│ 9 10 0│
│0 11 12│11 12 13│12 13 14│13 14 15│14 15 0│
├───────┼────────┼────────┼────────┼───────┤
│0  0  0│ 0  0  0│ 0  0  0│ 0  0  0│ 0  0 0│
│0  1  2│ 1  2  3│ 2  3  4│ 3  4  5│ 4  5 0│
│0  6  7│ 6  7  8│ 7  8  9│ 8  9 10│ 9 10 0│
│0 11 12│11 12 13│12 13 14│13 14 15│14 15 0│
│0 16 17│16 17 18│17 18 19│18 19 20│19 20 0│
├───────┼────────┼────────┼────────┼───────┤
│0  1  2│ 1  2  3│ 2  3  4│ 3  4  5│ 4  5 0│
│0  6  7│ 6  7  8│ 7  8  9│ 8  9 10│ 9 10 0│
│0 11 12│11 12 13│12 13 14│13 14 15│14 15 0│
│0 16 17│16 17 18│17 18 19│18 19 20│19 20 0│
│0 21 22│21 22 23│22 23 24│23 24 25│24 25 0│
├───────┼────────┼────────┼────────┼───────┤
│0  6  7│ 6  7  8│ 7  8  9│ 8  9 10│ 9 10 0│
│0 11 12│11 12 13│12 13 14│13 14 15│14 15 0│
│0 16 17│16 17 18│17 18 19│18 19 20│19 20 0│
│0 21 22│21 22 23│22 23 24│23 24 25│24 25 0│
│0 26 27│26 27 28│27 28 29│28 29 30│29 30 0│
├───────┼────────┼────────┼────────┼───────┤
│0 11 12│11 12 13│12 13 14│13 14 15│14 15 0│
│0 16 17│16 17 18│17 18 19│18 19 20│19 20 0│
│0 21 22│21 22 23│22 23 24│23 24 25│24 25 0│
│0 26 27│26 27 28│27 28 29│28 29 30│29 30 0│
│0  0  0│ 0  0  0│ 0  0  0│ 0  0  0│ 0  0 0│
├───────┼────────┼────────┼────────┼───────┤
│0 16 17│16 17 18│17 18 19│18 19 20│19 20 0│
│0 21 22│21 22 23│22 23 24│23 24 25│24 25 0│
│0 26 27│26 27 28│27 28 29│28 29 30│29 30 0│
│0  0  0│ 0  0  0│ 0  0  0│ 0  0  0│ 0  0 0│
│0  0  0│ 0  0  0│ 0  0  0│ 0  0  0│ 0  0 0│
└───────┴────────┴────────┴────────┴───────┘
   {+/,⍵}⌺5 3⊢6 5⍴⍳30
 39  63  72  81  57
 72 114 126 138  96
115 180 195 210 145
165 255 270 285 195
152 234 246 258 176
129 198 207 216 147

In addition, for matrix right arguments with movement 1, special code is provided for the following operand functions:

{∧/,⍵}   {∨/,⍵}   {=/,⍵}   {≠/,⍵} 

{⍵}      {,⍵}     {⊂⍵}     {+/,⍵}

{+/,A×⍵}     {E<+/,A×⍵}       
{+/⍪A×⍤2⊢⍵}  {E<+/⍪A×⍤2⊢⍵}

The comparison < can be one of < ≤ = ≠ ≥ >.

The variables r g b in the problem are integer matrices with shape 227 316 having values between 0 and 255. For present purposes we can initialize them to random values:

   r←¯1+?227 316⍴256
   g←¯1+?227 316⍴256
   b←¯1+?227 316⍴256

Opening Moves

I had other obligations and did not attend to the problem until 7 PM. A low-hanging fruit was immediately apparent: {+/,⍵×A}⌺s is not implemented by special code but {+/,A×⍵}⌺s is. The difference in performance is significant:

   edges1←{⍺←0.7 ⋄ 1 1↓¯1 ¯1↓⍺<(|EdgeDetect apply1 ⍵)÷1⌈(+⌿÷≢),⍵}
   apply1←{stencil←⍺ ⋄ {+/,stencil×⍵}⌺(⍴stencil)⊢⍵}

   cmpx 'e←⊃∨/0.2 edges1¨r g b' 'e←⊃∨/0.2 edges ¨r g b'
  e←⊃∨/0.2 edges1¨r g b → 8.0E¯3 |     0% ⎕
  e←⊃∨/0.2 edges ¨r g b → 6.1E¯1 | +7559% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

I fired off an e-mail reporting this good result, then turned to other more urgent matters. An example of the good being an enemy of the better, I suppose.

When I returned to the problem at 11 PM, the smug good feelings have largely dissipated:

  • Why should {+/,A×⍵}⌺s be so much faster than {+/,⍵×A}⌺s? That is, why is there special code for the former but not the latter? (Answer: all the special codes end with … ⍵}.)
  • I can not win: If the factor is small, then why isn’t it larger; if it is large, it’s only because the original code wasn’t very good.
  • The large factor is because, for this problem, C (special code) is still so much faster than APL (magic function).
  • If the absolute value can somehow be replaced, the operand function can then be in the form {E<+/,A×⍵}⌺s, already implemented by special code. Alternatively, {E<|+/,A×⍵}⌺s can be implemented by new special code.

Regarding the last point, the performance improvement potentially can be:

   edges2←{⍺←0.7 ⋄ 1 1↓¯1 ¯1↓(⍺ EdgeDetect)apply2 ⍵}
   apply2←{threshold stencil←⍺ ⋄ 
                    {threshold<+/,stencil×⍵}⌺(⍴stencil)⊢⍵}

   cmpx (⊂'e←⊃∨/0.2 edges'),¨'21 ',¨⊂'¨r g b'
  e←⊃∨/0.2 edges2¨r g b → 4.8E¯3 |      0%
* e←⊃∨/0.2 edges1¨r g b → 7.5E¯3 |    +57%
* e←⊃∨/0.2 edges ¨r g b → 7.4E¯1 | +15489% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

The * in the result of cmpx indicates that the expressions don’t give the same results. That is expected; edges2 is not meant to give the same results but is to get a sense of the performance difference. (Here, an additional factor of 1.57.)

edges1 has the expression ⍺<matrix÷1⌈(+⌿÷≢),⍵ where and the divisor are both scalars. Reordering the expression eliminates one matrix operation: (⍺×1⌈(+⌿÷≢),⍵)<matrix. Thus:

   edges1a←{⍺←0.7 ⋄ 1 1↓¯1 ¯1↓(⍺×1⌈(+⌿÷≢),⍵)<|EdgeDetect apply1 ⍵}

   cmpx (⊂'e←⊃∨/0.2 edges'),¨('1a' '1 ' '  '),¨⊂'¨r g b'
  e←⊃∨/0.2 edges1a¨r g b → 6.3E¯3 |      0%
  e←⊃∨/0.2 edges1 ¨r g b → 7.6E¯3 |    +22%
  e←⊃∨/0.2 edges  ¨r g b → 6.5E¯1 | +10232% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

The time was almost 1 AM. To bed.

Further Maneuvers

Fresh and promising ideas came with the morning. The following discussion applies to the operand function {+/,A×⍵}.

(0) Scalar multiple: If all the elements of A are equal, then {+/,A×⍵}⌺(⍴A)⊢r ←→ (⊃A)×{+/,⍵}⌺(⍴A)⊢r.

   A←3 3⍴?17
   ({+/,A×⍵}⌺(⍴A)⊢r) ≡ (⊃A)×{+/,⍵}⌺(⍴A)⊢r
1

(1) Sum v inner product: {+/,⍵}⌺(⍴A)⊢r is significantly faster than {+/,A×⍵}⌺(⍴A)⊢r because the former exploits mathematical properties absent from the latter.

   A←?3 3⍴17
   cmpx '{+/,⍵}⌺(⍴A)⊢r' '{+/,A×⍵}⌺(⍴A)⊢r'
  {+/,⍵}⌺(⍴A)⊢r   → 1.4E¯4 |    0% ⎕⎕⎕
* {+/,A×⍵}⌺(⍴A)⊢r → 1.3E¯3 | +828% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

(The * in the result of cmpx is expected.)

(2) Linearity: the stencil of the sum equals the sum of the stencils.

   A←?3 3⍴17
   B←?3 3⍴17
   ({+/,(A+B)×⍵}⌺(⍴A)⊢r) ≡ ({+/,A×⍵}⌺(⍴A)⊢r) + {+/,B×⍵}⌺(⍴A)⊢r 
1

(3) Middle: If B is zero everywhere except the middle, then {+/,B×⍵}⌺(⍴B)⊢r ←→ mid×r where mid is the middle value.

   B←(⍴A)⍴0 0 0 0 9
   B
0 0 0
0 9 0
0 0 0
   ({+/,B×⍵}⌺(⍴B)⊢r) ≡ 9×r
1

(4) A faster solution.

   A←EdgeDetect
   B←(⍴A)⍴0 0 0 0 9
   C←(⍴A)⍴¯1
   A B C
┌────────┬─────┬────────┐
│¯1 ¯1 ¯1│0 0 0│¯1 ¯1 ¯1│
│¯1  8 ¯1│0 9 0│¯1 ¯1 ¯1│
│¯1 ¯1 ¯1│0 0 0│¯1 ¯1 ¯1│
└────────┴─────┴────────┘
   A ≡ B+C
1

Whence:

   ({+/,A×⍵}⌺(⍴A)⊢r) ≡ ({+/,B×⍵}⌺(⍴A)⊢r) + {+/,C×⍵}⌺(⍴A)⊢r ⍝ (2)
1
   ({+/,A×⍵}⌺(⍴A)⊢r) ≡ ({+/,B×⍵}⌺(⍴A)⊢r) - {+/,⍵}⌺(⍴A)⊢r   ⍝ (0)
1
   ({+/,A×⍵}⌺(⍴A)⊢r) ≡ (9×r) - {+/,⍵}⌺(⍴A)⊢r                ⍝ (3)
1

Putting it all together:

edges3←{
  ⍺←0.7
  mid←⊃EdgeDetect↓⍨⌊2÷⍨⍴EdgeDetect
  1 1↓¯1 ¯1↓(⍺×1⌈(+⌿÷≢),⍵)<|(⍵×1+mid)-{+/,⍵}⌺(⍴EdgeDetect)⊢⍵
}

Comparing the various edges:

   x←(⊂'e←⊃∨/0.2 edges'),¨('3 ' '2 ' '1a' '1 ' '  '),¨⊂'¨r g b'
   cmpx x
  e←⊃∨/0.2 edges3 ¨r g b → 3.4E¯3 |      0%
* e←⊃∨/0.2 edges2 ¨r g b → 4.3E¯3 |    +25%
  e←⊃∨/0.2 edges1a¨r g b → 6.4E¯3 |    +88%
  e←⊃∨/0.2 edges1 ¨r g b → 7.5E¯3 |   +122%
  e←⊃∨/0.2 edges  ¨r g b → 6.5E¯1 | +19022% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
edges original
edges1 uses {+/,stencil×⍵} instead of {+/,⍵×stencil}
edges1a uses (⍺×mean,⍵)<matrix instead of ⍺<matrix÷mean,⍵
edges2 uses {threshold<+/,stencil×⍵}
edges3 uses the faster {+/,⍵} instead of {+/,stencil×⍵} and other maneuvers

Fin

I don’t know if the Finns would be impressed. The exercise has been amusing in any case.

Displaying cross-references with SharpPlot

Requirements: Update SharpPlot to v3.37 from my.dyalog.com > Downloads > Tools & Interfaces > GUI Tools > SharpPlot

SharpPlot v3.37 introduces Network Maps as a new chart type, and we’re going to use it to display the output of the ]XRef user command, which displays cross-references between all kinds of APL names :

      ]XRef ⎕SE.Parser
             DDEEEFLLMMNNPPPPPPPPPPPQQSSSTUaaaabbbcdddddddfffiilmmmmmmnnnnnnppppqqqqrrrsssssssssstttttuvvvxx∆⍵⍺ 
             EeRnrOOSAOAsRrsssssssss.uwwwrPrrrr:alu.aaaeee.ei.fq.aeioo.adeop.Daa.1mq.et:eipqtwwww:aqwxp.an.C... 
             LlRd:RW.XDRwEo:.eeeeeee.oDTiaPgggg:d.t.tttQff.ax.:..smndd..awv..art..:..qb:t.lzr.imp:b.vtp.lc.u... 
             I.OT:CE.APGiFp:Pttttttt.t.atpE.psv:....aaau.i.tC.:..k.lei..:....tm...:....:..i.:.tao:l...e....t... 
             M.Rr:ER.ROStIa:a........e.bc.R.o.a:....:..o.n.ua.:....elf..:....as...:....:..t.:..ts:e...r....:... 
             I.0a:S..GS.cXg:r.Samnpu.s.lh.:.s.l:....:ASt.e.rs.:....n.i..:....:....:....:..P.:....:....C....:... 
             T..p:P..S:.h.a:s.wloarp.:.e..:...u:....:rwe.d.ee.:....:.e..:....:....:....:..a.:....:....a....:... 
             E...:A...:.e.t:e.ildrep.:....:...e:....:gD..:.s..:....:.r..:....:....:....:..r.:....:....s....:... 
             R...:C...:.s.e:..toigfe.:....:...s:....:u...:....:....:.s..:....:....:....:..m.:....:....e....:... 
             ....:E...:....:..cwfsir.:....:....:....:m...:....:....:....:....:....:....:..s.:....:....:....:... 
             ....:....:....:..hni.x..:....:....:....:e...:....:....:....:....:....:....:....:....:....:....:... 
             ....:....:....:...oe....:....:....:....:n...:....:....:....:....:....:....:....:....:....:....:... 
             ....:....:....:...sr....:....:....:....:t...:....:....:....:....:....:....:....:....:....:....:... 
             ....:....:....:...ps....:....:....:....:s...:....:....:....:....:....:....:....:....:....:....:... 
             ....:....:....:...a:....:....:....:....:....:....:....:....:....:....:....:....:....:....:....:... 
             ....:....:....:...c:....:....:....:....:....:....:....:....:....:....:....:....:....:....:....:... 
             ....:....:....:...e:....:....:....:....:....:....:....:....:....:....:....:....:....:....:....:... 
 [FNS]        - - - - : - - - - : - - - - : - - - - : - - - - : - - - - : - - - - : - - - - : - - - - : - - - - 
 Parse       G.GG○G G GGGG. . . : . ○F.G.G:○○○○○! . ○GGF.○. .○F ○ .○. . ○!○○○G○○! : .○○○○ F :○○○○○○ ○ : ○○.F! . 
 Propagate    ○ . . . : . . . . : . . G . : . .○. . : . . . . : . . .○. : . . . . : . . .○. ○○. . . . :○. . . . 
 Quotes       . . . . : . . . . : . ○ . . : . . . . : . . . .○: .○. . ○ : . . . . ○ . . . . ○ . . .○. : . . . . 
 Switch       . G . . : . . . . : . . G .G: . . . . : . ○ . . : . . . . : . . . . : ○ .○. . : . . . . :○. . . . 
 deQuote      . . . . : . . . . : . . . . : . . . . : . . . . :○○ . . . : . . . . : . . . . ○ . . . . : . . . . 
 fixCase      . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . .○. 
 if           . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . 
 init        G.G. G GGGGGGFGGGGGGGGG.F.GF :○. .○. ○ : . . ○○F F . ○ ○ ○○: . .G. . : . . . .F: . . . . F . GF. . 
 splitParms   . . . . : . . . . : . ○ . . : . . .○.○: . . . . : . . . ○ : .○○ ○ ○○:○. .○. . : . .○. .○: . . . . 
 sqz          . . . . : . . . . : . . . . : . .○. . : . . . . : . . . . : . . . . : . .○. . : . . . . : . . .○. 
 upperCase    . . .G. : . . . . : . . . . G . .○. . : . . . .○: . . . . : . . . . : . .○. . : . . . . : . . .○. 
 xCut         . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . . . : . . .○○ 

We can capture the output of the user command by doing either
]mat←XRef ⎕SE.Parser (from session)
or
mat←⎕SE.UCMD']XRef ⎕SE.Parser' (from code)

Until Dyalog v16.0 (which has ]XRef -raw), we need to parse the output of ]XRef to get a square link matrix, along with the full list of nodes (in row/column order of the matrix) and list of original rows (functions).

    ∇ (mat nodes rows)←GetMatrix mat;nodelabs;rows;cols;labs;cat;diag
      (rows mat)←2↑(1,2</∧⌿mat=' ')⊂[2]mat        ⍝ cut at empty column
      (cols mat)←2↑(1,2<⌿∧/mat∊' -:')⊂[1]mat      ⍝ cut at - - - - : - - - -
      mat←1↓[1](' '∨.≠mat)/mat                    ⍝ trim first row and empty columns
      rows←~∘' '¨↓(-1⊃⍴mat)↑[1]rows               ⍝ row titles (list of strings)
      cols←~∘' .:'¨↓(-2⊃⍴mat)↑[1]⍉cols            ⍝ col titles (list of strings)
      nodes←rows∪cols                             ⍝ all titles
      mat←((mat,' ')⍪' ')[rows⍳nodes;cols⍳nodes]  ⍝ square matrix of nodes
    ∇

Now let’s wrap the SharpPlot initialisation into a single function that uses the .NET version if available and falls back to the cross-platform APL workspace if not:

    ∇ {dotnet}←Init
      :If dotnet←(,'W')≡3⊃'.'⎕WG'APLVersion'
          ⍝ .Net assembly (windows only)
          ⎕USING←',sharpplot.dll' ',system.drawing.dll'
      :Else
          ⍝ APL workspace (all platforms)
          :If 0=⎕NC'Causeway'   ⍝ copy workspace only once
              (System.Drawing←System←⍎'Causeway'⎕NS'').(⎕CY'sharpplot.dws')
          :EndIf 
      :EndIf
    ∇

Then we can write a platform-independent function that returns the SharpPlot instance with the chart drawn on it. We split nodes into two categories, functions and globals (ignoring locals and labels) and split links by destination node. By default, DrawNetworkMap lays out node categories on co-centric circles. Also, because the graph is uni-directional, we can afford to use straight links without damaging readability:

    ∇ sp←name Plot(mat nodes rows);catlabs;nodecat
      sp←⎕NEW Causeway.SharpPlot
     
      catlabs←'Function' 'Global'    ⍝ links are split by destination node
      nodecat←(≢nodes)⍴0             ⍝ ignored by default
      ((∨⌿mat∊'FR*')/nodecat)←1      ⍝ functions
      ((∨⌿mat∊'G')/nodecat)←2        ⍝ globals
      ((nodes∊rows)/nodecat)←1       ⍝ caller functions
     
      sp.Heading←name
      sp.HeadingStyle←Causeway.HeadingStyles.Left
      sp.SetMargins 40 30 30 30
      sp.KeyStyle←Causeway.KeyStyles.(BottomAlign+RightAlign)
      sp.SetILabels⊂nodes
      sp.SetILabelFont'Arial' 6 System.Drawing.FontStyle.Bold System.Drawing.Color.Black
      sp.SetColors⊂System.Drawing.Color.(SkyBlue LightCoral)
      sp.SetMarkers Causeway.Marker.Ball
      sp.SetMarkerScales 2
      sp.SetLineStyles Causeway.LineStyle.Solid
      sp.SetPenWidths 0.5
      sp.NetworkMapStyle←Causeway.NetworkMapStyles.(SplitByDestination+Dissected+ArrowLines+FixedArcs+NoAxes+NoLinkKey)
      sp.SetNetworkMapLinkArc 0         ⍝ straight lines
      sp.SetArrowStyle 5                ⍝ fixed-size arrows
     
      sp.SplitBy nodecat catlabs
      sp.DrawNetworkMap⊂↓(mat∊'GFR*')   ⍝ use a single width for all valid links
    ∇

We can then save the graph as SVG to a file (here we use the SvgMode that scales the SVG to fit its container):
sp.SaveSvg 'XRef.svg' Causeway.SvgMode.FixedAspect

Or, if feeding a web server or renderer, we can grab the SVG as a single string without writing to disk:
svg←sp.RenderSvg Causeway.SvgMode.FixedAspect

Windows users will be able to use the SharpPlot Viewer:
vw←⎕NEW Causeway.SharpPlotViewer sp
vw.Show ⍬

XRef

More examples of Network Maps can be found on the SharpPlot.com website in the Network Map Tutorials. To translate C# examples into APL, you can refer to the SharpPlot Rosetta Stone.