J two - ohhh...

[pozorvlak]

I've fixed the J Mandelbrot set program. Needless to say, the fix took precisely three characters :-)

[By the way, did anyone read that post? Does anyone else think J is interesting? Or did you just see a wall of punctuation and get scared off?]

The problem was that the bailout "absolute value greater than 2" test is performed after iterating the "plus-square" function 400 times. Now, iterates of plus-square can get big pretty fast: in fact, even within the small region under consideration, some points were overflowing after only eleven iterations. The first time it overflowed, it would return a complex number one of whose components was infinite: thereafter, it would return complex numbers whose real and/or imaginary parts were not-a-number (NaN). Now, the absolute value of NaN + i NaN is NaN: this is of course perfectly sensible, and exactly what NaN is for. Once an intermediate value becomes NaN, you want it to thread through your calculation, somewhat in the manner of Haskell's Maybe monad, not bothering you but getting on with the rest of the calculation (which is usually some large piece of array manipulation). A few data points that produce infinity or NaN can usually be ignored if the rest of the calculation goes OK.

Where things get odd is NaN's behaviour with respect to comparison operators. NaN is not equal to anything, even itself. NaN is not less than anything or greater than anything either. The upshot of which is that 2 < NaN returns False (or rather 0, since J uses Iverson's Convention). Arguably, 2 < NaN should return NaN (or maybe "Mu"?), but that wouldn't work in languages in which booleans and floats are a separate type. Hence, points which have overflowed are found to give absolute values less than 2, and thus (incorrectly) to be part of the Mandelbrot set.

So, the obvious fix would be to perform the bailout test earlier: to stop iterating as soon as |z| went over 2, and return true. Unfortunately, my J-fu is not yet strong enough for me to be able to do this without re-writing a big chunk of the code using an explicit while loop, which is not very Jish (explicit iteration is discouraged, not least because it's much slower). But there's an easier way. As well as not being greater than 2, NaN is also not less than 2. So, by changing the sense of the test round, and re-ordering the display characters (so points for which the test is true are displayed as '#', and those which test false are displayed as '.' rather than the other way round), we get the following:

   {&'.#' @ (2:>|) @ ((+*:)^:200 0:) (18 %~ i:_20) j.~/ (28 %~ _59 + i.75)
...........................................................................
...........................................................................
...........................................................#...............
...........................................................................
........................................................#..................
......................................................###..................
.....................................................######................
.....................................................######................
......................................................####.................
............................................#....###############...........
............................................#####################.###......
.............................................#######################.......
.........................................###########################.......
..........................................###########################......
........................................###############################....
...............................#........##############################.....
...........................########....################################....
..........................###########..###############################.....
.........................#############.###############################.....
......................#..#############.##############################......
....###############################################################........
......................#..#############.##############################......
.........................#############.###############################.....
..........................###########..###############################.....
...........................########....################################....
...............................#........##############################.....
........................................###############################....
..........................................###########################......
.........................................###########################.......
.............................................#######################.......
............................................#####################.###......
............................................#....###############...........
......................................................####.................
.....................................................######................
.....................................................######................
......................................................###..................
........................................................#..................
...........................................................................
...........................................................#...............
...........................................................................
...........................................................................

Hurrah!
Total changes: one character to change '<' to '>', two to change '.#' to '#.' :-)

Now here's the interesting bit: the Haskell version seems only to work because of what I can only assume is a bug in GHC's handling of IEEE 754 special values. The Haskell version behaves exactly like the J version until it gets to the stage of taking the magnitude of NaN + i NaN, at which point (in Hugs) it dies with an "arithmetic overflow!" error (grrrr: that's what Infinity and NaN are for), or (in GHC) it returns Infinity (which is greater than 2, of course). G'huh? How does Infinity make sense here? It's not a number, it doesn't have a magnitude, much less an infinite one. Even more weirdly, sqrt (nan*nan + (nan*nan)) returns NaN as expected.

Yet again, I suffer pain because someone didn't read IEEE 754 properly. Which is the IEEE's fault for charging heavily for their standard documents, rather than making them freely available like they would have done if they actually cared about wide dissemination and interoperability. Grrrrr.

Comments

[susannahf.livejournal.com]

I have an automatic Scary Code Filter that enables my eyes to slide right over the code, but read the post. I read the explanationy bit, and frequently find it interesting, and the SCF prevents me from going "Argh!"

[pozorvlak.livejournal.com]

Yeah, I do much the same. Did you read the previous post, though? The only metric I have is how many comments get left, and that post was Warnocked.

[susannahf.livejournal.com]

I skimmed it. BTW, the link from this post doesn't go there. In fact it seems to go to different places depending on what the current page is (eg friends page, your lj, post-only page all have different targets...)

[pozorvlak.livejournal.com]

Ooops. Fixed now.

[totherme.livejournal.com]

I scanned the post, and opened it in a new tab, so I could read and understand the code later. Later hasn't properly happened yet :)

[pozorvlak.livejournal.com]

:-) It turned out a lot longer than I'd thought. Still, the exercise of writing it was valuable.

By the way, here's a desyntaxification which I wrote but never posted, using $ for "apply", x +: y for "x + i y" and so on a la Haskell:

index_into '#.'
        $ (2<=).magnitude
        $ ((+ square) power 400 (const 0))    NB. this is the hard line
                (18 (flip divide) integers -20)
                (table (flip +:))
                (28 (flip divide) (-59 + naturals 75))

Still slightly shorter than the Haskell version :-)

