Revamping Mizar: A Modern Approach to Proofs

Mizar is a unique language created for writing and checking mathematical proofs. This language has been around since 1973, and over the years, it has developed a huge library of articles covering many mathematical topics. Mizar has a distinct way of working, which makes it both powerful and a bit complex. Recently, efforts have been made to rewrite Mizar in Rust, a modern programming language known for being efficient and safe.

The aim of this initiative is not only to create a version of Mizar that runs faster but also to find and fix mistakes hidden in the original system. Think of it as giving a vintage car a new engine while also cleaning out old junk that might cause it to stall.

#What is Mizar?

Mizar is primarily a proof language designed for mathematicians and logicians. It allows users to write proofs in a way that resembles natural language but with a strict structure. This language provides a formalized way to ensure that the logical steps taken in a proof are correct. Over the years, Mizar has built up a large library known as the Mizar Mathematical Library (MML), which contains thousands of articles and thousands of theorems.

The typical user of Mizar writes a document that outlines their proof, and Mizar's tools check the logic of these proofs to ensure they make sense. It's like having a math teacher who not only checks your homework but also helps you understand where you went wrong if you made a mistake.

#The Transition to Rust

Rust is known for its ability to manage memory safely and efficiently. By reimplementing Mizar in Rust, the developers aim to improve the performance of the proof-checking tool while maintaining the same logic.

The new version is called "mizar-rs." The team behind this has set themselves a couple of goals: to speed up the checking process and to uncover any bugs or issues that may be present in the original version. They even managed to make the proof-checking faster - around five times quicker on some tasks!

#Why Reimplement Mizar?

#A Fresh Start

While Mizar has served its purpose well for many years, its original code is quite old, written in Pascal, which is not as popular today. Over the decades, the coding style and practices have changed significantly, leading to what programmers often refer to as "technical debt." This is like owning a home where you keep adding new furniture without ever cleaning out the old stuff.

By rewriting Mizar in Rust, the developers not only aim to modernize the codebase but also to make it easier for developers new to the project to understand and contribute. Imagine trying to read an old recipe that keeps adding new ingredients without ever rewriting it; it becomes hard to follow.

#Performance Improvement

One key reason for the rewrite is improved performance. With the original system, checking large libraries of proofs could take a long time. By using Rust's modern capabilities, the new version does the same job much faster.

For example, using eight computer cores, the new proof Checker managed to check the entire MML in just a little over 11 minutes. This is a significant improvement compared to the original version.

#Internal Structure of Mizar

Mizar is made up of several components, each playing a crucial role in processing proofs. Here’s a simple breakdown:

#Parser

The first step is the "parser," which reads the Mizar file (the document where proofs are written) and converts it into a more manageable format known as an abstract syntax tree (AST). You can think of the parser as a translator, turning the original text into a structured version that a computer can easily understand.

#Analyzer

Next is the "analyzer." This component checks the logical structure of the proof. It looks for any inconsistencies or errors in how the terms and symbols are used. It’s like having a friend who understands the math well and reviews your work to ensure you haven’t made any silly mistakes.

#Checker

Finally, we have the "checker," which verifies each step of a proof. This is the part that actually confirms whether the steps taken in the proof are logically sound. If you want to think of a checker as a judge in a game, then the checker ensures the rules are followed and awards points (or dismisses steps) accordingly.

#Challenges in Recreating Mizar

#No Official Specification

One of the major challenges faced by the developers in this project was the lack of an official specification for the Mizar language. Typically, programming languages have detailed specifications that outline how they should work. Mizar, however, only had its original code as a reference. This was akin to trying to learn a new language by only listening to conversations without any grammar rules on paper!

#Access to Code

Additionally, the original source code was not publicly available for many years. It was only accessible to members of a particular group, making it difficult for developers outside that circle to participate. Luckily, thanks to the efforts of the team behind the mizar-rs project, the original code has now been made available to everyone.

#Lack of a Small Trusted Kernel

Mizar also does not have a "small trusted kernel," which means the components responsible for critical logic were tightly interconnected. To ensure correctness, the new implementation had to remain close to how the original Mizar operated, complicating the development process further.

#Bugs and Discoveries

As the team re-implemented Mizar, they uncovered several bugs in the original code. They could write proofs that led to contradictions due to issues in the logic of the original system. This showcases how rewriting code can provide a new perspective on existing problems, much like how decluttering your closet can reveal old clothes you forgot you even had!

#Example Bugs

Let’s take a look at a few examples of bugs found during the process:

1. Polynomial Arithmetic Overflow: The original code did not check for overflow in polynomial arithmetic. This means that if numbers got too large, the system could produce incorrect results, like a math class where students are taught that 2 + 2 can equal 5 on a bad day.

2. Negation Issues: In some cases, the proof-checking system could misinterpret the negation of statements, leading to absurd conclusions. It’s like arguing that if you’re not hungry, you must be full just because you had a snack earlier!

3. Flex-and Misinterpretations: There were issues related to complex logical expressions called flex-and statements that would lead to incorrect conclusions. This is somewhat like a puzzle that seems to fit but actually has a piece wrongly placed.

#Performance Gains

The move to Rust has resulted in notable performance improvements. The original Mizar took much longer to process articles because of its architecture and older programming methods. The new implementation is faster because Rust’s design allows for efficient programming patterns that cut down on wasted time.

#Future Work

While the new version of Mizar is already impressive, there’s always room for improvement. The team hopes to continue expanding mizar-rs, exploring its potential, and refining its capabilities.

For instance, they might lift certain restrictions that the original Mizar imposed, such as article name length. Imagine trying to name your pet fish with a long, complex name - it just doesn’t work with the limitations!

#Conclusion

Reimplementing Mizar in Rust has produced a faster, more efficient proof-checking tool that not only retains the original capabilities but also enhances the debugging process. By uncovering bugs and improving performance, the developers hope to breathe new life into Mizar.

This project highlights how modern tools can bring clarity to older systems and pave the way for future innovations in mathematical verification. Who knew checking math proofs could be so exciting? It’s like upgrading from an old bicycle to a brand new, shiny electric bike - the ride just gets a whole lot smoother!