Towards Improvements to Stencil
Background The stencil operator ⌺ was introduced in Dyalog version 16.0 in 2017. Recently we received some feedback (OK, complaints) that (a) stencil does padding which is unwanted sometimes and needs to be removed from the result and (b) stencil is too slow when it is not supported by special code. First, stencil in cases […]
2019 APL Problem Solving Competition: Phase I Problems Sample Solutions
The following are my attempts at the Phase I problems of the 2019 APL Problem Solving Competition. There are not necessarily “right answers” as personal style and taste come into play. More explanation of the code is provided here than common practice. All solutions pass all the tests specified in the official problem description. 1. […]
Ascending and Descending
Lexicographic Ordering Lexicographic ordering is what the APL primitives ⍋ and ⍒ provide: ⎕io←0 ⍝ ⎕io delenda est ⎕rl←7*5 ⍝ to get reproducible random results a←?11 3⍴3 a a ⌷⍨⊂ ⍋a 2 1 0 0 1 0 0 2 2 0 2 2 1 1 1 1 0 0 1 0 0 1 0 1 […]
Diane's Lasagne Problem
Making Lasagne Participants in the SA2 Performance Tuning workshop at the Dyalog ’18 User Meeting were encouraged to bring their own problems for the group to work on. Diane Hymas of ExxonMobil brought a good one. The one-liner computation is as follows: lasagne0 ← {groups {+⌿⍵}⌸ amts ×[⎕io] spices[inds;]} where n ← 8e5 spices ← […]
Progressive Index-Of
⎕io=0 is assumed throughout. A recent Forum post motivated investigations into the progressive index-of functions in the FinnAPL Idiom Library: pix ← {((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵) ⍳ ((⍴⍵)⍴⍋⍋⍺⍳⍵,⍺)} ⍝ FinnAPL Idiom 1 pixa ← {((⍋⍺⍳⍺,⍵)⍳⍳⍴⍺) ⍳ ((⍋⍺⍳⍵,⍺)⍳⍳⍴⍵)} ⍝ FinnAPL Idiom 5 In this note, we: explain what is progressive index-of explain why the two functions work investigate the […]
2018 APL Problem Solving Competition: Phase I Problems Sample Solutions
The following are my attempts at the Phase I problems of the 2018 APL Problem Solving Competition. There are not necessarily “right answers” as personal style and taste come into play. More explanation of the code is provided here than common practice. All solutions pass all the tests specified in the official problem description. The […]
Is it Sorted?
Motivation I have been working on the Dyalog APL quicksort implementation. The following programming puzzle arose in the process of doing the QA for this work. ⍵ is a simple array. Write a function sorted, without using ⍋ or ⍒, such that sorted ⍵ is 1 if ⍵ is sorted in ascending order and 0 […]
Dyadic Grade
⎕io=0 is assumed throughout. The essay talks only about ⍋ but the same ideas apply to ⍒. Background ⍋ has the distinction of being the first (in 1980) APL primitive function defined on major cells: the result orders items of a vector, rows of a matrix, planes of a 3-d array, etc. In the ordering […]
Linear Interpolation
⎕io=0 assumed throughout; works in 1-origin with the obvious modifications. Introduction On Wednesday, a question arrived via Dyalog Support from an intern in Africa: If M is the matrix on the left, use linear interpolation to compute the result on the right. 1 20 1 20 4 80 2 40 6 82 3 60 4 […]
Permuting Internal Letters
Friday Afternoon It’s something of a custom in Dyalog to send a “fun” e-mail to the group on Friday afternoons. My gambit for this past Friday was: x ←’ according to research it doesn”t matter’ x,←’ what order the letters in a word are’ x,←’ the human mind can still read it’ x,←’ the only […]
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 […]
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. […]
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 […]
Calculation v Look-Up
(⎕io←0 and timings are done in Dyalog version 15.0.) Table Look-Up Some functions can be computed faster by table look-up than a more traditional and more conventional calculation. For example: b←?1e6⍴2 cmpx ‘*b’ ‘(*0 1)[b]’ *b → 1.32E¯2 | 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ (*0 1)[b] → 1.23E¯3 | -91% ⎕⎕⎕ Some observations about this benchmark: (a) The […]
APL Exercises
These exercises are designed to introduce APL to a high school senior adept in mathematics. The entire set of APL Exercises has the following sections: Introduction 0. Beginnings 1. Utilities 2. Recursion 3. Proofs 4. Rank Operator 5. Index-Of 6. Key Operator 7. Indexing 8. Grade and Sort 9. Power Operator 10. Arithmetic 11. Combinatorial […]
50847534
⎕io←0 throughout. I was re-reading A Mathematician’s Apology before recommending it to Suki Tekverk, our summer intern, and came across a statement that the number of primes less than 1e9 is 50847478 (§14, page 23). The function pco from the dfns workspace does computations on primes; ¯1 pco n is the number of primes less […]
Constructions
Suki Tekverk, a summer intern, spent the last two weeks here studying APL. She will be a high school senior next September and is adept in math, so in addition to APL we also considered some math problems, proofs, and proof techniques, including the following: Given line segments x and y, construct (using compass and […]
A Memo Operator
Abstract Some functions are simply stated and easily understood as multiply-recursive functions. For example, the Fibonacci numbers are {1≥⍵:⍵ ⋄ (∇ ⍵-2)+∇ ⍵-1}. A drawback of multiple recursion is abysmal performance even for moderate-sized arguments, consequently motivating resorts to circumlocutions. The memo operator addresses the performance problem and restores multiple recursion to the toolkit of […]
Shuffle Faster Please!
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 […]
The Halting Problem Rendered in APL
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 […]
PQA
PQA is an acronym for Performance Quality Assurance. We developed PQA to answer the questions, which APL primitives have slowed down from one build of the Dyalog interpreter to the next, and by how much? Currently, PQA consists of 13,659 benchmarks divided into 136 groups. The Graphs The graph above (and all other graphs in […]
Quicksort in APL Revisited
A message in the Forum inquired on sorting strings in APL with a custom comparison function. First, sorting strings without a custom comparison function obtains with a terse expression: {⍵[⍋↑⍵]} ‘syzygy’ ‘boustrophedon’ ‘kakistocracy’ ‘chthonic’ ┌─────────────┬────────┬────────────┬──────┐ │boustrophedon│chthonic│kakistocracy│syzygy│ └─────────────┴────────┴────────────┴──────┘ Sorting strings with a custom comparison function can also be accomplished succinctly by simple modifications to the Quicksort […]
APL Puns
In the Beginning ⌊ floor ⌈ ceiling ⍟ log ⌊ and ⌈ were punnish when the notation was introduced in 1962. They have long since gone mainstream, used even by respectable mathematicians and computer scientists. To see why ⍟ is a pun, see the Vector article My Favourite APL Symbol. • […]
Response to Feedback on Cut, Under and Merge
At Dyalog ’15 John Scholes and I presented proposals for future operators cut, under, and merge. Following the release of the video of this presentation, we received some feedback from a user. Our response to the feedback may be of wider interest. It’s early days yet for cut, under, and merge (they are tentatively planned […]
The Reflex/Commute Operator
The monadic operator ⍨ is defined and modeled as follows: f⍨ ⍵ ←→ ⍵ f ⍵ ⍺ f⍨ ⍵ ←→ ⍵ f ⍺ {⍺←⍵ ⋄ ⍵ ⍺⍺ ⍺} Reflex Some common well-known functions can be written as f⍨ where f is itself a well-known function: +⍨ double ×⍨ square ?⍨ […]
Permutations
I started composing a set of APL exercises in response to a query from a new APL enthusiast who attended Morten’s presentation at Functional Conf, Bangalore, October 2014. The first set of exercise are at a low level of difficulty, followed by another set at an intermediate level. One of the intermediate exercises is: Permutations […]
In Praise of Magic Functions: Part II
Part I of this post was concerned with the development speed and execution speed of magic functions and should be read before this post. Benefitting from Future and Past Improvements Looking at the magic function for key in Part I, we see that its performance depends on the following APL primitives, listed with information on […]
In Praise of Magic Functions: Part I
A magic function is an APL-coded (dfn) computation in the C source of the interpreter. For example, some cases of ∧.= are coded as MAGIC(“(≢⍺)(↑∘.=↓)⍺⍳⍺⍪⍉⍵”). The rubric “magic function” includes magic functions and magic operators. Acknowledgments. Magic functions in Dyalog are made possible due to work done by John Scholes and Richard Smith. Development Speed […]
A Dialog on APL
A discussion between Nicolas Delcros and Roger Hui Nicolas, Prologue: From a language point of view, thanks to Ken Iverson, it is obvious that you want grade rather than sort as a primitive. Yet from a performance point of view, sort is currently faster than grade. Can one be “more fundamental” than the other? If […]
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 […]
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 […]
Changes of Heart
Karen Shaw started the ball rolling (hearts afluttering?) by asking Jay Foad to come up with a one-liner for St. Valentine’s Day; he then solicited contributions from the language development group. Nick Nickolov responded with the following, with no explanation other than that there is room for improvement: ⎕io←0 ⋄ (⊢,⌽)’ X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨0↓n-⍳(2×n),n←20] XXXXX XXXXX XXXXXXXXXX […]
The Diamond Kata
Acknowledgments Morten Kromberg is the other co-author of this text but the blogging software prevents his being listed as such. We are indebted to Jay Foad, Nick Nikolov, John Scholes, and Fiona Smith for comments on successive drafts of the MS. The Problem The diamond kata is a programming exercise used in the agile development, […]
Cholesky Decomposition
Morten was visiting Dyalog clients and forwarded a request: Can we have the Cholesky decomposition? If A is a Hermitian, positive-definite matrix, its Cholesky decomposition [0] is a lower-triangular matrix L such that A ≡ L +.× +⍉L. The matrix L is a sort of “square root” of the matrix A. For example: ⎕io←0 ⋄ […]
Quicksort in APL
Quicksort is a classic sorting algorithm invented by C.A.R. Hoare in 1961 [0, 1]. It has been known for some time that quicksort has a terse rendition in APL [2]. To get right to it, here is the code: Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵} The “pivot” ⍵⌷⍨?≢⍵ is randomly chosen. ((∇<S)⍪=S⍪(∇>S)) is a […]
Ken Iverson's Favourite APL Expression?
What was Ken Iverson’s favourite APL expression? I don’t know that he had one and if he had I don’t know what it was, but if I have to guess … From Sixteen APL Amuse-Bouches: The expression (0,x)+(x,0) or its commute, which generates the next set of binomial coefficients, is present in the document that […]
A Speed-Up Story
The first e-mail of the work week came from Nicolas Delcros. He wondered whether anything clever can be done with ∘.≡ on enclosed character strings. I immediately thought of using “magic functions“, an implementation technique whereby interpreter facilities are coded as dfns. I thought of magic functions because the APL expressions involved in this case […]
