From LALR(1) to LL(k)

I, Pedro Faria and Jose Pedro Silva have been working on a LALR to LL conversor. Our idea was to discover the problems involved in this type of automatic conversion.
Our main goal here was to receive an LALAR(1) grammar and produce an LL(k) one. As a test case we receive an Yacc and produce ANTLR.
For the purpose of testing we used the LogoLISS grammar, a language inspired in LOGO programming language and developed in my university to school grammars and program transformation.

The main Yacc grammar was kind of a big one, here it is:

Liss            : PROGRAM IDENT '{' Body '}'
                ;
Body            : DECLARATIONS Declarations
                     STATEMENTS Statements
                ;
Declarations    : Declaration
                | Declarations Declaration
                ;
Declaration     : Variable_Declaration
                ;
Variable_Declaration : Vars SETA Type ';'
                     ;
Vars        : Var
            | Vars ',' Var
            ;
Var         : IDENT Value_Var
            ;
Value_Var   :
            | '=' Inic_Var
            ;
Type        : INTEGER
            | BOOLEAN
            | ARRAY SIZE NUM
            ;
Inic_Var    : Constant
            | Array_Definition
            ;
Constant    : '(' Sign NUM ')'
            | TRUE
            | FALSE
            ;
Sign        :
            | '+'
            | '-'
            ;
Array_Definition  : '[' Array_Initialization ']'
                  ;
Array_Initialization  : Elem
                      | Array_Initialization ',' Elem
                      ;
Elem        : Sign NUM
            ;
Statements      : Statement
                | Statements Statement
                ;
Statement   : Turtle_Commands
            | Assignment
            | Conditional_Statement
            | Iterative_Statement
            ;
Turtle_Commands  : Step
                 | Rotate
                 | Mode
                 | Dialogue
                 | Location
                 ;
Step     : FORWARD Expression
         | BACKWARD Expression
         ;
Rotate   : RRIGHT
         | RLEFT
         ;
Mode     : PEN UP
         | PEN DOWN
         ;
Dialogue : Say_Statement
         | Ask_Statement
         ;
Location : GOTO NUM ',' NUM
         | WHERE '?'
         ;
Assignment      : Variable '=' Expression
                ;
Variable        : IDENT Array_Acess
                ;
Array_Acess     :
                | '[' Single_Expression ']'
                ;
Expression      : Single_Expression
                | Expression Rel_Op Single_Expression
                ;
Single_Expression  : Term
                   | Single_Expression Add_Op Term
                   ;
Term        : Factor
            | Term Mul_Op Factor
            ;
Factor      : Constant
            | Variable
            | SuccOrPred
            | '(' '!' Expression ')'
            | '(' '+' Expression ')'
            | '(' '-' Expression ')'
            | '(' Expression ')'
            ;
Add_Op      : '+'
            | '-'
            | OU
            ;
Mul_Op      : '*'
            | '/'
            | E
            | MULTMULT
            ;
Rel_Op      : IGUAL
            | DIF
            | '<'             | '>'
            | MENORIGUAL
            | MAIORIGUAL
            | IN
            ;
SuccOrPred  : SuccPred IDENT
            ;
SuccPred    : SUCC
            | PRED
            ;
Say_Statement  : SAY '(' Expression ')'
               ;
Ask_Statement  : ASK '(' STRING ',' Variable ')'
               ;
Conditional_Statement : IfThenElse_Stat
                      ;
Iterative_Statement : While_Stat
                    ;
IfThenElse_Stat     : IF Expression THEN '{' Statements '}' Else_Expression
                    ;
Else_Expression     :
                    | ELSE '{' Statements '}'
                    ;
While_Stat     : WHILE '(' Expression ')' '{' Statements '}'
               ;

This is a toy grammar to help students to understand and get a deep knoledge of some fundamental types of productions in grammars.
The kind of texts this grammar is able to analyse are:

PROGRAM logolissExample {
    DECLARATIONS
    x = (100) , y -> Integer ;
    z -> Boolean ;
    w = TRUE -> Boolean ;
    STATEMENTS
        FORWARD x
        RRIGHT
        y = (100)
        FORWARD e
        RRIGHT
        x = x - (100) + (20)
        FORWARD x + (100)
        RRIGHT
        FORWARD (100)
}

