Proving and Disproving Equivalence of Functional Programming Assignments

Explore an automated approach to verify the correctness of functional programming assignments in this 20-minute video presentation from PLDI 2023. Discover how researchers from EPFL developed a robust and scalable system for equivalence checking of Scala programs, capable of handling hundreds of student submissions simultaneously. Learn about the use of functional induction for recursion, function call matching for auxiliary functions, and a clustering algorithm leveraging equivalence transitivity to improve scalability. Examine the system's implementation on top of the Stainless verification system and its evaluation on over 4000 programs from a functional programming course and program equivalence checking literature. Gain insights into the system's ability to generate inductive equivalence proofs for correct programs and provide counterexamples for incorrect ones, demonstrating its high success rate in automated grading.