Array languages for Clojurians

A discussion in the Clojure data science Zulip led me to Slobodan Blazeski’s enlightening article Array languages for Lisp programmers in the journal of the British APL Association. He quotes Alan Perlis:

A language that doesn’t affect the way you think about programming is not worth knowing.

As a lisp, Clojure of course qualifies as one such mind-altering substance. (It arguably qualifies again on the basis of its focus on immutability.) But Blazeski’s article points out that array-based languages such as J, its predecessor APL ("A Programming Language"), and the proprietary q are equally mind-expanding. Let’s see what was – and remains – so compelling about the array programming approach to problems, and compare it to Clojure’s approach.

Array functions

Array languages make it both simple and easy to work on whole containers the same way as you work on scalars. Let’s look at J first. (Our array programming examples will be one-liners, with the result on the following lines.) We’ll start by adding the scalar 2 to an array of 2, 3, and 4:

2 + 2 3 4
4 5 6

The same + operator works on multiple arrays element-wise:

2 3 4 + 1 2 3
3 5 7

One operator to do both is pretty handy. We can of course replicate each with out-of-the-box Clojure:

(map (partial + 2) [2 3 4]) ; => (4 5 6)
(map + [2 3 4] [1 2 3])     ; => (3 5 7)

But Clojure’s arithmetic functions lack the number/array polymorphism of J’s +. Let’s use multimethods to achieve precisely that property:

(defmulti j+
  (fn [& args]
      (number? (first args))     :number
      (sequential? (first args)) :sequential
      :else                      (class (first args)))))

(defmethod j+ :number
  [n xs]
  (map (partial + n) xs))

(defmethod j+ :sequential
  [ys xs]
  (map + xs ys))

;; By the way, if you're hacking on this at your home REPL,
;; I recommend keeping this handy:
#_ (ns-unmap *ns* 'j+)

Now we have one function that can add scalars to vectors or vectors to vectors:

(j+ 2 [2 3 4])       ; => (4 5 6)
(j+ [2 3 4] [1 2 3]) ; => (3 5 7)

I may not need this in my day-to-day, but for some kinds of mathematical programming it is just what you want. Clojurians in that situation often reach for libraries like core.matrix, which takes a similar approach.

Array-making tools

To work fluently with multidimensional arrays, one needs a way to create them fluidly. J’s integer-sequence-creating operator i. creates pre-populated arrays of arbitrary dimensions:

i. 2 3
0 1 2
3 4 5

(And people say lisp is terse.) This operator produces an array of the given shape – 2 rows, 3 columns – and populates it with the incrementing integers from 0. Clojure’s sequence functions make this simple to implement:

(defn i-dot [n m]
  (take n (partition m (range))))

(i-dot 2 3)
;;=> ((0 1 2) (3 4 5))

We’re also going to need something to turn a sequence of values into an array (matrix) of some desired shape. For this J has the $ operator:

2 3 $ 'abcde'

Here’s a fairly slapdash Clojure replication, which we might conceive at the REPL:

(take 2 (partition 3 (cycle "abcde")))
; => ((\a \b \c) (\d \e \a))

That looks familiar. Because i. is so similar to $, we end up using the same Clojure functions to implement both:

(defn shape [n m coll]
  (take n (partition m (cycle coll))))

(shape 2 3 (vec "abcde")) ; => ((\a \b \c) (\d \e \a))

;; i-dot seems superfluous for many users when we can just write
(shape 5 5 (range))
;; => ((0 1 2 3 4) 
;;     (5 6 7 8 9) 
;;     (10 11 12 13 14) 
;;     (15 16 17 18 19) 
;;     (20 21 22 23 24))

One might legitimately say that while the Clojure version is both readable and concise, it isn’t optimized for performance the way it could be in an array language. This is a fair point: specialized languages have more leeway to focus their performance optimization efforts. Still, I found it interesting that one array language, IDL, ran into the same performance concern that Clojure did:

[W]hen you have very nested operations with vectors, during each step, IDL might create (possibly large) temporary storage for intermediate results. For really big data-sets one would have to play tricks to make it allocate a large enough contigious block of memory, or do special declarations, to tell the compiler/evaluator that what it was calculating was just temporary, and will be discarded soon. –from a mailing list comment on the original article

