Skip to content
LumenaryAcademy
Foundations 45 min

First steps in Lean

A programming language that is also a proof assistant. Where Lean came from, how to install elan and Lake, and your first programs, with

Code tested · 3AI-draftedAwaiting review by a computer scientist
MotivationH

One language, two jobs

Most programming languages let you say what to do. You write a function to sort a list, run it on a few examples, and if the output looks right you move on. Whether it is right for every list, including the empty one, the one with a million elements and the one where every element is equal, is a question the language leaves to you, your tests and your users.

Lean lets you say two things in the same file: what to do and why it is right. It is a functional programming language, with structures, pattern matching, type classes, arrays, hash maps and a compiler that produces fast native code. Lean itself, its compiler, its build tool and its editor support, is written in Lean. And it is a proof assistant: a language in which you can state a precise claim, such as "for every list xs, sorting xs gives a sorted list with the same elements", write a proof of it, and have the computer check every step of that proof. If Lean accepts the proof, there is no list, however strange, on which the claim fails.

Those two jobs are not two separate tools glued together. In Lean, a proof is a value, a claim is a type, and checking a proof is type checking. You will see in lesson 8 exactly what that means; for now the important thing is the consequence. The same language that runs your program can reason about it, and the same tool that catches a typo catches a false claim about your code.

Who uses this? Mathematicians use Lean to formalise mathematics: the community library Mathlib contains a large part of undergraduate mathematics and a growing amount of research mathematics, all checked by machine. Engineers use it to verify software: Amazon Web Services, for instance, models its Cedar authorisation language in Lean and proves properties of it. And because a Lean proof can be checked mechanically, AI systems that write mathematics are increasingly asked to write it in Lean, so that their output can be verified rather than trusted; Google DeepMind's AlphaProof, which in 2024 solved problems from the International Mathematical Olympiad, worked in Lean.

This course teaches Lean the programmer's way. The first seven lessons are about writing programs: expressions and types, data, recursion, type classes, monads, input and output, and the standard library. The last three are about proving that programs do what they should. If your interest is mathematics rather than software, Lumenary Math teaches that side in First steps in Lean and Formalising mathematics in Lean and Mathlib; the two tracks complement each other, and you can take them in either order.

History & global context

Where Lean came from

Lean was started in 2013 by Leonardo de Moura, then a researcher at Microsoft Research, who had already built automated reasoning tools, among them the Z3 solver, which is used widely to check software. The first commit to the Lean repository is from July 2013, and version 0.1 appeared in 2014. Lean 2 and Lean 3 followed in the next few years, and Lean 3 in particular found an enthusiastic audience among mathematicians, who in 2017 began building the shared library that became Mathlib.

Lean 3 had a limitation that its users kept running into: it was implemented in C++, so extending the system (writing new tactics, new notations, new automation) meant either writing C++ or using a slow interpreted layer. In 2018 de Moura and Sebastian Ullrich began a redesign from scratch. Lean 4 would be a general-purpose programming language good enough to implement itself: its parser, elaborator, compiler and editor server are written in Lean, and users can extend all of them, in Lean, from their own files. Lean 4 was made public in 2021, when de Moura and Ullrich described it in the paper The Lean 4 Theorem Prover and Programming Language, and version 4.0.0 was released in September 2023. Lean 4 is not backwards compatible with Lean 3; the community ported Mathlib to it, an enormous effort that was finished in 2023. In this course, "Lean" always means Lean 4.

Also in 2023, de Moura and Ullrich founded the Lean FRO (Focused Research Organization), a non-profit that employs a team to develop Lean full time, funded by philanthropic foundations and companies. Lean is open source under the Apache 2.0 licence, released in numbered versions about once a month, and developed in the open on GitHub with many outside contributors. This course uses Lean 4.35.0, the version Lumenary pins for all its Lean code. Lean changes quickly; when a lesson uses something recent, it says so.

DefinitionsH

The toolchain

Definition— elan

elan is the Lean toolchain manager, the equivalent of Rust's rustup. It installs Lean, keeps several versions side by side and, every time you run a Lean command inside a project, picks the version that project asks for.

Definition— lean

lean is the compiler and checker. lean file.lean reads a file, type-checks every definition and proof in it and prints any messages; lean --run file.lean also runs the file's main function. Lean compiles programs to C, which a C compiler bundled with Lean turns into native machine code.

Definition— Lake

Lake (short for "Lean Make") is the build tool and package manager. A Lake project has a configuration file, lakefile.toml, that names its libraries, its executables and its dependencies, and lake build compiles everything in the right order.

Definition— lean-toolchain

Every project has a one-line file called lean-toolchain naming the exact Lean version it uses, such as leanprover/lean4:v4.35.0. elan reads it, so everyone who works on the project uses the same compiler without thinking about it.

The easiest way to install all of this is through the editor. Install VS Code, then install the Lean 4 extension from inside it; the extension opens a setup guide that installs elan and Lean for you. If you prefer the terminal, the official instructions give a one-line command for Linux and macOS and a short PowerShell script for Windows. Either way, check what you have:

bash
elan --version
lean --version
lake --version

Lean is meant to be used interactively. In VS Code, the extension shows an infoview panel beside your code: put the cursor anywhere in a file and the infoview shows the messages for that line, the type of the expression under the cursor and, when you are writing a proof, what remains to be proved. Errors are underlined as you type, long before you run anything. Other editors (Emacs and Neovim among them) have Lean support too, built on the same language server.

If you would rather not install anything yet, the Lean playground runs Lean in your browser with the same infoview. Every program in this course works there.

Worked examplesH

Your first programs

Hello, world

Save this as hello.lean:

lean
def main : IO Unit := do
  IO.println "Hello, world!"
  IO.println "Habari, dunia! Olá, mundo! Xin chào thế giới!"

and run it with lean --run hello.lean:

text
Hello, world!
Habari, dunia! Olá, mundo! Xin chào thế giới!

Read the first line slowly, because almost every Lean program begins this way.

  • def introduces a definition: a name and what it means.
  • main is the name. As in C, Java or Rust, a program starts by carrying out its main.
  • : IO Unit is a type annotation; read the colon as "has type". main is an IO action, a description of input and output to be performed, that produces a value of type Unit when it is done. Unit is the type with exactly one value, written (); it means "nothing interesting", like void in C.
  • := separates a name from its definition.
  • do glues several actions into one, performed in order. The lines inside must be indented by the same amount; Lean uses indentation to see where the block ends.
  • IO.println takes a string and gives back the action of printing it on its own line. You apply a function by writing its argument after it, separated by a space: IO.println "hi", not IO.println("hi").

Strings are Unicode, so the Swahili, Portuguese and Vietnamese greetings print as written.

Asking Lean questions: #eval and #check

A Lean file is not only a program; it is also a conversation with the checker. Commands that start with # ask Lean something while it reads the file. The two you will use most are #eval, which evaluates an expression and shows its value, and #check, which shows its type without evaluating it.

lean
#eval 2 + 3 * 4
#eval "Lean " ++ "4"
#eval [1, 2, 3].length
#eval 10 - 25
#eval (10 : Int) - 25

#check 2 + 3 * 4
#check "Lean " ++ "4"
#check [1, 2, 3]
#check String.length
#check (10 : Int) - 25

Running lean on this file prints one line per command:

text
14
"Lean 4"
3
0
-15
2 + 3 * 4 : Nat
"Lean " ++ "4" : String
[1, 2, 3] : List Nat
String.length (b : String) : Nat
10 - 25 : Int

Most of this is what you would expect: * binds more tightly than +, ++ joins strings, and [1, 2, 3].length asks a list for its length. Two lines deserve a second look.