I was thinking recently about an automatic J desyntaxifier: you can easily get access to the result of lexing J code, but I can't see any facilities for getting access to an actual AST. The grammar's fairly simple, but it's more work than I really want to do :-(

[drj11.livejournal.com]

There is no AST in J. Parsing and evaluation are comingled in a way that I somehow avoided describing as "a ghastly monstrous way to implement a language" in my blog article Learning J Part III (http://drj11.wordpress.com/2007/04/27/learning-j-part-iii/) (see the section titled "Operator precedence is not enough"). If you think the grammar is simple enough then write it out for a user-defined conjunction.

I suspect that not enough J programmers know this.

On the other hand, I'm just a J newbie, so I could be completely off.

[pozorvlak.livejournal.com]

Thanks! I look forward to reading the whole series when I'm less sleepy.

More precisely, my thought was "You'd need to detect whether verbs were being used monadically or dyadically: that wouldn't be too hard, but what about conjunctions and adverbs? This is probably going to get beyond me swiftly if I try for too complete a solution. Still, I might get something that will produce first-approximations without too much difficulty".

As a Perl user, the thought of context-dependent grammar fills me with less horror than it might otherwise - I've seen that that kind of thing can be useful. On the other hand, it makes me rather less optimistic about the possibility of doing metahacking in J. A pity - that would have been cool.

[drj11.livejournal.com]

I wouldn't despair too much. People don't write evil conjunctions (er, or adverbs). In practice whether a conjunction reduces to a noun or a verb can be statically deduced. A parser (to produce an AST and thence a Haskell program or whatever desyntaxified result you want) could just be told about the rules for the built-in conjuctions. Essentially its just decorating all conjunction with their type. User defined conjunctions would need to be introduced to the parser in the same way. Or... you could probably programmatically derive a type for most user-defined conjunctions that actually got written (just not my Evil Conjunction).

[pozorvlak.livejournal.com]

By "desyntaxify", all I really meant was "replace punctuation symbols by their names". So $ becomes "shape", # becomes "count", and so on. My thought was that it might be a useful crutch for the early stages of learning the language. This would involve some level of analysis beyond lexing, so that you could tell eg monadic % (reciprocal) from dyadic % (division), etc...

[michiexile]

I'm sorry for contributing to Warnockage - especially given the courtesy you showed me - I read it, found it interesting, and concluded that I still cannot reliably parse J. :P

[pozorvlak.livejournal.com]

It's not easy, at least to begin with - writing that post was a major step in my J education :-)

[pozorvlak.livejournal.com]

I think the interesting things about that program were

1. polymorphism with respect to dimension rather than type;
2. points-free programming using hooks and forks rather than currying;
3. Iverson's Convention, and the possibilities it affords;
4. something else that I'm too tired to remember.

Of course, there are no doubt other interesting lessons J has to teach me :-)

[pozorvlak.livejournal.com]

Oh yeah:

4. Right-to-left evaluation and the absence of operator precedence. Oddly liberating, once you get used to it. Of course, to make it work you either need explicit brackets everywhere (as in Lisp) or very limited ranges of arity (J/RPN/PostScript).

[elvum.livejournal.com]

I found that the punctuation in J proved to be a barrier to my appreciation of its undoubted elegance. A bit like Perl then? ;-)

[pozorvlak.livejournal.com]

I suspected something of the sort might be the case :-)

I wonder if some people are generally better at handling punctuation-heavy syntax than others? Is it innate, or a result of training? I've heard several CS types say "syntax is irrelevant" or the like, but none of them use Perl or APL/J...