Beyond Functional Programming: Manipulate Functions with the J Language
by Adam Tornhill, February 2017
The Pragmatic Programmer recommends that we learn at least one new language every year. To be effective, the languages we learn should differ sufficiently from those we already master and ideally introduce us to a new paradigm too. Learning a different programming language affects the way we view code. A new paradigm may even alter our problem solving abilities by reshaping the way we think. The J programming language offers both of these qualities.
In this article we'll get a brief introduction to the J programming language. The goal is to wet your appetite for an exciting programming paradigm rather than providing an in-depth introduction. As we move along we'll learn just enough J to explore a fascinating corner of the language that lets us manipulate functions as data. You'll see how these techniques differ from traditional functional programming, why manipulating functions is interesting and how it lets you solve real problems with a minimum of code.
The Brevity of Array Languages
The J language stems from the family of array languages. Array languages sit on an interesting, albeit relatively unknown, branch in the family tree of programming languages. APL, the first array language, presents a radical departure from how we typically think about computer programming. Even though modern languages let us express our programs on a fairly high level we're still basically moving and processing data element by element. This level of abstraction is a constant source of irregularity and special cases in code. APL - and more recent array languages like J - give us as an alternative and interesting contrast to the von Neumann languages of today.
So what makes array languages so different? First of all they're extremely compact. Let me show you how compact by exploring a piece of APL code: x[⍋x←6?40]. Alright. What was that? A burst of line noise that made its way past the editors into the article you're reading? No, no. What we just saw was a _complete_ APL program. This brief program generates six lottery numbers in the range 1 to 40, no duplicates, and delivers them sorted in ascending order.
The first thing that strikes us in this APL example is the characterset. APL uses a special set of symbols in its syntax. Today we can play around with virtual keyboards (see Try APL), but in the 1960's, when APL was first implemented, the language required special hardware. It's probably fair to assume that requiring a curious programmer to buy a special keyboard and graphics card just to try a new programming language could be something of a deal breaker in terms of language adoption. That said, I've become a fan of the APL syntax. I even think that special symbols and charactersets are underused in today's programming languages. Symbols help us build compact mental models and make it easier to spot patterns and idioms in our code. It's a learning curve for sure, but a flat one.
When I started to talk about APL in some of my presentations, like Code That Fits Your Brain, people often remark that APL looks opaque and cryptic. If you agree with that statement you'd be happy to learn that the J language abandoned APL's symbols for a pure ASCII syntax. So let's translate our APL example above to J and see if we can make sense of it: /:~>:6?40. Much simpler, right? It's 100% ASCII after all.
As evident from this example, J is also a compact language. The example also shows that a different representation, like ASCII, doesn't necessarily improve our understanding in the strange world of array languages. That's because this is not a matter of syntax; array languages present a radically different way to code and solve problems. Let's explore how.
Meet True Simplicity in the J Language
What fascinates me the most about our APL and J examples is not so much what's there, but rather what's absent. Have a look at the code once again. There is no conditional logic. Even more interesting, there are no explicit loops even though the code models an inherently iterative problem.
The reason array languages pull this off is because arrays are the fundamental datatype. That means function in J operate on collections of things rather than individual values. The implication is that as soon as we start to think about data as collections rather than individual elements, a whole set of potential coding issues just go away. Suddenly there's no difference if we have 1.000, a single value or none; Our J code will look exactly the same. That means we can get rid of many special cases that we need to deal with in other languages. For example, think of the disastrous null pointers that plague most mainstream languages. In J you'd just model the absence of something as an empty array; The rest of your code stays the same. It's a simple yet powerful abstraction that lets you focus on the problem you're trying to solve without littering your code with special cases.
Alright, let's move ahead and get started with some J. I'd suggest that you download the latest version of the J language and environment to follow along as we walk though some examples.
Our first example is fairly trivial:
1 + 1 2
In the example above we add two numbers and J, since it's an interactive and interpreted language, prints the result immediately. As you see, the code you write yourself (like 1 + 1) is always indented in the J prompt. Results and errors from the J runtime are left aligned.
Next we'll do something more interesting. Let's repeat our addition, but this time with two arrays:
1 2 3 + 4 5 6 5 7 9
Remember when I said that arrays are fundamental data types in J? That's the array capabilities I've been talking about. We could repeat this operation with data of higher dimensions stored in multi-dimensional arrays. Our code would look the same and the J interpreter would handle the looping for us. But J can do more. Let's see how we can calculate the sum of the numbers in an array:
+/ 1 2 3 4 5 15
We've already met +, but what's about that slash character we put after it? And how does J manage to sum our array without any explicit loop? I'll answer it in a minute, but first we need to learn a bit of J jargon. J doesn't really have functions. Instead the language borrows its terminology from natural languages. + is a verb in J speech. And / is an adverb that, just as in natural languages, modifies its verb. In this case, the slash inserts +, the verb it refers to, between each number in our array. That is, +/ has the same effect as writing 1 + 2 + 3 + 4 + 5. If you're into functional programming, you can think of an adverb as a higher-order function; It takes a function as input and returns a new function that modifies the behavior of the original function.
The simplicity of J goes deeper than avoiding explicit loops. J's verbs have a remarkable simplicity in their definitions. It turns out that a verb/function in J always takes either one or two arguments and you usually don't even name those arguments. That's it. No more code review battles over the one true way to name an index argument. No need for syntactic sugar like keywords and variable arguments. Just one or two implicit arguments. Follow along and I'll explain how we program with those constraints by introducing a tacit style of programming.
The J language supports a tacit programming style (also called point-free style). A tacit style means that our functions don't identify the arguments they operate upon. We can exemplify a tacit function by specifying a verb of our own:
sum =: +/
The code above introduces a user defined verb names sum. As you see, there's not mention of any variable or function argument; The argument is implicit. We can now use sum like you'd expect:
sum 1 2 3 4 5 15
Yeah - works just like our previous example with adverbs when we typed +/ 1 2 3 4 5. Our sum verb is called a monadic definition. The term is unrelated to the kind of monads you'd find in Haskell land. Instead monadic means that it's a function that takes exactly one argument. That argument is always given to the right of the verb as you see in the invocation of sum in the example above.
The other category of verbs in J are called dyadic. A dyadic takes exactly two arguments, one to its left and one to its right. A simple example is the addition 1 + 1 that we met earlier.
Learn to Box
Limiting function to only one or two arguments sounds like quite a constraint. The reason it works so well in J is because, remember, our arguments are always arrays and these arrays can be of any dimension. Learning to re-frame our understanding of a problem to be able to express it as an operation on arrays is part of the challenge when you start out with J. However, that learning is likely to translate to other languages too. After all, taking some input, doing something to it, and generating some output is pretty much all a computer program does. J helps us get better at expressing that universal pattern.
But of course, sometimes we do run into limitations in J too. For example, arrays in J have to contain the same data type. Let's say you want to pass an array with an integer and a string into one of your verbs. In that case you need a box. A box in J is a data type that supports heterogeneous values. Here's how we work with boxes:
b =: (< 1) , (< 'hello') b ┌─┬─────┐ │1│hello│ └─┴─────┘ # b 2
In the first line we use the monadic verb < to put the value 1 into a box and the string hello into another box. We then use the dyadic verb , (called Append in J) to create an array out of our two boxes. The result of Append is assigned to our variable b. You also see that J has a nice printed representation of our boxed values. Finally we meet the monadic verb # (called Tally) that counts the number of items in our boxed array. Just as we'd expect, Tally reports two items.
Armed with our basic J knowledge we're ready to get some serious business going by starting to manipulate verbs just as if they were data too.
Write functions that manipulate functions
The J language has several functional elements although it's not a strict functional language. However, it does take the function abstraction a step further.
The basic idea in functional programming is that functions are first-class citizens. This promise looks rather shallow once we see its realization in different languages. Sure, we can pass functions as arguments, return functions from other functions and even compose functions. But there are few languages that allow us to _really_ manipulate functions in the same way we massage data. For example, what would it mean to subtract one function from another? Or to calculate the derivate of a function? I'd say both of these examples make sense from a mathematical perspective, yet Clojure doesn't know how to do it and neither does Scala nor F#. This is where J takes off.
Again we'll start simple. The verb Double +: does what it says and doubles its input values:
+: 2 4 +: 3 6
We talked about J's terminology earlier and so far we've met verbs and adverbs. J also has conjunctions. In natural language grammar, a conjunction is something that connects different words and phrases. J's conjunctions have a similar effect and we'll see that as we explore the Power Conjunction ^:.
The power conjunction applies a given verb n times. Here's how it works when applied to our Double verb:
(+: ^: 2) 2 8 (+: ^: 2) 3 12
The examples above instruct the power conjunction to apply its verb, Double (+:), twice. We could of course also write +: ^: 3 and have the Double verb applied three times. Let's capture that in a user defined verb, tacit style:
threeTimes =: +: ^: 3 threeTimes 2 16 threeTimes 1 2 3 4 5 8 16 24 32 40
As you see in the example above, our user defined verb threeTimes automatically generalizes to whole arrays. Instead of spending precious code on loops or iterations, we just let the language do the job for us. That leaves our code free to focus on the stuff that actually does something, the core of the problem we're trying to solve.
There's a particular beauty to conjunctions. But J's way of manipulating functions go deeper. We can let the language inverse the meaning of a verb. As we'll see soon, inversing verbs is more than just a neat party trick; Once we have the ability of automatically inversing a function we are able to abstract several common programming tasks using succinct idiomatic expressions.
Inverse Functions with the Power Conjunction
As I decided to learn the J language I looked for some small yet realistic problems to work on. I decided to start with the Dyalog APL challenge, an annual APL programming competition, but doing it in J instead. The 2014 competition had a simple and interesting problem labelled
How tweet it is. The task here is to shorten a message, yet retain most of its readability, by removing interior vowels from words. For example, the phrase
APL is REALLY cool would be shortened to
APL is RLLY cl. Let's give it a try.
The first step in this task is to tokenize the string. That's straightforward with J's Words verb, written ;::
b =: ;: 'APL is really cool' b ┌───┬──┬──────┬────┐ │APL│is│really│cool│ └───┴──┴──────┴────┘
The ;: verb splits our string on its separators. It also partitions the resulting sub-string into a box since the tokens have different lengths. We let the variable b refer to our boxed array so that we can play around with it in the J interpreter and iterate towards our solution.
The next step towards a tweetable sentence is to remove the interior vowels. This is fairly straightforward, but the details would distract us from our main topic of function inverses as we would need to learn more J verbs. So instead we'll pretend that we already have a verb `trimWord` that does the job for us (head over to my GitHub repository if you'd like to look at its implementation).
To use our trimWord verb we need to take the words out of the box, apply trimWord, and put the results back into a boxed array. We've already seen how the < verb lets us box a value. J provides a corresponding unbox operation with the > verb. Semantically, unbox (>) is the inverse of box (<). As a programmer, we immediately see that. More interesting, the J language knows about it.
J has a unique language feature that lets you inverse the meaning of a verb. It's a mechanism that works on most built-in verbs and, fascinatingly, also on most of our own user defined verbs. And in the cases where J isn't able to deduce an inverse automatically you can teach J about it by assigning an inverse yourself.
We already learned that the Power Conjunction ^: lets us control how many times a verb is applied. So what happens if we apply the power conjunction -1 times? That's right - we get an inverse that undoes the effect of applying the particular verb. Let's play around with this idea in the J interpreter to see how it may solve our tweetable problem. I've introduced comments (NB. in J) to explain the steps. Please note that negative numbers are entered with an underscore, like _1, in the J interpreter:
addTwo =: 2 & + NB. & binds one argument of a verb (think partial application) addTwo 1 2 3 4 5 3 4 5 6 7 undoAddTwo =: addTwo ^: _1 NB. Create the inverse of addTwo. That is, a verb that undos the effect of addTwo undoAddTwo 3 4 5 6 7 1 2 3 4 5 b =: < 1 NB. box the value 1 b NB. type the variable name to see its content ┌─┐ │1│ └─┘ unbox =: < ^: _1 NB. undo the effect of box by taking its inverse unbox b 1
The example above shows a mathematical inverse like plus and minus. We also see a logical relationship between box and unbox (those kind of non-mathematical relationships are the reason J prefers the term obverse over inverse).
So far I hope you find the inverse trick just as cool as I do. But how does it apply to our tweetable problem? Well, let's recap the pattern we want to express: first we'll unbox our words, then we let J apply trimWord to each of the words before we box the results. As we'll soon see, the general form of this pattern is common to many familiar programming problems. That's why J provides an idiomatic expression for it.
In J speech, this pattern is called Under (&.). Under works on two verbs that form a pipeline: the first verb is applied, then the second verb is applied to that result before the inverse of the first verb is applied to form the final result. Let's see it in action:
b =: ;: 'APL is really cool' b ┌───┬──┬──────┬────┐ │APL│is│really│cool│ └───┴──┴──────┴────┘ (trimWord&.>) b ┌───┬──┬────┬──┐ │APL│is│rlly│cl│ └───┴──┴────┴──┘
And there we are - we have a tweetable sentence. However, there's a bit more work before we're done done. That's good because it gives us an opportunity to uncover some more J ideas.
Turn the Dial to 11: Under under an Under
Our solution so far works as long as we have our words in an array of boxes. But our starting point is a raw string, not a box. How do we glue that together? Well, since we now have a solid grip on function inverses with Under we'll use the same idiom. We tokenize the string with ;:, trim the words in a box using our Under pipeline trimWord&.> before we put the trimmed tokens back into a string with the inverse to ;:. Here are those steps in J code. Note how J automatically deduces the inverse to the tokenize (;:) verb:
tweetable =: trimWord&.> &.;: tweetable 'APL is really cool' APL is rlly cl
As you might note in our solution above, J executes expressions from right to left. Sure, as you dive deeper into J you'll see that there are some exceptions. Or, to be more correct, J has a certain set of execution patterns that help your express more functionality with less code (these patterns are called forks and hooks, which we won't cover this time).
Function Inverses in the Real World
Function inverses are the kind of construct that changes how we view code. Once you've learned about function inverses you'll see use cases everywhere. It turns out to be a general pattern, no matter what programming language we use. For example, consider pairs of malloc/free, acquire/release, and open/close. All of them follow the pattern captured in the Under idiom: We do something to create a context, apply some functions in that context, and then leave our context by undoing the initial effects with a logical inverse like free, close, etc.
Most modern languages provide some mechanism to capture these steps - in C++ we use the RAII idiom, in Lisp we express it with macros, and in Java, well, we just wait a few years for an extension of the core language - but no approach is as succinct and powerful as J's.
Exploring the J language is likely to change how you view programming and make you think different about both functions and data. The Under idiom introduced in this article is just one example. J is full of mind melting ideas. For instance, just as we can inverse a function we can also derivate it or provide a list of functions as a declarative alternative to traditional conditional logic. I hope to explore those paths in future articles.
How hard is J to learn?
If this article is your first exposure to J, you probably find the language tricky at best and pure line noise at worst. You're in good company; The Internets are full of attempts at learning to decipher array languages. My favourite is a blog post by Ron Jeffries that starts with
J. This is HARD. However...No, really. This is hard. I owe a lot to Ron since it was his blog post that turned my attention to J. Somehow I thought I needed that challenge (I had a good day). I also found J hard to learn and I still struggle with problems I know how to solve in languages I'm more comfortable with.
However, if J makes it hard to write code, perhaps that's a good thing; We don't need more code. We need less code but with higher quality. The best way to achieve that is by re-framing and simplifying the problems we try to solve. J helps us with that.
That said I don't think J is hard per-se. J is only hard to learn if you already know how to program. In that case there are lots of habits to unlearn. We also need to break our automated interpretation of common programming symbols since they carry a radically different meaning in J. For example, a seasoned programmer expects curly braces and parentheses to be balanced. That's not the case in J where those symbols form different verbs. Breaking those code reading habits take time, yet it's kind of the easy part. The hard part is to change how we approach problem solving in code.
Finally, if you struggle with the J language you'll always find comfort in Dijkstra's words about its predecessor:
APL is a mistake, carried through to perfection. Now we know that Dijkstra was slightly wrong; J clearly carried both that mistake and its perfection further.