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!
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
1. Otherwise, we recursively execute
y - 1 to get our
py, or “previous
y”. Next, we check if the
1. If it does, we return
1 + y + py. Otherwise, we return
py divided by
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.
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
py have a greatest common divisor equal to
1, we’re computing
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
a_a =: 1 + +
Similarly, when we encounter the case where the greatest common divisor between
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
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. )
0, or “false”, we’ll return the result of
py a_b y. Otherwise, if
1, we’ll return the result of
py a_a y.
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.
<p>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, <strong>nothing shows your support more than signing up for <a href="#newsletter">my mailing list</a></strong>.</p>
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
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 )
a wants to conditionally apply either
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.
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.