No statements, only expressions
In Python or C, a program is made of two kinds of things. Statements do something: x = 5, return y, while (...). Expressions compute something: x + 1, f(y), a < b. Statements run in order and change the state of the machine; expressions produce values.
Lean, like Haskell and OCaml, keeps only the second kind. A Lean function body is a single expression, and running a function means working out its value. if is an expression (it has a value), local definitions are part of an expression, and even the do blocks you saw in lesson 1, which look like sequences of statements, turn out (lesson 6) to be one expression in disguise.
This has a practical consequence you will feel at once: there is nothing to assign to. let x := 5 gives the name x to the value 5 for the rest of the expression; it does not create a box whose contents can change. Functions return the same result whenever they are called with the same arguments. That property, purity, is what later lets us prove things about functions: a statement like "double n is always even" can only make sense if double n means one thing.
The other half of the story is types. Every Lean expression has a type, checked before anything runs, and Lean's type system is far more expressive than most: in later lessons, types will say not only "this is a list" but "this list has length 3" and "this number is less than the size of that array". This lesson starts with the everyday types and the functions between them.
The basic types
| Type | Values | Notes |
|---|---|---|
Nat | 0, 1, 2, … | arbitrary size; subtraction stops at 0 |
Int | …, −1, 0, 1, … | arbitrary size |
Float | 3.5, 0.1 | 64-bit IEEE 754 floating point |
UInt8 … UInt64 | 0 to 2⁸ − 1 … 2⁶⁴ − 1 | fixed width; arithmetic wraps around |
Bool | true, false | results of comparisons such as == and < |
Char | 'a', 'λ' | one Unicode character |
String | "naïve" | Unicode text |
Unit | () | "nothing interesting", like void |
α × β | (3, "three") | pairs; triples nest as α × β × γ |
Nat deserves special attention, because it is the type Lean chooses for a numeral when nothing says otherwise, and because it behaves differently from the integers of most languages. A Nat can be as large as memory allows, so it never overflows. (Small values are stored directly in a machine word; Lean switches to a big-number representation only when it has to, so ordinary arithmetic is fast.) But there are no negative Nats, so subtraction is truncated: 3 - 5 is 0.
Definition— Type ascription
Writing (e : T) tells Lean that the expression e should have type T. On a numeral, it chooses the type of the number: (7 : Int), (7 : Float), (7 : UInt8). On any other expression it is a check that Lean will report if it fails.
Here are the types at work. A file with only #eval and #check commands is checked rather than run, and each command prints its answer:
#eval 2 ^ 100
#eval 7 / 2
#eval 7 % 2
#eval 7 / 0
#eval (-7 : Int) / 2
#eval (-7 : Int) % 2
#eval (7 : Float) / 2
#eval 0.1 + 0.2
#eval 0.1 + 0.2 == 0.3
#eval (255 : UInt8) + 1
#eval 'λ'
#eval "naïve".length
#eval (3, "three")
#check 3.5
#check (3, "three")
#check 3 == 4
#check 3 = 41267650600228229401496703205376
3
1
0
-4
1
3.500000
0.300000
false
0
'λ'
5
(3, "three")
3.5 : Float
(3, "three") : Nat × String
3 == 4 : Bool
3 = 4 : PropGo through it line by line; each output has a lesson in it.
2 ^ 100is exact. No overflow, no rounding.- On
Nat,/rounds down and%is the remainder. 7 / 0is0. Lean does not crash or throw on division by zero. Every Lean function must return a value for every input of its type (the reason will become clear in lesson 4), so division is defined to return0when the divisor is0. This is a convention, not a claim about mathematics; if dividing by zero would be a mistake in your program, check for it.- On
Int,/rounds so that the remainder is never negative:-7 / 2is-4and-7 % 2is1, because-7 = 2 × (-4) + 1. C, Java and Rust round towards zero instead and would give-3and-1. Neither is wrong, but code ported between languages trips on the difference. - A numeral with a decimal point is a
Float. Floats print with six decimals, which hides their rounding:0.1 + 0.2prints as0.300000but is not equal to0.3, exactly as in every language that uses IEEE floating point. Never compare floats with==when the values come from arithmetic. UInt8holds 0 to 255 and wraps around, so255 + 1is0. The fixed-width types exist for speed and for talking to the outside world (bytes in a file, numbers in a network protocol)."naïve".lengthis5: Lean counts characters, not bytes, although the string is stored as UTF-8.
The last two lines introduce a distinction that runs through the whole language. 3 == 4 is a Bool: a value, true or false, that a program computes and branches on. 3 = 4 is a Prop: a proposition, a statement that may or may not be true and that you can try to prove. When you write if a < b then …, Lean quietly decides the proposition a < b for you, which is possible for numbers; for statements about all lists or all numbers, a program cannot just compute the answer, and a proof is needed. Lesson 8 is about Prop; until then, use ==, !=, < and ≤ in if and you will rarely notice.
Expressions with let and if
A function body is one expression, but it can give names to intermediate values with let, and it can choose between two values with if. Here is a classic calculation, Zeller's congruence for the day of the week of a date in the Gregorian calendar:
/-- The day of the week for a Gregorian date, by Zeller's congruence:
0 is Saturday, 1 is Sunday, ..., 6 is Friday. -/
def dayOfWeek (year month day : Nat) : Nat :=
-- January and February count as months 13 and 14 of the previous year.
let y := if month < 3 then year - 1 else year
let m := if month < 3 then month + 12 else month
let k := y % 100 -- year within the century
let j := y / 100 -- the century
(day + 13 * (m + 1) / 5 + k + k / 4 + j / 4 + 5 * j) % 7
def dayName (n : Nat) : String :=
["Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"].getD n "?"
def describe (event : String) (year month day : Nat) : String :=
s!"{event}: {dayName (dayOfWeek year month day)}"
def main : IO Unit := do
IO.println (describe "Organisation of African Unity founded, 1963-05-25" 1963 5 25)
IO.println (describe "India's independence, 1947-08-15" 1947 8 15)
IO.println (describe "First Moon landing, 1969-07-20" 1969 7 20)
IO.println (describe "1 January 2000" 2000 1 1)Organisation of African Unity founded, 1963-05-25: Saturday
India's independence, 1947-08-15: Friday
First Moon landing, 1969-07-20: Sunday
1 January 2000: SaturdaySeveral things to notice.
(year month day : Nat)declares three parameters of the same type at once.- Each
letline names a value for everything below it. The names are not variables:yis the shifted year, once and for all. - Both
ifs are expressions with values, so they sit on the right oflet. Anifmust always have anelse, since the expression needs a value either way, and both branches must have the same type. - The formula relies on
Natdivision rounding down, which is exactly what Zeller's congruence wants. WithIntorFloatyou would have to round by hand. List.getD n "?"returns elementnof the list, or the default"?"if there is none. Lean has no "index out of range" exception here; you say what should happen instead.
Defaults, named arguments and where
/-- A duration in seconds, as h:mm:ss (or mm:ss when `withHours` is false). -/
def clock (seconds : Nat) (withHours : Bool := true) : String :=
let h := seconds / 3600
let m := seconds % 3600 / 60
let s := seconds % 60
if withHours then s!"{h}:{pad m}:{pad s}" else s!"{h * 60 + m}:{pad s}"
where
pad (n : Nat) : String := if n < 10 then s!"0{n}" else toString n
/-- Average pace in seconds per kilometre, rounded down. -/
def pace (seconds : Nat) (metres : Nat) : Nat := seconds * 1000 / metres
def main : IO Unit := do
let marathon := 42195
let time := 3 * 3600 + 27 * 60 + 5
IO.println s!"Finish time: {clock time}"
IO.println s!"Pace: {clock (pace time marathon) (withHours := false)} per km"
IO.println s!"Ten kilometres at that pace: {clock (pace time marathon * 10)}"Finish time: 3:27:05
Pace: 4:54 per km
Ten kilometres at that pace: 0:49:00(withHours : Bool := true) gives a parameter a default value, used when the caller leaves it out. A caller can also pass any argument by name, (withHours := false), which documents the call and lets arguments come in any order. The where clause defines a helper, pad, that is visible only inside clock (its full name is clock.pad). Use where for small helpers that would clutter the file at the top level; use let for values that depend on the parameters.
Notice the order of operations in seconds * 1000 / metres: multiplying first keeps the precision that dividing first would throw away, a habit worth having whenever you compute with Nat.
Functions are values
In Lean a function is a value like any other, with a type of the form A → B (type -> if you cannot type →; the editor turns \to into →). A function of two arguments has type A → B → C, and the arrow groups to the right: A → (B → C). That is not a curiosity of notation. It says that a two-argument function is a function that takes the first argument and returns a function waiting for the second. This is called currying, after the logician Haskell Curry, and it means that you can give a function fewer arguments than it takes and get a function back.
def add (a b : Nat) : Nat := a + b
def twice (f : Nat → Nat) (x : Nat) : Nat := f (f x)
#check (add)
#check add 3
#eval twice (add 3) 10
#eval twice (fun x => x * x) 3
#eval twice (· * 2) 5
#eval [1, 2, 3, 4, 5].map (fun x => x * 10)
#eval [1, 2, 3, 4, 5] |>.map (· * 10) |>.filter (· > 20)
#eval (toString ∘ (· + 1)) 41add : Nat → Nat → Nat
add 3 : Nat → Nat
16
81
20
[10, 20, 30, 40, 50]
[30, 40, 50]
"42"add 3is a partial application: a function of typeNat → Natthat adds 3.twice (add 3) 10applies it twice: 10, 13, 16.twiceis a higher-order function: one of its parameters is itself a function.fun x => x * xis an anonymous function (a lambda;λ x => x * xmeans the same). Lean usually infers the type ofxfrom where the function is used.(· * 2)is shorthand forfun x => x * 2: the·(type\cdot) marks where the argument goes. It is the most common way to write small functions in Lean code.xs.map fappliesfto every element of a list;filterkeeps the elements for which a test returnstrue. Lesson 3 shows how lists are defined, and lesson 7 the rest of the standard library.|>.feeds the value on the left into a method call on the right.xs |>.map f |>.filter preads left to right, in the order things happen, where the nested form(xs.map f).filter preads inside out. The plain pipex |> fmeansf x, andf <| xalso meansf x, used to avoid a pair of parentheses around a long argument.g ∘ f(type\circ) is composition: the function that appliesf, theng.
The #check (add) in parentheses shows the type as an arrow. Without the parentheses, #check add shows the signature, add (a b : Nat) : Nat, which includes the parameter names. Both describe the same function.
Precedence
Function application binds more tightly than any operator. add 1 2 * 3 means (add 1 2) * 3, and f x + 1 means (f x) + 1. To pass a computed argument, parenthesise it: f (x + 1). A negative literal also needs parentheses: f (-1), since f -1 means f - 1. If you remember one rule from this section, remember that a space between two things is the tightest-binding operator in the language.
How experienced Lean programmers write
A few habits are worth adopting from the start.
Write the type of every top-level definition. Lean can infer many types, but a signature is documentation, it makes error messages point at the right place, and it is what readers and the documentation generator see first. Inside a function, leave types off lets unless the number type matters.
Pick the right number type. Use Nat for counts, sizes and indices: they cannot be negative, and the standard library's lengths and indices are Nats. Use Int the moment a value can go below zero, and convert explicitly (Int.ofNat n, or just (n : Int), which Lean understands as a conversion; i.toNat goes back, sending negatives to 0). Use Float for measurements and science, and fixed-width types such as UInt64 only when you need machine arithmetic. Lean's proof tools understand Nat and Int well and Float hardly at all, which matters once you start proving things.
Prefer small functions and the pipeline style. A chain like xs |>.filter p |>.map f |>.foldl g init is idiomatic and easy to read. Lean compiles these efficiently, and later lessons show how to prove facts about each step.
Let the editor tell you types. Hover over any name, or put #check in front of an expression, whenever you are unsure what something is. It is faster than guessing, and it is what experienced Lean programmers do all day.
Common misconceptions
Misconception
"7 / 2 is 3.5." Not unless you ask for a Float. Numerals default to Nat, so 7 / 2 is 3. Write (7 : Float) / 2, or 7.0 / 2, for 3.5. The same applies inside a definition: if the parameters are Nats, so is every division between them.
Misconception
"Division by zero will raise an error." On Nat and Int, x / 0 is 0, silently. Lean's arithmetic is total: it gives an answer for every input. If zero would mean a bug in your program, test for it, or (in lesson 5) make it impossible with a type that rules zero out.
Misconception
"let x := 1 creates a variable I can change later." It names a value. Writing let x := x + 1 below it creates a new x that hides the old one; the old one is unchanged. Lesson 6 shows let mut, which looks like assignment and is useful in do blocks, but it too is translated into a chain of fresh names behind the scenes.
Misconception
"== and = are the same thing." a == b computes a Bool; a = b states a Prop. In an if, both usually work, because Lean can decide equality of numbers and strings. In a theorem, you state equalities with =. Mixing them up becomes important in lessons 8 and 9.
Exercises
Predict each answer first, then check it with #eval in your editor or the playground.
1. Expressions, types and functions
Warm-upComputationalWhat does Lean show for #eval (-9 : Int) / 4?
2. Expressions, types and functions
Warm-upComputationalWhat does #eval (3 : Nat) - 5 + 5 show?
3. Expressions, types and functions
CoreComputationalWith def twice (f : Nat → Nat) (x : Nat) : Nat := f (f x), what is the value of twice (twice (· * 2)) 1?
4. Expressions, types and functions
CoreComputationalWhat does this command show?
#eval [5, 12, 7, 30] |>.filter (· > 6) |>.map (· / 2)
5. Expressions, types and functions
CoreComputationalWhat is the value of (250 : UInt8) + 10?
6. Expressions, types and functions
CoreHumanGiven def scale (factor : Float) (x : Float) (y : Float) : Float × Float := (factor * x, factor * y), what is the type of scale 2.0?
7. Expressions, types and functions
CoreHumanWhich of these expressions have type Bool (rather than Prop)? List their letters.
- A:
3 == 4 - B:
3 = 4 - C:
"a" != "b" - D:
true && false - E:
∀ n : Nat, n + 0 = n
Further reading and resources
- Functional Programming in Lean: Getting to Know Lean · David Thrane ChristiansenThe official book's first chapter covers evaluating expressions, types and functions in more depth.
- The Lean Language ReferenceIts chapter on basic types gives the precise behaviour of Nat, Int, Float, fixed-width integers, characters and strings.
- Types and functional programming (Lumenary CS)The ideas behind this lesson, independent of any one language.