I-Beam Mnemonics

Posted on by

I-Beam (⌶) is an operator that takes as its operand a numeric code and derives a function which isn’t really considered to be part of the APL language – for example: something which could be experimental, which might provide access to parts of the interpreter that should only be accessed with care, or may set up specific conditions within the interpreter to help in testing. Principally, I-Beam functions exist for internal use within Dyalog but as of version 15.0 there are 55 I-Beam functions that are published and available for general use. How on earth are you supposed to remember all the different codes?

To an extent, you are not. It is perhaps no bad thing that they are a little difficult to remember: I-Beam functions are experimental, liable to be changed or even removed and should be used with care. The codes appear to be somewhat random partly because they are somewhat random – mostly selected on the whim of the developer who implemented the function. However, some codes were chosen less randomly than others – quite a few are grouped so that I-Beams that provide related functionality appear consecutively or at least close together but the most interesting ones are “named” – or, at least, given a numeric code that is derived from a name or otherwise memorable value. So here are some of those unofficial mnemonics that may help you better remember them too.

A favourite trick for deriving a code from a meaningful name is to devise a name containing the letters I, V, X, L, C, D and M, and then convert that into a number as if it were a Roman numeral. Thus:

  • “Inverted table IndeX of” is abbreviated to IIX, which is I-Beam 8
  • “Syntax Colouring” rather awkwardly becomes “Cyntax Colouring”, thence CC and I-Beam 200
  • “Called Monadically” is CM, or 900
  • “Memory Manager” is MM – I-Beam 2000
  • “Line Count” is LC, or rather L,C – 50100

Another favourite is to use numbers that look or sound like something else:

  • The compression I-Beam is 219, which looks a bit like “ZIP”
  • The case folding I-Beam is 819, or “BIg”
  • When support for function trains was in development an I-Beam was used to switch between different implementations – 1060, or “lOCO[motive]” (this I-Beam is no longer in use)
  • The number of parallel threads I-Beam is 1111 – four parallel lines
  • The fork I-Beam is 4000: 4000 is 4K; “Four K” said very quickly might sound like “Fork”

For others the function is associated, or can be associated, with something already numeric:

  • The I-Beam to update function timestamps is 1159 – a memorable time
  • The I-Beam to delete the content in unused pockets is 127 – the same as the ASCII code for the delete character
  • The draft JSON standard is RFC 7159 and support for it is implemented as 7159⌶
  • The now-deprecated I-Beam to switch between Random Number Generator algorithms is 16807 – the default value used to derive the random seed in a clear workspace

Tips for the use of I-Beam functions

  • Do not use I-Beam functions directly in application code – always encapsulate their use in cover-functions that can quickly be modified to protect your application in the event that Dyalog should change the behaviour of, or withdraw, an I-Beam function.
  • Do not use I-Beam functions that are not documented by Dyalog in the Language Reference or elsewhere – those designed to test the interpreter may have undesirable side effects.
  • Do let Dyalog know if you find an I-Beam function particularly useful and/or have suggestions for its development. Some new features are initially implemented as I-Beam functions to allow such feedback to shape their final design.
Email, RSS Follow

Shuffle Faster Please!

Posted on by

Andy reported that in the shuffle QA some functions take a long time:

m9249   “4½ days so far”
rankop  21.5 hours
m12466  26.3 hours
points  7.2 hours

Background: Shuffle QA is an intensification of the normal QA. The suite of over 1800 QA functions is run under shuffle, whereby every getspace (memory allocation) is followed by every APL array in the workspace being shifted (“shuffled”) and by a simple workspace integrity check. The purpose is to uncover memory reads/writes which are rendered unsafe by events which in normal operations are rare.

m9249

m9249 tests +\[a], ×\[a], ⌈\[a], and ⌊\[a]. It ran in under 3 seconds in normal operations; for it to take more than 4½ days under shuffle, getspace is clearly the dominant resource and hereafter we focus on that.

m9249 used expressions like:

assert (+⍀x) ≡ {⍺+⍵}⍀x

