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