Rules

After some time thinking about this problem we tried to solve the left recursion problem. ANTLR does not know how to handle with left recursion, so we must use the EBNF support to translate this productions.

Grammar rules in BNF provide for concatenation and choice but no specific operation equivalent to the * of regular expressions are provided. In Yacc the only way we get repetition is using the following pattern:

A : A a | a ;

We call this kind of rules a left recursive rule.

So, we discover this two generalized rules to remove left recursion in Yacc grammars (click on the image to expand):

Implementation

So, we start right over the implementation of the conversor. We used Yapp because lately we have been using a lot of Perl, so we are want to get deeper into Perl packages.

We start to implement the definition of a Yacc grammar in Yapp:

productions : production             
            | productions production 
            ;
production  : nonTerminal ':' derivs ';' 
            ;
derivs      : nts            
            | derivs '|' nts 
            |
            ;
nts         : nt     
            | nts nt 
            ;
nt          : terminal    
            | nonTerminal 
            | sep         
            ;
terminal    : STRING_TERMINAL     
            ;
nonTerminal : STRING_NON_TERMINAL
            ;
sep         : SEPARATOR 
            ;

And we move along to represent this information in a structure. We chose an peculiar structure to help us processing it.
This is the structure defined as Haskell types:

type Grammar = [Production]
type Production = HashTable ProductionName [Derivation]
type Derivation = [HashTable NTS Type]
type Type = String
type NTS = String

Easy to find stuff, easy to implement in Perl 🙂
So, this is our Yapp grammar again but this time with semantic actions:

productions : production             { return $_[1]; }
            | productions production {
                                       push @{$_[1]},@{$_[2]};
                                       return $_[1];
                                     }
            ;

production  : nonTerminal ':' derivs ';' { return [ { $_[1] => $_[3] } ]; }
            ;

derivs      : nts            { return [$_[1]]; }
            | derivs '|' nts {
                               push @{$_[1]},$_[3];
                               return $_[1];
                             }
            |                { return [[ { 'epsilon' => 'epsilon' } ]]; }
            ;
nts         : nt     { return $_[1]; }
            | nts nt {
                       push @{$_[1]},@{$_[2]};
                       return $_[1];
                     }
            ;
nt          : terminal    {
                            return [ { $_[1] => 'terminal' } ];
                          }
            | nonTerminal {
                            return [ { $_[1] => 'nonTerminal' } ];
                          }
            | sep         {
                            return [ { $_[1] => 'sep' } ];
                          }
            ;
terminal    : STRING_TERMINAL     {
                                    return $_[1];
                                  }
            ;
nonTerminal : STRING_NON_TERMINAL {
                                    return $_[1];
                                  }
            ;
sep         : SEPARATOR           {
                                    return $_[1];
                                  }
            ;

After we had this structure filled in we applied the two rules shown before and we get rid of left recursion for good.

So, after we process the following grammars with our transformer:

a   : a B C
    | //nothing
    ;

expr : expr "+" expr
     | expr "-" expr
     | expr "*" expr
     ;

We get:

a   : (B C)*
    ;

expr : ( "+" expr)+
     | ( "-" expr)+
     | ( "*" expr)+
     ;

You can see all the code produced (including makefiles) in my github repo.

Other rules

We have noticed that only removing the left recursion makes this grammar work in ANTLR.
We are aware that to fully convert an LALR grammar to LL we need one other step: Left Factoring.

Because our LL system is lookahead we does not have to mind about ambiguous grammars.
Examples like this are not a problem for our destination system.

expr: T A B
    | T C D
    ;

However if our destination grammar was LL(1) we needed to convert this to it’s EBNF form.

Lexer

We also translated the Lex used in flex to ANTLR. The main problem here is that we used only matching functions in Perl and we do not used any grammar for this effect.
The main problem is that the regular expressions in flex are different to regexps in ANTLR.
You can see the Perl code for yourself here.
But you if you want to do a translation from flex to ANTLR better you define a flex grammar.

Permutations in pure functional ActionScript