Since {⍺+⍵} is not recognized by the scan operator ⍀ and therefore not supported by special code, {⍺+⍵}⍀x is done by the general O(n*2) algorithm for scans, AND on each scalar the operand {⍺+⍵} is invoked and a getspace is done. The improved, faster QA does this:

F ← {1≥≢⍵:⍵ ⋄ x ⍪ (¯1↑⍵) ⍺⍺⍨ ¯1↑x←⍺⍺ ∇∇ ¯1↓⍵}
assert (+⍀x) ≡ +F x

With such a change, the faster m9249 runs in 22 minutes under shuffle instead of over 4½ days, without any reduction in coverage.

The number of getspace are as follows: +⍀x takes O(1). The second expression {⍺+⍵}⍀x does ×\1↓⍴x separate scans, and each one takes O((≢x)*2) getspace; the total is therefore O(((≢x)*2)××/1↓⍴x) ←→ O((≢x)××/⍴x). The third expression +F is linear in ≢x and is therefore O(≢x) in the number of getspace. In m9249 the largest x has size 33 5 7. The following table shows the orders of complexity and what they imply for this largest x:

+⍀x O(1) 1
{⍺+⍵}⍀x O((≢x)××/⍴x) 38115 = 33 × ×/ 33 5 7
+F x O(≢x) 33

The ratio between 38115 and 33 goes a long way towards explaining why the time to run m9249 under shuffle was over 4½ days and is now 22 minutes. (Why does m9249 still take 22 minutes? It tests for the four functions + × ⌈ ⌊, for various axes, for different datatypes, and for different axis lengths.)

rankop

Another shuffle sluggard rankop took 47 hours. rankop tests expressions of the form f⍤r⊢yand x f⍤r⊢y for various functions f. The techniques used for reducing the number of getspace differ from function to function. We look at x↑⍤r⊢y as an illustration.

assert (4↑⍤1⊢y) ≡ 4{⍺↑⍵}⍤1⊢y

⍴y was 2 7 1 8 2 8. The expression took 7.6e¯5 seconds normally and 7.5 seconds under shuffle. The left hand side requires O(1) getspace, the right hand side O(×/¯1↓⍴x). The expression was changed to:

assert (4↑⍤1⊢y) ≡ 2 7 1 8 2 4↑y

Feels like cheating, doesn’t it? 🙂 The new expression takes 0.115 seconds under shuffle.

m12466

m12466 tests n⌈/[a]x (and n⌊/[a]x). Previously, it did this by comparing n⌈/[a]x against n{⍺⌈⍵}/[a]x for x with shape 7 17 13 11, for each of the four axes, for two different values of n, and for the 1-, 2-, 4-, and 8-byte numeric datatypes. It required 5238426 getspace and 26.3 hours to run under shuffle.

F←{p⍉⍺⍺⌿(⊂(⎕io-⍨⍳|⍺)∘.+⍳(1-|⍺)+(⍴⍵)[⍵⍵])⌷(⍋p←⍒⍵⍵=⍳⍴⍴⍵)⍉⍵}

F is a dyadic operator. The left operand ⍺⍺ is ⌈ or ⌊; the right operand ⍵⍵ is the axis; and n(⌈ F a)x is the same as n⌈/[a]x. n(⌈ F a)x mainly does n⌈⌿x; other axes are handled by transposing the axis of interest to be the first, then doing n⌈⌿x, then transposing the axes back into the required order. n(⌈ F a)x is much more complicated than n{⍺⌈⍵}/[a]x but has the advantage of using only O(1) getspace.

The revamped m12466 function uses 13717 getspace and 2 minutes to run under shuffle.

points

points is a function to test monadic format (⍕) for different values of ⎕pp.

points←{⍺←17 ⋄ ⎕pp←⍺
  tt←{(⌽∨\⌽⍵≠⍺)/⍵}                   ⍝ trim trailing ⍺s.    
  ~0∊∘.{                             ⍝ all pairs (⍳⍵)       
    num←'0'tt↑,/⍕¨⍺'.'⍵              ⍝ eg '9.3'             
    num≡⍕⍎num                        ⍝ check round trip     
  }⍨⍳⍵
}

