CSLib: The Lean Computer Science Library Clark Barrett, Swarat Chaudhuri, Fabrizio Montesi, Jim Grundy, Pushmeet Kohli, Leonardo de Moura, Alexandre Rademaker, Sorrachai Yingchareonthawornchai Abstract We introduce CSLib, an open-source framework for proving computer-science-related theorems and writing formally verified code in the Lean proof assistant. CSLib aims to be for computer science what Lean’s Mathlib is for mathematics. Mathlib has been tremendously impactful: it is a key reason for Lean’s popularity within the mathematics research community, and it has also played a critical role in the training of AI systems for mathematical reasoning. However, the base of computer science knowledge in Lean is currently quite limited. CSLib will vastly enhance this knowledge base and provide infrastructure for using this knowledge in real-world verification projects. By doing so, CSLib will (1) enable the broad use of Lean in computer science education and research, and (2) facilitate the manual and AI-aided engineering of large-scale formally verified systems. 1 Introduction On its face, Mathlib [ 41 ] is a library of mathematical results and techniques formalized in the Lean [ 31 ] proof assistant. In reality, it is much more than that—it is a community effort by mathematicians all over the world to collect the world’s mathematical knowledge in a form that can easily be vetted and shared. Mathlib provides a platform for a new way to do mathematics, where many people can confidently collaborate on large and challenging projects [ 37 ] . Also, by representing a wide range of mathematical definitions and proofs in a machine-checkable form, it opens up new opportunities for AI systems to aid the process of mathematical discovery [ 44 , 18 ] . This new approach to mathematics is being embraced by a new generation of mathematicians and has gained many prominent champions [ 40 , 23 ] . Mathlib is at the heart of this paradigm shift, and as such, it is hard to overstate its impact. Computer science has always been close to mathematics. Many computer science departments originally emerged as offshoots of mathematics departments, and even today, the distinction between computer science theory and mathematics is blurry. Moreover, computer scientists have long recognized formal mathematics as a power tool that enables the design of reliable and secure systems [ 3 , 8 , 17 ] . However, until now there has been no effort to build a Mathlib-like universal repository of formalized computer science knowledge. In this white paper, we introduce CSLib, 1 1 1 The main CSLib website is at https://cslib.io . The current CSLib codebase is at https://github.com/leanprover/cslib/ . a library for Lean-based formal verification and computer science research that seeks to change this state of affairs. CSLib has two “pillars”: 1. Formalizing all essential computer science concepts in Lean . The formalizations include, but are not limited to, models of computation such as the \lambda -calculus and resource-bounded Turing machines; numerous algorithms and data structures accompanied by proofs of correctness and complexity; concurrency theory; foundations of programming languages; and mathematical tools relevant to computer science that do not currently appear in Mathlib. 2. Building an infrastructure for Lean-based reasoning about everyday imperative code . This infrastructure consists of an intermediate programming language, called Boole, that allows classical imperative constructs to be interspersed with specifications written in Lean; machinery for generating Lean-language verification conditions from Boole code; and verified Boole implementations of the algorithms and data structures covered in Pillar 1. Collectively, the Lean code and proofs in CSLib enable the use of Lean as a medium for mathematically grounded computer science research and development. For example, we can imagine a theory researcher using CSLib’s built-in abstractions to quickly mock up a novel approximation algorithm and theorems capturing its essential properties, a programming languages researcher using the framework to build verified compilers, or a systems researcher using the library to model new network protocols with worst-case guarantees. The Boole framework offers a crucial bridge from Lean to everyday programming languages. Specifically, we envision a world in which code in mainstream languages like Rust and C++ is automatically translated into Boole at scale. CSLib’s built-in infrastructure turns the task of verifying these Boole-language programs into that of proving Lean-language theorems. This proof task is then solved using Lean-language proof machinery. CSLib’s Impact. We see the impact of CSLib taking two forms: addressing an urgent practical need for reliable software systems, and fulfilling a long-term need for more rigorous and scalable computer science. On the first point, progress on software reliability and security is more time-critical than ever because of new risks that developments in AI pose to the world’s computing infrastructure. Today’s AI systems have a remarkable ability to analyze code, making it much easier for an AI-powered malicious actor to find and exploit vulnerabilities. At the same time, AI coding agents are writing more and more of the world’s code. While this leads to overall productivity gains, AI can also introduce correctness errors and security vulnerabilities into code [ 35 ] . Formal methods can mitigate these risks by mathematically proving code—whether human-written or AI-generated—to be free of bugs and vulnerabilities. However, the impact of formal methods has been historically constrained by the immense human effort that they require. Consider seL4 [ 22 ] , the world’s first formally verified operating system kernel. The system had a profound impact: an seL4-powered drone in the DARPA HACMS program famously resisted six weeks of sustained attacks by an elite red team, leading the drone to be called the “most secure drone in the world.” But seL4 also highlights the cost penalties associated with traditional formal verification. The system required over 20 person-years of proof effort and included about 480,000 lines of formal specification and proof in the Isabelle [ 33 ] framework. Such costs are difficult to justify in most commercial settings. The CSLib vision addresses this bottleneck in two ways. Once CSLib has been built, a developer would be able to derive reliable and secure systems compositionally, by putting together pre-verified CSLib components. Second, CSLib can simplify the use of AI in formal verification. AI systems have already demonstrated superhuman formal proof capabilities in the pure mathematics setting [ 18 ] . However, to leverage these capabilities in broad-domain code verification, we need a comprehensive language in which to specify code properties. Lean and CSLib will provide this language. In addition, CSLib will serve as a repository of high-quality data on which to train AI systems for formalization and formal proof. Beyond this impact on practical formal verification, CSLib will serve as a platform for 21st-century computer science research. The formal verification that CSLib enables will induce confidence in claims and allow the large-scale reuse of foundational concepts. We can also imagine AI tools trained on CSLib discovering novel algorithms and settling open claims, extending to computer science the role that AI agents are beginning to play in mathematics research. {forest} (a) Models & logics {forest} (b) Algorithms and data structures Figure 1 : CSLib’s Pillar 1: A possible organization of covered topics. 2 Technical Approach Now we provide some more details on the two pillars of CSLib’s technical approach. 2.1 Pillar 1: Formalizing Computer Science in Lean CSLib’s first development pillar uses Lean to formalize a comprehensive body of models of computation, algorithms, and data structures, along with properties of these artifacts and proofs of these properties. The formalizations are designed to form a coherent and integrated framework rather than a collection of unrelated modules. Such unification leads to a whole that is greater than the sum of its parts and has been key to Mathlib’s impact. The pillar has a synergistic relationship with Mathlib. On the one hand, it heavily uses Mathlib modules for, say, big-O reasoning and probability theory. On the other hand, it formalizes some core mathematics—for example, certain lemmas from combinatorics needed to analyze approximation algorithms or inequalities needed to prove the convergence of optimization algorithms—that are useful in computer science but do not currently appear in Mathlib. Depending on the circumstances, we may either contribute these formalizations to Mathlib or keep them within the CSLib repository. Now we provide some more details on this pillar’s targets. Models & Logics. Over the years, computer scientists have designed a wide range of models of computation . These include models for deterministic, nondeterministic, probabilistic, and quantum computation; models for functional computations, online algorithms, and interactive protocols; models that solve decision problems; and models that approximately solve optimization problems. Many of these models have never been formalized; the ones that have tend to exist in isolated repositories. A key goal of CSLib’s Pillar 1 is to create a unified body of formalizations of these models. Another piece is the formalization of specification notations for models and algorithms. For example, temporal logics are natural for specifying properties of stateful systems; Hoare logic is a standard mechanism for specifying procedural code; separation logic simplifies the specification of low-level imperative computations; linear logic is suitable for reasoning about resource usage and concurrent behaviors. At this point, there is no unified codebase consisting of such specification notations, and CSLib will address this problem. (a) ⬇ structure LTS ( State : Type u ) ( Label : Type v ) where /-- The transition relation . -/ Tr : State → Label → State → Prop (b) ⬇ def LTS . IsBisimulation ( lts : LTS State Label ) ( r : State → State → Prop ) : Prop := ∀ ⦃ s1 s2 ⦄, r s1 s2 → ∀ μ, ( (∀ s1 ’, lts . Tr s1 μ s1 ’ → ∃ s2 ’, lts . Tr s2 μ s2 ’ ∧ r s1 ’ s2 ’) ∧ (∀ s2 ’, lts . Tr s2 μ s2 ’ → ∃ s1 ’, lts . Tr s1 μ s1 ’ ∧ r s1 ’ s2 ’) ) (c) ⬇ theorem LTS . IsBisimulation . inv ( h : lts . IsBisimulation r ) : lts . IsBisimulation ( flip r ) := by simp only [ IsBisimulation ] at h simp only [ IsBisimulation ] intro s1 s2 hrinv μ constructor case left => intro s1 ’ htr specialize h hrinv μ have h ’ := h .2 s1 ’ htr obtain ⟨ s2 ’, h ’⟩ := h ’ exists s2 ’ case right => intro s2 ’ htr specialize h hrinv μ have h ’ := h .1 s2 ’ htr obtain ⟨ s1 ’, h ’⟩ := h ’ exists s1 ’ Figure 2 : (a) Definition of a Labeled Transition System (“LTS”), which models the observable behavior of the possible states of a discrete computational system. (b) Definition of a bisimulation between two states. (c) Theorem establishing that the inverse of a bisimulation is a bisimulation. ⬇ structure TimeM (α : Type *) where ret : α time : ℕ namespace TimeM protected def pure {α} ( a : α) : TimeM α := ⟨ a , 0⟩ def bind {α β} ( m : TimeM α) ( f : α → TimeM β) : TimeM β := let r := f m . ret ⟨ r . ret , m . time + r . time ⟩ instance : Monad TimeM where pure := pure bind := bind /-- Advances the time cost by ‘ c ‘ ( default 1) without changing the value . -/ def tick ( c : ℕ := 1) : TimeM PUnit := ⟨. unit , c ⟩ macro "✓[" c : term "]" body : doElem : doElem => ‘( doElem | do TimeM . tick c ; body : doElem ) /-- ‘✓ x ‘ is ‘ pure x ‘, adding one tick . -/ macro "✓" body : doElem : doElem => ‘( doElem | ✓[1] body ) -- Simp lemmas @ [ simp ] theorem ret_pure {α} ( a : α) : ( pure a : TimeM α). ret = a := rfl @ [ simp ] theorem ret_bind {α β} ( m : TimeM α) ( f : α → TimeM β) : ( m >>= f ). ret = ( f m . ret ). ret := rfl @ [ simp ] theorem ret_tick ( c : ℕ) : ( tick c ). ret = () := rfl @ [ simp ] theorem time_bind {α β} ( m : TimeM α) ( f : α → TimeM β) : ( m >>= f ). time = m . time + ( f m . ret ). time := rfl @ [ simp ] theorem time_pure {α} ( a : α) : ( pure a : TimeM α). time = 0 := rfl @ [ simp ] theorem time_tick ( c : ℕ) : ( tick c ). time = c := rfl -- additional simp lemmas for <* and *> and <*> (...) end TimeM Figure 3 : A monadic API for complexity analysis of elementary algorithms. An object of type \mathtt{TimeM}~\alpha comprises \mathtt{ret} , which is a value of type \alpha , and the \mathtt{time} cost incurred by the computation of this value. The \mathtt{bind} operation chains together two computations and defines the time cost of the composition as the sum of the time costs of the individual operations. The helper function \mathtt{tick} assigns the time cost. The notation \checkmark is syntactic sugar for the invocation of \mathtt{tick} . The final section asserts some basic lemmas that help simplify expressions involving \mathtt{TimeM} . ⬇ import ComplexityAPI variable {α : Type } [ LinearOrder α] def merge : List α → List α → TimeM ( List α) | [], ys => return ys | xs , [] => return xs | x :: xs ’, y :: ys ’ => do ✓ let c := x ≤ y if c then let rest ← merge xs ’ ( y :: ys ’) return ( x :: rest ) else let rest ← merge ( x :: xs ’) ys ’ return ( y :: rest ) /-- Merge sort algorithm that returns a ‘ TimeM ( List α)‘ where the time represents the total number of comparisons . -/ def mergeSort ( xs : List α) : TimeM ( List α) := do if xs . length < 2 then return xs else let half := xs . length / 2 let L := xs . take half let R := xs . drop half let L ’ ← mergeSort L let R ’ ← mergeSort R let result ← merge L ’ R ’ return result /-- MergeSort is functionally correct . -/ theorem mergeSort_correct ( xs : List α) : IsSorted ( mergeSort xs ). ret ∧ List . Perm ( mergeSort xs ). ret xs := by -- Proof omitted /-- Time complexity of mergeSort counted as the number of comparisons . -/ theorem mergeSort_time ( xs : List α) : let n := xs . length ( mergeSort xs ). time ≤ n * clog2 n := by -- Proof omitted Figure 4 : An implementation of Mergesort using the API in Figure 3 . Note how each invocation of the sorting routine returns a sorted list along with a computational cost. With these definitions in place, one can formally state and prove theorems establishing the correctness of Mergesort and its worst-case number of comparisons. While the specific set of formalizations that we will build in this pillar will necessarily evolve over time, Figure 1 -(a) spells out some of the models and logics we currently plan to cover. Figure 2 -(a) and Figure 2 -(b) give concrete examples of formalizations. Specifically, Figure 2 -(a) shows (part of) a Lean definition of labeled transition systems [ 43 ] , a classic model for stateful systems, and Figure 2 -(b) defines bisimulations, a key notion of equivalence between system states. If two states s_{1} and s_{2} are related by a bisimulation, then s_{1} can mimic all transitions of s_{2} by a corresponding transition and vice versa, and the states reached through these original and mimicking transitions remain related by the bisimulation. Transition systems and bisimulations have numerous applications in computer science, in areas from hardware design [ 7 ] to control [ 12 ] to machine learning [ 45 ] . Formal definitions of these concepts and associated theorems (such as the theorem in Figure 2 -(c)) are therefore valuable both from a theoretical and a practical perspective. However, such formalizations are not naturally in scope for Mathlib and are thus an example of the distinct capabilities that CSLib will provide. Algorithms & Data Structures. Pillar 1 will also use Lean to build a comprehensive repository of formally verified algorithms and data structures. Our long-term ambition is for this library to cover all of computer science. In the medium term, we aim for this library to cover all algorithms and data structures that a typical computer science graduate is likely to encounter. Figure 1 -(b) names some of the algorithmic categories that we plan to cover. A key objective in this thread is to formalize analysis of algorithms, including, in particular, the complexity of algorithms. We note that there is much prior work on automatic, lightweight complexity analysis of programs [ 14 , 38 ] , and some work on proof-assistant-based complexity verification of specific algorithms [ 6 , 5 ] and formalization in Isabelle [ 32 ] . However, we are only aware of one effort [ 19 ] on the systematic formalization of algorithmic complexity in Lean. That formalization [ 4 ] was focused on stochastic oracle computations; by contrast, we aim for a universal framework for complexity analysis. The precise definition of the framework that we propose will require more work and evolve over time. For now, we show in Figure 3 a simple monadic API, akin to Mathlib’s Writer monad and inspired by prior work on analysis of functional algorithms [ 9 , 11 ] , that will be part of CSLib’s complexity analysis framework. The API packages return values of procedures with the cost of computing these values; see Figure 4 for an example of its use. Treating time complexity as a computational effect makes correctness and complexity analysis orthogonal. Also, by giving users control over tick placement, the framework enables experimentation with different cost models, enabling a diverse set of complexity analyses. At the same time, the API has multiple limitations. For example, it relies on manual tick annotations that a user could accidentally get wrong rather than automated verification of execution costs. Also, it cannot directly prove statements of the form “no algorithm can solve problem X faster than f(n) .” However, because it is lightweight and allows proof of many interesting theorems about algorithmic complexity, it is a good starting point for our efforts. In the longer run, we plan to complement this approach with heavier-weight methods that formalize complexity via explicit RAM and query models. 2.2 Pillar 2: Infrastructure for Reasoning about Everyday Code CSLib’s second pillar will develop a powerful new infrastructure for reasoning about everyday imperative code. Lean has recently added substantial support for the definition [ 42 ] and verification 2 2 2 https://lean-lang.org/doc/reference/latest/The--mvcgen--tactic/ of imperative programs, and we intend to leverage these advances in our Pillar-1 efforts. The methods we pursue in the present pillar are complementary in that they connect Lean-based formal reasoning to the verification of code in mainstream languages like Rust, Python, and C++. Our approach builds on the rich tradition of deductive verification techniques and tools [ 10 , 16 ] , in particular systems built on top of intermediate verification languages (IVLs). Perhaps best-known is the Boogie IVL [ 27 , 26 ] , which is used by many systems (e.g., Dafny [ 25 ] , Viper [ 20 ] , CIVL [ 24 ] , and the Move Prover [ 46 ] ). CSLib’s Pillar 2 will be based on a new IVL called Boole , partly inspired by Boogie, but also leveraging the capabilities and advantages of Lean. Figure 5 : CSLib Code Reasoning Vision. Figure 5 illustrates the long-term vision for CSLib-based code reasoning. We envision a framework with support for multiple front-end languages. A user can write their code accompanied by specifications in Lean. These are then transpiled (translated via compilation) to Boole. We plan to build a deductive verification platform built around Boole, which can use various algorithms and back-ends to generate verification conditions in Lean. These can then be discharged using various Lean automation techniques. ⬇ import Strata . MetaVerifier import Smt import Smt . Rat open Strata def loopSimple : Strata . Program := # strata program Boole ; procedure loopSimple ( n : int ) returns ( r : int ) spec { requires ( n >= 0); } { var sum : int ; var i : int ; sum := 0; i := 0; while ( i < n ) invariant ( i <= n && (( i * ( i -1)) div 2 == sum )); { sum := sum + i ; i := i + 1; } assert [ sum_assert ]: (( n * ( n -1)) div 2 == sum ); assert [ neg_cond ]: ( i == n ); r := sum ; }; # end # prove_vcs loopSimple by all_goals ( try smt ) Figure 6 : A simple program, written in the Boole dialect of Strata, for computing the sum of the first n positive integers. This vision is guided by several forward-looking design principles, which aim to avoid shortcomings and pitfalls revealed by previous work: ( i ) Boole should look like pseudocode and be easy for humans to understand; ( ii ) Boole and its ecosystem will be embedded in Lean, and both the transpilation step and the verification condition generation step should be implemented with the goal of minimizing the trusted computing base (TCB); ( iii ) verification conditions should be generated as Lean goals and should be intuitive for humans to read and easily connectable to the code they came from; and ( iv ) code specifications and verification conditions should be able to leverage the rich formal universe defined in CSLib’s Pillar 1. Verification condition generation from Boole will build on infrastructure and ideas from other open source projects, such as Loom [ 13 ] and Strata. Loom 3 3 3 https://github.com/verse-lab/loom provides a mechanism for the definition of shallowly-embedded languages in Lean (including a Dafny-like language called Velvet), with strong guarantees about correct verification condition generation. Strata 4 4 4 https://github.com/strata-org/Strata is an open-source project that aims at facilitating the creation of domain-specific languages called dialects , which are deeply embedded in Lean. ⬇ case entry_invariant_0 ⊢ ∀ ( n : Int ), 0 < n → n ≥ 0 → 0 ≤ n ∧ True case arbitrary_iter_maintain_invariant_0 ⊢ ∀ ( n i sum : Int ), 0 < n → i < n → i ≤ n ∧ i * ( i - 1) / 2 = sum → n ≥ 0 → i + 1 ≤ n ∧ ( i + 1) * ( i + 1 - 1) / 2 = sum + i case sum_assert ⊢ ∀ ( n i sum i ’ sum ’ : Int ), n ≥ 0 → ( if 0 < n then 0 < n else True ) → ( if 0 < n then i < n else True ) → ( if 0 < n then i ≤ n ∧ i * ( i - 1) / 2 = sum else True ) → ( if 0 < n then ¬ i ’ < n else True ) → ( if 0 < n then i ’ ≤ n ∧ i ’ * ( i ’ - 1) / 2 = sum ’ else True ) → ( if if 0 < n then False else True then if 0 < n then False else True else True ) → n * ( n - 1) / 2 = if 0 < n then sum ’ else 0 case neg_cond ⊢ ∀ ( n i sum i ’ sum ’ : Int ), n ≥ 0 → ( if 0 < n then 0 < n else True ) → ( if 0 < n then i < n else True ) → ( if 0 < n then i ≤ n ∧ i * ( i - 1) / 2 = sum else True ) → ( if 0 < n then ¬ i ’ < n else True ) → ( if 0 < n then i ’ ≤ n ∧ i ’ * ( i ’ - 1) / 2 = sum ’ else True ) → ( if if 0 < n then False else True then if 0 < n then False else True else True ) → ( if 0 < n then i ’ else 0) = n ∀ ( n : Int ), 0 < n → n ≥ 0 → 0 ≤ n ∧ True Figure 7 : Lean verification conditions generated from the program in Figure 6 . Figure 6 shows a simple snippet of Lean code containing a program written in Boole. Boole is implemented as an extension of the Core dialect of Strata, which in turn is largely modeled after the classic Boogie IVL. After a prelude that imports and opens relevant packages, the program itself can be written in an easily readable form. Notice the spec keyword, which signals a specification. In this case, there is a requirement (precondition) that n should be non-negative indicated by the requires keyword. We can also specify a loop invariant using the invariant keyword as well as more general program invariants that should hold at specific points in the code using the assert keyword. We can verify the assertions by translating the specifications and code into verification conditions. This can be done by assigning Lean semantics to each construct in the program and then following the standard deductive verification approach, which involves proving, for certain loop-free paths in the program, that for all possible executions along that path, the precondition for the path ensures the postcondition of the path. The # prove_vcs command in our example invokes a prototype verification condition generator that generates goals in Lean. A set of generated goals is shown in Figure 7 . The first goal, for example, represents a path from the entry to the procedure to the beginning of the loop. The precondition of the program requires n\geq 0 , and the loop condition must be true, implying i