I have been working with ActionScript3 and Flex to do apps for Android. I have never used this languages before, so in the beginning I was with my hart open to understand this languages, specially ActionScript3, the only thing I knew about ActionScript is that is used a lot for flash animations and that was it.

At a first glance ActionScript3 seemed to me to be a standard object oriented language, but after I grasp a little bit more and I found that the version 3 has a lot of functional flavor in it.
I started to find more and more examples of it: definition of high-order functions, map, filter and so…

I have to say that I deeply continue to prefer the Haskell notation with concern to high order and the 2 functions, but the point of ActionScript3 was never be totally functional, but incorporate some features of it.

So, outside of work I remember the beautiful definition of permutations in Haskell and I start try to implement the same algorithm in ActionScript3.

perms xs = [x:ps | x <- xs, ps <- perms (xs\\[x])]

For the non Haskell programmers I will explain: We receive the list and here use the list comprehension notation, basically we can translate a list comprehension in the form:
as a function this way . So, that’s basically the first part of our definition. The second one is the cartesian product of the two lists.
Finally the definition of the function is simply the exclusion of the element from the list .

So, I first came out with this solution:

public static function perms(xs:Array):Array {
    if(xs.length == 0) {
        return [[]];
    }   
    return xs.map(
        function(x:*,index:uint,array:Array):* {
            var ret:Array = new Array();
            var p:Array = perms( exclude(xs,x) );
            for(var j:uint=0 ; p[j] ; j++) {
                var ps:Array = p[j] as Array;
                ps.unshift(x);
                ret.push(ps);
            }   
            return ret;
        }   
    );  
}

public static function exclude(xs:Array, elem:*):Array {
    return xs.filter(
        function(item:*,index:uint,array:Array):Boolean { return item != elem; }
    );  
}

I had to define the function, because it does not exist in ActionScript3 and I understand that.
The code is not as pretty as you expect to be in Haskell or other functional language, but is pretty much the same, as you ca see in the following definition, where I only use .

public static function permss(xs:Array):Array {
    if(xs.length == 0) {
        return [[]];
    }
    return xs.map(
        function(x:*,index:uint,array:Array):* {
            var p:Array = permss( exclude(xs,x) );
            return p.map(
                function(y:*,_:uint,__:Array):* {
                    var ps:Array = y as Array;
                    ps.unshift(x);
                    return ps;
                }
            );
        }
    );
}
public static function exclude(xs:Array, elem:*):Array {
    return xs.filter(
        function(item:*,index:uint,array:Array):Boolean { return item != elem; }
    );
}

Correct sorting with Frama-C and some thoughts on Formal Methdos

A couple of years ago, during my masters on Formal Methods I have been working with automatic provers and I also used Frama-C, this is a tool that allow the user to prove C code directly in the source code, using a special notation in the comments, called ACSL notation.

Frama-C allows you to make two kinds of proofs, security and safety ones. The safety ones are related with arrays index out of bounds access, and so. This kind of proofs are related to the language itself and they are easy to do if you use loop invariants, pre and post conditions.
If you use a high level language, like JAVA you won’t have almost none safety problems.
Because C is too close to machine level code, we can do things that we do not intend (or maybe we do and we use C exactly because it allows this kind of things). For example:

// foo.c file
#include <stdio.h>

int main() {
    char *a = "I like you";
    char *b = "I hate you";
    
    if(&a < &b) a = *(&a + 1); 
    else        a = *(&a - 1); 

    printf("%s\n", a); 
}

As you can see, I never used the variable for nothing, just have declared it. And the result is:

[ulissesaraujocosta@maclisses:c]-$ gcc -o foo foo.c 
[ulissesaraujocosta@maclisses:c]-$ ./foo
I hate you

This lack of security of language C is one of the reasons we need to write safety statements. Of course this kind of things is why C is so fast and powerful, the person in charge is always the programmer. If you are interested in this kind of tricks and want to understand more about this and smashing the stack and so, feel free to read more posts in my blog about this subject.

The other kind of statements (security ones) are related to the functionality of the program and that’s basically where the problem or the effort is, I will talk about this later on. First let’s see the algorithm and the implementation in C.

Code