The expression is 14 15 16 17 points¨ 100, meaning that for each of the 100 numbers num as text,

  1.1   1.2   1.3   1.4   1.5     1.100
  2.1   2.2   2.3   2.4   2.5     2.100
  3.1   3.2   3.3   3.4   3.5 ... 3.100
...
 99.1  99.2  99.3  99.4  99.5    99.100
100.1 100.2 100.3 100.4 100.5   100.100

a “round-trip” num≡⍕⍎num is evaluated. The expression requires 1.3 million getspace and 7.2 hours to run under shuffle.

A much more efficient version with respect to getspace is possible. Let x be a vector. ⍕¨x requires O(≢x) getspace; ⍕x requires O(1) getspace and, like ⍕¨x, formats each individual element of x independently.

points1←{
  ⎕io←⎕ml←1                                                 
  tt←{(⌽∨\⌽⍵≠⍺)/⍵}                   ⍝ trim trailing ⍺s     
  x←1↓∊(' ',¨s,¨'.')∘.,'0'tt¨s←⍕¨⍳⍵  ⍝ numbers as text      
  y←⍎x                                                      
  {⎕pp←⍵ ⋄ x≡⍕y}¨⍺                   ⍝ check round trip     
}

14 15 16 17 points1 100 requires 11050 getspace and less than 2 minutes to run under shuffle.

What to do?

Andy says that the shuffle QA takes over 2000 hours (!). The shuffle sluggards will be tackled as done here by using more parsimonious APL expressions to compare against the aspect being QA-ed. Going forward, a new QA function will be run under shuffle as it is being developed. The developers will be unlikely to tolerate a running time of 4½ days.

Email, RSS Follow

Loops, Folds and Tuples

Posted on by

For-loops
Given an initial state defined by a number of variables, a for-loop iterates through its argument array modifying the state.

    A←... ⋄ B←... ⋄ C←...       ⍝ initial state
    :For item :In items         ⍝ iterating through array "items"
        A←A ... item            ⍝ new value for A depending on item
        C←C ... A ... item      ⍝ new value for C depending on A and item
        ...                     ⍝ state updated
    :EndFor
    A B C                       ⍝ final state

In the above example the state comprises just three variables. In general, it may be arbitrarily complex, as can the interactions between its various components within the body of the loop.

Dfns
Dfns don’t have for-loops. Instead, we can use reduction (or “fold”) with an accumulating vector “tuple” of values representing the state. Here is the D-equivalent of the above code:

    ⊃{                      ⍝ next item is ⍺
        (A B C)←⍵           ⍝ named items of tuple ⍵
        A∆←A ... ⍺          ⍝ new value for A depending on item ⍺
        C∆←C ... A∆ ... ⍺   ⍝ new value for C depending on A∆ and item ⍺
        ...                 ⍝ ...
        A∆ B C∆             ⍝ "successor" tuple (A and C changed)
    }/(⌽items),⊂A B C       ⍝ for each item and initial state tuple A B C

In this coding, the accumulating tuple arrives as the right argument (⍵) of the operand function, with the next “loop item” on the left (⍺). Notice how the items vector is reversed (⌽items) so that the items arrive in index-order in the right-to-left reduction.

If you prefer your accumulator to be on the left, you can replace the primitive reduction operator (/) with Phil Last’s foldl operator, which also presents its loop items in index-order:

    foldl←{⊃⍺⍺⍨/(⌽⍵),⊂⍺}    ⍝ fold left

then:

    A B C {                 ⍝ final state from initial state (left argument)
        (A B C)←⍺           ⍝ named items of tuple ⍺
        A∆←A ... ⍵          ⍝ new value for A depending on item ⍵
        C∆←C ... A∆ ... ⍵   ⍝ new value for C depending on A∆ and item ⍵
        A∆ B C∆             ⍝ successor tuple (A and C changed)
    } foldl items

