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 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]
    (cond
      (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.

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'
abc
dea

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))

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.

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
10

*/ 5 5 5
125

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
120

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)).

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:

{[x;y](x*x)+(y*y)+2*x*y}[20;4]
576

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:

{(x*x)+(y*y)+2*x*y}[20;4]
576

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.)

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))
        (list)
     (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.

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

q:

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

Lisp:

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

Clojure:

(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.