Numberphile recently posted a video about an interesting recursive function called “Fly Straight, Dammit!” which, when plotted, initially seems chaotic, but after six hundred thirty eight iterations, instantly stabilizes.

This sounds like a perfect opportunity to flex our J muscles and plot this function ourselves!

An Imperative Solution

The simplest approach to plotting our “Fly Straight, Dammit!” graph using the J programming language is to approach things imperatively:

a =: monad define
  if. y < 2 do.
    1
  else.
    py =. a y - 1
    gcd =. y +. py
    if. 1 = gcd do.
      1 + y + py
    else.
      py % gcd
    end.
  end.
)

We’ve defined our a monadic verb to return 1 if we pass in a “base case” value of 0 or 1. Otherwise, we recursively execute a on y - 1 to get our py, or “previous y”. Next, we check if the gcd of y and py equals 1. If it does, we return 1 + y + py. Otherwise, we return py divided by gcd.

This kind of solution shouldn’t look too foreign to anyone.

Let’s plot values of a to verify our solution:

require 'plot'
'type dot' plot a"0 i. 1000

This works, but it’s very slow. We know that our recursive calls are doing a lot of duplicated work. If we could memoize the results of our calls to a, we could save quite a bit of time. Thankfully, memoizing a verb in J is as simple as adding M. to the verb’s declaration:

a =: monad define M.
  ...
)

Now our imperative solution is much faster.

Using Forks and Hooks

While our initial solution works and is fast, it’s not taking advantage of what makes J a unique and interesting language. Let’s try to change that.

The meat of our solution is computing values in two cases. In the case when y and py have a greatest common divisor equal to 1, we’re computing 1 plus y plus py. Our imperative, right to left implementation of this computation looks like this:

1 + y + py

We could also write this as a “monadic noun fork” that basically reads as “1 plus the result of x plus y:

a_a =: 1 + +

Similarly, when we encounter the case where the greatest common divisor between y and py is greater than 1, we want to compute py divided by that gcd. This can be written as a “dyadic fork”:

a_b =: [ % +.

We can read this fork as “x divided by the greatest common divisor of x and y.”

Now that we’ve written our two computations as tacit verbs, we can use the “agenda” verb (@.) to decide which one to use based on the current situation:

a_a =: 1 + +
a_b =: [ % +.

a =: monad define M.
  if. y < 2 do.
    1
  else.
    py =. a y - 1
    has_gcd =. 1 = y +. py
    py (a_b ` a_a @. has_gcd) y
  end.
)

If has_gcd is 0, or “false”, we’ll return the result of py a_b y. Otherwise, if has_gcd is 1, we’ll return the result of py a_a y.

More Agenda

We can elaborate on the idea of using agenda to conditionally pick the verb we want to apply to help simplify out base case check.

I find myself producing lots of ranging content from books and articles, like the one you're reading now, to open source software projects. If you like what I'm doing, nothing shows your support more than signing up for my mailing list.

First, let’s define our base case and recursive case as verbs that we can combine into a gerund. Our base case is simple. We just want to return 1:

base_case =: 1:

Our recursive case is just the (memoized) else block from our previous example:

recursive_case =: monad define M.
  py =. a y - 1
  has_gcd =. 1 = y +. py
  py (a_b ` a_a @. has_gcd) y
)

Our function, a wants to conditionally apply either base_case or recursive_case, depending on whether y is greater or less than one. We can write that using agenda like so:

a =: base_case ` recursive_case @. (1&<)

And because our base_case verb is so simple, we can just inline it to clean things up:

a_a =: 1 + +
a_b =: [ % +.

recursive_case =: monad define M.
  py =. a y - 1
  has_gcd =. 1 = y +. py
  py (a_b ` a_a @. has_gcd) y
)

a =: 1: ` recursive_case @. (1&<)

Using agenda to build conditionals and pseudo-“case statements” can be a powerful tool for incorporating conditionals into J programs.

Going Further

It’s conceivable that you might want to implement a tacit version of our recursive_case. Unfortunately, my J-fu isn’t strong enough to tackle that and come up with a sane solution.

That said, Raul Miller came up with a one-line solution (on his phone) and posted it on Twitter. Raul’s J-fu is strong.