If the number of elements in the state tuple is large, it can become unwieldy to name each on entry and exit to the operand function. In this case it simplifies the code to name the indices of the tuple vector, together with an at operator to denote the items of its successor:

    T ← (...) (...) ...         ⍝ intitial state tuple T
    A B C D ... ← ⍳⍴T           ⍝ A B C D ... are tuple item "names"

    T {                         ⍝ final state from initial state (left argument)
        A∆←(A⊃⍺) ... ⍵          ⍝ new value for A depending on item ⍵
        C∆←(C⊃⍺) ... A∆ ... ⍵   ⍝ new value for C depending on A∆ and item ⍵
        A∆ C∆(⊣at A C)⍺         ⍝ successor tuple (A and C changed)
    } foldl items

where:

    at←{A⊣A[⍵⍵]←⍺ ⍺⍺(A←⍵)[⍵⍵]}   ⍝ (⍺ ⍺⍺ ⍵) at ⍵⍵ in ⍵

There is some discussion about providing a primitive operator @ for at in Dyalog V16.

Examples
Function kk illustrates naming tuple elements (S E K Q) at the start of the operand function.
Function scc accesses tuple elements using named indices (C L X x S) and an at operator.

Tuples: a postscript
We might define a “tuple” in APL as a vector in which we think of each item as having a name, rather than an index position.

    bob         ⍝ Tuple: name gender age
┌───┬─┬──┐
│Bob│M│39│
└───┴─┴──┘

    folk        ⍝ Vector of tuples
┌──────────┬────────────┬──────────┬────────────┬─
│┌───┬─┬──┐│┌─────┬─┬──┐│┌───┬─┬──┐│┌─────┬─┬──┐│
││Bob│M│39│││Carol│F│31│││Ted│M│31│││Alice│F│32││ ...
│└───┴─┴──┘│└─────┴─┴──┘│└───┴─┴──┘│└─────┴─┴──┘│
└──────────┴────────────┴──────────┴────────────┴─

    ↓⍉↑ folk    ⍝ Tuple of vectors
┌─────────────────────────┬────────┬───────────────┐
│┌───┬─────┬───┬─────┬─   │MFMF ...│39 31 31 32 ...│
││Bob│Carol│Ted│Alice│ ...│        │               │
│└───┴─────┴───┴─────┴─   │        │               │
└─────────────────────────┴────────┴───────────────┘

    ⍪∘↑¨ ↓⍉↑ folk   ⍝ Tuple of matrices
┌─────┬─┬──┐
│Bob  │M│39│
│Carol│F│31│
│Ted  │M│31│
│Alice│F│32│
 ...   . ..
└─────┴─┴──┘

APLers sometimes talk about “inverted files”. In this sense, a “regular” file is a vector-of-tuples and an inverted file (or more recently: “column store”) is a tuple-of-vectors (or matrices).

Email, RSS Follow

The Halting Problem Rendered in APL

Posted on by

The halting problem is the problem of determining, from a description of a program and an input, whether the program will finish running or continue to run forever. It was proved in the negative by Alonzo Church and Alan Turing in 1936, and can be rendered in Dyalog APL as follows:

Suppose there is an operator H such that f H ⍵ is 1 or 0 according to whether f ⍵ halts. Consider:

In dfns

   f←{∇ H ⍵:∇ ⍵ ⋄ ⍬}

For f 0, if ∇ H 0 is 1, then ∇ 0 is invoked, leading to an infinite recursion, therefore ∇ H 0 should have been 0. On the other hand, if ∇ H 0 is 0, then the ⍬ part is invoked and is the result of f 0, therefore ∇ H 0 should have been 1.

Presented as a table: For f 0

suppose ∇ H 0 is invokes consequence ∇ H 0 should be
1 ∇ 0 infinite recursion 0
0 ⍬ f 0 results in ⍬ 1

Therefore, there cannot be such an operator H.

In Tradfns

   ⎕fx 'f x' '→f H x'

For f 0

suppose f H 0 is invokes consequence f H 0 should be
1 →1     infinite loop 0
0 →0 f 0 exits 1
Email, RSS Follow

Rencontres Dyalog APL 2016 – Paris, France

