As you know I am trying to participate on the last challenge on the blog La Sombra de Dijkstra, where you must provide a program that compares two Fortran IV programs and must determine if both programs are equivalent. I have finished the first component, the Abstract Syntax Tree of the program. This will allow me to run the program creating an interpreter, and also will allow me to analyze the program structure — the complete Abstract Syntax Tree as graph — and make some heuristics on it.
First I want to convert that AST into Lambda Calculus functions to check if both programs are beta equivalent regarding its Lambda Calculus. I know that the program is not functional, and probably I will not find the proper representation, but I want to try it. Then I will try to reduce the graph to the lesser amount of calls, for example, removing duplicate Goto statements, trying to simplify the graph. To do that, and to use the Functional Graph Library (FGL) on the graph analysis, I must implement the Labellable instance for each node to work with each node type directly, rather than using text labels — Show instances for now.
The resulting AST for the first example, where the code can be seen as in this link, is as follows.
The resulting AST for the second example, where the code can be seen as in this link, is as follows.
The main problem is the fact that Fortran IV analyzer should be able to analyze different programs with up to 1000 lines of code. I don’t know if Parsec — the Parser Combinator library that I am using — will be capable to process that amount of code. Probably I will request one of those example files. You can find the source here.
Entries 