11/11/23, 10:32 PM Final project description: CSCI 2041 (001) Advanced Programming Principles (Fall 2023)
Final project description
This final project, you will write a program that can write proofs about ocaml code. The purpose of your program is to have it do homeworks 6 through 8 for you. This means that your program should be able to:
read ocaml definitions (including type definitions)
read statements that need proving
understand simple hints about how to carry out the proof
either produce proofs (with intermediate steps) of those statements, or indicate that it cannot find a proof
To get a sense of all that goes into your project, I’ve created two files. This first file (https://canvas.umn.edu/courses/391238/files/39178979?wrap=1) (https://canvas.umn.edu/courses/391238/files/39178979/download?download_frd=1) contains a description of all the things your program should be able to do when you’ve completed the project. It is itself a valid input for your program as well. You’re encouraged to get started on a more minimal syntax, and this second file (https://canvas.umn.edu/courses/391238/files/39179461?wrap=1) (https://canvas.umn.edu/courses/391238/files/39179461/download?download_frd=1) is a bare-bones version you can use for that.
Overview of the input
The syntax for your tool is chosen such that your files are (or could be) valid ocaml code, which allows you to execute functions and properties you defined in utop, for instance. To get a good idea on the precise syntax, I suggest opening the sample files from the first paragraph.
The input files to your tool have three kinds of statements:
Type definitions. These correspond to defining a variant type in ocaml, but in a simpler form: no ‘a types, or nested parentheses can occur (so instead of writing “Foo of ‘a list * (int * int)”, you’d have to write “Foo of (mylist * int * int)”). There are also no type synonyms (no writing “type x = y”, since y does not start with a constructor).
Function definitions. These always start with ‘let rec’, always carry type information, and the expressions are limited to function applications, constructors, and match statements. We ignore the “define before use” requirement ocaml has, and assume that once a function is defined with a certain name, that name will not get redefined.
Prove statements. These ask for a proof of your tool. They start with ‘let (*prove*)’ followed by a lemma name and a list of the variables in that lemma, with the types of those variables. For example: let (*prove*) append_nil (x : mylist) = (append x Nil = x) . Prove statements are optionally followed by a hint. You will implement two kinds of hints:
https://canvas.umn.edu/courses/391238/pages/final-project-description 1/4
Code Help
(*hint: induction x *)
(*hint: induction x
| Nil -> ()
| Cons -> (induction y) *)
(Cons (h,t)) (Cons (y,lst2))) z
append (Cons (h,t)) lst = Cons (h,append t lst)
append (append
append (Cons (h,t)) (Cons (y,lst2))
h:=h, t:=t,
lst:=Cons (y,lst2)
11/11/23, 10:32 PM Final project description: CSCI 2041 (001) Advanced Programming Principles (Fall 2023)
Induction hints, written as: . Here, ‘x’ is the variable on which to do induction.
Axiom hints, written as: (*hint: axiom *) . This indicates that your tool should accept the statement without trying to prove it. We’ll be able to use this to get proofs for – for example – homework 7 where there are assumptions about functions without a corresponding implementation. It’s also useful to know quickly whether a certain proof would go through with a certain helper lemma, and you don’t want to spend time on trying to prove the helper lemma in case it wouldn’t actually help you.
You’re allowed to write more hints. For instance, it can be helpful to be able to specify which lemmas or definitions to try using and in which order to try them. In the homeworks, there was a case where you needed case distinction within an induction proof. You don’t have to get this to work, but in case you do, here’s a suggestion for its syntax:
Besides statements, the input allows the use of comments the same way ocaml does. This means we allow comments to be nested. All comments are ignored.
If you feel like you have a good understanding of what the input looks like, take a look at the first assignment (https://canvas.umn.edu/courses/391238/pages/project-part-parser) , which asks you to write a parser for this language.
Mechanics of finding the proofs
Our main workhorse for finding proofs is to find proofs by calculation. The use of induction is specified with a hint, so it’s much easier to get right (once the proofs by calculation work). To find a proof by calculation, we take an expression of the form ‘L = R’, and apply rewrite steps to both ‘L’ and ‘R’ until there is some point where they produce the same value. This means we have to write a function that applies a rewrite step. Constructing a rewrite step takes an expression and a rewrite rule, and then attempts to apply the rewrite rule to the expression. For example, if
is our expression, and is our rewrite rule, then there is precisely one way to carry out the rewrite step: it is to apply the rule to
the sub term . To see that we can indeed apply the rule to this term, we have to find a matching.
A matching of a pattern x to an expression e is a substitution such that the pattern under that substitution becomes equal to the expression. In our example, the substitution would be:
. It might be useful to make an abstraction of substitutions.
Once you can find a matching, you can recursively search through the term trying to apply the rewrite rule(s) to every subterm.
https://canvas.umn.edu/courses/391238/pages/final-project-description 2/4
Computer Science Tutoring
11/11/23, 10:32 PM Final project description: CSCI 2041 (001) Advanced Programming Principles (Fall 2023) A link to the assignment that has you find matchings will be posted here.
Improving the prover
The other ingredient towards generating calculation proofs, is to select rules in a smart way: eventually we’ll want to try every rule, but there might be steps that risk taking us further from our goal, and steps that don’t have any effect on our progress towards our goal. This means we’ll use a couple of heuristics to select the best rule.
Moreover, we build in the induction strategy (after a hint), which means looking at the type definitions.
I’ll write more about this as the course progresses, but please go ahead and see which midterm and homework exercises you can complete with your solver, provided you come up with the right lemmas and induction hints.
There are some obvious implications to this course if you were to share your project and your project’s source code:
Future iterations of students will be able to use it to do their homework. Future students will be able to plagiarize it and submit it as their project. Current fellow students will be able plagiarize your code.
At the same time, one student already asked me whether they could post their project on github so that it would help them in getting internships. I totally get that, so here’s what we’ll do:
Your parser(s) can be posted to github (or something similar) one week after the deadline, this means November 26.
Similarly, subsequent partial submissions can be posted to github one week after their respective deadlines.
This takes care of the issue of plagiarism: If your code looks too much like that of fellow students on the day of the deadline (or soon after), both you and the fellow students are in trouble. If your code looks much like that of fellow students some time after the deadline of the corresponding part to which
Another question you might have is which outside resources you’re allowed to use for this project. Here the rule is: don’t copy entire pieces of code (> 10 lines), but small snippets (~ 3 short lines or one long one) are okay, provided you add a reference to where your code came from. This will also apply to (iterated) use of chatgpt or github copilot: if you’re using it for small code snippets, that’s okay but let us know via the comments of your code. Near the end of this class I’ll ask you about the use of AI in one of my quizzes, to find out whether allowing it gave unfair advantages.
https://canvas.umn.edu/courses/391238/pages/final-project-description 3/4
11/11/23, 10:32 PM Final project description: CSCI 2041 (001) Advanced Programming Principles (Fall 2023) Sharing ideas outside of your group is encouraged. Just don’t share code. If you found a good instructional website that helped you write your code, please share that instead.
There are three partial submissions, and one final:
in the first (Nov 19th), you demonstrate that you have a working parser
in the second (Nov 26th), you demonstrate that you can match a pattern to an expression (at the top level)
in the third (Dec 3rd), you demonstrate that you can find a rewrite-proof, and your match rule should work accurately.
for the final project (Dec 10th), you demonstrate that you are able to do induction proofs, and that you’ve added tests to your project.
Each submission depends on the previous ones, but the grading depends only on the new part. Accordingly, the only way to get ‘partial credit’ for, say, getting your parser to work, is to get it by handing it in at the first deadline.
However, if you’re able to demonstrate that the new part works, this also means that you’re caught up on the work of previous submissions. When that happens, we can give points back to those earlier submissions by having the highest of the grades count for the earlier submission. (If you get a 10% and then a 90%, it’ll count as two 90%s, but if you get a 90% and then a 10%, then the 10% still counts as 10%).
https://canvas.umn.edu/courses/391238/pages/final-project-description 4/4
Programming Help