Expression Difference
Author
Aman Kumar Dewangan
Title
Expression Difference
Description
Denotes difference between two given expressions.
Category
Essays, Posts & Presentations
Keywords
Tree Difference, Tree Diffing, Difference, ExpressionTree, SequenceAlignment, ExpressionDifference
URL
http://www.notebookarchive.org/2021-07-615l50c/
DOI
https://notebookarchive.org/2021-07-615l50c
Date Added
2021-07-13
Date Last Modified
2021-07-13
File Size
0.8 megabytes
Supplements
Rights
Redistribution rights reserved
Download
Open in Wolfram Cloud
WOLFRAM SUMMER SCHOOL 2021
Expression Difference
Expression Difference
Aman Kumar Dewangan
National institute of Technology Raipur
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 without proper indentation and spacings 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 .
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.*) IfAtomQ[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___]}:> IfxHead === 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*) MapFunctione, Replacee, 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]]]]]]} ; IfLength[e1] > Length[e2], Do[AppendTo[diff, Delete[count]], Length[e[[1]]] - Length[e[[2]]]], DoAppendTo[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*)
Variables :
Variables :
Explanation :
Explanation :
Understanding Output Patterns:
Understanding Output Patterns:
Basics and Examples
Basics and Examples
Example 1:
Example 1:
Example 2:
Example 2:
Example 3:
Example 3:
Example 4:
Example 4:
Example 5:
Example 5:
Example 6:
Example 6:
Example 7:
Example 7:
Example 8:
Example 8:
Example 9:
Example 9:
Example 10:
Example 10:
Example 11:
Example 11:
Example 12:
Example 12:
Example 13:
Example 13:
Example 14:
Example 14:
Example 15:
Example 15:
Possible Issues:
Possible Issues:
Applying ExpressionDifference on Large Expressions may not work :
Case 1(Fails for Long Expression which involve Recursive Implementation) :
Case 1(Fails for Long Expression which involve Recursive Implementation) :
In[]:=
s1=Hold@Replace[{expr1,expr2},{(*EvaluatingtheSequence"seq"usingSequenceAlignmentOperationonthegivenexpressiondependingupontheDelayedRuleofMatchingCondition.*){xHead_[xe___],yHead_[ye___]}:>If[xHead===yHead,count++;SequenceAlignment[{xe},{ye}],AppendTo[diff,ExpressionDifference[xHead,yHead]];count++;SequenceAlignment[{xe},{ye}]]}];s2=Hold@ReplacePart[{expr1,expr2},{(*EvaluatingtheSequence"seq"usingSequenceAlignmentOperationonthegivenexpressiondependingupontheDelayedRuleofMatchingCondition.*){xHead_[xe___],yHead_[ye___]}:>If[xHead===yHead,count++;SequenceAlignment[{xe},{ye}],AppendTo[diff,ExpressionDifference[xHead,yHead]];count++;Sequence[{xe},{ye}]]}];ExpressionDifference[s1,s2]
Out[]=
{ReplacePart[1{ye}]}
Case 2 (Partially Wrong Output in some cases):
Case 2 (Partially Wrong Output in some cases):
In[]:=
ExpressionDifference[Table[RandomInteger[x],{x,10,20,1}],Integrate[+1,x]]
2
x
Out[]=
{Replace[_Plus]},ReplacePart[1x],ReplacePart2,Delete[3],Delete[3],Delete[3],Delete[3],Delete[3],Delete[3],Delete[3],Delete[3],Delete[3]
3
x
3
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.
Keywords
Keywords
◼
Tree Difference
◼
Tree Diffing
◼
Difference
◼
ExpressionTree
◼
SequenceAlignment
◼
ExpressionDifference
Acknowledgment
Acknowledgment
◼
Connor Gray(Mentor)
◼
Carlos Muñoz (TA)
◼
Silvia Hao (TA)
References
References
Cite this as: Aman Kumar Dewangan, "Expression Difference" from the Notebook Archive (2021), https://notebookarchive.org/2021-07-615l50c
Download