The algorithm I use here is just a simple example. I used bubble sort, this is a sort algorithm not very efficient, but it uses none more memory then the needed to store the structure you want to sort.
To get a visual understanding of the algorithm (and to see it inefficiency) check out this youtube video.

This is the implementation of the algorithm:

void swap(int *i, int *j) {
    int tmp = *i;
    *i = *j;
    *j = tmp;
}

void bubbleSort(int *vector, int tam) {
    int j, i;
    j = i = 0;
    for(i=0; i<tam; i++) {
		for(j=0; j<tam-i-1; j++) {
            g_swap = 0;
            if (vector[j] > vector[j+1]) {
                swap(&vector[j],&vector[j+1]);
            }
        }
    }
}

Pre, Post conditions and thinking formally

So, as you can see in the video (or in the code) the algorithm is pretty much simple, we pick the element cross the array times and for each element we compare with , this times.

We have as pre conditions: The size of the must be greater than zero, and all the positions in that vector exists, so in Frama-C we use the , where and are indexes of the to say that all elements exist.

Ans as pos conditions we must ensure that the array is sorted ( I will talk predicate this later).
You may think that this by itself is enough to make a complete proof, but you are wrong. Image that my function clear all the elements in the array and fill the array with , our code will be proved and its wrong!

So, we need to say more… First thing that can pop to your head is OK, we will say that we have the same numbers in the beginning and in the end and you write this:

In fact this is closer (not yet right), imagine that you give as input:
. If your code returns (we miss the repeated ) the code will be proved.
So, the solution if to make a predicate and prove for the multi set.
So, this are the post conditions:

Frama-C is so cool because for example at the pos condition if we want to refer to the state in the beginning (before call the function) we use and if we want to refer to the moment after the call we heave the keyword, remember we are at the post condition, so this wil be executed in the end (so means the end of the function call).

Predicates

So, here is the predicate. Predicates receive a state and the parameters (just like a function) and they return bool values (true or false). Inside we use regular ACSL notation. Here I define that for an array to be sorted each element must be less or equal to the next one.

/*@ predicate Sorted{L}(int a[], integer l, integer h) =
  @   \forall integer i; l <= i < h ==> a[i] <= a[i+1];
  @*/

The is defined inductively, so we receive two states and and the array and the range where we want to permute.
We write multiple rules for the permutation, reflection, symmetry, transitivity and finally the most important one, the . So basically here we say that a permutation is a set of successive swaps.

/*@ inductive Permut{L1,L2}(int a[], integer l, integer h) {
  @  case Permut_refl{L}:
  @   \forall int a[], integer l, h; Permut{L,L}(a, l, h) ;
  @  case Permut_sym{L1,L2}:
  @    \forall int a[], integer l, h;
  @      Permut{L1,L2}(a, l, h) ==> Permut{L2,L1}(a, l, h) ;
  @  case Permut_trans{L1,L2,L3}:
  @    \forall int a[], integer l, h;
  @      Permut{L1,L2}(a, l, h) && Permut{L2,L3}(a, l, h) ==>
  @        Permut{L1,L3}(a, l, h) ;
  @  case Permut_swap{L1,L2}:
  @    \forall int a[], integer l, h, i, j;
  @       l <= i <= h && l <= j <= h && Swap{L1,L2}(a, i, j) ==>
  @     Permut{L1,L2}(a, l, h) ;
  @ }
  @
  @ predicate Swap{L1,L2}(int a[], integer i, integer j) =
  @      \at(a[i],L1) == \at(a[j],L2)
  @   && \at(a[j],L1) == \at(a[i],L2)
  @   && \forall integer k; k != i && k != j ==> \at(a[k],L1) == \at(a[k],L2);
  @*/

So, as you can see the bubble sort function itself have 18 lines of code, and in the end with the annotations for the proof we end with 90 lines, but we proved it!

Thoughts

My main point here is to show the thinking we need to have if we want to prove code in general. Pick what language you want, this is the easiest way you will have to prove software written in C. Sometimes if your functions are too complex you may need to prove it manually. The problem is not on the Frama-C side, Frama-C only generates the proof obligations to feed to automatic provers, like Yices, CVC3, Simplify, Z3, Alt-Ergo and so.