10 - 25 is 0. A bare number like 10 is a Nat, a natural number: 0, 1, 2 and so on, with no negatives and no upper limit. Since there is no natural number for 10 - 25 to be, subtraction on Nat stops at zero. Writing (10 : Int) tells Lean that this 10 is an integer, and then the answer is -15. This is the first of many places where Lean's types change the meaning of what looks like the same expression; lesson 2 is about exactly that.

#check String.length shows the type of a function: it takes a string, which its definition calls b, and returns a Nat. Reading types like this is how experienced Lean programmers explore a library they do not know yet. In VS Code you can also hover over any name to see its type and documentation.

Definitions of your own

lean
/-- A greeting, with the city it is heard in. -/
def greeting (city : String) (hello : String) : String :=
  s!"In {city} you might hear: {hello}"

/-- "1 day", "2 days": the word agrees with the number. -/
def count (n : Nat) (word : String) : String :=
  if n == 1 then s!"{n} {word}" else s!"{n} {word}s"

def daysToWeeks (days : Nat) : String :=
  s!"{count days "day"} is {count (days / 7) "week"} and {count (days % 7) "day"}"

def main : IO Unit := do
  IO.println (greeting "Nairobi" "Habari")
  IO.println (greeting "Hanoi" "Xin chào")
  IO.println (daysToWeeks 100)
  IO.println (daysToWeeks 365)
text
In Nairobi you might hear: Habari
In Hanoi you might hear: Xin chào
100 days is 14 weeks and 2 days
365 days is 52 weeks and 1 day

A function definition lists its parameters, each in parentheses with its type, then the result type after the last colon. greeting takes two strings and returns a string. The comment that starts with /-- is a documentation comment: the editor shows it when you hover over the name. (-- starts an ordinary comment that runs to the end of the line, and /- … -/ an ordinary block comment.)

s!"..." is an interpolated string: each expression in braces is evaluated, converted to text and spliced in. / and % on natural numbers are division rounded down and the remainder. if … then … else … is an expression with a value, like x if c else y in Python or c ? x : y in C, which is why count needs no return: its body is its result. Calls are nested with parentheses, IO.println (greeting "Nairobi" "Habari"), so that Lean knows greeting gets both strings and IO.println gets the result.

A project with Lake

A single file is fine for experiments, but real programs live in Lake projects. Create one:

bash
lake new greeter
cd greeter
lake build
lake exe greeter

lake new creates a directory with everything a project needs: lakefile.toml (the configuration), lean-toolchain (the Lean version), Main.lean (the program, with a main), a library directory Greeter/ with its root file Greeter.lean, a .gitignore, and even a ready-made GitHub Actions workflow that builds the project on every push. lake build compiles it, through C, into a native executable under .lake/build/bin/, and lake exe greeter runs it, printing Hello, world!. The generated lakefile.toml is short enough to read in full:

text
name = "greeter"
version = "0.1.0"
defaultTargets = ["greeter"]

[[lean_lib]]
name = "Greeter"

[[lean_exe]]
name = "greeter"
root = "Main"

A library (lean_lib) holds your definitions and theorems; an executable (lean_exe) has a main. Most projects have one library and zero or more executables, and Main.lean imports the library with import Greeter. Lesson 10 returns to Lake, dependencies and the package registry.

ExplanationH

How Lean reads a file

It helps to know what happens when Lean reads your file, because it explains most of the error messages you will meet.

Lean processes a file from top to bottom, one command at a time. A command is a def, a theorem, an #eval, an import and so on. For each one, Lean elaborates what you wrote: it fills in everything you left implicit (the types of numbers, the arguments it can infer, the instances of type classes), checks that every piece fits, and, for a definition, hands the result to the kernel, a small, carefully written core that rechecks it independently. Only then does it move on. Two consequences:

  • A name must be defined before it is used. You cannot call a function that appears further down the file. (Lesson 4 shows how to define functions that call each other.)
  • An error in one command does not stop Lean from checking the rest. You see all the problems in the file at once, and the editor marks each where it occurs.

Here is a typical mistake, giving greeting a number where it wants a string, in a file called oops.lean:

lean
def greeting (city : String) (hello : String) : String :=
  s!"In {city} you might hear: {hello}"

#eval greeting "Nairobi" 42
text
oops.lean:4:25: error(lean.synthInstanceFailed): failed to synthesize instance of type class
  OfNat String 42
numerals are polymorphic in Lean, but the numeral `42` cannot be used in a context where the expected type is
  String
due to the absence of the instance above

Hint: Type class instance resolution failures can be inspected with the `set_option trace.Meta.synthInstance true` command.

The message starts with where the problem is: file oops.lean, line 4, column 25, which is exactly where 42 begins. The rest is more informative than it first looks. In Lean, a numeral like 42 does not have a fixed type: it can be a Nat, an Int, a Float, or a number of any type that says how to read numerals (lesson 5 shows how to add that to your own types). Here the expected type is String, and since strings have no way to be written as numerals, Lean reports that it found no OfNat String 42, no way to make the number 42 into a string. Translated: you passed a number where a string was expected. Reading such messages, and noticing which expected type they mention, is a skill you will build quickly.

Two ways of running code are worth keeping apart. #eval runs while the file is being checked: it is a development tool, and its output appears in the editor, not in a program you ship. main is what runs when the program runs, through lean --run (which interprets it, convenient for small scripts) or as a compiled executable built by Lake (which is much faster).

Common misconceptionsH

Common misconceptions

Misconception

"Lean is only for mathematicians." Mathematics is Lean's most visible use, but Lean 4 was designed as a general-purpose programming language, and Lean itself is the largest program written in it. You can write command-line tools, parsers, interpreters and servers in Lean, and you can choose for each part of a program whether to prove things about it. Plenty of Lean code has no proofs at all.

Misconception

"If Lean accepts my file, my program is correct." Lean checks that your program is well typed and that your proofs prove what they state. If you have not stated anything about your program, Lean has guaranteed only that it is well typed, as Java or Rust would. And a proof shows exactly the statement it proves; if the statement is not what you meant, the proof does not help. Lessons 9 and 10 return to the art of writing specifications that say what you mean.

Misconception

"10 - 25 should be -15; Lean has a bug." Lean is doing exactly what the type says. 10 and 25 are natural numbers by default, and subtraction of natural numbers is truncated at zero. Use Int when you need negative numbers, and watch for this whenever you subtract Nats.

Exercises

Exercises

Try each one in your editor or the playground before you look at the hints.

1. First steps in Lean

Warm-upHuman

A project you cloned has a lean-toolchain file asking for a Lean version you have not installed. Which tool notices this and installs the right version for you?

Choose one

2. First steps in Lean

Warm-upHuman

You want to know the type of String.append without running anything. Which command do you write?

Choose one

3. First steps in Lean

CoreComputational

What does Lean show for this command?

#eval 7 - 9 + 4

4. First steps in Lean

CoreComputational

With count and daysToWeeks defined as in the lesson, what does #eval daysToWeeks 8 show? (Include the quotation marks if you like; they are ignored.)

5. First steps in Lean

Warm-upComputational

Lean answers #check "Lean".length with a line of the form "Lean".length : T. What is T?

6. First steps in Lean

CoreHuman

Lean reports an error as shop.lean:12:8: error: …. On which line of shop.lean should you look?

7. First steps in Lean

CoreHuman

Which of these statements about Lean are true? List their letters.

  • A: Lean was started by Leonardo de Moura at Microsoft Research in 2013.
  • B: Lean 4 is written largely in Lean itself.
  • C: Lean 4 can compile Lean 3 files unchanged.
  • D: The Lean FRO, a non-profit, has developed Lean since 2023.
  • E: A file that Lean accepts can contain no mistakes of any kind.

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

Further reading and resources