Today I gave a tutorial on the Lean programming language and its use for theorem proving. This presentation has an interesting background and I am interested in improving it.
I have known about interactive theorem provers for a while, and during the past couple of years I have taught a course where we ask students to prove properties by hand. Since then, I have been trying tutorials, watching talks and I couldn’t get into any of the different languages: Agda, Idris and Coq.
The main issue is that people who give 50-minute talks about it already know everything about it and can’t really see the issue from the eyes of an ignorant. In particular, ignorants regarding mathematics. Even watching and reading Philip Wadler’s Propositions as Types excellent talk and articles.
Since i’m a frequent z3 user, I’ve heard about the Lean theorem prover (and language) but I really didn’t pay much attention, until I had some free time (actually a deadline for a boring task) and tried the Natural Number Game (NNG) and it blew my mind.
NNG presents theorem proving as a game, in which by completing a level, you learn new tools (lemmas and tactics) that you can use in the next levels. If feels like a puzzle!
Sokoban is a great example that can be compared with this game. If you would try all possible combinations of movements, you would solve any level in an unlimited time. But by looking at the screen, you use your pattern recognition skills to try alternatives that are more probable to solve the level, using a bit of backtracking if you make a wrong decision. Sudoku is a similar game.
NNG takes the same approach, but the Goal window of lean (that shows context and goals) as the game viewport. You see the current scenario (in local variables) and the direction where you want to go (on the goals). You can then make movements (using tactics) that hopefully move you towards your goal. If it doesn’t, you can go back and delete some code.
What NNG lacks is a small explanation of the basic syntax and tactics. Luckily, the Lean window is interactive and you can move your cursor around and learn by moving around the proof. In a sense, it’s similar to the Fog of War in RTS games.
After finishing NNG, I tried to write some useful proofs for work, but I ended up spending 90% of the time reading the lean source code to understand what is available to me. Only after a while I learnt about mathlib and library_search. But even having a productive lemma searcher, I need to understand what tactics I can use to manipulate my context in order to advance towards something I have in hand. This is still a lot of effort to me, and the official documentation (both lean’s and mathlib) requires much more examples and explanations for newbies.
With the goal of trying to get more people to use Lean (and help me!), I gave a tutorial for a mixed audience ranging from undergraduates to full professors. I felt I was the right person to give this tutorial because I know almost nothing about theorem proving and Lean in particular. I showed just the basic steps and left some notes for attendees to make their own path afterwards.
I have made the materials available, including a written version of the tutorial, including exercises and solutions. Feel free to follow them and provide me feedback.
Lean supports several idioms and it is one of the biggest barriers to entering this world. Python’s motto of “one obvious way to write it” that doesn’t even apply to Python would help novices here. Reading the standard library is quite hard because it is written in a “difficult” style that makes use of monads and utf-8 characters. It makes it easier for mathematicians that understand what they are doing, but makes it very hard for non-mathematicians looking for a tactic or lemma that is missing in their proof.
I present Lean as being three different languages: the one for executing code, the one for logic and proofs, and the tactic language (meta). I understand they all boil down to being the same language, but for the user, they are used in different contexts.
I know that you can define a lemma or theorem using def, but that makes it hard for novices to understand what code will execute and what code is used just for proofs. I present proofs in begin-end blocks, showing a procedimental style that mimics the one we use in paper. I understand that they all can be written using lambdas and monads, but that is code quite hard to understand.
This style was the one that clicked for me and I wrote the tutorial to help hackers that can learn by example and have no strong mathematical foundations other can proofs by induction and a bit of Haskell understanding.