CodeEquivalenceUtilities

CodeEquivalenceUtilities is a collection of Wolfram Language functions that can be used to test if different pieces of code are equivalent without the need for evaluation. This allows comparison of unevaluated expressions that may have non-deterministic outputs (e.g. random values, dates, etc). This Paclet represents the underlying technology that powers several automated code grading systems, such as the online exercises for EIWL and Wolfram Challenges.

Installing CodeEquivalenceUtilities

From the Wolfram Language Paclet Repository

Using Wolfram Language version 13.0 or later:

PacletInstall["Wolfram/CodeEquivalenceUtilities"]

Using GitHubInstall

Using Wolfram Language version 12.0 or later:

ResourceFunction["GitHubInstall"]["rhennigan", "CodeEquivalenceUtilities"]

From Github

The CodeEquivalenceUtilities release comes in the form of a .paclet file, which contains the entire package and its documentation. Download the latest release from the GitHub repo's releases page. To install, run the following command in the Wolfram Language:

PacletInstall["/full/path/to/CodeEquivalenceUtilities.paclet"]

This will permanently install the CodeEquivalenceUtilities paclet. The Wolfram Language will always use the latest installed version of CodeEquivalenceUtilities. Installed versions can be enumerated using the command:

PacletFind["Wolfram/CodeEquivalenceUtilities"]

And all versions can be uninstalled using the command:

PacletUninstall["Wolfram/CodeEquivalenceUtilities"]

Paclet Guide

Equivalence for Wolfram Language code can be defined in many ways. The methods used by CodeEquivalenceUtilities attempt to determine intensional equivalence by transforming expressions into a canonical representation.

Equivalence Testing

CodeEquivalentQ - test if two unevaluated expressions are equivalent

EquivalenceTestData - get additional information about the equivalence test performed by CodeEquivalentQ

Code Transformation

ToCanonicalForm - convert an expression into a canonical representation for direct comparison

MakeCanonicalForm - convert to canonical form without evaluating the input

FromCanonicalForm - convert a canonical representation back into a normal evaluatable expression

Examples

Basic Examples

Check if two expressions are equivalent:

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

---

View the canonical representations of expressions:

MakeCanonicalForm[RandomInteger /@ Range[5]]

MakeCanonicalForm[Array[RandomInteger, 5]]

These are directly comparable:

% === %%

Scope

Get additional information about the equivalence test:

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

---

View the sequence of transformations used to convert an expression to its canonical form:

MakeCanonicalForm[Array[RandomInteger, 5], "Trace" -> True] // Column

---

Convert a canonical representation to a normal expression:

MakeCanonicalForm[Array[RandomInteger, 5]]

FromCanonicalForm[%]

Evaluate:

ReleaseHold[%]

Neat Examples

Here is a list of expressions, some of which are equivalent to others:

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]]
};

Find the sequence of transformations for each expression:

Short[traces = Most@ToCanonicalForm[#, "Trace" -> True] & /@ expressions]

Generate a graph for each sequence:

paths = Graph[DirectedEdge @@@ Partition[#, 2, 1]] & /@ traces

Combine the graphs:

graph = Graph[GraphUnion @@ paths, Sequence[
   VertexLabels -> Placed["Name", Tooltip], 
    GraphLayout -> "LayeredDigraphEmbedding"]];

Equivalent expressions converge to the same connected component:

HighlightGraph[graph, paths]

Group the expressions into their corresponding equivalence class:

grouped = GroupBy[expressions, ToCanonicalForm]

TableForm[KeyValueMap[Reverse@*List, grouped]]

License

This project is licensed under the terms of the MIT license. See the LICENSE file in the root directory of this source tree for details.