The Purpose of the Project is to design a function that tells difference between two given expressions and denotes the changes that need to be made to reference expression(expr_1) to make it appear same as another expression (expr_2) and produce the same evaluation. The approach involves visualizing these expressions as trees and record these differences in expression as a list of “Insert”, “Delete” and “ReplacePart” operations which on being applied to reference expression(expr_1) results in the other expression(expr_2).
ExpressionDifference Definition
ExpressionDifference Definition
The Problem of identifying Differences in Expressions has a very large scale application, as working with large expressions in Wolfram can make code look messy . Any piece of code should be able to clearly demonstrate what it' s doing and should be clearly distinguishable . The ExpressionDifference Function does the same . It clearly demonstrates how one expression can be converted into other expression with the use of Insert, ReplacePart and Delete operations . We explored that while working with expressions in Wolfram, sometime it becomes difficult to point out the differences between 2 expressions . Hence, ExpressionDifference solves this problem .
Variables:
Variables:
◼
The argument “expr1_” and “expr2” here are the arguments of the ExpressionDifference Function on which the operations are performed. The expression “expr1_” is the reference expression on which the differences obtained will be applied in order to obtain expression “expr2”.
◼
Variable “seq” contains the “SequenceAlignment” of the (Arguments of a function)/(list) or Head of the function depending upon the matching TestCases.
◼
“diff” is an empty list in which after obtaining the differences between the two expressions(expr1_,expr2_) the differences will be appended in this list in sequential order.
◼
“count” variable is a pointer to each and every element of the expression. In case there’s a difference between the two expression it tells the position where the difference exactly needs to be applied with respect to expression “expr1_”.
Code:
Code:
ExpressionDifference[expr1_, expr2_]:= Module[ {seq,diff={}, count=0}, (*Module Variables*) (*Checking if the two expressions are different or not.*) If[MatchQ[expr1, expr2]==True, Return[{}]]; (*Checking if the given input expression is an AtomQ or not.*) If[AtomQ[expr1] && AtomQ[expr2], AppendTo[diff, Replace[_ -> expr2]]; Return[diff] ]; (*Evaluating the Sequence "seq" using SequenceAlignment Operation on the given expression depending upon the DelayedRule of Matching Condition.*) seq = Replace[{expr1,expr2}, {xHead_[xe___], yHead_[ye___]}:> If[xHead === yHead, count++; SequenceAlignment[{xe}, {ye}] , AppendTo[diff, ExpressionDifference[xHead, yHead]]; count++; SequenceAlignment[{xe}, {ye}] ] ]; (*Mapping through each and every element of the expresssion and Appending the operations that need to be performed on expression "expr1" in list "diff*) Map[Function[e, Replace[e, Except[{{___}, {___}}]:> count = count + Length[e] , {{}, e2_}:> AppendTo[diff, Insert[e2, count]]; count = count + Length[e2] , {e1_, {}}:> AppendTo[diff, Delete[count]]; , {e1_, e2_}:> Do[ AppendTo[diff, ReplacePart[count->common]]; count++; , {common, e[[2, ;;Min[Length[e[[1]]], Length[e[[2]]]]]]} ]; If[Length[e1] > Length[e2], Do[AppendTo[diff, Delete[count]], Length[e[[1]]] - Length[e[[2]]]], Do[AppendTo[diff, Insert[e2[[count]],count]]; count++, Subtract[Length[e[[2]]], Length[e[[1]]]]] ] ]; ], seq]; Return[diff]; (*Returning the List of Differences between the two expressions*) ]
Understanding Output Patterns:
Understanding Output Patterns:
Basics and Examples
Basics and Examples
Example 1:
Example 1:
Example 2:
Example 2:
Example 3:
Example 3:
In[]:=
ExpressionDifference[Sin[x],Sin[y]]
Out[]=
{ReplacePart[1y]}
Example 4:
Example 4:
Example 5:
Example 5:
In[]:=
ExpressionDifference[{1,2,3},{1,"a",2,"b",3}]
Out[]=
{Insert[{a},2],Insert[{b},4]}
Example 6:
Example 6:
Example 7:
Example 7:
In[]:=
ExpressionDifference[f[x,y],g[x]]
Out[]=
{{Replace[_g]},Delete[2]}
Example 8:
Example 8:
In[]:=
ExpressionDifference[Plus[Log[3x+y],5],Times[100,Times[x,2]]]
Out[]=
{{Replace[_Times]},ReplacePart[1200],ReplacePart[2x]}
Example 9:
Example 9:
Example 10:
Example 10:
Example 11:
Example 11:
Possible Issues:
Possible Issues:
Applying ExpressionDifference on Large Expressions may not work :
Concluding remarks
Concluding remarks
◼
This version of ExpressionDifference fails to deal with cases figuring out the difference in the long expressions which involve recursive implementation of ExpressionDifferecne though it completely works fine for shorter expressions, and hence the recursive case still needs to be worked upon.
◼
For text, it’s comparatively straightforward to find and indicate minimal changes. The idea is to develop an approach that involves figuring out how to do this for general symbolic expressions and figure out which changes can automatically be merged in a 3-way merge process.
◼
The Minimum Tree Distance Approach is one of the possible ways to solve the problem, where we figure out the minimum number of operations that we need to perform on any expression “expr1” to convert it into “expr2”. In this way, we could figure out the number of changes, and then we can perform operations like Insert, ReplacePart and Delete accordingly on the given expressions.
◼
Another approach involves Hashing of the expression tree and its branches and comparing the hash obtained for each branch with another expression to realize what’s the difference in the trees and accordingly suggest the necessary changes to the given expression.
◼
The Future Scope of this Project involves developing with Functions like “DifferenceApply” and “DifferenceVisualize.” “DifferenceApply” would apply a List of differences to expression “expr1” to convert it into another expression “expr2” and “DifferenceVisualize” would show what’s different between the two expressions.
Acknowledgment
Acknowledgment
◼
Connor Gray(Mentor)
◼
Carlos Muñoz (TA)
◼
Silvia Hao (TA)
References
References