Skip to content
LumenaryAcademy
Foundations 50 min

Expressions, types and functions

Everything 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.

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

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.

DefinitionsH

The basic types

TypeValuesNotes
Nat0, 1, 2, …arbitrary size; subtraction stops at 0
Int…, −1, 0, 1, …arbitrary size
Float3.5, 0.164-bit IEEE 754 floating point
UInt8 … UInt640 to 2⁸ − 1 … 2⁶⁴ − 1fixed width; arithmetic wraps around
Booltrue, falseresults 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:

lean
#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 = 4
text
1267650600228229401496703205376
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 : Prop

Go through it line by line; each output has a lesson in it.

  • 2 ^ 100 is exact. No overflow, no rounding.
  • On Nat, / rounds down and % is the remainder.
  • 7 / 0 is 0. 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 return 0 when the divisor is 0. 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 / 2 is -4 and -7 % 2 is 1, because -7 = 2 × (-4) + 1. C, Java and Rust round towards zero instead and would give -3 and -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.2 prints as 0.300000 but is not equal to 0.3, exactly as in every language that uses IEEE floating point. Never compare floats with == when the values come from arithmetic.
  • UInt8 holds 0 to 255 and wraps around, so 255 + 1 is 0. 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".length is 5: 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.

Worked examplesH

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:

lean
/-- 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)
text
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: Saturday

Several things to notice.

  • (year month day : Nat) declares three parameters of the same type at once.
  • Each let line names a value for everything below it. The names are not variables: y is the shifted year, once and for all.
  • Both ifs are expressions with values, so they sit on the right of let. An if must always have an else, since the expression needs a value either way, and both branches must have the same type.
  • The formula relies on Nat division rounding down, which is exactly what Zeller's congruence wants. With Int or Float you would have to round by hand.
  • List.getD n "?" returns element n of 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

lean
/-- 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)}"
text
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.

IntuitionH

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.

lean
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)) 41
text
add : Nat → Nat → Nat
add 3 : Nat → Nat
16
81
20
[10, 20, 30, 40, 50]
[30, 40, 50]
"42"
  • add 3 is a partial application: a function of type Nat → Nat that adds 3. twice (add 3) 10 applies it twice: 10, 13, 16.
  • twice is a higher-order function: one of its parameters is itself a function.
  • fun x => x * x is an anonymous function (a lambda; λ x => x * x means the same). Lean usually infers the type of x from where the function is used.
  • (· * 2) is shorthand for fun 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 f applies f to every element of a list; filter keeps the elements for which a test returns true. 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 p reads left to right, in the order things happen, where the nested form (xs.map f).filter p reads inside out. The plain pipe x |> f means f x, and f <| x also means f x, used to avoid a pair of parentheses around a long argument.
  • g ∘ f (type \circ) is composition: the function that applies f, then g.

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.

ExplanationH

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 misconceptionsH

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

Exercises

Predict each answer first, then check it with #eval in your editor or the playground.

1. Expressions, types and functions

Warm-upComputational

What does Lean show for #eval (-9 : Int) / 4?

2. Expressions, types and functions

Warm-upComputational

What does #eval (3 : Nat) - 5 + 5 show?

3. Expressions, types and functions

CoreComputational

With 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

CoreComputational

What does this command show?

#eval [5, 12, 7, 30] |>.filter (· > 6) |>.map (· / 2)

5. Expressions, types and functions

CoreComputational

What is the value of (250 : UInt8) + 10?

6. Expressions, types and functions

CoreHuman

Given def scale (factor : Float) (x : Float) (y : Float) : Float × Float := (factor * x, factor * y), what is the type of scale 2.0?

Choose one

7. Expressions, types and functions

CoreHuman

Which 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

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

Further reading and resources