Simplified Fractal Modules

As I mentioned in my original post for my fractal series, I was unsatisfied with the way that I was abstracting common code. While cleaning up some params this week, I also figured out an abstraction for my escape-time algorithm that’s not too bad.

My code this week is in my mandelbrot repo on Github tagged blog_2016_07_25. Links to the previous articles are available in the README.

The Cleanup

Let’s look at Fractals.EscapeTime.Mandelbrot from a few weeks ago.

Module attributes and functions and macros

Mandelbrot defined these three module attributes:

@magnitude_cutoff         2.0
@magnitude_cutoff_squared 4.0
@max_iterations           256

I talked about the escape-time algorithm a few weeks back. The algorithm needs two numbers: a magnitude cutoff and a maximum number of iterations. Exceeding the cutoff means the original grid point is outside the fractal; exceeding the maximum number of iterations means the grid point is inside. Triggering either one means stopping the escape-time algorithm.

I defined this function, but I should have called it outside?:

def escaped?(z) do
  Complex.magnitude_squared(z) >= @magnitude_cutoff_squared
end

I used @magnitude_cutoff_squared because computing the square root is very slow (as far as mathematical computations go). Just compare the square of the magnitude to the square of the cutoff.

Consequently, @magnitude_cutoff was unused.

I did not define an inside? function but should have. Instead I inlined its definition in the termination step in the escape-time algorithm:

Stream.drop_while(fn {z, i} -> !escaped?(z) && i < @max_iterations end)

I hate that I extracted only the one function here.¹

Misnamed and duplicated

So when I wrote a few paragraphs back that “I did not define an inside? function”, that’s technically true. I did define a macro for Fractals.Colorizer, but called it escaped?:

defmacro escaped?(iterations) do
  quote do
    unquote(iterations) >= @maximum_iterations
  end
end

It would have been better if I had used this macro in the escape-time algorithms, too. It would have been much much better if I had named it right, instead of naming it pretty much the opposite of what it computed. It’s a code smell so bad, they don’t even have a name for it. At least it did compute the right thing for the colorizing algorithms.

Long escape-time algorithm

The the escape-time algorithm is necessarily a bit long:

def escape_time(grid_point) do
  cmplx(0.0, 0.0)
  |> Stream.iterate(&iterator(&1,grid_point))
  |> Stream.with_index
  |> Stream.drop_while(fn {z, i} -> !escaped?(z) && i < @max_iterations end)
  |> Stream.take(1)
  |> Enum.to_list
  |> List.first
end

The drop_while test could be simplified, but overall this isn’t bad code. It’s bad because I had three different versions of this in the three fractals modules with very little variation.

Fixing the smells

I knew I would eventually clean all of this up, and as I expected, the trigger to start the clean up came when I started looking at new fractals. I tried out a sinusoidal Mandelbrot a few weeks ago and found that I needed more iterations and a larger cutoff. I could have set the module attributes on the SinusoidalMandelbrot module to higher values, but then it occurred to me that I might like to play around with those settings, even on my existing fractals.

So I set out to turn the magnitude cutoff (squared) and maximum iterations into Params. And all of the smells described above got fixed along the way.

Done?

As I mentioned above, the escaped? function was poorly named and duplicated in each module for a fractal. escaped? the macro was named completely wrong and as a macro in Fractals.Colorizer. inside? was inlined in the escape-time algorithm.

So I created Fractals.EscapeTime.Helpers.

inside? is the escaped? macro moved out of Fractals.Colorizer:

defmacro inside?(iterations, max_iterations) do
  quote do
    unquote(iterations) >= unquote(max_iterations)
  end
end

outside? is now a macro:

defmacro outside?(z, cutoff_squared) do
  quote do
    Complex.magnitude_squared(unquote(z)) >= unquote(cutoff_squared)
  end
end

max_iterations and cutoff_squared are now parameters because they come from a Params struct, not from module attributes. I don’t pass in the Params struct itself because I want to use these macros in when guards on functions (or at least inside?), and unpacking a struct isn’t allowed in a guard.

For the escape-time algorithm, I have a done? function:

def done?({z, iterations}, params) do
  outside?(z, params.cutoff_squared) ||
    inside?(iterations, params.max_iterations)
end

Since I don’t use done? in a guard, I can implement it as a function that takes a Params struct. z and iterations come in a tuple because that’s their natural form in the escape-time algorithm.

Escape-time algorithm

With the new done? function, I could write this:

def pixels(grid_points, params) do
  Enum.map(grid_points, &escape_time(&1, params))
end

def escape_time(grid_point, params) do
  Complex.zero
  |> Stream.iterate(&iterator(&1, grid_point))
  |> Stream.with_index
  |> Stream.drop_while(fn zi -> !done?(zi, params) end)
  |> Stream.take(1)
  |> Enum.to_list
  |> List.first
end

In last year’s Elixir solution, I passed in a function for iterator which was determined by a case expression.² This time I figured I’d use the __using__ macro to provide common code in Fractals.EscapeTime.

pixels is the same across all three fractals, so that was an obvious candidate to pull into __using__:

defmacro __using__(_options) do
  quote do
    def pixels(grid_points, params) do
      Enum.map(grid_points, &escape_time(&1, params))
    end
  end
end

When I use Fractals.EscapeTime in Mandelbrot and Julia and BurningShip, I get this definition of pixels for free in each module, as if I typed it into each of those modules. escape_time is a free variable in the macro definition, but once used it’s bound to the definition in the module that using Fractals.EscapeTime.

The escape_time functions looks pretty similar in the three modules. Mandelbrot and BurningShip³:

def escape_time(grid_point, params) do
  Complex.zero
  |> Stream.iterate(&iterator(&1,grid_point))
  |> Stream.with_index
  |> Stream.drop_while(fn zi -> !done?(zi, params) end)
  |> Stream.take(1)
  |> Enum.to_list
  |> List.first
end

Julia:

def escape_time(grid_point, c) do
  grid_point
  |> Stream.iterate(&iterator(&1,c))
  |> Stream.with_index
  |> Stream.drop_while(fn zi -> !done?(zi, params) end)
  |> Stream.take(1)
  |> Enum.to_list
  |> List.first
end

It’s only the first two lines of the pipe that are different: what value do start with, and what do you pass to iterator? I got hung up on trying to abstract out the Stream.iterate(&iterator(...args...) since the only difference is what gets passed to iterator. Every solution just seemed more complicated than it needed to be, and, really, what’s wrong with a little bit of duplication?

So I looked for function calls that I could pull out easily: everything from Stream.with_index to the end. Another function was born, EscapeTime.escape_time:

def escape_time(stream, params) do
  stream
  |> Stream.with_index
  |> Stream.drop_while(fn zi -> !done?(zi, params) end)
  |> Stream.take(1)
  |> Enum.to_list
  |> List.first
end

I could rewrite Mandelbrot.escape_time (and BurningShip.escape_time) like so:

def escape_time(grid_point, params) do
  Complex.zero
  |> Stream.iterate(&iterator(&1, grid_point))
  |> EscapeTime.escape_time
end

Julia.escape_time became:

def escape_time(grid_point, params) do
  grid_point
  |> Stream.iterate(&iterator(&1, params.c))
  |> EscapeTime.escape_time
end

As I looked at this, I realized that EscapeTime.escape_time could be called by pixels.

So Mandelbrot.escape_time became Mandelbrot.iterate:

def iterate(grid_point, _params) do
  Stream.iterate(Complex.zero, &iterator(&1, grid_point))
end

The other two modules for fractals got the same refactor.

I updated pixels in the EscapeTime.__using__ macro:

defmacro __using__(_options) do
  quote do
    def pixels(grid_points, params) do
      Enum.map(grid_points, fn grid_point ->
        grid_point
        |> iterate(params)
        |> Fractals.EscapeTime.escape_time(params)
      end)
    end
  end
end

iterate is bound to the module’s own version. Everything else is a parameter or an explicit call to a very specific function.

I really like this solution.

Next week

I’m going to play around with the fractals this week, tweaking the cutoff and maximum iterations. I may implement another coloring scheme or two. And if I’m really lucky, I’ll try a new fractal or two.

Footnotes

elixir fractals