Intro

J is an array programming language of APL family 1. I discovered it through a talk from StrangeLoop 2. Being fan of learning programming languages in general it immediately struck me as something totally different, something I have not seen before.

While this project is not a new effort and it has sophisticated documentation, I and many other people find it sometimes hard to approach. In this book I will break down solutions for Advent of Code 3 puzzles in J and explain some common primitives and their semantics.

This book is by no means a sophisticated guide to a language but hopefully it is useful enough to get more people started and make language more approachable.

Basics

Unlike many common languages J is evaluated right to left with no operator precedence. This is a common warning for newcomer, * does not have priority over + in J.

Expression 5 * 3 + 1 evaluates to 20, not 16.

Functions take at most two arguments and they are passed in infix form. There are reserved names x and y for function's left and right argument respectively.

   plus =: {{ x + y }}

   3 plus 5
8

Here we can define a function plus and call it. J is a dynamically typed language, so there are no separate type definitions. Type will be inferred.

J is an array programming language, which means its primitives work on arrays. To define an array J simply uses space as a separator and no additional syntax constructs.

   3 plus 0 2 3 4
3 5 6 7

Here we call our plus function again with its right argument array and this would evaluate to another array. There is not need to additional looping / calling collection functions, + that we use in our plus definition is rank-polymorphic. Like many other primitives provided.

There are quite a few primitives baked into the language that are defined as special characters, normally used for other purposes. For example a curly brace { can be used to fetch elements from the array by their index.

   1 { 3 5 6 7
5

Many more primitives can be found at the language wiki vocabulary 1. This can be overwhelming so we will explain their usage 1-by-1 as we solve puzzles from AoC.

Day 6: Tuning Trouble

In this book we won't be going in order of puzzles suggested by AoC, rather in order of increasing complexity (in terms of number of primitives used to solve the task).

Here we start with day 6, where we are given a string and we need to find first occurrence of unique 4 characters and return its index.

Introduction

Our approach to this problem on a high level will be following: we want to split our input into windows of 4 characters, those windows will be sliding, characters would overlap, since we want to find a first occurrence. Then we want to check whether characters in the input are unique and if so we would flag them with some marker. Finally we want to find first occurrence of that marker in transformed input - this will be our answer.

To get started we can take our input and save it in some file 2020/input6 which we then can read with J-builtin fread. I will be using one of example inputs to illustrate how J operations work.

   input =: fread '2022/input6'
   input
bvwbjplbgvbhsrlpgdmjqwftvncz

Scan & Sliding Windows

Now in order to scan the input string there's a scan operator \, but we cannot just \ input since scan operator is a function that is expecting another function (HOF). So we need to pass it some other function first. It takes its argument on the left.

For those familiar with functional programming there's an identity function in J which is defined as ]. Actually there are two, [ is also an identity. For our use-case it wouldn't matter which one of those to use, but I will cover differences later.

For those who don't - identity is just a function that passes its arguments through without any modification, so our scan would just output those windows back to us.

If we try calling our newly composed scan function on our input we would see something like following.

   ]\ 'bvwbjplbgvbhsrlpgdmjqwftvncz'
b
bv
bvw
bvwb
...

As we see this produces prefixes of our input in consecutive manner, this is not quite what we need. However this function we created ]\ can take an extra argument on the left. This argument defines length of the window in output.

   4 ]\ 'bvwbjplbgvbhsrlpgdmjqwftvncz'
bvwb
vwbj
wbjp
...

That's it! We've got our sliding windows.

Unique characters

Now we need to somehow check if characters are unique in the window, to do so we can use nub ~.. This primitive takes input and produces set of its unique members.

   ~. 'bvwb'
bvw

So if we call it on a string that is in the first window, then we can see that its output has last b removed. This is handy but this would not quite cut it for us just yet, we need to compare output of nub ~. with its original argument.

J has a regular comparison operator = but this operator will compare strings symbol by symbol and will return another array as an output, so we can't quite use it here. Trying to compare strings of unmatching length will produce a length error.

   'bvwb' = 'bvw'
|length error
|   'bvwb'    ='bvw'

Fortunately there is another comparison operator that is called match -: and it is used mainly for 'tolerant' comparison as described in docs. Match would return us a single value, 1 in case of match and 0 otherwise and this is exactly the type of flag that we need.

   'bvwb' -: 'bvw'
0

Let's define our function that will check uniqueness as is_unique

   is_unique =: {{ y -: ~. y }}

