Determining Code Equivalence for Automated Grading

Richard Hennigan
Wolfram Research

Join the Conversation #WolframTechConf

An Elementary Introduction to the Wolfram Language

The book includes sets of online programming exercises where users can obtain instant feedback about their solutions

https://www.wolfram.com/language/elementary-introduction/

This required a system to check if user-submitted code was “equivalent” to code in an answer key, which didn’t seem like a very difficult problem (at first)

Piece of cake, right?

Two potential strategies for determining equivalence

Check if the inputs are the same

It’s nice and simple, but quickly shows limitations.

HoldComplete[1+2+3]===HoldComplete[1+2+3]

HoldComplete[3+2+1]===HoldComplete[1+2+3]

Evaluate and check if outputs are the same

This seems to make more sense and generally matches our intuition about what should be considered a correct answer.

3+2+1===1+2+3

Considerations for comparing outputs

Side effects of evaluation

Should these actually be considered the same program?

1+2+3===Echo[1+2+3]

They have the same output, but we wouldn’t consider them equivalent

Export["hello.txt","Hello world"]==="hello.txt"

Some code should be restricted

We don’t want to evaluate every single thing that users submit.

1+2+3===Quit[]

Random values

What do we do when random values are involved?

RandomInteger[1000]===RandomInteger[1000]

We can’t always rely on the inputs either.

HoldComplete[RandomInteger[{1,1000}]]===HoldComplete[RandomInteger[1000]]

Seeding the random number generator can help, but what about situations like this?

(SeedRandom[1]; RandomInteger[10,10])===(SeedRandom[1]; Reverse[RandomInteger[10,10]])

One could argue that a reversed list of random integers is “just as good” as long as they come from the same distribution.

It’s a harder problem than it initially appears

But the Wolfram Language is perfectly suited to handle these types of problems

So how does it work?

Finding equivalence through code transformations

Types of equivalence mentioned so far

Same input

Same output

But wait, there’s more!

Finding equivalence through code transformations

Same input

Same output

Equivalence by definition

Propositional equivalence

Finding equivalence through code transformations

Equivalence by definition

Definition[Red]//InputForm

Red===RGBColor[1,0,0]

Should these evaluate to the same expression?

expression1=HoldComplete[PieChart[Range[3],ChartStyle->{Red,Green,Blue}]];
expression2=HoldComplete[PieChart[Range[3],ChartStyle->{RGBColor[1,0,0],Green,Blue}]];

evaluated1=ReleaseHold[expression1];
evaluated2=ReleaseHold[expression2];
GraphicsRow[{evaluated1,evaluated2}]

evaluated1===evaluated2

Finding equivalence through code transformations

Equivalence by definition

Definition[Red]//InputForm

Red===RGBColor[1,0,0]

Should these evaluate to the same expression?

expression1=HoldComplete[PieChart[Range[3],ChartStyle->{Red,Green,Blue}]];
expression2=HoldComplete[PieChart[Range[3],ChartStyle->{RGBColor[1,0,0],Green,Blue}]];

evaluated1=ReleaseHold[expression1];
evaluated2=ReleaseHold[expression2];
GraphicsRow[{evaluated1,evaluated2}]

evaluated1===evaluated2

Invisible differences can be difficult

symbols1=DeleteDuplicates[Cases[evaluated1,_Symbol,Infinity]];
symbols2=DeleteDuplicates[Cases[evaluated2,_Symbol,Infinity]];
common=Intersection[symbols1,symbols2];

Complement[symbols1,common]

Complement[symbols2,common]

Possible solution: use definition as a replacement rule

transformed1=expression1/.HoldPattern[Red]:>RGBColor[1,0,0]

transformed1===expression2

Finding transformation rules is hard, so let’s automate

Unlike most other programming languages, there is no difference between code and data in the Wolfram Language (a feature called homoiconicity). So things like most definitions are accessible programmatically. Here are all the rules for the named colors:

colorRules=Cases[
Flatten[ToExpression[#,StandardForm,OwnValues]&/@Select[Names["*"],!MemberQ[Attributes[#],ReadProtected]&]],
HoldPattern[_:>_RGBColor]
]

This set of rules allows us to replace any named colors in an expression with its equivalent RGBColor representation:

transformed1=expression1/.colorRules

transformed2=expression2/.colorRules

transformed1===transformed2

Finding equivalence through code transformations

Same input

Same output

Equivalence by definition

Propositional equivalence

Finding equivalence through code transformations

Propositional equivalence

Creating transformation rules from symbol definitions is simple enough, but it’s far from complete. There are many other rules we could use that don’t correspond to any definition. For example, any Range could be rewritten as an equivalent Table:

Range[10]===Table[i,{i,10}]

Range[2,10,2]===Table[i,{i,2,10,2}]

Expressed as a rule

rangeToTable=HoldPattern[Range[a__]]:>Table[i,{i,a}]

Example use

Inputs are different:

expression1=HoldComplete[Range[RandomInteger[100]]];
expression2=HoldComplete[Table[i,{i,RandomInteger[100]}]];

So are the outputs:

ReleaseHold[expression1]
ReleaseHold[expression2]

Equivalent by transformation:

expression1/.rangeToTable
expression2/.rangeToTable

Finding equivalence through code transformations

Potential issues

Transformation direction matters

We have a rule for transforming a Range into a Table, but what about the other direction? Unfortunately, the converse is not always true for such rules. There isn’t an equivalent Range for the following Table, for example:

Table[word,{word,{"Hello","World"}}]

If we wanted to transform in the other direction, we would a different pattern with additional restrictions, which is a bit messier:

HoldPattern[Table[i_,{i_,a:Repeated[_Integer|_Real,3]}]]:>Range[a]

In the earlier example with the color rules, we could have just as easily used the reverse rules instead, e.g.

RGBColor[1,0,0]:>Red

Similarly, do we want to transform Tables into Ranges where appropriate, or do we want to transform Ranges into Tables? In order to remove ambiguity and avoid cycles in our transformations, we’ll always choose the direction that corresponds to mapping from the smaller to larger equivalence class as defined by the patterns. For example, the set of expressions that would be matched by the pattern

HoldPattern[Table[_,{_Symbol,_Integer,_Integer}]]

also have a representation in the equivalence class defined by

HoldPattern[Table[_,{_Symbol,_Integer,_Integer,_Integer}]]

since we can always convert expressions of the first type with the rule

HoldPattern[Table[expr_,{i_Symbol,imin_Integer,imax_Integer}]]:>Table[expr,{i,imin,imax,1}]

Pattern matching limitations

Example rule for Table:

rule=HoldPattern[Table[expr_,{i_Symbol,n_Integer}]]:>Table[expr,{i,1,n,1}];

An expression that this can match:

expression=HoldForm[Table[Table[i,{i,n}],{n,3}]];

We know n will be an integer here, but the pattern doesn’t match since it’s a symbol while unevaluated:

expression//.rule

Desired output:

Table[Table[i,{i,1,n,1}],{n,1,3,1}]

Extending patterns with types

Taking transformations farther

PacletDirectoryAdd["/Users/richardh/IdeaProjects/CodeEquivalence/"];
<<CodeEquivalence`;

c1=ToCanonicalForm[HoldForm[Array[Range,5,3]]]
c2=ToCanonicalForm[HoldForm[Range/@Range[3,7]]]
c3=ToCanonicalForm[HoldForm[Table[j,{i,5},{j,i+2}]]]

c1===c2===c3

Basic types

x ∷ Int//InputForm

Visualizing transformations

...as a sequence of replacements:

ToCanonicalForm[HoldForm[Table[Table[i,{i,n}],{n,3}]],"Trace"->True]//Column

...as a set of sequences that merge if equivalent:

expressions={
HoldForm[Table[i,{i,5},{j,i+2}]],
HoldForm[Array[Range,5,3]],
HoldForm[Table[ConstantArray[i,i+2],{i,5}]],
HoldForm[First[Rest[Range/@Range[10]]]],
HoldForm[Range/@Range[3,7]],
HoldForm[Part[Table[Table[j,{j,i}],{i,10}],2]]
};

UnsameQ@@@Subsets[expressions,{2}]

It’s easy to see that they are all unique, but some are equivalent to others.

equivalentGroups=GatherBy[expressions,ToCanonicalForm]

CodeEquivalentQ@@@equivalentGroups

SameQ@@@ReleaseHold@equivalentGroups

equivalentGroups===GatherBy[expressions,ReleaseHold]

Let’s generate a graph to see just how they are connected.

seq=Function[expr,FixedPointList[ToCanonicalForm[#,"MaxIterations"->1]&,expr]]

traces=seq/@expressions;
traceGraph[trace_]:=Graph[Rule@@@Partition[Hash/@trace,2,1]];
graphs=traceGraph/@traces;
fullGraph=GraphUnion@@graphs;
HighlightGraph[fullGraph,graphs]

The graph components correspond to equivalent expressions

Length@WeaklyConnectedComponents@fullGraph

Length@DeleteDuplicates@ReleaseHold@expressions

Sandbox Evaluation

EvaluateSafely[Echo/@Range[5]]

Side effects are tracked:

EvaluateSafely[Table[Print[(i^2)];(i^2),{i,5}]]

Holding attributes are respected:

EvaluateSafely[Table[Trace[(i^2)];(i^2),{i,3}]]

Relevant definitions are captured at the time of evaluation:

InputForm[%]

Ways to define program equivalence

However, this is not a necessary condition in general. These simple programs are certainly equivalent by reflexivity, yet they produce different outputs:

PieChart[Range[5]]===PieChart[Range[5]]

RandomInteger[1000]===RandomInteger[1000]

It’s also not even a sufficient condition. In this example, the same output is reached, but the programs do very different things:

<<CodeEquivalence`;

CodeEquivalentQ[RandomInteger/@Range[5],Array[RandomInteger,5]]

CodeEquivalentQ[
Pause[31536000000]; Table[Range/@Range[i],{i,2^100}],
Pause[31536000000]; Table[Array[Range,j],{j,1,2^100}]
]

CodeEquivalentQ[
Pause[31536000000]; Table[Range/@Range[i],{i,2^100}],
Pause[31536000000]; Table[Array[Range,j],{j,1,2^100+1}]
]

The data used to determine equivalence can be inspected:

EquivalenceTestData[
First[Rest[Range/@Range[2^100]]],
Part[Table[Table[j,{j,i}],{i,2^100}],2]
]

If an equivalent form is found, the test immediately returns:

EquivalenceTestData[RandomInteger/@Range[5],RandomInteger/@Range[5]]

Additional forms can be inspected by using the “AllTests” option:

EquivalenceTestData[RandomInteger/@Range[5],RandomInteger/@Range[5],"AllTests"->True]

For some expressions, the visual appearance is the main concern, so these two are considered equivalent even though their canonical forms won’t match:

CodeEquivalentQ[PieChart[((Range[5])^2)],PieChart[((Range[2,10,2])^2)]]

Rasterization is used to determine equivalence in these cases:

EquivalenceTestData[PieChart[((Range[5])^2)],PieChart[Table[(i^2),{i,2,10,2}]]]

Canonical Forms

Symbol names are normalized:

c1=ToCanonicalForm[HoldForm[Table[i,{i,n}]]]
c2=ToCanonicalForm[HoldForm[Table[j,{j,n}]]]

InputForm[c1]

InputForm[c2]

c1===c2

In some cases, the type of a symbol can be inferred:

ToCanonicalForm[HoldForm[Table[i,{i,5}]]]
ToCanonicalForm[HoldForm[Table[i,{i,1.0,5.0}]]]

ToCanonicalForm[HoldForm[f[x_Integer]:=Range[x]]]
ToCanonicalForm[HoldForm[f[x_Real]:=Table[i,{i,1.0,x}]]]

Type inference allows transformations to proceed further. In this case, the tables don’t expand to their canonical form without typing information since i could potentially be a List, Integer, etc.

ToCanonicalForm[HoldForm[Table[Table[1,i],{i,n}]]]
ToCanonicalForm[HoldForm[Table[Table[1,i],{i,n ∷ Int}]]]

Most of the transformations are associated with List-related functions:

ToCanonicalForm[HoldForm[Array[Range,5,3]]]
ToCanonicalForm[HoldForm[Range/@Range[3,7]]]
ToCanonicalForm[HoldForm[Table[j,{i,5},{j,i+2}]]]

ToCanonicalForm[HoldForm[{3,7,11,15,19,23,27,31,35,39,43,47}]]
ToCanonicalForm[HoldForm[Range[3,47,4]]]

ToCanonicalForm[HoldForm[Cases[Range[5],_?EvenQ]]]

ToCanonicalForm@HoldForm[Reverse[IntegerDigits[4294967296]][[2]]]
ToCanonicalForm@HoldForm[IntegerDigits[4294967296][[-2]]]

Arguments are sorted when it makes sense to do so:

ToCanonicalForm[HoldForm[Length[{5,2,3,7,2,4,3}]]]

ToCanonicalForm[HoldForm[Mean[{5,2,3,7,2,4,3}]]]

The transformations are primarily motivated by EIWL exercise answers, so symbols that appear there will be more likely to have a canonical form:

ToCanonicalForm[HoldForm[Hue[.12345]]]//InputForm

ToCanonicalForm[HoldForm[StringJoin[{"hello",StringJoin[{"wo","rld"}]}]]]

ToCanonicalForm[HoldForm[Graphics[Style[Circle[],Red]]]]//InputForm

ToCanonicalForm[HoldForm[{Today,Now,Here}]]

Additional Utilities

Sandbox Evaluation

EvaluateSafely[Echo/@Range[5]]

Side effects are tracked:

EvaluateSafely[Table[Print[(i^2)];(i^2),{i,5}]]

Holding attributes are respected:

EvaluateSafely[Table[Trace[(i^2)];(i^2),{i,3}]]

Relevant definitions are captured at the time of evaluation:

InputForm[%]