I have some experience in machine learning, mainly clustering and classifiers. However, I am somewhat of a newbie when it comes to NLP.
That said I am aware of all the various issues and difficulties involved in processing natural language eg part-of-speech, ambiguity, negation detection etc. I am also aware of certain models to represent text such as bag-of-words and Word vector representation.
Whilst the specific problem I have is a textual problem, it is not to my mind a natural language problem. Instead I need to compare 1000s of files of programming code to determine how similar they are to one another.
Unlike natural language processing where we remove stop-words and we care very much about issues such as ambiguity and the scope of negation etc, with programming code there is no ambiguity, at least not with reserved key words such as "function", "if", "else, "while", "end", nor is there any ambiguity with core mathematical functions and other operators eg "log", "sin", "tanh" etc.
For my problem, we can assume all files are in the same programming language (let's say R) and let's also assume that each programming file contains at most 250 lines of code.
The initial objective is to produce a correlation matrix that shows how similar the code files are to one another.
There are to my mind 2 ways of approaching this:
Quick and simplistic. I propose to remove from each text file:
- All comments as I'm not interested in each developer's individual comments
- All excessive white space, ie remove all formatting ensuring there is only one space between reserved words and blocks of code
This is the only pre-processing I would do in a simplistic solution.
I then propose to use the Doc2Vec model to reduce each file to a single vector and then compare the various vectors to one another by calculating the correlation coefficient.
Does this seem reasonable to people for a very quick and simplistic solution? If not, please advise what other pre-processing you would do and/or what model you would use to represent the files.
More advanced. An immediate flaw with the simplistic solution is that it is too naive. For instance:
If Code A and Code B have exactly the code (ie same functions that perform exactly the same task and all variable and object names are the same) except that Code A's functions are listed in a slightly different order to those listed in Code B's file, then a line-by-line comparison of the two code files will obviously show differences. However, if the code in file B was ``reordered'' so that the functions were in exactly the same order as file A, then there wouldn't be any differences.
Code A and Code B could in logical terms be exactly the same (ie same number of functions that perform logically the same operations and output) except that object, variable and function names are different (after all that is a subjective choice by each coder) then again we would have significant differences. For example, in Code A's file there is a function called MyFunction(a,b) whereas in Code B's file there is a function called CopyMyFunction(x,y). Now if both functions perform exactly the same operations (eg the sum of the two input values) then logically the code is the same - it's just the variable names that are different.
Finally a more complicated version. Suppose there is a function in Code A's file called MyAverage(a,b) that performs the operations, returning as output d:
c = a + b
d = c/2
Suppose in Code B's file there is also a function called MyAverage(a,b) that performs the same calculation but in only one step, ie
c = (a + b)/2
Logically the two functions produce exactly the same output, albeit Code A does it in 2 steps whereas Code B does it in 1 step.
The above are clearly only some examples of the types of issues that could be encountered.
The objective is not to determine whether there has been plagiarism or whether sections of code have been copied from one code file to another. Instead, if a serious error (a bug or logical error) is subsequently found in one code file, then I need a means of identifying how likely that same error occurs in other code files, ie has that bug propagated itself by being copied from file to file?
How would people approach the more advanced problem? For instance, to solve the last problem (ie determining whether two sections of code are logically equivalent) I could see two ways of approaching this:
- Renaming of variables and substitution. So in Code A, as variable c is defined as "a + b", it could be substituted into the expression for variable d with the addition of the brackets. After the substitution, variable d could be renamed as variable c. In this case, Code B would then be the same as Code A.
- Simulation of output. In more complicated function, the above technique may not always work. Instead, if the outputs of the two functions are the same when given the same inputs, can we deduce that the logic of the two must be the same within a certain level of confidence? The problem with this is that simulating millions of inputs would be very time consuming and expensive surely.
Other than the above I've no idea how to approach this problem.
Any thoughts on the approach and/or resources to use?
I am happy to be directed to a good reference or resource on the issue.