I’ve been learning at least one new programming language a month through Exercism which has been really fun and interesting. I frequently say that “every language you learn teaches you something about all the others you know” and with nearly a dozen under my belt so far I’m starting to worry about the combinatorics of that statement.
APL isn’t on the list of languages but I’ve seen it in codegolf solutions often enough that it seemed worth a look.
Now, when I say “learning” I mean “good enough to do 5 toy exercises” which is what you need to do to in order to earn the badge for that month in the “#12in23 challenge” (gamification FTW). That’s often sufficient for me to get a taste for the language and see if it’s something I’d like to dive deeper into.
It means I’ve been watching a lot of “<language> beginner tutorial” videos recently, which may have been what prompted YouTube to suggest to me a video from code_report; I think this one comparing a leetcode solution to the problem
find the GCD (greatest common divisor) of the smallest and largest numbers in an array
written in 16 (sixteen!!!) languages. Some of those I know a little or a moderate amount about, but one stood out. The APL solution comprises 5 glyphs (symbols) representing operations
⌈/∨⌊/I’ve seen APL solutions pop up in codegolf and they’ve just looked like madness,
which is probably fair. The linked video prompted me to look into some of their
other videos and they do a great job explaining the glyphs in APL and how they
compare to other languages. It turns out this madness is not nearly as hard to
read as it looks. The above glyphs represent “maximum” (⌈), “reduce” (/), “GCD”
(∨), and “minimum” (⌊) and those all correspond well to the problem statement.
The function itself is
“point-free” whereby the
argument(s) aren’t specified at all; like saying mean rather than mean(x).
For the truly adventurous: ‘The Hideous Beauty of Point-Free Programming; An
exercise in combinators using
Haskell’
I ended up diving deeper and deeper, and it all started to make more and more sense.
In a recent stream, ThePrimeagen responded to the comment about some language that “<x> is more readable” with “readability is just familiarity” and that stuck with me - I’m not entirely sure I 100% agree with it because I can find several ways to write some code that someone familiar with that language will either find easy or hard to read, despite familiarity. I think {dplyr} in R does a fantastic job of abstracting operations with verbs and making data pipelines easy to comprehend, certainly much more than the base-equivalent code.
So, would APL be “readable” if I was more familiar with it? Let’s find out!
There aren’t that many glyphs in APL - there are far more unique functions in most big libraries from any mainstream language. Looking at the top of the ‘ride’ editor for Dyalog APL there are 80 glyphs. To make a slightly unfair example, there are a lot of exported functions (288 of them) in {dplyr}…
packageVersion("dplyr")## [1] '1.0.10'ns <- sort(getNamespaceExports("dplyr"))
head(ns, 20)## [1] ".data" "%>%" "across" "add_count" "add_count_"
## [6] "add_row" "add_rownames" "add_tally" "add_tally_" "all_equal"
## [11] "all_of" "all_vars" "anti_join" "any_of" "any_vars"
## [16] "arrange" "arrange_" "arrange_all" "arrange_at" "arrange_if"tail(ns, 20)## [1] "tbl_vars" "tibble" "top_frac"
## [4] "top_n" "transmute" "transmute_"
## [7] "transmute_all" "transmute_at" "transmute_if"
## [10] "tribble" "type_sum" "ungroup"
## [13] "union" "union_all" "validate_grouped_df"
## [16] "validate_rowwise_df" "vars" "with_groups"
## [19] "with_order" "wrap_dbplyr_obj"Taking the functions listed as S3method or export in the
NAMESPACE
file is 470+. Sure, these aren’t all user-facing, but still. Lots.
So, 80 isn’t a “huge” number, if that’s the entire language.
I watched some more videos about what the glyphs mean and how they work. I started to become slightly familiar with what they mean. Learning is done with the hands, not the eyes, though - as this (not new) blog post goes into great detail on, so I felt that I needed to actually write something. I installed Dyalog APL and the ride editor (given that it uses glyphs, a non-standard editor seems to make sense; I’ve otherwise been completing the Exercism solutions in emacs). I also found tryapl.org as an online editor.
The first step was to just follow along what I’d seen in the videos. I had most recently watched this one that does include a comparison to R (and Julia) so I tried to recreate what I’d seen built up. I was shocked that I actually could!
From reshaping into a matrix, to building up the sequence, to inserting the combinator - it all came together easily enough.
On “combinators” - if you aren’t familiar with Lambda Calculus and have a spare hour, this is a wonderful talk explaining the basics and demonstrating them using JavaScript.
More videos, more learning. I found this one which is another leetcode problem which was roughly
find the maximum value of the sum of rows of a matrix
That sounded like something R would easily handle, but this particular
video didn’t feature R. It did feature C++, the solution for which
requires two for loops and looked (to me) horrific - I’m used to just
passing a matrix to an R function and not having to worry about loops.
I’ve had many discussions on this topic because for whatever reason, for
loops have a particular reputation in R despite them not (necessarily) being
any worse than any other solution. The short response is that if you’re using one
when you could be using vectorisation, you’re probably stating your problem poorly
and can do better (in terms of readability, performance, or both). This video
covers the points really nicely.
Jenny Bryan made the point that
Of course someone has to write loops… It doesn’t have to be you
alluding to the fact that vectorisation (either with the *apply family or purrr)
still has a C loop buried within (I covered some of this myself in another post).
Miles McBain makes a point of never using them (directly).
Okay, so, returning to the leetcode problem. The APL solution in the video is
reshaping (⍴) a vector to a matrix then reducing (/) addition (+) across rows (last-axis; c.f. first axis would be +⌿) and reducing (/) that with maximum (⌈)
making the entire solution
x ← 3 3⍴1 2 3 5 5 5 3 1 4
⌈/+/x
15which is an elegant, compact solution. APL agrees to ignore the [1] at the
start of R’s default output if R agrees to ignore the odd indenting of APL commands.
As a sidenote: I love that I finally get to use the OG assignment arrow ←
that inspired the usage in R (as <-). This isn’t some ligature font, it’s the
actual arrow glyph with Unicode code point U+2190. The APL keyboard has this on
a key and that was common around the time that it made it into R (or S).
The video explains that this solution is
particularly nice because it’s explicit that two “reduce” operations
are occurring. The + operator in APL can be either unary (takes 1 argument) or
binary (takes 2 arguments) but it can’t loop over an entire vector. To achieve that,
it’s combined with / which performs “reduce”, essentially applying + across
the input.
It’s a fairly straightforward answer with R, too:
a <- matrix(c(1, 2, 3,
5, 5, 5,
3, 1, 4),
3, 3, byrow = TRUE)
a## [,1] [,2] [,3]
## [1,] 1 2 3
## [2,] 5 5 5
## [3,] 3 1 4max(rowSums(a))## [1] 15and done. Nice. No for loops. Or are there? Of course there are, somewhere, but
can we write this “like” the APL solution and be more explicit with the “reduce”
steps over binary operators? R has a Reduce() function for exactly this case.
A simplified rowSums() function could just be applying the sum operation to
the rows of the matrix
s <- function(x) apply(x, 1, sum)but sum(x) is itself vectorised - it’s an application of the binary + operation
across a vector, so really we could have
s <- function(x) apply(x, 1, \(y) Reduce(`+`, y))
s(a)## [1] 6 15 8This isn’t so bad compared to APL which “naturally” performs the reduction
over that dimension. Compare (⍝ signifies a comment):
x
1 2 3
5 5 5
3 1 4
⍝ "rowSums"
+/x
6 15 8
⍝ "colSums"
+⌿x
9 8 12There’s nothing here that says x needs to have more than 1 dimension, though -
it’s the same operator(s) on a vector, just that they do the same thing
+/(1 2 3)
6
+⌿(1 2 3)
6max is also vectorised, so a simple, ostensibly binary version of that could be
m <- function(x, y) ifelse(x > y, x, y)
m(1, 2)## [1] 2m(4, 2)## [1] 4Together, an R solution using these could be
Reduce(m, s(a))## [1] 15which, if we shortened Reduce to a single character
R <- Reducewould be
R(m, s(a))## [1] 15That’s not a lot more characters than APL. I’ve abstracted at least one of the functions, though - APL uses the operators directly, in which case we’d have
maxWealth <- \(x) R(m, apply(x, 1, \(y) R(`+`, y)))
maxWealth(a)## [1] 15That’s only using Reduce, binary +, a simplified max (which we could
imagine was a built-in we could shorten to m), and the apply over rows.
Comparing these directly (with some artistic license):
m R + R
⌈ / + /The point of this whole exercise wasn’t to rebuild the APL solution in R - it was to think more deeply about what abstractions R offers and how they compare to a language that uses (only) the atomic constructs directly.
I love that in R I can pass either individual values or a vector to sum
and it “just deals with it”
sum(4, 5, 6) # sum some "scalars"## [1] 15vals <- c(4, 5, 6)
sum(vals) # sum a vector## [1] 15This ability to hide/abstract the looping over dimensions and to work directly with
objects with more than one dimension is what qualifies R as an “array language”.
This is also (mimicking, perhaps) “rank polymorphism” which APL does have. Julia
gets around this with “broadcasting”. But, at least in R, this hides/abstracts some of what is happening, and sometimes/often, that’s a for loop.
Does every programmer need to know the gory details? Absolutely not. Might it be useful for gaining a better understanding of the language and how to work with it? I really think it is. It’s why I’m digging further and further into functional programming in general.
I do believe that the APL solution is more explicit in what it’s doing; that it doesn’t hide (much, if any) of the implementation details. I’m comfortable with the abstractions in R and will continue to write R for this reason, but if I had a need to do some array math in any other language, I now feel like APL really does have a lot to offer.
Bonus Round
I was thinking about the leetcode problem and thought that a slightly more complex version would be to return “which row has the maximum?” rather than the maximum itself.
In R, there is another useful function to achieve this
which.max(rowSums(a))## [1] 2so, have I learned enough APL to do this myself?
There’s a “Grade Down” operator (⍒) which seems equivalent to R’s
order(decreasing = TRUE) and a “First” operator (⊃) like head(n = 1)
so a solution seems to be to get the indices of the sorted (decreasing)
elements then take the first one
⊃⍒+/x
2Apparently an alternative would be to find the (first) element of the input (⍵) that
matches the maximum which would be
{⍵⍳⌈/⍵}(+/x)
2which, at least to me, isn’t as elegant.
Lastly, Kieran Healy relayed to me a small algorithm for finding ‘primes smaller than some number’ in APL which cleaned up as
((⊢~∘.×⍨)1↓⍳)(50)
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47This makes use of some combinators (e.g. the C-combinator ⍨ - possibly the
coolest glyph in the entire system),
but roughly involves filtering values not (~)
members (∈) of values produced by the outer (º) product (.) using
multiplication (×) (i.e. numbers that can be made by multiplying other
numbers) from the sequence (⍳) from 2 to some value (dropping (↓) 1;
3↓⍳8 == 4:8). With the small amount I’ve learned - mostly from watching
someone else use the language - I was able to decipher at least what the
operators were in all of that, even if I probably couldn’t come up with the
solution myself.
I’m happy to call that “readable”.
I looked around for code to generate the primes below some number in R. I couldn’t (easily) find one that worked without an explicit loop. I found a version in {sfsmisc} which compacts to
primes. <- function(n) {
## By Bill Venables <= 2001
x <- 1:n
x[1] <- 0
p <- 1
while((p <- p + 1) <= floor(sqrt(n)))
if(x[p] != 0)
x[seq(p^2, n, p)] <- 0
x[x > 0]
}
primes.(50)## [1] 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47Taking inspiration from the APL solution, though - what if we just generate all
products from the set of numbers 2:n and exclude those as “not prime” from all
the numbers up to n?
primes <- function(n) {
s <- 2:n
setdiff(s, c(outer(s, s, `*`)))
}
primes(50)## [1] 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47That… works! It’s slower and uses more memory, for sure, but that wasn’t our criteria, and isn’t relevant for a once-off evaluation. Even better - I can “read” exactly what it’s doing.
I’ve learned a lot and I’ll continue to learn more about APL because I really do think that understanding how these operators come together to build a function will be enlightening in terms of a functional approach.
I still haven’t made it to trying out BQN (almost constructed by incrementing
each letter of APL, IBM -> HAL style, but perhaps officially
“Big Questions Notation”, and sometimes
pronounced “bacon”) but it sounds like it has some newer improvements over APL
and will be worth a try.
As always, comments and discussions are welcome here or on Mastodon.
devtools::session_info()
## ─ Session info ───────────────────────────────────────────────────────────────
## setting value
## version R version 4.1.2 (2021-11-01)
## os Pop!_OS 22.04 LTS
## system x86_64, linux-gnu
## ui X11
## language (EN)
## collate en_AU.UTF-8
## ctype en_AU.UTF-8
## tz Australia/Adelaide
## date 2023-07-07
## pandoc 3.1.1 @ /usr/lib/rstudio/resources/app/bin/quarto/bin/tools/ (via rmarkdown)
##
## ─ Packages ───────────────────────────────────────────────────────────────────
## package * version date (UTC) lib source
## assertthat 0.2.1 2019-03-21 [3] CRAN (R 4.0.1)
## blogdown 1.17 2023-05-16 [1] CRAN (R 4.1.2)
## bookdown 0.29 2022-09-12 [1] CRAN (R 4.1.2)
## bslib 0.4.1 2022-11-02 [3] CRAN (R 4.2.2)
## cachem 1.0.6 2021-08-19 [3] CRAN (R 4.2.0)
## callr 3.7.3 2022-11-02 [3] CRAN (R 4.2.2)
## cli 3.4.1 2022-09-23 [3] CRAN (R 4.2.1)
## crayon 1.5.2 2022-09-29 [3] CRAN (R 4.2.1)
## DBI 1.1.3 2022-06-18 [3] CRAN (R 4.2.1)
## devtools 2.4.5 2022-10-11 [1] CRAN (R 4.1.2)
## digest 0.6.30 2022-10-18 [3] CRAN (R 4.2.1)
## dplyr 1.0.10 2022-09-01 [3] CRAN (R 4.2.1)
## ellipsis 0.3.2 2021-04-29 [3] CRAN (R 4.1.1)
## evaluate 0.18 2022-11-07 [3] CRAN (R 4.2.2)
## fansi 1.0.3 2022-03-24 [3] CRAN (R 4.2.0)
## fastmap 1.1.0 2021-01-25 [3] CRAN (R 4.2.0)
## fs 1.5.2 2021-12-08 [3] CRAN (R 4.1.2)
## generics 0.1.3 2022-07-05 [3] CRAN (R 4.2.1)
## glue 1.6.2 2022-02-24 [3] CRAN (R 4.2.0)
## htmltools 0.5.3 2022-07-18 [3] CRAN (R 4.2.1)
## htmlwidgets 1.5.4 2021-09-08 [1] CRAN (R 4.1.2)
## httpuv 1.6.6 2022-09-08 [1] CRAN (R 4.1.2)
## jquerylib 0.1.4 2021-04-26 [3] CRAN (R 4.1.2)
## jsonlite 1.8.3 2022-10-21 [3] CRAN (R 4.2.1)
## knitr 1.40 2022-08-24 [3] CRAN (R 4.2.1)
## later 1.3.0 2021-08-18 [1] CRAN (R 4.1.2)
## lifecycle 1.0.3 2022-10-07 [3] CRAN (R 4.2.1)
## magrittr 2.0.3 2022-03-30 [3] CRAN (R 4.2.0)
## memoise 2.0.1 2021-11-26 [3] CRAN (R 4.2.0)
## mime 0.12 2021-09-28 [3] CRAN (R 4.2.0)
## miniUI 0.1.1.1 2018-05-18 [1] CRAN (R 4.1.2)
## pillar 1.8.1 2022-08-19 [3] CRAN (R 4.2.1)
## pkgbuild 1.4.0 2022-11-27 [1] CRAN (R 4.1.2)
## pkgconfig 2.0.3 2019-09-22 [3] CRAN (R 4.0.1)
## pkgload 1.3.0 2022-06-27 [1] CRAN (R 4.1.2)
## prettyunits 1.1.1 2020-01-24 [3] CRAN (R 4.0.1)
## processx 3.8.0 2022-10-26 [3] CRAN (R 4.2.1)
## profvis 0.3.7 2020-11-02 [1] CRAN (R 4.1.2)
## promises 1.2.0.1 2021-02-11 [1] CRAN (R 4.1.2)
## ps 1.7.2 2022-10-26 [3] CRAN (R 4.2.2)
## purrr 1.0.1 2023-01-10 [1] CRAN (R 4.1.2)
## R6 2.5.1 2021-08-19 [3] CRAN (R 4.2.0)
## Rcpp 1.0.9 2022-07-08 [1] CRAN (R 4.1.2)
## remotes 2.4.2 2021-11-30 [1] CRAN (R 4.1.2)
## rlang 1.0.6 2022-09-24 [1] CRAN (R 4.1.2)
## rmarkdown 2.18 2022-11-09 [3] CRAN (R 4.2.2)
## rstudioapi 0.14 2022-08-22 [3] CRAN (R 4.2.1)
## sass 0.4.2 2022-07-16 [3] CRAN (R 4.2.1)
## sessioninfo 1.2.2 2021-12-06 [1] CRAN (R 4.1.2)
## shiny 1.7.2 2022-07-19 [1] CRAN (R 4.1.2)
## stringi 1.7.8 2022-07-11 [3] CRAN (R 4.2.1)
## stringr 1.5.0 2022-12-02 [1] CRAN (R 4.1.2)
## tibble 3.1.8 2022-07-22 [3] CRAN (R 4.2.2)
## tidyselect 1.2.0 2022-10-10 [3] CRAN (R 4.2.1)
## urlchecker 1.0.1 2021-11-30 [1] CRAN (R 4.1.2)
## usethis 2.1.6 2022-05-25 [1] CRAN (R 4.1.2)
## utf8 1.2.2 2021-07-24 [3] CRAN (R 4.2.0)
## vctrs 0.5.2 2023-01-23 [1] CRAN (R 4.1.2)
## xfun 0.34 2022-10-18 [3] CRAN (R 4.2.1)
## xtable 1.8-4 2019-04-21 [1] CRAN (R 4.1.2)
## yaml 2.3.6 2022-10-18 [3] CRAN (R 4.2.1)
##
## [1] /home/jono/R/x86_64-pc-linux-gnu-library/4.1
## [2] /usr/local/lib/R/site-library
## [3] /usr/lib/R/site-library
## [4] /usr/lib/R/library
##
## ──────────────────────────────────────────────────────────────────────────────