Roger Hui - Computer Scientist

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 … Read

Jun 2020
in Algorithms, APL Language, Implementation, Tips & Tricks

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. Chunky Monkey … Read

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 … Read

Feb 2019
in Algorithms, APL Language

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 ← … Read

Nov 2018
in Dyalog '18, Events, Musings

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 … Read

Oct 2018
in APL Language

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 … Read

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 … Read

May 2018
in APL Language

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 … Read

Apr 2018
in APL Language

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 … Read

Apr 2018
in APL Language

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 … Read

Jan 2018
in Musings, Recreational

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 … Read

Jul 2017
in APL Language

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. … Read

May 2017
in Algorithms, Recreational

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 … Read

May 2017
in APL Language

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: Some observations about this benchmark: (a) The advantage of table look-up depends on the time to calculate the function directly, versus the time to do … Read

Apr 2017
in APL Language

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: Introduction0. Beginnings1. Utilities2. Recursion3. Proofs4. Rank Operator5. Index-Of 6. Key Operator7. Indexing8. Grade and Sort9. Power Operator10. Arithmetic11. Combinatorial ObjectsThe Fine Print Sections 2 and 10 are the most interesting … Read

Sep 2016
in Algorithms

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 … Read

Sep 2016
in Algorithms, APL Language, Musings

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 … Read

Aug 2016
in Musings

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 … Read

Jun 2016
in APL Language

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 … Read

May 2016
in Algorithms, APL Language

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 … Read

Apr 2016
in Algorithms

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 … Read

Mar 2016
in Windows

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 … Read

Feb 2016
in Algorithms, APL Language, Tips & Tricks

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. • … Read

Dec 2015
in Recreational

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 … Read

Nov 2015
in APL Language, Dyalog '15, Videos

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 ?⍨ … Read

Oct 2015
in APL Language

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 … Read

Jul 2015
in Algorithms, APL Language

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 … Read

Jun 2015
in Algorithms, APL Language

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 … Read

Jun 2015
in Algorithms, APL Language

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 … Read

May 2015
in APL Language

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 … Read

Apr 2015
in APL Language

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 … Read

Mar 2015
in Musings

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 … Read

Feb 2015
in Algorithms, APL Language

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, … Read

Jan 2015
in Algorithms, APL Language

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 ⋄ … Read

Jan 2015
in APL Language

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 … Read

Dec 2014
in APL Language

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 … Read

Dec 2014
in APL Language, Musings

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 … Read

Nov 2014
in APL Language, Tips & Tricks

APL Programmer

By

By

By

By