Posted on by

It is really good to see APL events come back to life! In April of 2014, we witnessed the re-birth of SWEDAPL, which had been dormant for some time – but now meets twice a year and is perhaps the most vibrant APL meeting on our circuit, with many young developers developing new products and features in APL. The last SWEDAPL meeting drew a substantial international crowd, including a number of Danes – and the next one, scheduled for April 1st, is making a guest appearance in Copenhagen, hosted by Simcorp A/S – a bit like the Tour de France 🙂

paris16This year we are really happy to be back in France, which has also had a relatively dormant APL community for the last decade or so – at least in terms of holding meetings. In this case we decided to arrange a meeting with the help of our French distributor – Quantys. Although the invitation was to a “Dyalog User Meeting“, about half of the attendees were users of other APL systems than Dyalog APL – with a little luck this meeting will turn out to contain the seeds for a rebirth of an independent French APL group. Fingers crossed!

Everyone please note: If you want to organise a local APL event, and you invite a speaker from Dyalog, we will do everything we can to send one or two delegates to your meeting. The current “circuit” includes Finland, Germany and Sweden twice a year, France and the East Coast USA. We have been known to show up at the Bay Area Users’ Group from time to time, in Toronto, at J and kx meetings – and recently also at FunctionalConf in Bangalore.

After welcoming remarks from Marc Righetti of Quantys, Gitte talked about Dyalog’s commitment to ensure that APL is well-integrated with modern computing platforms and infrastructure, which is always in the throes of another revolution. The current movement towards cloud computing and the need for platform independence is no exception. The good news is that Dyalog is growing to meet the challenge; we expect to add another couple of heads this year and grow the company by another ten percent.

Dan Baronet is a native of Montreal, Canada. As one of our French-speaking team members, he ended up doing most of the heavy lifting, with presentations on the upcoming v15.0 release, and a recap of the recent language enhancements in version 14.0 – in particular, the rank and key operators and function trains. Nicolas Delcros also spoke in French on the subject of his most recent work on integrating the publishing capabilities of Adrian Smith’s NewLeaf tool to SharpPlot, under the name SharpLeaf. I was only allowed to interrupt the flow of French twice, first with a road map presentation and, in the afternoon, a brief introduction to Futures and Isolates.

At the end of an action-packed day, Quantys treated us all to Champagne and snacks – many thanks to Marc for running the show and taking good care of us. A single day was much too short a time to do justice to the last decade of Dyalog achievements – so we will have to be back more regularly!

Email, RSS Follow

FinnAPL Forest Seminar 2016

Posted on by
The view from the Sauna. Some people actually went in!

The view from the Sauna. Some people actually went in!

Finns probably have better reasons to look forward to spring more than most of us: not only does it get much easier to keep that hole in the ice open, it is time for the annual FinnAPL Forest Seminar!

This year, just under 20 of us gathered for two days (Thursday March 10th and Friday March 11th) at Hirvihaara Manor, about an hour north of Helsinki, to update each other on what we have been getting up to recently.

Thursday

After a warm welcome from Jouko Kangasniemi, Chairman of FinnAPL, Veli-Matti Jantunen from Statistics Finland kicked the proceedings off with a talk titled “The long way of an APL2 bigot to Dyalog world”, where he discussed features of recent versions of Dyalog APL, awarding some of them them varying numbers of thumbs up, declaring some to be irrelevant. A few were found to be flawed… We are hoping to talk him into a repeat at Dyalog’16 as this was a valuable and thought-provoking review!

I was on next – with the Spring 2016 version of the Dyalog Road Map. As should be confirmed by the slides, there is not a big change in direction. We are planning to increase headcount by another 10% this year and continue investing in the core interpreter technology, APL compilers, and tools to help you build applications on a growing number of platforms.

Ants on the left. Ray Cannon on the right

Ants on the left. Ray Cannon on the right

After lunch, Ray Cannon showed us how to “Build a better ant brain”, producing wonderful, coloured, animations with ants crawling all over the big screen, using MiServer 3.0 and a bit of JavaScript – running under Dyalog APL on a Raspberry Pi!

