permute

The implementation of a function is in the CSG/Impl folder. A proof is in the CSG/Proof folder. They are both imported and tied together in the human reviewed file in a theorem that makes a mathematical statement about the function. Lean checks mechanically that the theorems are proven via the supplied proofs. Here you have to trust the Lean checker, but neither the proof nor the implementation.

Then you know that the statement in the file you reviewed holds about that function.

Regarding fuzzing. It cannot find the special cases I listed in the readme, because these cases are very rare.

Yet with formal verification we can prove that the implementation actually satisfies the specification for all of infinitely many possible inputs.

Good question!

One complication: For union the spec would look a little bit different than for intersection. I defined the solid associated to a mesh in a way that does not include the surface of the mesh itself. That works for the intersection. For union we would have:

solidWithSurface (meshUnion M₁ M₂) = solidWithSurface M₁ ∪ solidWithSurface M₂

I think it would not be hard to reduce the implementation and the proof of correctness to the intersection: There are some tricks which you can do like flipping the orientation of a mesh and putting a large cube that contains both meshes around it and then intersect these. (And then at the end doing the reverse trick.) Hopefully the implementation would not actually do this, but this construction could be used in the proof.

I learned working with the Isabelle proof assistant in a university course. There were weekly exercises and a group project at the end. (Actually proving things by hand, no LLM.) That really helped. Before that course it was also hard for me to get into this.

Other than that you can also read introductory material for set theory. There the meaning of all of the unicode symbols you can see in the spec should be explained.

I think this would need to be reimplemented for performance. But maybe the spec can be reused. As agents get better we might reimplement the same spec for performance with minimal human effort. (See notes regarding performance and floats in readme.)

Maybe what you mean is that kernels of proof assistants must be small. Here I am referring to a geometry processing kernel (that is formally verified by a proof assistant). The implementation of the algorithm can be very long, the proof that it conforms to the spec can be very long. But lean checks the proof. And so you only have to trust the spec and that the lean proof assistant is correct.

In the 93 lines I assumed a reviewer already trusts that the kernel of the Lean proof assistants is correct. We have to trust somethings.

Note that the claims are about the kernel that computes the mesh intersection, not the web demo: While the kernel is formally verified, the UI and glue code (that call the kernel) are not. I once hit a bug that looked like there were holes in the resulting mesh: I found that it was an overflow in the glue code (now fixed) that converts the exact rationals coordinates of the output mesh, for which we prove the specification, to floats before sending them to the GPU. All geometry is happening inside the kernel, for which we know the specification holds.

There are two things here: The proof and how you would represent that in a program that you actually can run.

From the math side, I am confident that the construction and proof can be extended to the real numbers and that can be formalized in lean with minimal changes in the existing proof. (Mathematically speaking, we can replace the rationals with any ordered field and the proof should run through.)

I chose to model the problem with rational numbers because the intersections of polygons with rational coordinates have rational coordinates and rational numbers can easily be represented in the computer.

To have a computable implementation with real numbers, you have to make some choice about which part of the real numbers you want to be able to represent in the computer. For example if sqrt(2) and sqrt(3) is important to you, I think you can have a program that can represent them if they occur in any input coordinates and can represent any resulting coordinates exactly symbolically besides the rational numbers (I think this requires minimal changes in the code, the required lean machinery to work with such numbers can be separated from the geometrical code), but a program can’t be able to represent all real numbers exactly since there are too many of them.

Another interesting direction to take this would be to allow spline segments instead of line segments, since intersections of splines with rational coordinates can have non rational coordinates, but I think can still be represented exactly in the computer. This would require a bigger change and would be interesting geometrically.

Yes, it runs significantly longer.

Opus 4.8 ran autonomously for about 8 hours to provide program and proof of correctness, given the formal specification. And in previous experiments, Opus 4.7 failed and I was only able to do it using that model when I cut the work for the agents in smaller steps.

Much of the work the agent is to provide the proof of correctness. The upside is that less time is needed for human review and we can guarantee the absence of bugs that might be expensive when they come up in production.

Historically formal verification was only worth it for very critical software. In the readme I reference related work from NASA, that implemented and verified a different algorithm concerned with polygons, with the intended application to compute keep out zones for autonomous vehicles. This was 2021 before capable LLMs and in the paper they mention that they manually wrote 700 lemmas to produce such a formal proof manually. I hope that as it gets cheaper now, formal verification is used more widely.