Develop heuristics for bracket autoclosing in inputs
by Xinyu Luo
Purdue University / New York University
by Xinyu Luo
Purdue University / New York University
Abstract
In this project, we are finding the missing bracket from a code block by heuristic algorithm. And we will return the most likely positions where the user missed the bracket. We are working on finding the missing right bracket on full form codes. Our heuristic algorithm includes sanity check and heuristic selections for common cases of missing a bracket. We randomized 100 samples from nearly all Wolfram Language examples in the WolframLanguageSymbol. Fortunately, we have the succeed ratio around 70% - 80%, which means for a high probability we can find the missing bracket. And we also showed that after testing on 1000 examples, the average length of potential solutions are around 3, which means on average case this algorithm will only offer 3 potential positions of the missing bracket. In the future, if we package up this function and integrate it in to the Mathematica, I believe it would be a great help for users of finding the missing bracket.
In this project, we are finding the missing bracket from a code block by heuristic algorithm. And we will return the most likely positions where the user missed the bracket. We are working on finding the missing right bracket on full form codes. Our heuristic algorithm includes sanity check and heuristic selections for common cases of missing a bracket. We randomized 100 samples from nearly all Wolfram Language examples in the WolframLanguageSymbol. Fortunately, we have the succeed ratio around 70% - 80%, which means for a high probability we can find the missing bracket. And we also showed that after testing on 1000 examples, the average length of potential solutions are around 3, which means on average case this algorithm will only offer 3 potential positions of the missing bracket. In the future, if we package up this function and integrate it in to the Mathematica, I believe it would be a great help for users of finding the missing bracket.
1. Problem Statement and Input Preparation
1. Problem Statement and Input Preparation
1.1 Problem Statement
1.1 Problem Statement
This problem is finding the missing bracket of a given broken code with one right bracket missing. We will give potential positions of the missing bracket.
1.2 Input Preparation
1.2 Input Preparation
Define expr as the correct code. We will randomly drop one of the right bracket from expr, and we call the missing bracket code brokenStr. And we drop all the whitespace characters for the broken codes and the original codes for testing convenient in this project.
The following showed a code example as expr. We assumed the code we are testing on is a full form code without whitespace character. And we call it as str.
In[]:=
expr=Hold[MinNet[net_,k_:2]:=Module[{d=DSets[net,k],q,b},If[First[d]=!={},AllNet[k],q=ISets[b=Map[Table[Position[d,NetStep[net,#,a]]〚1,1〛,{a,0,k-1}]&,d]];DeleteCases[MapIndexed[#2〚2〛-1#1&,Rest[Map[Position[q,#]〚1,1〛&,Transpose[Map[Part[#,Map[First,q]]&,Transpose[b]]],{2}]]-1,{2}],_0,{2}]]]]
Out[]=
Hold[MinNet[net_,k_:2]:=Module[{d=DSets[net,k],q,b},If[First[d]=!={},AllNet[k],q=ISets[b=(Table[Position[d,NetStep[net,#1,a]]〚1,1〛,{a,0,k-1}]&)/@d];DeleteCases[MapIndexed[#2〚2〛-1#1&,Rest[Map[Position[q,#1]〚1,1〛&,Transpose[(#1〚First/@q〛&)/@Transpose[b]],{2}]]-1,{2}],_0,{2}]]]]
In[]:=
str=StringDelete[ToString[FullForm[expr]],WhitespaceCharacter]
Out[]=
Hold[SetDelayed[MinNet[Pattern[net,Blank[]],Optional[Pattern[k,Blank[]],2]],Module[List[Set[d,DSets[net,k]],q,b],If[UnsameQ[First[d],List[]],AllNet[k],CompoundExpression[Set[q,ISets[Set[b,Map[Function[Table[Part[Position[d,NetStep[net,Slot[1],a]],1,1],List[a,0,Plus[k,-1]]]],d]]]],DeleteCases[MapIndexed[Function[Rule[Plus[Part[Slot[2],2],-1],Slot[1]]],Plus[Rest[Map[Function[Part[Position[q,Slot[1]],1,1]],Transpose[Map[Function[Part[Slot[1],Map[First,q]]],Transpose[b]]],List[2]]],-1],List[2]],Rule[Blank[],0],List[2]]]]]]]
We randomly drop one of the right bracket from str to get brokenStr.
In[]:=
brokenStr=StringDelete[StringDrop[str,RandomChoice[StringPosition[str,"]"]]],WhitespaceCharacter]
Out[]=
Hold[SetDelayed[MinNet[Pattern[net,Blank[]],Optional[Pattern[k,Blank[]],2]],Module[List[Set[d,DSets[net,k]],q,b],If[UnsameQ[First[d],List[]],AllNet[k],CompoundExpression[Set[q,ISets[Set[b,Map[Function[Table[Part[Position[d,NetStep[net,Slot[1],a]],1,1],List[a,0,Plus[k,-1]]]],d]]]],DeleteCases[MapIndexed[Function[Rule[Plus[Part[Slot[2],2],-1],Slot[1]]],Plus[Rest[Map[Function[Part[Position[q,Slot[1]],1,1]],Transpose[Map[Function[Part[Slot[1,Map[First,q]]],Transpose[b]]],List[2]]],-1],List[2]],Rule[Blank[],0],List[2]]]]]]]
1.3 Visualizing the Missing Bracket
1.3 Visualizing the Missing Bracket
Function diffTrackFunc defined as finding the missing bracket in brokenStr and str.
In[]:=
diffTrackFunc[brokenStr_,str_]:=First[First[Position[(StringTake[brokenStr,{#,#}]===StringTake[str,{#,#}])&/@Range[StringLength[brokenStr]],False]]]idx=diffTrackFunc[brokenStr,str]
Out[]=
338
The missing bracket is at position 112 of the str, visualizing as following:
In[]:=
StringTake[str,{idx-15,idx+15}]StringTake[brokenStr,{idx-15,idx+15}]
Out[]=
[Part[Slot[2],2],-1],Slot[1]]],
Out[]=
[Part[Slot[2],2,-1],Slot[1]]],P
2. Heuristics Algorithms
2. Heuristics Algorithms
We will first refilled all the possible positions of the missing bracket. Then, we will use the heuristics algorithm to filter the impossible refilled case. Our basic idea for heuristics algorithms includes three kinds of checks, sanity check, argument check and low weighted cases check. The first part is sanity check. For the sanity check, we filter all the impossible cases, such as the refilled bracket is in between of a keyword or it is already a leave node, etc. For the argument check, we are going to check whether the number of arguments of each keyword are correct or not. For the low weighted cases check, we mainly screen out some cases that are not very likely to happen, such as a right bracket directly in the front of a left bracket and implicated multiple. Details are shown in the following sub sections.
2.1 Sanity Check Heuristic Function
2.1 Sanity Check Heuristic Function
The sanity check will filter the following cases:
1) There should not be any missing bracket in between the keyword, like “Trans]pose”
2) There should not be any missing bracket right after a comma, like “,]”.
3) There is not such a case that a digit joint with a wolfram language word like “list[]9”.
4) SyntaxQ check - we select all the possible string which can pass the wolfram language syntaxQ check.
1) There should not be any missing bracket in between the keyword, like “Trans]pose”
2) There should not be any missing bracket right after a comma, like “,]”.
3) There is not such a case that a digit joint with a wolfram language word like “list[]9”.
4) SyntaxQ check - we select all the possible string which can pass the wolfram language syntaxQ check.
Codes for sanityCheck. listRefillStringPassSyntaxQ is the list where all the possible refilled strings can pass the sanity check and syntaxQ check.
In[]:=
sanityCheck[brokenStr_,n_]:=(!Between[n,{2,StringLength[brokenStr]}]||!AllTrue[StringPart[brokenStr,{n-1,n}],LetterQ])&&(!StringMatchQ[StringTake[brokenStr,n-1],___~~","~~WhitespaceCharacter...~~EndOfString])&&(!StringMatchQ[StringDelete[StringTake[brokenStr,n;;-1],WhitespaceCharacter],DigitCharacter~~___])listRefilledString=Association@Table[If[sanityCheck[brokenStr,n],n->StringInsert[brokenStr,"]",n],Nothing],{n,StringLength[brokenStr]+1}];listRefillStringPassSyntaxQ=DeleteDuplicates@Select[listRefilledString,SyntaxQ];
2.2 Argument Check
2.2 Argument Check
After sanity check, we will check for the argument number of every keyword in the refilled string is correct or not. And it is worth to mention that after the sanity check, all the string in the listRefillStringPassSyntaxQ can have an expression tree. In the argument number check, we have to omit the leaf nodes of the expression tree since there will be no argument of the keyword in the leaf nodes.
Omit leaf nodes. Get the number of each keyword. Get the correct number of arguments of each keyword. And get the candidate score for every refilled string, the score is .
#correctkeywordsarguments
#totalkeywords
In[]:=
ArgumentCountExptLeaves[tree_]:=Map[{TreeData[#],Length[TreeChildren[#]]}&,Select[TreeLevel[tree,All],Not@*TreeLeafQ]]syntaxInfo[x_]:={}syntaxInfo[HoldComplete[x_Symbol]]:=SyntaxInformation[x]argumentPatternFunc[x_]:=Lookup[syntaxInfo[x],"ArgumentsPattern",{___}]underScoreCountFunc[x_]:=Count[argumentPatternFunc[x],Verbatim[_]|{___}]optionalCountFunc[x_]:=Count[argumentPatternFunc[x],_Optional]argumentNumCheckFunc[x_]:=argumentNumCheckFunc[x]=If[MemberQ[argumentPatternFunc[x],Verbatim[__]|Verbatim[___]],{underScoreCountFunc[x],Infinity},{underScoreCountFunc[x],underScoreCountFunc[x]+optionalCountFunc[x]}]candidateScoreExptLeaves[cand_]:=Mean[Boole[Between[#[[2]],argumentNumCheckFunc[#[[1]]]]&/@ArgumentCountExptLeaves[ExpressionTree[ToExpression[cand,StandardForm,Hold],"HeldHeads"]]]]
Select all the possible positions which can also pass the argument check (maximum candidate score).
In[]:=
candidateScoreList=candidateScoreExptLeaves/@listRefillStringPassSyntaxQ
Out[]=
6,16,17,23,24,31,32,35,41,42,53,54,61,62,63,69,70,74,83,84,88,89,92,93,94,100,101,104,106,110,112,116,117,124,125,130,131,132,138,139,148,149,150,170,171,174,175,176,182,183,186,187,188,192,193,201,202,207,208,212,213,221,222,223,231,232,235,240,242,245,249,251,257,258,259,261,266,267,268,271,277,293,294,304,305,313,314,318,319,323,324,328,329,333,335,338,342,348,350,358,359,363,364,367,368,376,377,381,382,390,391,392,397,399,403,405,417,418,421,422,430,431,435,436,4401,4421,4461,447,452,454,4671,468,469,4771,479,485,4911,493,5001,501,506,507,510,5161,518
56
59
18
19
55
59
18
19
56
59
18
19
55
59
27
29
18
19
55
58
51
55
54
59
53
57
54
59
53
58
53
57
27
29
27
29
16
17
54
59
53
57
54
59
52
57
53
59
26
29
52
57
53
59
26
29
53
58
27
29
53
58
17
18
54
59
53
57
55
59
53
57
54
59
27
29
51
56
53
58
25
27
55
59
27
29
50
53
56
59
18
19
55
59
27
29
18
19
56
59
18
19
55
59
27
29
18
19
54
59
53
57
54
59
53
57
54
59
53
57
55
59
53
57
54
59
27
29
53
57
55
59
27
29
53
57
27
29
27
29
27
29
27
29
49
53
55
59
27
29
27
29
53
57
55
59
27
29
27
29
55
58
14
15
55
59
55
57
56
59
55
57
56
59
55
57
56
59
55
57
57
59
55
57
57
59
55
57
28
29
28
29
55
58
26
27
28
29
49
51
57
59
56
57
57
59
56
57
56
59
55
57
56
59
55
57
57
59
55
57
56
59
28
29
55
57
28
29
28
29
28
29
52
53
57
59
56
57
57
59
56
57
57
59
56
57
58
59
57
59
57
58
57
58
57
59
57
58
57
58
28
29
28
29
55
59
18
19
27
29
28
29
55
58
In[]:=
perfectIndicesFunc[brokenStr_]:=Keys@Select[candidateScoreListFunc[brokenStr],EqualTo[Max[candidateScoreListFunc[brokenStr]]]]perfectIndices=Keys@Select[candidateScoreList,EqualTo[Max[candidateScoreList]]]
Out[]=
{440,442,446,467,477,491,500,516}
Here we visualize all possible candidates can pass the sanity check and the argument check.
All possible positions of the missing bracket, colored red.
In[]:=
visPotentialPositions[brokenStr_,potentialIdx_]:=StringInsert[brokenStr,ToString[Style["]",Red],StandardForm],potentialIdx]visPotentialPositions[brokenStr,perfectIndices]
Out[]=
Hold[SetDelayed[MinNet[Pattern[net,Blank[]],Optional[Pattern[k,Blank[]],2]],Module[List[Set[d,DSets[net,k]],q,b],If[UnsameQ[First[d],List[]],AllNet[k],CompoundExpression[Set[q,ISets[Set[b,Map[Function[Table[Part[Position[d,NetStep[net,Slot[1],a]],1,1],List[a,0,Plus[k,-1]]]],d]]]],DeleteCases[MapIndexed[Function[Rule[Plus[Part[Slot[2],2],-1],Slot[1]]],Plus[Rest[Map[Function[Part[Position[q,Slot[1]],1,1]],Transpose[Map[Function[Part[Slot][1],Map][First,q]]],Transpose][b]]],List][2]]],-1],List][2]],Rule][Blank[],0],List][2]]]]]]]
A manipulation for visualizing the possible positions of missing bracket.
From those two visualization, we can see that the correct position is included in the list.
2.3 Other Low Weighted Cases Heuristic Check
2.3 Other Low Weighted Cases Heuristic Check
After the sanity check and the argument check, we still have many candidates. We are going to add more heuristic check to filter low weighted cases. And we will also omit the low weighted cases. Here, we added two more heuristic check for low weighted cases:
1) It is nearly impossible for user to directly write a right bracket before a left bracket in wolfram language, like “][”.
2) It is nearly impossible for user to write implicated multiplication, like “f[]g[]”.
1) It is nearly impossible for user to directly write a right bracket before a left bracket in wolfram language, like “][”.
2) It is nearly impossible for user to write implicated multiplication, like “f[]g[]”.
The visualization after the low weighted cases heuristic check.
We can see the correct answer is on n = 2.
3. Testing and Visualizing
3. Testing and Visualizing
We are testing on 1000 examples of all wolfram language examples of the “WolframLanguageSymbol”. The testing is on two different levels. The first is we are going to test the accuracy based on what is ratio of the correct answer is including in the suggested position. The second is on average number of potential positions this algorithm will return. In the end, we showed that most of the string will return equal to or less than 3 potential positions of the missing bracket.
Since total examples size is 1.03G, I uploaded the whole dataset to wolfram cloud and set to public authority, here is the link:
https://www.wolframcloud.com/obj/2341783d-be8f-4bd0-bad0-7e400b91486e
Since total examples size is 1.03G, I uploaded the whole dataset to wolfram cloud and set to public authority, here is the link:
https://www.wolframcloud.com/obj/2341783d-be8f-4bd0-bad0-7e400b91486e
We packaged up some codes from the section 2, some functions for sanity check, argument check, and additional heuristic check. After those checks, we got our candidate list.
A function for checking the code, we see whether the candidate include the correct answer.
A function generate the broken code for testing.
Download and generate the testing example from “WolframLanguageSymbol”. Since it needs 10 - 20 mins to download, we will not run the code here, and we will import the data from local computer.
Save it to the local storage since the whole testing dataset is around 1G.
Get 1000 examples of codes which length less than 10^4.
Get the accuracy.
The average size of candidate position of missing bracket. (Size 2-4, I typed wrongly as 2-3 on my post.)
A histogram about the distribution of cadidates number
Concluding remarks
Concluding remarks
Testing from the 1000 random examples of “WolframLanguageSymbol”, we achieved the accuracy of successfully finding the missing bracket from 70% to 80%, and the average size of candidate position of missing bracket from 2 to 4, with over 70% of those testing examples offering less than or equal to 4 candidate positions of the missing bracket.
In the future, I hope to extend this missing bracket heuristic algorithm to multiple missing brackets finding problem. Also, for the additional heuristic check, we can let the user to add more additional checking conditions to make the missing bracket function more personalize.
In the future, I hope to extend this missing bracket heuristic algorithm to multiple missing brackets finding problem. Also, for the additional heuristic check, we can let the user to add more additional checking conditions to make the missing bracket function more personalize.
Keywords
Keywords
◼
Heuristic algorithm
◼
String manipulation
Acknowledgment
Acknowledgment
Having Christopher Wolfram as my mentor is my extreme fortune. I am also very grateful for every help from Wolfram Research. It is amazing that worlfram research can provide a great friendly community with extremely helpful supervise. I have to say this will be one of the best research experience I have ever had. Again, thanks for Christopher’s patient and detailed supervision, thanks for this great community.