What is Lean?

Lean is a powerful theorem prover and programming language developed by Microsoft Research. It's designed for writing and verifying mathematical proofs, but its expressive type system and functional programming features make it applicable to a broader range of formal verification tasks. Think of it less like a traditional programming language and more like a highly precise tool for stating and proving complex logical statements, similar to how a mathematician uses formal notation.

At its heart, Lean is a dependently typed functional programming language. This means that types can depend on values, which allows for incredibly expressive type signatures. This capability is crucial for formalizing mathematics, where types can represent properties or propositions that must hold true. For developers familiar with TypeScript, the concept of strong typing and type inference will feel familiar, but Lean takes this to a much deeper level.

Core Concepts and Syntax in a TypeScript Context

To understand Lean, it's helpful to draw parallels with TypeScript. While the syntax is distinct, the underlying ideas of type safety, functions, and data structures can be mapped.

Definitions and Declarations

In Lean, you declare definitions and theorems. A definition is essentially a named value or function. A theorem is a statement that needs to be proven. In TypeScript, you declare constants, variables, and functions.

Consider a simple definition in Lean:

def add (n m : Nat) : Nat := n + m

This defines a function `add` that takes two natural numbers (`Nat`) and returns their sum. A TypeScript equivalent would be:


function add(n: number, m: number): number {
  return n + m;
}

The `Nat` type in Lean is analogous to `number` in TypeScript, though Lean's `Nat` is strictly non-negative integers, providing a stronger guarantee.

Propositions and Proofs

This is where Lean diverges significantly from typical programming languages. Lean allows you to state propositions (statements that can be true or false) and then provide proofs for them.

A simple proposition might be: 'for all natural numbers n, n + 0 = n'. In Lean, this is written as a theorem:


theorem add_zero (n : Nat) : n + 0 = n :=
begin
  -- Proof goes here
end

The `begin ... end` block is where the proof is constructed. This is a proof assistant environment. In TypeScript, you don't typically prove properties of your code in this formal way. You might write unit tests to *verify* that your code behaves as expected for certain inputs, but these are not formal proofs in the mathematical sense.

The proof itself involves using tactics to break down the proposition into smaller, provable steps. For `add_zero`, Lean's standard library already has the proof, but if you were to write it, you might use tactics like `rw` (rewrite) or `reflexivity`.

Data Types

Lean has a rich type system, including algebraic data types (ADTs), similar to those found in languages like Haskell or Rust, and increasingly available in TypeScript via discriminated unions.

For example, a boolean type in Lean:


enum Bool : Type :=
| tt : Bool  -- True
| ff : Bool  -- False

This is conceptually similar to a TypeScript enum or a discriminated union:


type Bool = 'true' | 'false';
// or
type Bool = {
  kind: 'true'
} | {
  kind: 'false'
};

Lean's ADTs can be much more complex, allowing for recursive definitions and dependent types, enabling the formalization of intricate mathematical structures.

Functions and Pattern Matching

Functions in Lean are first-class citizens and can be defined using pattern matching, much like in functional programming languages and increasingly in modern JavaScript/TypeScript.

Consider a factorial function in Lean:


def factorial (n : Nat) : Nat :=
match n with
| 0 => 1
| m + 1 => (m + 1) * factorial m

The TypeScript equivalent using pattern matching (though less idiomatic than a simple if/else for this case) might look like:


function factorial(n: number): number {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
// Or with a more explicit (and less common for numbers) pattern match:
// type Nat = 0 | { _tag: 'succ', pred: Nat };
// function factorial(n: Nat): number { ... }

Lean's pattern matching is exhaustive by default, meaning the compiler will warn you if you haven't covered all possible cases for a given type. This is a significant safety feature that TypeScript also strives for with its type system and control flow analysis.

Why Use Lean?

The primary motivation for using Lean is to achieve a high degree of certainty about the correctness of statements. For mathematics, this means ensuring proofs are absolutely rigorous. In software engineering, it can be applied to:

  • Formalizing critical algorithms: Ensuring that complex algorithms, especially in areas like cryptography or distributed systems, behave exactly as specified under all conditions.
  • Verifying hardware designs: Proving that a hardware design meets its specifications.
  • Developing secure software: Building software where certain security properties can be formally guaranteed.

The learning curve for Lean is steep, especially for those without a background in formal logic or advanced functional programming. However, for problems where absolute correctness is paramount, the investment can be worthwhile. The ability to express complex properties and rigorously verify them is a capability unmatched by standard programming languages.

The Role of TypeScript in Understanding Lean

The article