![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
I've been learning the programming language J recently, and in the course of my studies came across this example program by Ewart Shaw, to draw an ASCII-graphics Mandelbrot set:
You'll need to recall that the Mandelbrot set is the subset M of the complex numbers such that c is in M iff the iterates of the function fc : z → z2 + c do not tend to infinity when you use 0 as your starting value. It's an interesting and useful theorem that, if |fcn(0)| > 2 for some n, then it will tend to infinity, and thus c is not in the Mandelbrot set. So we have a rough test for Mandelbroticity: iterate fc some large number of times, and if the absolute value of the result is greater than 2 then it's not in the Mandelbrot set.
The first thing to notice about this program is that it's very short. J is a descendent of APL, which was famed for its terseness: J departs from APL in not requiring a special character set, however. APL seems to have been the source of the "one-liner wars" and the game now most commonly played as Perl golf. Part of APL/J's terseness comes from having very short (one- or two-character) names for all the standard functions, but most of it comes from relying on a different paradigm of programming from most languages of the time (or, indeed, from most languages now).
The second thing to notice is that, to the uninitiated eye at least, it looks like line noise or cartoon characters swearing. Structured programming advocates would say that APL was unmaintainable, to which APL fans would usually reply "So what? I can re-write the entire program in the time it would take you to find the right part of your code to fix". Though I'm sure this remark was mainly intended to enrage Edgser Dijkstra (at which it succeeded), there's a serious point here: if all interesting programs are short, it doesn't matter how hard it is to write and maintain long ones. APL-like languages make the solutions to very many interesting problems very short, thus obviating most of the impetus behind structured programming, object-oriented programming, etc (though later versions of APL added all the usual structured-programming features anyway, and J's namespace mechanism can apparently be (ab)used to allow OOP).
Now, to the code. J has no precedence among functions (called "verbs"): evaluation is right-to-left in the absence of brackets. This means that, say 3 * 4 + 1 is 15 rather than 13. The conflict with established mathematical notation is deliberate: APL, like Lisp, was originally an attempt to establish a new mathematical notation that turned out to be good to program in. So, we read it right-to-left.
i.75 is the array 0 .. 74. Two things to note: arrays are built-in, and there are built-in functions to generate and manipulate them.
% is the division function. %~ is the flipped division function: x %~ y is y/x. ~ is an adverb. Another useful adverb is /, which is similar to Haskell's foldl or Python's reduce: +/ is "sum over array".
_59 is -59: since - is a verb, and thus subject to right-to-left evaluation it's useful to distinguish between, say, -20 + i.5 = -(20 + i.5) = _20 _21 _22 _23 _25 and _20 + i.5 = _20 _19 _18 _17 _16. So _59 + i.75 is the integers from 0 to 74 plus -59, which is to say _59 _58 _57 ... 14 15. Note how the addition automatically maps over the array. All verbs are polymorphic in the dimensions of their arguments: if I'd asked for (i.75) + i.75, I would have got a zip instead, ie (0+0) (1+1) (2+2)... (and note that the brackets around the first (i.75) are needed, because of right-to-left evaluation and because i. can take an array as its argument). Generally, the polymorphism will do what you want, but if you need more precise control you can use the " (rank) conjunction.
28 %~ _59 + i.75 is the array calculated above divided by 28, ie _59/28 _58/28 _57/28 ... 15/28. Again, the operation 28 %~ maps over the entire array.
j. is the "complex number" function: x j. y is x + iy, or xjy in J notation. This is exactly like Haskell's +: function. j.~ is the flipped complex number function. Note that complex numbers are built-in, and all built-in functions are defined to work properly on complex numbers. Incidentally, J also implements IEEE 754 not-a-number, infinity and minus infinity out of the box, calling them _., _ and __ respectively.
We've already mentioned that /, when applied to a monadic (one-argument) verb is similar to foldl; when applied to a dyadic (two-argument) verb it means "table" or "outer product". So j.~/, in its two-argument form, will form a table of y + ix, for all x in its left argument and all y in its right argument. Most (all?) standard J functions have separate but related monadic and dyadic meanings - for instance %, which is division when used dyadically, means "reciprocal" when used monadically. If you're thinking "that's not what monadic means!" then yes, it's not what monadic means in category theory, but it is what monadic means in the theory of rewriting systems, and it's a toss-up as to who got there first (probably the APLers, come to think of it: the first paper on APL dates from 1957). Besides, we're all abusing Leibniz's term anyway :-)
i:_20 is the integers from 20 to -20, or, in J notation, 20 to _20: Note the similarity between i. and i:, which is meant to aid memory. Hence (18 %~ i:_20) is 20/18 ... _20/18 as before. So (18 %~ i:_20) j.~/ 28 %~ _59 + i.75 is a two-dimensional array of complex numbers with real part between -59/28 and 47/28, and imaginary part between -20/18 and 20/18.
*: is "square". There's a mnemonic here, too: *:, +:, %: and -: are square, double, square root and halve, respectively.
+*: is a chain of the two verbs "+" and "*:". This is a construction known as a "hook", part of J's support for tacit (point-free) programming. Hooks are evaluated as follows: (f g) y is y f g y = y f (g y), and x (f g) y is x f g y. So x (+*:) y is x plus the square of y: so +*: is the function f at the core of the definition of the Mandelbrot set.
^: is the "power" conjunction, which might also be called "iterate". So (+*:)^:400 is "plus-square" iterated 400 times.
0: is the constant function with value 0. ((+*:)^:400 0:) is another hook, this time a monadic one: by the rules previously mentioned, it's evaluated as ((+*:)^:400 0:) y = y (+*:)^:400 (0: y) = y (+*:)^:400 0. In other words, the 400th iterate of the map, starting at 0 and with constant term y. This being J, y can be an array: the function then returns the array of results obtained by taking each element of the starting array as input.
@ is function composition, much like Haskell's . or $ (though because there's no verb precedence, there's no need to distinguish the cases).
(2:<|) is a train of three verbs, called a fork. There's a rule for evaluating forks, too: in the monadic case, (f g h) y = (f y) g (h y). The classic example is the fork +/ % #, which takes the mean of a list: the three verbs meaning sum, divide and count, respectively. In the case at hand, the three verbs are 2: (constant function taking the value 2), < (less than), and | (absolute value). So (2:<|) y is 1 (true) if the absolute value of y is greater than 2 (remember the Interesting and Useful Theorem above). Naturally, it works with arrays too.
& is the "bond" conjunction, which does partial evaluation, aka currying (fixing one or more arguments of a function, to give another function with fewer arguments). 1&+ is the "add one" function: we could have written the fork above as 2&<|. { is "from", which indexes into arrays: there are lots of similar functions that involve curly brackets in their names, like {. (head/take), {: (tail), }. (behead/drop), }: (curtail), and so on. So {&'#.' indexes into '#.', which leads to another important point: strings are arrays of characters, and can be manipulated with all the standard array-munging functions. Remember that 1 is true and 0 is false in J: these are exactly the indices of . and # in the string '#.'.
Taken all together, this program generates a 75x41 array of complex numbers in the region of the origin, and puts a # at a given position if that number appears to be in the Mandelbrot set, and a . if it isn't. Brilliant! Let's try it...
A little investigation shows that the iterates of f quickly become NaN: I have no idea why this happens. However, if we drop the number of iterations low enough, we can still get a decentish-looking Mandelbrot set:
Haskellites may be interested to learn that the roughly-equivalent Haskell code:![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
totherme, compiled after a mere three or four attempts, and worked properly (albeit slowly) as soon as it compiled, giving the desired result:
{&'#.' @ (2:<|) @ ((+*:)^:400 0:) (18 %~ i:_20) j.~/ 28 %~ _59+i.75 It embodies so many J features and techniques that I'm going to analyse it here as an introduction to the language.You'll need to recall that the Mandelbrot set is the subset M of the complex numbers such that c is in M iff the iterates of the function fc : z → z2 + c do not tend to infinity when you use 0 as your starting value. It's an interesting and useful theorem that, if |fcn(0)| > 2 for some n, then it will tend to infinity, and thus c is not in the Mandelbrot set. So we have a rough test for Mandelbroticity: iterate fc some large number of times, and if the absolute value of the result is greater than 2 then it's not in the Mandelbrot set.
The first thing to notice about this program is that it's very short. J is a descendent of APL, which was famed for its terseness: J departs from APL in not requiring a special character set, however. APL seems to have been the source of the "one-liner wars" and the game now most commonly played as Perl golf. Part of APL/J's terseness comes from having very short (one- or two-character) names for all the standard functions, but most of it comes from relying on a different paradigm of programming from most languages of the time (or, indeed, from most languages now).
The second thing to notice is that, to the uninitiated eye at least, it looks like line noise or cartoon characters swearing. Structured programming advocates would say that APL was unmaintainable, to which APL fans would usually reply "So what? I can re-write the entire program in the time it would take you to find the right part of your code to fix". Though I'm sure this remark was mainly intended to enrage Edgser Dijkstra (at which it succeeded), there's a serious point here: if all interesting programs are short, it doesn't matter how hard it is to write and maintain long ones. APL-like languages make the solutions to very many interesting problems very short, thus obviating most of the impetus behind structured programming, object-oriented programming, etc (though later versions of APL added all the usual structured-programming features anyway, and J's namespace mechanism can apparently be (ab)used to allow OOP).
Now, to the code. J has no precedence among functions (called "verbs"): evaluation is right-to-left in the absence of brackets. This means that, say 3 * 4 + 1 is 15 rather than 13. The conflict with established mathematical notation is deliberate: APL, like Lisp, was originally an attempt to establish a new mathematical notation that turned out to be good to program in. So, we read it right-to-left.
i.75 is the array 0 .. 74. Two things to note: arrays are built-in, and there are built-in functions to generate and manipulate them.
% is the division function. %~ is the flipped division function: x %~ y is y/x. ~ is an adverb. Another useful adverb is /, which is similar to Haskell's foldl or Python's reduce: +/ is "sum over array".
_59 is -59: since - is a verb, and thus subject to right-to-left evaluation it's useful to distinguish between, say, -20 + i.5 = -(20 + i.5) = _20 _21 _22 _23 _25 and _20 + i.5 = _20 _19 _18 _17 _16. So _59 + i.75 is the integers from 0 to 74 plus -59, which is to say _59 _58 _57 ... 14 15. Note how the addition automatically maps over the array. All verbs are polymorphic in the dimensions of their arguments: if I'd asked for (i.75) + i.75, I would have got a zip instead, ie (0+0) (1+1) (2+2)... (and note that the brackets around the first (i.75) are needed, because of right-to-left evaluation and because i. can take an array as its argument). Generally, the polymorphism will do what you want, but if you need more precise control you can use the " (rank) conjunction.
28 %~ _59 + i.75 is the array calculated above divided by 28, ie _59/28 _58/28 _57/28 ... 15/28. Again, the operation 28 %~ maps over the entire array.
j. is the "complex number" function: x j. y is x + iy, or xjy in J notation. This is exactly like Haskell's +: function. j.~ is the flipped complex number function. Note that complex numbers are built-in, and all built-in functions are defined to work properly on complex numbers. Incidentally, J also implements IEEE 754 not-a-number, infinity and minus infinity out of the box, calling them _., _ and __ respectively.
We've already mentioned that /, when applied to a monadic (one-argument) verb is similar to foldl; when applied to a dyadic (two-argument) verb it means "table" or "outer product". So j.~/, in its two-argument form, will form a table of y + ix, for all x in its left argument and all y in its right argument. Most (all?) standard J functions have separate but related monadic and dyadic meanings - for instance %, which is division when used dyadically, means "reciprocal" when used monadically. If you're thinking "that's not what monadic means!" then yes, it's not what monadic means in category theory, but it is what monadic means in the theory of rewriting systems, and it's a toss-up as to who got there first (probably the APLers, come to think of it: the first paper on APL dates from 1957). Besides, we're all abusing Leibniz's term anyway :-)
i:_20 is the integers from 20 to -20, or, in J notation, 20 to _20: Note the similarity between i. and i:, which is meant to aid memory. Hence (18 %~ i:_20) is 20/18 ... _20/18 as before. So (18 %~ i:_20) j.~/ 28 %~ _59 + i.75 is a two-dimensional array of complex numbers with real part between -59/28 and 47/28, and imaginary part between -20/18 and 20/18.
*: is "square". There's a mnemonic here, too: *:, +:, %: and -: are square, double, square root and halve, respectively.
+*: is a chain of the two verbs "+" and "*:". This is a construction known as a "hook", part of J's support for tacit (point-free) programming. Hooks are evaluated as follows: (f g) y is y f g y = y f (g y), and x (f g) y is x f g y. So x (+*:) y is x plus the square of y: so +*: is the function f at the core of the definition of the Mandelbrot set.
^: is the "power" conjunction, which might also be called "iterate". So (+*:)^:400 is "plus-square" iterated 400 times.
0: is the constant function with value 0. ((+*:)^:400 0:) is another hook, this time a monadic one: by the rules previously mentioned, it's evaluated as ((+*:)^:400 0:) y = y (+*:)^:400 (0: y) = y (+*:)^:400 0. In other words, the 400th iterate of the map, starting at 0 and with constant term y. This being J, y can be an array: the function then returns the array of results obtained by taking each element of the starting array as input.
@ is function composition, much like Haskell's . or $ (though because there's no verb precedence, there's no need to distinguish the cases).
(2:<|) is a train of three verbs, called a fork. There's a rule for evaluating forks, too: in the monadic case, (f g h) y = (f y) g (h y). The classic example is the fork +/ % #, which takes the mean of a list: the three verbs meaning sum, divide and count, respectively. In the case at hand, the three verbs are 2: (constant function taking the value 2), < (less than), and | (absolute value). So (2:<|) y is 1 (true) if the absolute value of y is greater than 2 (remember the Interesting and Useful Theorem above). Naturally, it works with arrays too.
& is the "bond" conjunction, which does partial evaluation, aka currying (fixing one or more arguments of a function, to give another function with fewer arguments). 1&+ is the "add one" function: we could have written the fork above as 2&<|. { is "from", which indexes into arrays: there are lots of similar functions that involve curly brackets in their names, like {. (head/take), {: (tail), }. (behead/drop), }: (curtail), and so on. So {&'#.' indexes into '#.', which leads to another important point: strings are arrays of characters, and can be manipulated with all the standard array-munging functions. Remember that 1 is true and 0 is false in J: these are exactly the indices of . and # in the string '#.'.
Taken all together, this program generates a 75x41 array of complex numbers in the region of the origin, and puts a # at a given position if that number appears to be in the Mandelbrot set, and a . if it isn't. Brilliant! Let's try it...
pozorvlak@delirium:~> cd j601/
pozorvlak@delirium:~/j601> ./jconsole
{&'#.' @ (2:<|) @ ((+*:)^:400 0:) (18 %~ i:_20) j.~/ 28 %~ _59 + i.75
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
...################################################################........
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
###########################################################################
########################################################################### Bugger.A little investigation shows that the iterates of f quickly become NaN: I have no idea why this happens. However, if we drop the number of iterations low enough, we can still get a decentish-looking Mandelbrot set:
{&'#.' @ (2:<|) @ ((+*:)^:12 0:) (18 %~ i:_20) j.~/ 28 %~ _59+i.75
...........................................................................
......................................................##...................
.......................................................#...#...............
........................................................#..................
.......................................................###.................
...................................................#########...............
....................................................########...............
....................................................########...............
..........................................###...#############.##.....#.....
..........................................######################..##.##....
...........................................###########################.....
.........................................#.###########################.....
........................................##############################.....
........................#...............##############################.....
........................#.....#........#################################...
..........................#########....################################....
.........................###############################################...
........................###############################################....
....................#.################################################.....
....................#################################################......
...#################################################################.......
....................#################################################......
....................#.################################################.....
........................###############################################....
.........................###############################################...
..........................#########....################################....
........................#.....#........#################################...
........................#...............##############################.....
........................................##############################.....
.........................................#.###########################.....
...........................................###########################.....
..........................................######################..##.##....
..........................................###...#############.##.....#.....
....................................................########...............
....................................................########...............
...................................................#########...............
.......................................................###.................
........................................................#..................
.......................................................#...#...............
......................................................##...................
...........................................................................Haskellites may be interested to learn that the roughly-equivalent Haskell code:
import Complex
-- Iterated functions
f `power` n = foldl (.) id $ take n $ repeat f
-- The original J version works with negative powers too, using J's
-- autoinversion features.
board = [[((-59 + x)/28) :+ (y/18) | x <- [0..74]] | y <- [-20 .. 20]]
f c z = z^2 + c
main = putStr $ unlines $
map (map (\c -> if magnitude (((f c) `power` 400) 0) >= 2 then '.'
else '#')) board which I wrote while trying to explain the J code to totherme, compiled after a mere three or four attempts, and worked properly (albeit slowly) as soon as it compiled, giving the desired result:........................................................................... ........................................................................... ...........................................................#............... ........................................................................... ........................................................#.................. .......................................................##.................. .....................................................######................ .....................................................######................ ......................................................####................. ............................................#....##############............ ............................................##.##################.###...... .............................................#######################....... .........................................#.#########################....... ..........................................###########################...... ........................................###############################.... ...............................#........##############################..... ...........................########....################################.... ..........................###########..###############################..... .........................#############.##############################...... ......................#..#############.##############################...... ....###############################################################........ ......................#..#############.##############################...... .........................#############.##############################...... ..........................###########..###############################..... ...........................########....################################.... ...............................#........##############################..... ........................................###############################.... ..........................................###########################...... .........................................#.#########################....... .............................................#######################....... ............................................##.##################.###...... ............................................#....##############............ ......................................................####................. .....................................................######................ .....................................................######................ .......................................................##.................. ........................................................#.................. ........................................................................... ...........................................................#............... ........................................................................... ...........................................................................Maybe I'm finally getting the hang of this strong typing business...
Tags: