Introduction
The Mandelbrot set is a computer geek’s dream. It has everything you want for a coding demo. It’s a simple idea but it produces beautiful images. And it’s computationally intensive so it can be used to evaluate optimizations.
Let’s use it to practise my current curiosity: functional JavaScript using Ramda. The source code is on GitHub; you can see it running on Plunker. This article is aimed at people who are familiar with JavaScript and who are curious about functional programming.
What is the Mandelbrot set?
Quick recap: I think of the Mandelbrot set as a function over complex numbers. For any complex number, this function describes whether a particular iterative function, using that number as its initial seed, ever reaches infinity. (And since it is known that if the function ever exceeds two then it is certain to go to infinity, we treat two as being equivalent to infinity). The function is best presented visually as coloured points (pixels) on the complex plane. If the function goes to infinity on the first iteration for complex number z = a + ib then we draw a white pixel at z. If it stays bounded forever then we draw a black pixel. Otherwise we draw a shade of grey – the longer the function takes to go to infinity, the darker the pixel.
In theory the only input to the Mandelbrot function is a region of the complex plane. In practice we have to put an upper bound – max – on our iterations. If after max iterations the function still hasn’t escaped to infinity, then we assume that it never will. The greater the value of max, the more precise our image will be (but the slower our program will run).
Thoughts on functional programming
Functional programming is a paradigm – a particular way of thinking. For a classical imperative programmer it takes a lot of getting used to. I think the single most important technique – the one that you will use constantly – is projection. In other words, take a sequence S and function f. For each member n of S, evaluate f(n) to produce a new sequence; this is the projection of f onto S. (Often the hardest part of functional programming is to visualize your goal in terms of projections).
That’s pretty much what we want to do in our demo. We want to draw the Mandelbrot set onto an HTML canvas. That canvas has a finite number of pixels and each one represents a unique complex number. So our input sequence is the complex numbers that we are rendering, our projection function is the Mandelbrot function, and the resulting sequence is the pixel shades to be drawn on the canvas.
As a practical matter, it’s easier to think (and code) in terms of rows and columns. If our canvas is w pixels wide and h pixels high then we have h rows to draw and in each row we will need w shade values (i.e. RGB pixel colour values).
If you’re familiar with a language like F# then you’ll know that those functional languages are extremely strongly typed. They perform mathematical levels of inference to figure out that some parameter must be an integer because it gets passed around and some function ten levels up the stack adds one to it. What happens in JS, whose typing is, shall we say, not as strong? Simple: there’s little support for that aspect of functional programming. As usual in JS, supplying the right types is up to us.
Parallelism
You’ve probably heard that functional programming makes parallel processing easier. The Mandelbrot function is a terrific way to demo this because (a) the calculation for each point is intensive; and (b) the points are independent of each other. So if we can share the work amongst four cores, we should see a big performance improvement over the default JavaScript model of doing everything on a single core.
Dividing up the work is easy – if we have n cores to play with then we can give each core h / n rows to calculate. Then we just need a bit of JavaScript to spawn up some Web Workers and collate their results when they’re done.
Getting started
Before we launch into those fun Mandelbrot calculations we have a bit of preparatory work to do. At the moment all we have is the dimensions, in pixels, of our HTML canvas. We need somehow to transform these into the realm of complex numbers. Time for a projection! First we need to choose our initial region in the complex number plane. A good starting point is the region between ( -2 + 1.5i) and (1 – 1.5i).
There are lots of ways to do this, but for this application it’s always worth keeping performance in mind. When we get into the Mandelbrot iterations we are going to have enough work to do without having to convert pixel indexes to complex co-ordinates. Plus, having those co-ordinates ready in pre-baked sequences gives us easy inputs to our projections. So let’s do this: we’ll prepare two arrays, one for the a axis and one for the b (actually, can we agree right now to call them the x and y axes instead? Thanks 😊). For each axis we know the start and end of the range (or the start and length of the range, if you prefer). We also know the number of pixels available to render that axis. How to do this functionally? Here’s one way:
// from /src/js/mandel.js
function getSteps(start, distance, numPoints) {
const increment = distance / (numPoints - 1);
return R.range(0, numPoints).map(n => n * increment + start);
}
Rather than thinking in terms of a loop that adds elements to a result list, we describe the ‘steps’ list as the transformation of a basic sequence of natural numbers. For example, if we wanted to go from 5 to 15 in 3 steps we would start with the first three counting numbers, i.e. [0, 1, 2], and transform them:
[5 + (10/2) * 0, 5 + (10/2) * 1, 5 + (10/2) * 2] = [5, 10, 15]
If our canvas is 1000 x 1000 pixels then we will now have a 1000 number array that goes from xmin to xmax, and likewise for y. We want to run a projection over the y values called ‘drawRow’. To draw a row for a given y value we will need to run a projection over the x values. For each (x,y) combination in the row we do two things: (i) evaluate the Mandelbrot function at the point x + iy; and (ii) convert the function result to an RGB colour. This is an example of a ‘pipe’:
(x + iy) –> mandel(maxIterations) –> convertToColour(maxIterations) –> RGB
Let’s back up a bit and spell out our two functions:
function getMandelShade (maxIterations, z) --> integer function mandelShadeToColour (maxIterations, numIterations) --> RGB
Currying
Notice how the complex number z is the last argument to the getMandelShade function, and the getMandelShade function’s output is the last argument to the mandelShadeToColour function. This is the basic situation where functional programmers consider using currying. The point of currying is that if getMandelShade(maxIterations, z) returns an integer, then getMandelShade(maxIterations) must return a function that takes a complex number and returns an integer (and likewise for mandelShadeToColour(maxIterations)).
Currying is key to making our pipe work. We pass the initial input to the first function in the pipe. The result from that function is then passed to the second function, and so on. That’s why it was important to make z the last argument of getMandelShade. This allows currying to work its magic.
And that’s one of the main benefits of the Ramda library. All of Ramda’s built-in functions (such as map) are curried, and they take the target (your list in the case of map) as the last argument. Plus, it has a nifty curry function that turns a plain old JS function like getMandelShade into one that we can call curry-style.
So what does the f.p. JavaScript/Ramda code for this pipe look like? Pretty much the same as what we wrote above!:
// from calcmandel.worker.js const rowColours = mandelXs.map(R.pipe(getMandelShade(maxIterations, mandelY), mandelShadeToColour(maxIterations)));
And that’s one of the nice things about functional programming: the source code is very similar to our written explanation of the algorithm, rather than being contorted by the mechanics of loops and variable assignments. There are fewer moving parts, which means fewer places for things to go wrong.
The flip-side is that functional programs can often be quite overwhelming, because they express so many ideas in a small space.
Advanced function manipulation – mapIndexed
Maybe what I’ve shown so far hasn’t impressed you and you’re thinking “This is just a different way of manipulating data structures – I could do that with a loop.” Let’s see if we can make it a bit more exciting by manipulating the functions themselves.
The motivation here is that sometimes Ramda’s map function isn’t quite enough, because it doesn’t give you the index of the list element that you’re projecting. For example, when we compute a Mandelbrot row, it would make things a lot simpler further down the line if we could tag the result with the row’s index (i.e. tag the nth row with n). The code does exactly that:
// from calcmandel.worker.js
const result = mapIndexed((mandelGridY, canvasY) => getMandelRowWithIndex(maxIterations, mandelGridXpoints, canvasY, mandelGridY))(mandelGridYPoints);
This is just like R.map, but the projection function takes a second parameter (canvasY) that gives us the element’s index. The interesting question is, what’s the definition of mapIndexed?
const mapIndexed = R.addIndex(R.map);
Wow! How does that work? This is actually JavaScript in action. Officially, the first argument to map is a function, f, that takes one argument, n, being an element of S. But of course JS is pretty liberal about function arguments, and you can happily pass two arguments to a function that expects only one. The addIndex method takes advantage of this, replacing f with a function that maintains an index and passes it, along with n, to the original f.
Carl's personal website - May the Source be with you 