My point here is to show the cost of proving software. Proving software, specially if the language is too low level (like C – you need to care about a lot more things) is hard work and is not easy to a programmer without theoretical knowledge.
On the other side, you end up with a piece of software that is proved. Of course this proof is always requirements oriented, ny that I mean: if the requirements are wrong and the program is not doing what you expect the proof is along with that.
I do not stand to proof of all the code on the planet, but the proper utilization of FM (formal methods) tools for critical software.

I steel been using Frama-C since I learned it in 2009, nowadays I use it for small critical functions (because I want, I’m not encouraged to do so) and I have to say that the use of FM in the industry is far. As I told you Frama-C is the easiest automatic proof tool you will find at least that I know.

Talking with Marcelo Sousa about the use of FM in industry, we came to the conclusion that the people that are making this kind of tools and have the FM knowledge don’t make companies. I think if more brilliant people like John Launchbury make companies, definitely FM will be more used.

Source code

Here is all the code together if you want to test it:

// #include <stdio.h>

/*@ predicate Sorted{L}(int a[], integer l, integer h) =
  @   \forall integer i; l <= i < h ==> a[i] <= a[i+1];
  @
  @ predicate Swap{L1,L2}(int a[], integer i, integer j) =
  @      \at(a[i],L1) == \at(a[j],L2)
  @   && \at(a[j],L1) == \at(a[i],L2)
  @   && \forall integer k; k != i && k != j ==> \at(a[k],L1) == \at(a[k],L2);
  @*/

/*@ inductive Permut{L1,L2}(int a[], integer l, integer h) {
  @  case Permut_refl{L}:
  @   \forall int a[], integer l, h; Permut{L,L}(a, l, h) ;
  @  case Permut_sym{L1,L2}:
  @    \forall int a[], integer l, h;
  @      Permut{L1,L2}(a, l, h) ==> Permut{L2,L1}(a, l, h) ;
  @  case Permut_trans{L1,L2,L3}:
  @    \forall int a[], integer l, h;
  @      Permut{L1,L2}(a, l, h) && Permut{L2,L3}(a, l, h) ==>
  @        Permut{L1,L3}(a, l, h) ;
  @  case Permut_swap{L1,L2}:
  @    \forall int a[], integer l, h, i, j;
  @       l <= i <= h && l <= j <= h && Swap{L1,L2}(a, i, j) ==>
  @     Permut{L1,L2}(a, l, h) ;
  @ }
  @*/

/*@ requires \valid(i) && \valid(j);
  @ //assigns *i, *j; //BUG 0000080: Assertion failed in jc_interp_misc.ml
  @ ensures \at(*i,Old) == \at(*j,Here) && \at(*j,Old) == \at(*i,Here);
  @*/
void swap(int *i, int *j) {
    int tmp = *i;
    *i = *j;
    *j = tmp;
}

/*@ requires tam > 0;
  @ requires \valid_range(vector,0,tam-1);
  @ ensures Sorted{Here}(vector, 0, tam-1);
  @ ensures Permut{Old,Here}(vector,0,tam-1);
  @*/
void bubbleSort(int *vector, int tam) {
    int j, i;
    j = i = 0;
    //@ ghost int g_swap = 0;

  /*@ loop invariant 0 <= i < tam;
    @ loop invariant 0 <= g_swap <= 1;
    //last i+1 elements of sequence are sorted
    @ loop invariant Sorted{Here}(vector,tam-i-1,tam-1);
    //and are all greater or equal to the other elements of the sequence.
    @ loop invariant 0 < i < tam ==> \forall int a, b; 0 <= b <= tam-i-1 <= a < tam ==> vector[a] >= vector[b];
    @ loop invariant 0 < i < tam ==> Permut{Pre,Here}(vector,0,tam-1);
    @ loop variant tam-i;
    @*/
    for(i=0; i<tam; i++) {
      //@ ghost g_swap = 0;
      /*@ loop invariant 0 <= j < tam-i;
        @ loop invariant 0 <= g_swap <= 1;
        //The jth+1 element of sequence is greater or equal to the first j+1 elements of sequence.
        @ loop invariant 0 < j < tam-i ==> \forall int a; 0 <= a <= j ==> vector[a] <= vector[j+1];
        @ loop invariant 0 < j < tam-i ==> (g_swap == 1) ==> Permut{Pre,Here}(vector,0,tam-1);
        @ loop variant tam-i-j-1;
        @*/
		for(j=0; j<tam-i-1; j++) {
            g_swap = 0;
            if (vector[j] > vector[j+1]) {
                //@ ghost g_swap = 1;
                swap(&vector[j],&vector[j+1]);
            }
        }
    }
}

/*@ requires \true;
  @ ensures \result == 0;
  @*/
int main(int argc, char *argv[]) {
    int i;
    int v[9] = {8,5,2,6,9,3,0,4,1};

    bubbleSort(v,9);

//     for(i=0; i<9; i++)
//         printf("v[%d]=%d\n",i,v[i]);

    return 0;
}

If you are interested in the presentation me and pedro gave at our University, here it is:

Lines of Code and related lines-oriented-statistics with Perl

A project I’m involved right now is making a Static code analyzer. The main goal is to produce a RoR front-end webapp with the capability to submit code ad analyze it statically. Our main goal languages are C/C++, but we will attach other tools to do some work for other languages. For Static I mean without the need to run the program. One thing we will never be able to answer with Static analysis is the behavior of the program, but we can answer some things that with dynamic analysis we can not, so there is not such a think like one is better or more complete than the other.

The RoR front-end is almost done and quick contribution I gave was a Perl script that receives a folder as input and analyzes all the source code available inside the folder (recursive). You can find the README.markdown under the same folder.
This analysis is just oriented to quantity of lines of code.

How to use

Well, if you don’t want to read the README.markdown file and experiment the script I will show you the output and the command you need to produce this images.

So, by default you only need to say the input folder and the output prefix name for the images, like so we an say:

[ulissesaraujocosta@maclisses:trab1]-$ perl count.pl -open ../../../Static-Code-Analyzer/ -out work

This will produce the following 3 images (click on the images to enlarge):

By default the script always produce this 3 images: number of files per language, number of lines per language and the ratio between them (the average of lines per file, per language).

We can also see this values in percentage, related to overall project (folder).
Image number 3 will be the same, because does not make sense ratio percentage.

[ulissesaraujocosta@maclisses:trab1]-$ perl count.pl -open ../../../Static-Code-Analyzer/ -out work_percent -percent

And my favorite, produce an image with a overall picture of the percentage use of each language on the project.

[ulissesaraujocosta@maclisses:trab1]-$ perl count.pl -open ../../../Static-Code-Analyzer/ -out work_All -all

With this script you can also generate pie charts, by default it uses bars charts, please read the README.markdown for more information.

How to improve and support more languages?

If you want to improve the script feel free to fork on github and maybe we can discuss more about the script.
To support more languages you just have to add one more entrance in the hashtable and write:

extension => {"nrFiles" => 0, "nrLines" => 0, "comments" => function_to_catch_comments, "nrComments" => 0, "percentageNrFiles" => 0, "percentageNrLines" => 0, "percentageNrComments" => 0}

This is an example of the entrace for C++:

"cpp"  => {"nrFiles" => 0, "nrLines" => 0, "comments" => sub { return shift =~ m/(\*(.|\n|\r)*?\*)|(^[ \t\n]*\/\/.*)/; },    "nrComments" => 0,
                         "percentageNrFiles" => 0, "percentageNrLines" => 0, "percentageNrComments" => 0
                        },

This is a simple presentation I gave about the module I used: GD::Graph

A* search algorithm

Time to talk about efficiently pathfinding and graph traversal algorithms. The first algorithm related with graphs pathfinding I learned was Dijkstra’s algorithm and I remember the feeling for learning how to find the shortest path (minimal cost to be generic) in a graph, it was amazing to me, so that I learned a few more and did a simple academic GPS core system.

Dijkstra’s algorithm is truly beautiful, but unfortunately the complexity it too high to be considered time efficient.

If you want to go from point to Dijkstra’s wil search all the surrounding nodes, as you can see in this image:

So I start to find more efficient implementations for the pathfinding problem and I discover A Star.

