Using Regular Expressions for Program Transformation


I have been investigating the problem of practical code transformation to deal with small changes that have to be made across a large collection of programs in different programming languages. So the problem is not to transform a program entirely but doing small transformations to a large set of programs that too when we have C, Perl, Java etc source programs in that set. This has practical application in software development, code refactoring and testing. A lot of cost savings in software testing is possible if test the suits are well maintained and are automagically transformed using some method. I used a method and published findings on ip.com which is rather a full system explanation of what I described here in 2011 There are some interesting obstacles to transforming programs. I will try to explain as well as understand some of them through this post.

When we want to transform a set of programs in different languages what we are dealing with is a bunch of Context Free Grammars (CFG) implemented using syntax symbols that are a result of 'wild' imagination of authors (wild characters can not be domesticated that is!). The transformation therefore, has to deal with two things: 1) CFG 2) syntax symbols. It is not obvious, but I have worked out after some effort and intuition that best chance to modify these programs is only through full knowledge of each of these CFGs and their syntax. However, we can make some complex changes of practical importance without their knowledge using Regular Expressions (RE).

Regular expressions are nothing but a representation of Finite Automata (FA). From the knowledge of Formal Languages, we know that not all CFGs have corresponding REs. Therefore even partial CFG parsing using REs may be impossible depending on the portion of CFG we are looking to transform. In other words, regex alone can not make some modifications no matter how small the change is. For programmers this would mean, there will always be mismatches for some REs when used across multiple programs (same language). The problem of coming up with a RE to always match patterns across programming languages or in single programming language defined by CFG is not solvable.

It is also tempting to think that, using some specially designed syntax symbols, modification of a program using RE may be possible. Unfortunately as long as what we use is RE we can not modify a language defined by CFG no matter what syntax symbols we use. The problem lies in the grammar, not syntax symbols.

As stated earlier, we can still make many meaningful and useful changes to programs across languages. We used two heuristic approaches successfully (very!):

1) Identify if what needs to be modified (portion) across the programs is an FA. If it is, write a regular expression to modify it. This will not fully succeed because syntax symbols of various languages may make it impossible to identify an FA. Thus this as well will work partially.

2) Identify a subset of CFG that can be matched easily using a set of REs and custom parsing. This can be used to modify the subset of CFG across programs and languages again partially.

If we learn to make better use of successful transformation we can achieve a lot of practical advantages and save labour. For idealists, a plugin can be implemented for all languages in question to program the compiler front end to do the transformation for us. I have written a small interpreter that can accept instructions on what to change in a program. I have called it the Test Mutation Language.

Ragu Kattinakere

Comments

DocJava said…
Is the test mutation language system that you're willing to share with others? I would be keen to give it a go.
thanks!
December 26, 2014 at 3:51 AM
Ragu Kattinakere said…
Hi Douglas, the language is domain specific and the system is customized to our workflow. I wish I could share, my employer has rights on it.

However there is no bar to implement that same outside. You can implement a simple system yourself if you follow the method described in the links above.

Thanks for stopping by.
April 27, 2015 at 9:28 AM
Post a Comment

Popular posts from this blog

How To Manage Contacts in Outlook

Sun's ceo calls it Lookout! But many use it including me. Managing contacts in Outlook is tricky. Here are few things I do when I move. By default all email ids are recorded in a file called Outlook.NK2 which is, by generocity of Microsoft, hidden. These are used to auto fill when we type an emil id. These are not stored in the address book. Its default location is: C:\Documents and Settings\ \ Application Data \Microsoft\Outlook\Outlook.NK2 is your user login id on the computer. Application Data is a folder that is hidden from view. Go to Tools->View and select Show Hidden files. When I move, I copy/backup this file. When I setup outlook on new machine, I zimbly copy the backup file to the default location in the new machine. Address book is a sacred thing. Mine is mostly empty! To manage autofill email address we can use a freeware availale online. It is called NK2View (Download).
Read more

Pageant for Mac - Using Jump Server on Mac

Image
If you use putty on windows, you probably used pageant to store multiple keys, ssh to jump server and then ssh to your work machine. If you ended up on Mac for some reason and you have a production situation, there is no reason to panic. Mac systems have Keychain - a software that manages your keys including ssh keys. There are 3 steps to use it for jumping . 1. Add your ssh keys to Keychain. 2. Create an ssh  config file to access jump terminal 3. Agent forwarding 1. Adding keys If you had ppk/putty keys you need to convert them. If you have ssh keys then you can add them without converting. I had puttygen on my mac. If you were using Windows machine, you can convert ppk keys to ssh key on Windows and then add on Mac. I had two keys - if you have only one that is fine. puttygen user_rsa.ppk -O private-openssh -o user_rsa.key puttygen jump.ppk -O private-openssh -o jump.key If a window pops up then DO NOT hit generate key.  1. Load y...
Read more