Now that might look uncomfortable at first, let's walk it step-by-step. y is referring to functions right argument so we can mentally substitute it with original string bvwb. We use y few times in this function similar how you can reference variable multiple times in any other programming language.

If we recall previous chapter we know that J is evaluating right to left so inside of our function 'body' first thing that gets evaluated is ~. y, meaning finding unique subset of our string. Once that is done all is left 'tolerant' comparison with match -: that would return us 1 or 0.

If we try calling our new function on few inputs we can see that it is working as expected.

   is_unique 'bvwb'
0
   is_unique 'abcd'
1

Putting it all together

We have defined a function that tests if string consists of unique set of characters and we also covered how to scan our input in fixed size windows. Previously we used identity ] to compose our scan operator ]\, but we can actually just substitute our identity for is_unique to array of flag markers as an output.

   4 is_unique\ 'bvwbjplbgvbhsrlpgdmjqwftvncz'
0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

This returns us array of flags, and all that is left is to find a first occurrence of 1 in this array. To do this we can use index of i., which returns first occurrence of an element in array. i. is a counter-intuitive, since it takes array to search in on the left and elements to look for on the right so we need an extra pair of braces to make sure ordering (remember J evaluates right-to-left)

   (4 is_unique\ 'bvwbjplbgvbhsrlpgdmjqwftvncz') i. 1
1

With this we have everything to put together solution for the first part of the problem, right? Well, not quite. As we use sliding windows, indexes we output are of those windows. So instead of getting 5 for first example input in description we would get 1 and we need to add window length to it.

Fortunately as J evaluates right-to-left we can just add 4 + to our function body to get correct result.

   solve_part1 =: {{ 4 + (4 is_unique\ y) i. 1 }}

As we can see, we have some duplication here, we can actually extract 4 as another function argument (it would be left argument with reserved name x).

   solve =: {{ x + (x is_unique\ y) i.1 }}

Here is a complete solution.

   input =: fread '2022/input6'
   is_unique =: {{ y -: ~. y }}
   solve =: {{ x + (x is_unique\ y) i.1 }}
   part1 =: 4 solve input
   part2 =: 14 solve input

Tacit Programming

One of distinct features of J is its brevity and to facilitate it tacit or point-free programming is often used 1. In short it is a style of programming where arguments are omitted. In J this is particularly easy to achieve since each function takes up to two argument, so it is easy to imagine them on both sides.

If we go back to our plus example, previously we defined it via what is called direct definition (using {{ }}) and referred to our arguments as x and y for left and right argument respectively.

   plus =: {{ x + y }}

However this can be reduced to tacit form, leveraging the fact that x is always coming from the left and y - from the right.

   plus =: +

This definition now becomes trivial so our plus function is just a plus + primitive which we can inline.

Being able to do this for a single primitive is not very useful on its own, so let's look at the definition of a function that is finding average of an array.

   mean =: {{ (+/ y) % (# y) }}

We have some new primitives here, let's go over them one-by-one.

/ is another function that is taking a function on its left, similar to \, this primitive is called reduce or fold, when called on y it will compute sum of ys elements.
# is just a simple function that is computing length of y, it is called tally.
% is division sign, since both slashes forward and backward are already used for other purposes, J reserves % for division.

Given this, if we read the original mean definition we should be able to interpret it as something like compute sum of the argument and then divide it by its length, the very definition of average.

However in J you can write this in its tacit form, omitting the argument to get +/ % #, let's breakdown how it works.

Fork

Tacit definition of mean +/ % # is combinator called fork. Combinator is simply a function that is taking another function and producing yet another one. In our previous example, both scan \ and reduce / are such combinator functions. Unlike scan and reduce, fork does not have any special symbol assigned to it, instead whenever J interpreter sees 3 functions side-by-side, it will evaluate it in special order.

   (f h g) input

Is equivalent to:

   (f input) h (g input)

This is exactly what mean is doing, in its case f is +/ and g is #. It computes both sum of elements and length of the array and then divides result of first by result of second producing mean value.

Let's break down evaluation order below.

   (+/ % #) 1 2 3

Here we apply tacit definition of mean to array 1 2 3. Again J does not have any special syntax to define array literal, it is constructed just by stacking numbers next to one another. Having braces around tacit form of mean is important, without braces J will interpret it as consecutive application of primitives on our array, first tally # then division % (which when called with one argument will return reciprocal or 1 % y) and finally computing sum on the result (which is single item so it just returns result back).

Applying fork evaluation rules we get.

   (+/ 1 2 3) % (# 1 2 3)

Which evaluates to.

   6 % 3

Giving us final result of 2.

Like any other function this tacit form can be given a name and used with that name.

   mean =: +/ % #
   mean 1 2 3
6

When it is assigned to a name, outer braces are not necessary anymore.

Why bother?

We have seen how with clever interpretation we can define our mean as a set of seemingly random symbols +/ % #. And a natural question arises, why should you ever do this?

What is wrong with the following direct definition?

   mean =: {{ (+/ y) % (# y) }}

There is no definitive answer, some people writing J enjoy tacit style because of brevity, there is an argument that it improves performance of the interpreter, because tacit definitions are parsed first then executed. Number of performance optimizations for tacit forms are listed on J's wiki.

Surprisingly but for me personally tacit forms make it easier to work with code, move things around, reorganize, refactor. I guess it enables it due to the fact that tacit definitions needs to be read in specific order like formulas and have certain rules can be applied when manipulating them almost mechanically like algebraic constructs.

Left & right identity

We touched briefly that there are two identity functions in J. Left [ and right ] identity. And they performed identically for us when solving day 6 problem using sliding windows.

The difference comes when this function is invoked with both arguments, in this case left [ identity will return its left argument and right ] - right one respectively.

As with many things in J, this comes in handy when composing multiple functions. Let's consider a plus + primitive and write in a fork expression like following.

   plus =: [ + ]

Now this looks like an arbitrary set of symbols to anyone unfamiliar with J's special execution order for fork. This fork has its both arguments so it will evaluate slightly differently from the one we described previously.

Rules for this one would look like following.

   x (f h g) y

Will be evaluated to:

   (x f y) h (x g y)

In this case branches of the fork with get both x and y, then h will be applied to their results. When we apply fork evaluation rules for our plus example we would get behavior similar to following direct definition.

   plus_direct =: {{ (x [ y) + (x [ y) }}

Summing that with specifics of identity functions when calling with multiple argument we can see that this complex notation is actually equivalent so a single + primitive, since identity in first set of braces will evaluate to x, and identity in second - to y, leaving us with the same plus definition that we wrote a few chapters back.

Rewriting Day 6

Our final solution for day6 problem was something along the lines.

   input =: fread '2022/input6'
   is_unique =: {{ y -: ~. y }}
   solve =: {{ x + (x is_unique\ y) i.1 }}
   part1 =: 4 solve input
   part2 =: 14 solve input

Let's try to apply what we learned about fork combinator and left and right identity functions in order to create a tacit of out of this as an exercises.

We start with is_unique function, we see that it takes a nub ~. of it's right argument then matches -: it with it's right argument again determining if the string passed on the right is matching unique set of its characters.

Using one of the identity functions (does not matter which one again), we can rewrite it as follows.

   is_unique =: {{ (] y) -: (~. y) }}

But is exactly how fork would evaluate for ] -: ~.! Again it works with [ too. If we update solution with this new is_unique and re-run it we should see matching results.

We could try calling our tacit form on some input and should see that it performs the same as its direct definition peer.

   (] -: ~.) 'abcd'
1

Let's have a look at solve. This is a bit more complex, since we have arguments inside braces. We would need need to introduce another primitive here in order to continue to manipulate our formula.

~ - reflex, is another function that takes a function, it swaps places of arguments, meaning a function would take it's left x argument on the right as y and same for right y, which will be passed on the left as x.

Reflex does not do anything for functions like +, but we plan to use it for i. which finds the index of first occurrence in the array. Using reflex, our last part of solve function could look like:

   {{ 1 i.~ (x is_unique\ y) }}

We now start to see something that resembles a fork, but it has a value in place of it's left branch. Turns out that is fine, in case we have a value / constant on the left branch J will still interpret it as a fork since it has some special evaluation rules for that. This wouldn't work however if we would not swap the order on i., that's why we needed to introduce a reflex ~. Again reflex ~ is a combinator, a function that expects a function and produces another function, similar to scan \ we already use in this solution.

So if we try to write it in tacit form, we would get a perfectly legal expression in J.

   first_flag =: 1 i.~ is_unique\

Now we can simply use it in another tacit definition that would complete our solution for day6.

   solve =: [ + first_flag

We use another fork here, with left identity [ on the left. This is important and unlike in previous case we cannot simply swap it over for right identity ], since solve would take the window length on the left and the input string on the right. Writing it with right identity ], will tell J to add location of our first flag with the original string which does not make a lot of sense.

Advent of Code in J