Project Proposal

Adding an Analytical Tool as an extension to the Mapcode Development Environment

Organizational Benefit: An Analytical Tool in the Development Environment would facilitate the user to generate a behavior graph of his programs. This would help reduce the number of bugs at the time of development itself and consequently, saves time, effort and cost of the organization in doing the rework. The tool focuses on increasing the reuse of the available information.

Earlier work: Mapcode [1] is a mathematical notation for describing programs and proving their properties using basic mathematics. It has been developed by Prof. K. Viswanath [2]. An interpreter has been designed to support this notation. The idea of adding an Analytical Tool to the Mapcode Environment is the experimental evaluation of my thesis “Need of Analytical Tools in the Programming Environments”. I have designed the tool and am already in the process of implementing it. I have been using ANTLR for creation of syntax trees and also tree pattern matching. The pattern matcher is still in the development stage.

Concept: The Analytical Tool has been designed to use syntax-directed translation since it is visually easy to comprehend and after translation, only the necessary information is retained on which analysis is done. I have taken order of complexity as the property to be analyzed for every Mapcode Program. The tool creates syntax trees for the source programs after compiling the program. I have used pattern matching to automate the transformation of the syntax trees. The Mapcode notation has a range of patterns which occur commonly across almost all programs. These patterns have been captured and incorporated into the tool so that it may automatically check if the syntax tree is matching any of the patterns specified. If pattern matching is successful, the rewrite rules or actions specified corresponding to the patterns is performed and transformation of the syntax tree is done without the need of user interaction. If patterns match is not successful, the tool interacts with the user to perform the transformation of the syntax tree. The need of transformation arises from the fact that the programs written for software are very lengthy and order of complexity only depends on the number of iterations involved in a particular module. We need to analyze only that information which affects the order of complexity of the program. Transformation helps to discard all the unwanted information. After the transformation is performed, new syntax tree is executed and graph is displayed. The graph plots the execution time of the program corresponding to the various input sizes.It provides information about how the execution time varies as the input size increases or decreases and also, to what input size is the program scalable i.e to what input size will the program remain stable and not behave in an unexpected manner. For future use, the transformed syntax tree and the behavior analysis are stored and every time a new transformation is performed, all the stored syntax trees are compared and if anyone matched with the new transformation, the syntax tree is not executed; instead, the analysis is directly taken from the previous execution. Excessive use of pattern matching helps in increased use of reuse.

Future Work: This tool can be extended to include analysis for other properties as well like performance, reliability, accuracy, etc. Every property would have different patterns and different transformations. The tool can also be integrated with a powerful theorem prover like PVS [3] so that the analysis can also be proved for all the inputs of the program instead of testing the program for limited set of inputs. The tool can be extended as a learning tool having its own intelligence so as to minimize the extent of user interaction. It should be able to recognize all the new patterns, store the patterns and corresponding actions performed by the user for the respective patterns or warn the user against an invalid transformation and guide the user through a step-by-step process of what should be done.

Risks/Challenges: The graph displayed by the tool might not be in accordance with the expected output. It might be deficient in many ways and it will need time to make it sophisticated.

Overview of the tool: