Saturday, May 21, 2016

Some things I learned while creating a small program in Mercury

Some time ago I started creating a program using the Mercury programming language to create images using the Escape Time algorithm. The goal was to learn about the language by solving a small problem.

The current result of this experiment can be found here https://github.com/ldfallas/graphicswithmercury/. Here's a list of things I learned.

Terms for configuration files

For this program I wanted to have a configuration file to specify :

  • The resolution of the final image
  • The coordinates used to render the fractal
  • The formula to use with the escape time algorithm
  • The palette to be used to render the final image

To create this configuration file I could use XML or create a special file format and parse it using Mercury's DCG. However I chose to use a different alternative, which is to use the term syntax.

Here's an example of the configuration file:

  fractal_config(
   image_resolution(320,200),
   top_left(-2.0, 1.5),
   bottom_right(1.0 , -1.5),
   formula(z*z + z + c),
   palette(
      single(10,20,30),
      range(from(10, 30, 40),  to(30, 50, 76),127),
      range(from(200, 100, 50),to(150, 0, 0),100),
      range(from(200, 100, 50),to(150, 10, 10),27),
      single(0,0,0)
   )
).      

Here I'm saying that:

  • The image will have a 320px by 200px resolution
  • The real coordinates of this image are between -2.0 and 1.0 in the X axis and 1.5 and 1.5 in the Y axis
  • The formula used in the escape time algorithm will be z*z + z + c
  • The palette will be constructed with the given ranges of colors

In order to read these term I used the term and parser modules which provides an easy interface for reading terms.

Here's a code snippet showing how the file is being loaded.

:- pred read_fractal_configuration_from_file(
            string::in,
            maybe_error(fractal_configuration)::out,
            io::di, io::uo) is det.

read_fractal_configuration_from_file(FileName, Configurati      onResult, !IO) :-
    parser.read_term_filename( FileName,  ReadTermResult, !IO),
    ((ReadTermResult = term(_, Term),
         term_to_fractal_configuration(Term, ConfigurationResult))
      ; (ReadTermResult = error(ErrMessage, _),
          ConfigurationResult = error(ErrMessage))
      ; (ReadTermResult = eof,
          ConfigurationResult = error("Empty file"))
     ).

The parser.read_term_filename reads these terms to a term data structure. The term_to_fractal_configuration predicate creates a configuration structure from these terms. An error is returned if the file doesn't have the expected structure. This is archived using the maybe_error data type.

Here's an example of how the first part of the configuration is loaded:

:- pred term_to_fractal_configuration(
            term(string)::in,
            maybe_error(fractal_configuration)::out) is det.

term_to_fractal_configuration(Term, Result) :-
    (if Term = functor(atom("fractal_config"),Args,_) then
        term_to_fractal_config_resolution(Args, Result)
     else
        error_message_with_location("Expecting 'fractal_config'",Term, Message),
        Result = error(Message)
    ).

One interesting feature of the term library is that it stores line number information. This makes it easy to report errors that occurred in a specific line of the input file:

:- pred error_message_with_location(
            string::in,
            term(string)::in,
            string::out) is det.

error_message_with_location(Msg, functor(_, _, context(_, Line)), ResultMsg) :-
     string.append(", at line:",string.int_to_string(Line),TmpString),
     string.append(Msg, TmpString, ResultMsg).
error_message_with_location(Msg, variable(_, context(_,Line)), ResultMsg) :-
     string.append(", at line:",string.int_to_string(Line),TmpString),
     string.append(Msg, TmpString, ResultMsg).

Now the main predicate for reading the documentation from terms is the following:

:- pred term_to_fractal_config_resolution(
            list(term(string))::in, 
            maybe_error(fractal_configuration)::out).

term_to_fractal_config_resolution(Terms, Result) :-
   (if Terms = [functor(atom("image_resolution"),
                     [ functor(integer(Width), _, _),
                       functor(integer(Height), _, _) ],
                     _)|Rest1] then
       (if  Rest1 = [functor(atom("top_left"),
                     [ functor(float(LeftX), _, _),
                       functor(float(TopY), _, _) ],
                     _)|Rest2] then
                (if  Rest2 = [functor(atom("bottom_right"),
                     [ functor(float(RightX), _, _),
                       functor(float(BottomY), _, _) ],
                     _)|Rest3] then
                    
                    (if Rest3 = [functor(atom("formula"), [Term], _)|Rest4], term_to_expression(Term, ok(Expr)) then
                        (if Rest4 = [PaletteConfig], term_to_palette_config(PaletteConfig, ok(Palette)) then 
                              Result  = ok(config( { Width, Height },
                                                   { LeftX, TopY },
                                                   { RightX, BottomY },
                                                   Expr,
                                                   Palette
 ))
                          
                           else
                              Result = error("Error reading palette")
                        )
                    else
                      Result = error("Error reading formula"))
                 else
                    Result = error("Error expecting: bottom_right(float,float)")
        )

        else
           Result = error("Error expecting: top_left(float,float)")
        )
    else
       Result = error("Error expecting: image_resolution(int,int)")
    ).

One improvement opportunity here is to separate this predicate into several parts to avoid this nesting structure.

As shown above our final goal is to create a result of the following type:

:- type fractal_configuration --->
    config( { int, int },              % image resolution
            { float, float },          % top left cartesian coordinates
            { float, float },          % bottom right cartesian coordinates
            expression,                % formula
            array({ int, int, int })). % palette

This structure provides the necessary information to render the fractal. One special datatype here is expression which is used to store the formula used with the escape time algorithm.

This data type looks like this:


:- type operator ---> times ; plus ; minus ; division.

:- type expression ---> 
     literal_num(float)
     ; var(string)
     ; imaginary
     ; bin_operation(expression, operator, expression).

Since the term library parser can parse arithmetic expressions, I can write simple code that translates terms to these abstract datatype.

Here's the definition of the predicate that does the translation:

:- pred term_to_expression(term(string)::in, maybe_error(expression)::out) is det.

term_to_expression(functor(atom(AtomStr),Ops,_), Expr) :-
   (if (Ops = [Op1,Op2],
        op_to_string(Operator,AtomStr),
        term_to_expression(Op1, ok(Op1Expr)),
        term_to_expression(Op2, ok(Op2Expr))) then
      Expr = ok(bin_operation(Op1Expr, Operator, Op2Expr))
    else
      (if Ops = [] then
          (if AtomStr = "i" then
             Expr = ok(imaginary)
           else
             Expr = ok(var(AtomStr)))
       else
          Expr = error("Error"))
   ).
term_to_expression(functor(float(X),_,_), Expr) :-
   Expr = ok(literal_num(X)).
term_to_expression(functor(integer(X),_,_), Expr) :-
   Expr = ok(literal_num(float(X))).
term_to_expression(functor(big_integer(_,_),_,_), error("Error")).
term_to_expression(functor(string(_),_,_), error("Error")).
term_to_expression(functor(implementation_defined(_),_,_), error("Error")).
term_to_expression(variable(_,_), error("Error")).

Reading the palette

The palette used by the escape time algorithm is just an array of colors. The configuration file allows two kinds of elements for specifying the colors :

  • single(RED, GREEN, BLUE) a single color for the current entry
  • range(from(RED1, GREEN1, BLUE1), to(RED1, GREEN2, BLUE2), COUNT) to create a range of colors of COUNT steps between the two colors.

The following code reads the palette configuration:

:- pred terms_to_palette(
            list(term(string))::in, 
            list({int, int, int})::in,
            maybe_error(array({int,int,int}))::out) is det.

terms_to_palette([],TmpResult, ok(ResultArray)) :-
   list.reverse(TmpResult, ReversedList),
   array.from_list(ReversedList, ResultArray).

terms_to_palette([Term|Rest],TmpResult,Result) :-
   (if Term = functor(atom("single"),
                     [functor(integer(R),_,_),
                      functor(integer(G),_,_),
                      functor(integer(B),_,_)],
                     _) then
       terms_to_palette(Rest, [{R,G,B}|TmpResult], Result)
     else
      (if Term = functor(atom("range"),[
                            functor(atom("from"),
                                    [functor(integer(R1),_,_),
                                     functor(integer(G1),_,_),
                                     functor(integer(B1),_,_)],_),
                            functor(atom("to"),
                                    [functor(integer(R2),_,_),
                                     functor(integer(G2),_,_),
                                     functor(integer(B2),_,_)],_),
                            functor(integer(Count),_,_)
                         ], _) then
           int_interpolate_funcs(R1, R2, 1, Count, _, R2RFunc),
           int_interpolate_funcs(G1, G2, 1, Count, _, G2GFunc),
           int_interpolate_funcs(B1, B2, 1, Count, _, B2BFunc),
           gen_colors_for_range(1, Count, R2RFunc, G2GFunc, B2BFunc, [], RangeList),
           list.append(TmpResult, RangeList,  NewTmpResult),
           terms_to_palette(Rest, NewTmpResult, Result)
       else
           Result = error("Problem reading palette configuration"))
).

Given the following configuration:

...
   palette(
       range(from(20,244,100), to(200,0,56), 15),
       single(0,0,0)
...

We can generate the following palette:

1. {20, 244, 100}
2. {32, 226, 96} 
3. {45, 209, 93} 
4. {58, 191, 90} 
5. {71, 174, 87} 
6. {84, 156, 84} 
7. {97, 139, 81} 
8. {110, 122, 78} 
9. {122, 104, 74} 
10. {135, 87, 71} 
11. {148, 69, 68}
12. {161, 52, 65} 
13. {174, 34, 62} 
14. {187, 17, 59}
15. {200, 0, 56}
16. {0, 0, 0}