A Star algorithm

I find this algorithm in wikipedia, and I will paste it here because there are a few things I want to explain.

function A*(start,goal)
     // The set of nodes already evaluated.
     closedset := the empty set
     // The set of tentative nodes to be evaluated.
     openset := set containing the initial node
    // The map of navigated nodes.
     came_from := the empty map                 
    // Distance from start along optimal path.
     g_score[start] := 0                        
     h_score[start] := heuristic_estimate_of_distance(start, goal)
    // Estimated total distance from start to goal through y.
     f_score[start] := h_score[start]           
     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from, came_from[goal])
         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)
             if y not in openset
                 add y to openset
                 tentative_is_better := true
             elseif tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false
             if tentative_is_better = true
                 came_from[y] := x
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_estimate_of_distance(y, goal)
                 f_score[y] := g_score[y] + h_score[y]
     return failure
 
 function reconstruct_path(came_from, current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node

If you are familiarized with Dijkstra’s algorithm you probably noticed a lot of coincidences in the algorithm. You are right!
So, we have some structures to use: the is the set of nodes already evaluated by A Star, containing the nodes being evaluated, being the commulative distance to this node, being the heuristic result for this node (I will explain this in a minute) and being the sum of and .

A good thing about A Star is the nodes it needs to search until find the Best-First-Search path:

Seems good right? All the juice of this algorithms lies on the heuristic function, I like the result of the Manhattan distance, but you can read this blog post and find out more about this subject.
Basically this heuristic is empirical knowledge, this particular Manhattan distance calculates the distance from point to point in a grid.

I tried to use it in a Geometric graph and it worked fine too!

Point of view

I’m particularly interested in optimizing this algorithm as much as possible and will be doing that using C++.
So, I spend 30 minutes observing the code and I was already very familiarized with Dijkstra’s. I think as a Software Engineer you have to find good algorithms to your problem, deeply understand them, but your job is not done after that! After find a good solution and understand it to the point you are able to explain it to a non-CS person you have to *observe* the code, talk with it and, believe me, don’t make the literal implementation of it, It will be slow, or at least it probably could be more efficient!

So, let’s forget about the problem this algorithm solves and try to identify inefficient chunks in the algorithm. The first thing that cames to my mind is: we need to have a bunch of structures to keep a lot of node related information, a lot of vectors, sets and so.

So, let’s identify what I mean by that:

function A*(start,goal)
...
     while openset is not empty
...
         x := the node in openset having the lowest f_score[] value
...
         foreach y in neighbor_nodes(x)
...
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_estimate_of_distance(y, goal)
                 f_score[y] := g_score[y] + h_score[y]

With this chunk of code I want to highlight that we are iterating throw all neighbors for each belongs to , then we get the minimum from and change the arrays for .

The first thing hitting me is, I can make a MinHeap and I can keep all the information for each in the node itself, like so I won’t be wasting time in accessing positions in a set and I just make a question to the node object.

So, I start to put all this information in the nodes side and keep only track of the locally created minHeap. This is the result:

LinkedList<Edge*> AStar::findPath(Node* start, Node* goal) {
    LinkedList<Edge*> ret;
    MinHeap<Node*, Comparator> openSet;
    bool tentative_is_better = false;

    float h = heuristic(start,goal);

    start->setStatus(NODE_OPEN);
    start->getOrSetScore().set(NULL, h,0,h);
    openSet.insert(start);

    while(!openSet.isEmpty()) {
        Node x = openSet.getMin();
        AStarScore & xScore = x->getOrSetScore();

        if(x == goal) return process(ret,x);
        openSet.removeMin();
        x->setStatus(NODE_CLOSE);
        ArrayList<Edge> & neighbors = x->getEdges();
        for(int i = 0; i < neighbors.getLength (); i++) {
            Node *y = neighbors [i]->getDstNode();
            AStarScore & yScore = y->getOrSetScore();
            GeoNodeStatus yStatus = y->getStatus();

            if(yStatus == NODE_CLOSE) {
                continue;
            }   

            float tentative_g_score = xScore.g_score + x->getEdge(y)->getCost();

            if(yStatus != NODE_OPEN) {
                y->setStatus(_version,GEONODE_OPEN);
                tentative_is_better = true;
            } else if(tentative_g_score < yScore.g_score) {
                tentative_is_better = true;
            } else {
                tentative_is_better = false;
            }   
            if(tentative_is_better) {
                yScore.parent = x;
                yScore.g_score = tentative_g_score;
                yScore.h_score = heuristic(y,goal);
                yScore.f_score = yScore.g_score + yScore.h_score;
                openSet.insert(y);
            }
        }
    }
    return process(ret,goal);
}

Where is the function that iterate throw the nodes, starting with and go the parent until node and construct the path in reverse order, from to .

One side note, A star is so close to Dijkstra, that if you make you function return always zero, A star will work just like Dikjstra (the first image).

Basically the ideas I want to transmit here is the A star algorithm, it implementation and (the most important one) the process of how to look to an algorithm. Summarizing I think a Software Engineer could not just implement algorithms and substitute all the words in the algorithm for in C++ and so. I think we should look for an algorithm as a valuable aid and if we convert it to code we must improve it. Ultimately copying an algorithm to code is a good opportunity to leave our personal touch in the code.

Acknowledgments

Images from here.

Memory Leak detector

When you are writing a program and you want it to be able to run for a long period of time or when some procedure is called a times in the lifetime of running program (let tend to infinity) maybe is a good opportunity to make sure all your calls have one call (, in C++).This sounds very natural to any experienced programmer.

Now imagine that you have download some huge chunk of code and you want to call it times, lets say 100 times per second. Maybe the person who wrote the code, did not think about memory management and maybe you do not have the patience to read the huge piece of code. What you need is a memory leak detector.

If you do not have any of these problems might be interested in knowing how to gain millions of euros on the internet.

Here I will show an example of how to write a simple memory leak detector in C++ for C , is trivial to convert it to verify memory leaks in C++.

The main idea is to keep the line number of each we do and then verify if we did , we will accomplish this by redefining the and call, without need to write our own or , thanks to C pre processor.

First we define an entity, this keep all the information we need about each call.

class Entity {
private:
	unsigned int _address;
	unsigned int _line;
public:
	Entity(unsigned int addr, unsigned int line) {
		this->_address = addr;
		this->_line = line;
	}
	unsigned int & getOrSetAddress() {
		return this->_address;
	}
	unsigned int getLine() {
		return this->_line;
	}
};

typedef std::list<Entity *> Memory;
Memory *memory;

I used the standard C++ lists instead of std::vector because I will need to remove and add elements, without the need to call in algorithms module, what bugs me.

Now I will define the function to add elements to our std::list

void InsertOnMalloc(unsigned int addr, unsigned int n) {
	if(!memory)
		memory = new Memory;

	memory->insert(memory->begin(), new Entity(addr,n));
}

Now I will define the function to remove elements to our std::list

void RemoveOnFree(unsigned int addr) {
	if(!memory)
		return;
	for(Memory::iterator it = memory->begin(); it != allocList->end(); it++)
	{
		Entity *entity = *it;
		if(entity->getOrSetAddress() == addr) {
			memory->remove();
			break;
		}
	}
}

The idea so far is to call for each call and for each . After this if we have any element in our we need to print that out, to see which line we do not call .

void ShowLeaks() {
	for(Memory::iterator it = memory->begin(); it != memory->end(); it++)
		std::cout << "Must make free to this malloc call: " << (*it)->getLine() << std::endl;
}

Now, lets do the real juice of this leak detector: here I will modify the call to a regular followed by an insertion, and a call for a regular call followed by removal on our list

#define malloc(p) mallocz((p),__LINE__)
#define free(p) freez((p))

static inline void *  mallocz(unsigned int size, int line) {
	#undef malloc
	void *ptr = (void *)malloc(size);
	#define malloc(p) mallocz((p),__LINE__)
	Insert((unsigned int)ptr, line);
	return(ptr);
};
static inline void  mydelz(void *p) {
	RemoveOnFree((int)p);
	#undef free
	free(p);
	#define free(p) freez((p))
};

Now, if you want to use this “library” in your code, you save it to file and on you code you just import it and then call to show what you forgot to make .