Skip to content
LumenaryAcademy

Lumenary CS · Programming languages

Lean

A functional programming language that is also a proof assistant: write a program, state what it should do, and have the machine check that it does, from a first program to a verified project.

Lean is a functional programming language and an interactive theorem prover in one. Leonardo de Moura started it at Microsoft Research in 2013; Lean 4, a redesign written largely in Lean itself, became public in 2021, reached version 4.0 in 2023, and is developed today by the non-profit Lean FRO together with a large open-source community. In Lean you can write ordinary programs (with structures, pattern matching, type classes, monads, arrays and hash maps, compiled to fast native code) and, in the same file, prove theorems about them that the computer checks. Mathematicians use it to formalise mathematics in the Mathlib library; engineers use it to verify software; and AI systems use it to write proofs that can be checked rather than trusted.

This course is for anyone who already knows what a variable, a loop and a function are: the Start level of Lumenary CS or equivalent experience in any language. No functional programming or formal logic is assumed. It teaches Lean as a programming language first (expressions and types, structures and inductive types, recursion and termination, type classes and dependent types, monads, IO and the standard library) and then as a tool for verifying programs: propositions as types, proofs with tactics, proofs about your own functions, an overview of macros and the ecosystem, and a small compiler proved correct. Lumenary Math's lessons First steps in Lean and Formalising mathematics in Lean and Mathlib teach the mathematical side; the two fit together.

To run the code, install elan, Lean's official toolchain manager, by following the instructions at lean-lang.org/install, or install the Lean 4 extension for VS Code, which sets everything up for you; or run programs in the browser at the official Lean playground. Every complete program in these lessons was checked and run with Lean 4.35.0, core Lean without Mathlib, by Lumenary's test suite, and the output shown is the output it printed. The lessons were drafted with AI assistance and are awaiting review by a human computer scientist.

AI-draftedAwaiting review by a computer scientist
  • Chloe · The Designer
    “Why is the language built this way?”
  • Margaret · The Profiler
    “What does it print, and what does it cost?”
  • Gideon · The Language Lawyer
    “What exactly does the language guarantee?”

Foundations · 4 lessons

Foundations

Install Lean with elan and Lake, explore with #eval and #check, and learn the core language: expressions and types, functions, structures, inductive types, pattern matching, and recursion that Lean can prove terminates.

  1. 1First steps in LeanA programming language that is also a proof assistant. Where Lean came from, how to install elan and Lake, and your first programs, with 45 min
  2. 2Expressions, types and functionsEverything in Lean is an expression with a type. Numbers that never overflow and numbers that do, local definitions, functions as values, and the small notations that make functional code pleasant to read. 50 min
  3. 3Structures, inductive types and pattern matchingModel your data precisely. Records with structure, choices and trees with inductive, and pattern matching that the compiler checks for every case you forgot. 55 min
  4. 4Recursion and terminationLean has no loops in its core, only recursion, and it insists that every recursive function ends. Structural recursion, well-founded recursion with termination_by, and the honest escape hatches. 55 min

Practice · 3 lessons

Practice

Write generic code with polymorphism, type classes and dependent types; structure effects with monads, do-notation, IO and mutable-looking loops; and use arrays, hash maps and the rest of the standard library efficiently.

  1. 5Polymorphism, type classes and dependent typesWrite a function once and use it at many types; let the compiler find the right addition, comparison or printing for each; and let types depend on values, so that a vector's length and an index's bound are checked before the program runs. 60 min
  2. 6Monads, do-notation and IOHow a pure language handles failure, state and the outside world. Option and Except, the Monad class behind do-notation, mutable-looking loops that are pure underneath, and real input and output. 60 min
  3. 7Arrays, hash maps and the standard libraryFast data structures in a pure language. Arrays updated in place thanks to reference counting, strings, hash maps, hash sets and tree maps from Std, and how to choose between them. 55 min

Professional · 3 lessons

Professional

Read propositions as types and write proofs in term mode and with tactics, prove that your own functions meet their specifications, meet macros, Mathlib and the community, and build a small compiler with a proof that it is correct.

  1. 8Propositions as types, and writing proofsIn Lean a statement is a type and a proof is a program of that type. Proofs written as terms, proofs built step by step with tactics, and the automation that does the routine work. 65 min
  2. 9Proving properties of your programsSpecifications, tests that run at compile time, proofs by induction that follow your code, fast implementations proved equal to simple ones, and values that carry their own proofs. 65 min
  3. 10Macros, the Lean ecosystem, and a verified compilerHow Lean lets you extend its own syntax, how professionals build and share Lean projects, and a complete project to finish the course, a small compiler with a proof that it is correct. 70 min

Further reading and resources

  • Lean (lean-lang.org)The official home of Lean: installation, documentation, use cases and news.
  • Lean documentationThe index of official books, manuals and tools.
  • The Lean Language ReferenceThe official, detailed description of the language, its tactics and its standard library; Lean has no separate standards document, and this reference together with the implementation is the definition.
  • Functional Programming in Lean · David Thrane ChristiansenThe official book for programmers learning Lean as a programming language.
  • Theorem Proving in Lean 4The official book on Lean's logic and on writing proofs.
  • Lean playgroundEdit and check Lean code in the browser, with nothing to install.
  • Lean Zulip chatWhere the Lean community, from beginners to core developers, asks and answers questions.
  • The Lean 4 source codeThe compiler, the standard library and Lake, all open source under the Apache 2.0 licence.