My technical keynote in the morning had included a demo of a very early prototype of a Python interface, which will allow APL users to tap in to Python libraries. I was, therefore, very interested in the next presentation by Esa Pursiheimo from the VTT Technical Research Centre of Finland – which gave us all an introduction to the Python language. There is no question that the Python community has built libraries that could be very useful to APLers (although I cannot say the language itself impressed me much 🙂 ).

The last presentation of the day, titled “Data Driven Documents” (aka “D3”), was also about using libraries written in other programming language to extend APL applications. In this case the language was JavaScript. Jouko Kangasniemi from the Confederation of Finnish Industries (EK) showed how he is generating JavaScript to call the popular D3 Graphics Library and publish charts that are relevant to Economic planners in Finland. A collection of animated charts created using this technology can be found at http://ek.fi/materiaalipankki/tietografiikka/talous/viikon-graafit/.

Since we were in Finland, the afternoon ended with a visit to a traditional “smoke sauna”, before we all scrubbed up for the banquet.

Cheers! From left to right (more or less): Antero Ranne, Gitte Christensen, Esa Lippu, Miika Rämä, Simo Kilponen, Jouko Kangasniemi, Heikki Viitamäki, Esa Pursiheimo, Olli Paavola, Kaarlo Reipas, Göran Koreneff, Morten Kromberg, Kimmo Kekäläinen, Veli-Matti Jantunen, Timo Korpela, Ray Cannon (Missing: Anssi Seppälä)

Cheers! From left to right (more or less): Antero Ranne, Gitte Christensen, Esa Lippu, Miika Rämä, Simo Kilponen, Jouko Kangasniemi, Heikki Viitamäki, Esa Pursiheimo, Olli Paavola, Kaarlo Reipas, Göran Koreneff, Morten Kromberg, Kimmo Kekäläinen, Veli-Matti Jantunen, Timo Korpela, Ray Cannon (Missing: Anssi Seppälä)

Friday

The first talk on Friday morning was perhaps the most interesting from my point of view: Antero Ranne of the Ilmarinen Mutual Pension Insurance Company: Parallel showed how he was able to speed up financial simulations by a factor of approximately 3 on his Intel i7-based laptop, using Futures and Isolates in Dyalog version 14.0. It is really good to see that domain experts wield this tool!

After coffee, Gitte presented the work that she had done to put APL on the map as an invited speaker at a recent conference on the history of information technology in the Nordic region. She also reminded us all that we will be celebrating the 50th anniversary of the first running APL system on November 27 (http://silvermapleweb.com/first-cleanspace/). At Dyalog ’16 on October 9th-13th in Glasgow, Scotland, Dyalog will set time aside to celebrate this anniversary in collaboration with the British APL Association. If you have a good story about ground-breaking work done in APL in the early days, please get in touch and discuss how you might contribute to the celebrations!

Once again, I found myself standing between the audience and lunch – fortunately there are enough juicy language features and interfaces coming in versions 15.0 and 16.0 and I did not have anyone walk out before I was done. I even had time to talk about a workspace that we added several years ago, after discovering that several members of the audience were unaware of it: The “loaddata” workspace, which contains functions to read and write Excel Spreadsheets, CSV files, XML and ODBC data sources. If you have not seen it yet, try loading it and take a look.

After another excellent lunch, Anssi Seppälä of Enease Oy wrapped up the formal part of the programme with a talk on an inverted vectorial database implemented in the J programing language, named JD. JD makes it straightforward to manage large timeseries containing records of power usage and the quality of electricity delivered to consumers, perform analyses and generate visualisations of the data.

Several of us continued discussing programming challenges, while drinking (STRONG!!!) Finnish coffee and eating the wonderful cakes that were provided all day by Hirvihaara Manor, before heading back home after another successful FinnAPL Forest Seminar – we look forward to the 2017 edition!

Gitte and I managed to get about 40 hours at home before boarding the next plane, heading for Paris for the first French Dyalog User Meeting in recent history. More about that coming soon!

Email, RSS Follow