This of course is the drawback Rich Hickey encountered with Clojure’s lazy sequences. That doesn’t make lazy sequences bad. They are merely unsuited to one particular set of requirements, suggesting the need for a different tool in that situation. In Clojure’s case this gave rise to transducers, which avoid creating intermediate or cached values by creating a single compound transformation to use in one eager pass over its input. (See What are good use cases for transducers?) To me, this demonstrates Clojure’s power as a general-purpose language, able to deal with varying requirements without switching languages just for a particular feature.

Array reducers

The creator of APL and co-creator of J, Kenneth E. Iverson, wrote:

Because my formal education was in mathematics, the fundamental notions in APL have been drawn largely from mathematics.

This suggests that the one- and two-character primitives found in Iverson’s languages can find their ancestry in mathematical symbols. We can confirm this by tracing J’s i. back to its predecessor in APL: ⍳ – the actual lowercase Greek letter iota, standing here for "integers". For instance, one would enter the expression ⍳10 to generate the first 10 integers.

An APL keyboard layout

An APL keyboard layout

This meant that to program APL required a specialized keyboard, an experience which you can replicate in the browser with Try APL. To the modern programmer a bespoke piece of input hardware for a programming language may seem bizarre. But Clojurians should remember that their own Lisp lineage traces back to an entire computer architecture (the Lisp Machine), including a series of keyboards, designed around their programming language.

The [:a {:href ""} ("Space Cadet keyboard")], for Lisp machines ca. 1980

The Space Cadet keyboard, for Lisp machines ca. 1980

With such a close relationship to mathematical notation, it occurs to ask how APL-derived languages represent mathematical functions like the sum () or product () of a sequence, which have clear use in array programming. J achieves this with adverbs, which are cleverly designed with more power than an individual symbol for each operation:

An adverb applies to a verb to produce a related verb; thus +\ is the verb “partial sums.” –K.E. Iverson, A Personal View of APL

That is, J has an entire system of modifying functions to create new ones. For one, element-wise arithmetic operators like the + we replicated earlier transform into array-consuming versions when combined with /:

+/ 1 2 3 4

*/ 5 5 5

As lispers, we should recognize the power of this approach right away. We solve the same problem with a similarly generalizable solution, higher order functions, which let us reduce over sequential collections any way we like:

(reduce + [1 2 3 4]) ; => 10

;; reduce & apply are interchangeable in this context,
;; because Clojure's arithmetic functions are variadic:
(apply * [5 5 5]) ; => 125

Applying J’s adverbed +/ to multidimensional arrays causes them to work column-wise. For this next example, remember that i. 2 3 returns the equivalent of [[0 1 2] [3 4 5]].

+/ i. 2 3
3 5 7

Once again we can compute this with out-of-the-box Clojure, because our map is variadic on collections:

(apply map + (shape 2 3)) ; => (3 5 7)

I visualize this apply map idiom as "rotating" the sequences by 90 degrees before feeding them to the sequence function.

We could also use the j+ we defined above, giving us a closer translation:

(apply j+ (shape 2 3)) ; => (3 5 7)

Adverbs let J solve something like a factorial simply. Consider this J expression, which I find easiest to read right-to-left as "create an array 5 elements long of incrementing integers starting at 0, increment each, and then compute the product of that sequence":

*/ 1+ i. 5

We can robotically transliterate that to Clojure, piece by piece:

(->> (range 5)            ; incrementing integers [0, 4]
     (map (partial + 1))  ; add one to each (`inc` is more idiomatic)
     (reduce *))          ; compute the product of the sequence

;; which suggests that `j+` could be of use:
(reduce * (j+ 1 (range 5)))

But personally I would probably use (reduce * (range 1 6)).

Omitting parameters

Another cool feature in q that caught Blazeski’s eye was the ability to omit arguments to a function, like so:

{x+y+z}⇔{[x;y;z] x+y+z}

To be honest, this snippet from Blazeski’s article confused me deeply. The example is a little under-specified; the q docs on this topic can help, but we need to take a brief detour.

Here’s a "signed lambda" function definition-and-invocation in q:


In Clojure we would write this as

((fn [x y] (+ (* x x) (* y y) (* 2 x y))) 20 4)
=> 576

That is, we define an anonymous function that sums the squares and double of its parameters x and y, and call it with the arguments 20 and 4. The q docs point out that

Functions with 3 or fewer arguments may omit the signature and instead use default argument names x, y and z.

This allows us to rewrite the above more concisely as an "unsigned lambda", or what Clojurians dub an anonymous function:


It should now be clear that Clojure’s anonymous function syntax provides a more general version of this syntactic sugar:

(#(+ (* % %) (* %2 %2) (* 2 % %2)) 20 4)
=> 576

That is, instead of providing implied arguments up to—but only!—x, y, and z, Clojure provides % and %n. It’s interesting to note the trade-offs of these two approaches: %n is longer, but allows greater variability; xyz may be more readable, but are more likely to conflict with existing names. (I tend to stick to % and avoid %2, %3, and so on unless it’s something obvious like the (compare %2 %1) idiom.)

Blazeski ported this omitted-arguments feature to Common Lisp using a macro. Clojure already has anonymous function syntax baked in, but if it didn’t, macros and reader literals would give us access to it anyway. This may be useful to remember if you come across a syntactic feature in another language that Clojure doesn’t have. The lesson here is not that Clojure was ahead of the curve (though it was) but that a lisp with macros is endlessly extensible. As Blazeski puts it:

It seems it’s always the same old story. As soon as Lisp integrates the needed utility or invests into a domain-specific language, the advantage of the other language is lost. The big ball of mud is like a warlock, able to steal opponents’ powers while still staying the same.

Clojure avoided the Lisp language family’s "big ball of mud" reputation by building on fresh foundations with a few syntactic extensions and clear, consistent, effective abstractions. But the point stands: it is the superhero that takes on new powers with a touch.

A puzzle

The programming world seems to have mostly moved on from arguing language effectiveness on the code golf course. This is truly a blessing, but we’ll make an exception on pedagogical grounds.

The problem is from an undated comp.lang.lisp post extolling the virtues of q’s predecessor K:

We have a list of elements, some are duplicates. We’re trying to figure out how to find the duplicate elements and increase a counter value by 1 for each instance of the element found. The list consists of lists with two elements, the first being the incremental counter, the second being the string sought. Example:
((1 "one") (1 "two") (1 "three") (1 "one") (1 "four") (1 "two"))
The result should be:
((2 "one") (2 "two") (1 "three") (1 "four"))

The array programming solution is impressively concise, and quite readable. v is the input value:

count:flip(count each group v[;1];unique v[;1])

I won’t repeat the Common Lisp solutions here; they’re fine for what they are. But the problem is ill-formed. One could solve it as-is, with v as the input value again:

(reduce (fn [acc [s xs]]
          (cons (list (count xs) s) acc))
     (group-by second v))
;; ((1 "four") (1 "three") (2 "two") (2 "one"))

But we should look a little askance at such an answer, as programmers but especially as Clojurians. It works, but what problem is it really solving? Sifting out the true problem from someone’s stated requirements is a vital skill. We should ignore the crufty half-solution implied in the problem statement and solve the true, hidden task:

(frequencies ["one" "two" "three" "one" "four" "two"])
;; => {"one" 2, "two" 2, "three" 1, "four" 1}

Delightful simplicity from the right data structure and a well-designed standard library.

Parsing identifiers

We’ve already explored most of the benefits of array languages: concision, functions which change according to input or adverbs, and "the opportunities opened by thinking at the higher level of container abstraction." We’ll finish with one more translation exercise:

This piece of [Haskell] code goes through a parse tree of Haskell source code, locates every reference to an identifier that ends with Widget, puts it on a list, and removes duplicates so every identifier is represented in the list only once.

In Haskell:

extractWidgets :: (Data a) => a -> [String]
extractWidgets = nub . map (\(HsIdent a)->a) . listify isWidget
  where isWidget (HsIdent actionName)
      | "Widget" `isSuffixOf` actionName = True
    isWidget _ = False


a:distinct raze over x
a where a like "*Widget"


(defun widgets (l)
  (unique (keep (f like x "*Widget") (flatten l))))


(defn widgets [tree]
  (distinct (filter #(string/ends-with? % "Widget")
                    (flatten tree))))

Take it for a test drive:

(widgets '(abcWidget foo (abcWidget bar abcWidget defWidget)
                     (baz abcWidget defWidget)
                     (qrsWidget tuvWidget)
                     (qrsWidget xyzWidget)))
;; => (abcWidget defWidget qrsWidget tuvWidget xyzWidget)

It’s nice to travel: try the food, learn a few phrases, visit their monuments. It shows us how strongly history molds a culture, and how differently lives can be lived. We visit other programming language communities to broaden our horizons and remind ourselves that other sometimes folks have different tools for different needs, and sometimes they have the same needs and the same tools, only under a different set of names.

Dave Liepmann, 04 May 2020