Mandelbrot Set Fractal in Fortress

One of my favorite embarrassingly parallel problems is the rendering of the Mandelbrot set fractal. It is a simple program that produces very interesting images.

There are many ways to optimize this program, however I'm going to avoid these optimizations and try to create a naive implementation of the problem, just to see to the program looks like in Fortress. Also I'm going to try to take advantage of the parallel for loops that Fortress provides.


The first thing to define is something to represent complex numbers (remember this is a non-optimize version of the problem) . It seems that in the current reference implementation of there's no native support complex number (that I could find). So this gave me the opportunity to implement it.

value object Complex( real:RR64, img:RR64)
   opr+(self,other:Complex) = Complex(real+other.real,img+other.img)
   opr juxtaposition(self,other:Complex) = 
          Complex((real other.real) - (img other.img),
                  (real other.img) + (other.real img))
   toString() = ("Complex(" real ", " img ")")
end

opr |x:Complex| = SQRT(x.real^2 + x.img^2)


complexExp (o : Complex,n : Integral) = do
   if (n = 1) 
      then o
      else (o complexExp(o,n - 1))
   end
end

opr^(o:Complex,n:Integral) = 
   if (n = 2) 
     then (o o)
     else complexExp(o,n)
   end 

Note that this implementation is not complete, only the required elements for the Mandelbrot set are implemented. It is interesting that multiplication in Fortress doesn't use the '*' operation but it uses juxtaposition of elements to be multiplied. That is, instead of saying (x*y) you say (x y).

Then we need something that helps us to convert from screen coordinates to real coordinates. To do this I created the following function:

lFunc(x1 : RR64,y1 : RR64, x2 : RR64, y2 :RR64) = do
   m = (y2 - y1) / (x2 - x1)
   b = y1 - (m x1)
   fn(x) => (m x) + b
end

Note that this function returns another function that preforms the conversion.

Now the following code shows the implementation of the Mandelbrot set algorithm for one row in the image.

lineMandelbrot[\W\](startIndex : ZZ32, endIndex : ZZ32, 
                    lineData :Array[\ZZ32,ZZ32\], 
                    f :RR64 -> RR64, y : RR64) = do

   for i <- startIndex:endIndex do
      p0 = Complex( f(i) , y)
      p : Complex := p0 
      j : ZZ32 := 0
      maxIteration = 255
      while ( |p| < 2.0  AND j < maxIteration ) do
         p := p^2 + p0
         j := j+1
      end      
      lineData[i] := j
   end
end

Note that I use a parallel for loop for the external for statement in order to say that each point can be calculated independently in a separate thread.

This code looks very nice when formated with Fortify:



Finally the following code show the main program. For the graphic generation, a PPM file was used since is the easiest image format to generate!.

run(a:String...) = 
  do
     imageWidth = 100
     imageHeight = 100
     startY = -1.0
     endY = 1.0
     startX = -1.0
     endX = 1.0

     image =  array[\ZZ32\](imageWidth)

     fout: BufferedWriter = outFileOpen "output.ppm"
     outFileWrite(fout,"P3\n")
     outFileWrite(fout,"" imageWidth " " imageHeight "\n")
     outFileWrite(fout,"255\n")

     
     startIY = 1
     endIY = imageHeight

     fY = lFunc(startIY,startY,endIY,endY)
     fX = lFunc(0,startX,imageWidth - 1,endX)

     for iY <- seq(startIY#endIY) do         
         print "Line: " iY "\n"
         lineMandelbrot(0,imageWidth - 1,image,fX,fY(iY))    

         for i <- seq(0#imageWidth) do
            outFileWrite (fout,"0 0 " image[i]  "   ")
         end
         outFileWrite(fout,"\n")
     end     
     outFileClose(fout)
     ()
end

Since the reference implementation focus is not performance, I think is not fair to publish benchmarks or something like that. However I noticed that by playing around with the NumFortressThreads environment variable (found by looking at the source code) I got different execution times in my dual core machine .

Parallel For Loops in Fortress

On interesting and promising feature of Fortress is that for loops are parallel by default. This is documented in the 2.8 For Loops Are Parallel by Default section of the Fortress Language Specification document.

It seems that the reference implementation already supports this feature. For example when running this code:

component ForLoops

export Executable

run(args:String...):() = do
   for i <- 1:10 do
      print("Iteration " i ""\n")
   end
end

end

The output shows:

Parsing /home/ldfallas/blog/fortress/for/forloopexperiment.fss with the Rats! parser: 283 milliseconds
Read /home/ldfallas/fortress/FortressLibrary.tfs: 566 milliseconds
Iteration 10
Iteration 9
Iteration 6
Iteration 4
Iteration 8
Iteration 7
Iteration 2
Iteration 5
Iteration 1
Iteration 3
finish runProgram
1711 milliseconds

According to the specification the generator section of the for loop controls this behavior (section 13.15 and 13.14) . If the sequencial generator is used, the loop is executed in the classic order. For example:

component ForLoops

export Executable

run(args:String...):() = do
   for i <- sequential(1:10) do
      print("Iteration " i ""\n")
   end
end

end

The output is:

Parsing /home/ldfallas/blog/fortress/for/forloopexperimentSeq.fss with the Rats! parser: 282 milliseconds
Read /home/ldfallas/fortress/FortressLibrary.tfs: 546 milliseconds
Iteration 1
Iteration 2
Iteration 3
Iteration 4
Iteration 5
Iteration 6
Iteration 7
Iteration 8
Iteration 9
Iteration 10
finish runProgram
1523 milliseconds

Formating Fortress code with Fortify

A couple of days ago I noticed that a new tool to generate LaTeX code from Fortress source code was available. The tool is called Fortify can be found in the same page where the reference implementation is located.

In this post I'm going to try to create a little example and run Fortify to see the output of the generated LaTeX document.

One of the interesting things about Fortress is that, the language will have an alternative syntax that uses a lot of graphical symbols that will make a Fortress program look like a mathematical document.

For this test I took my old Numerical Analysis book and copied the Newton Raphson algorithm.

The program looks like this:

component Test

export Executable

nr(approx:RR64,f : RR64 -> RR64, f' : RR64 -> RR64,
   N : Number,tol : RR64) = do

  i:Number := 1
  p:RR64 := 0
  p0:RR64 := approx
  ready:Boolean := false

  while(i <= N AND NOT ready) do
     p := p0 - f(p0)/f'(p0)
     if  |p - p0|  < tol then 
        ready := true
     end
     i := i + 1 
     p0 := p
  end

  p
end

myF(x) = cos(x) - x
myF'(x) = - sin(x) - 1

run(a:String...) = print nr(1.5,myF,myF',10,0.0001)

end

Fortify is a tool that works inside Emacs. So I loaded fortify inside Emacs:

(load "..../fortify.el")

Then loaded Fortify by calling M-x fortify.

Selected the code:



And pressed M-&, then LaTeX code is generated.




To the generated code I added the LaTeX document declaration elements and imported a macros file included with Fortify.

\documentclass{article}
\usepackage{url, amssymb, amsmath, amsthm, stmaryrd, xspace}
\usepackage{amsfonts, graphicx, fullpage, times, hyperref}
\input ../fortify/fortify-macros

\begin{document}

....

\end{document}

After running LaTeX the code looks like this: