\documentclass{article} \usepackage{amsthm} \usepackage{mathpartir} \usepackage{url} \usepackage{imprimatur} % With hyperref, a block built with the public profile links to its Lean. % Links are coloured, but quietly: a muted blue for the Lean sources and other % URLs, a dark slate for cross-references and citations. \usepackage{xcolor} \definecolor{leansource}{RGB}{43,91,140} \definecolor{crossref}{RGB}{55,65,85} \usepackage[colorlinks,urlcolor=leansource,linkcolor=crossref,citecolor=crossref]{hyperref} \newtheorem{theorem}{Theorem} \newtheorem{example}{Example} % The paper's environments, as imprimatur.toml's [aliases] declares them. \leanblockalias{leangrammar}{} \leanblockalias{leanrules}{} \leanblockalias{leantheorem}{theorem} \leanblockalias{leanexample}{example} \leanblockalias{leanconventions}{} \leanblockalias{leannotation}{} % Conventions of the generated rules: \val is a value, and \rulelabel{Key}{label} % makes a rule a target for \ref. \newcommand\val{v} \makeatletter \newcommand\rulelabel[2]{\def\@currentlabel{#2}\label{rule:#1}} \makeatother \begin{document} \section{A small calculus, generated from Lean} This paper presents a simply-typed $\lambda$-calculus whose definitions and results are in Lean. Everything in a \texttt{lean...} environment below is generated from the Lean development by imprimatur; the rest is written by hand, and the hand-written statements are checked against Lean. The examples are Lean theorems about particular terms, stated by imprimatur as sentences; their names $\mathtt{x}$, $\mathtt{y}$, $\mathtt{z}$ and $\mathtt{f}$ are set in typewriter, to tell them from the metavariables $x$ and $y$ that stand for any name. \subsection{Syntax} Terms are name-carrying: a variable is a name, and an abstraction binds a name. The grammar is generated from the inductive types. The descriptions on the right are the authors': imprimatur keeps them when it regenerates the grammar, and uses the constructors' docstrings only for new ones. \begin{leangrammar}[sum=-gvNYDo1w4, dflt=VDpvVT8fbS]{Stlc.Ty}{Types} \label{gram:Stlc.Ty}\begin{LeanGrammar} \LeanProduction{\tau}{types}{\mathsf{b}}{\leanslot{Stlc.Ty.base}{the base type}} \LeanAlternative{\tau_{1} \to \tau_{2}}{\leanslot{Stlc.Ty.arrow}{functions}} \end{LeanGrammar} \end{leangrammar} \begin{leangrammar}[sum=FuF0yc-Xpz, dflt=Z7b8j8i4cU]{Stlc.Tm}{Terms} \label{gram:Stlc.Tm}\begin{LeanGrammar} \LeanProduction{e}{terms, with names}{x}{\leanslot{Stlc.Tm.var}{a variable}} \LeanAlternative{\lambda x{:}\tau.\, e}{\leanslot{Stlc.Tm.lam}{an abstraction, binding $x$ in $e$}} \LeanAlternative{e_{1}\; e_{2}}{\leanslot{Stlc.Tm.app}{an application}} \LeanAlternative{()}{\leanslot{Stlc.Tm.unit}{the unit value}} \end{LeanGrammar} \end{leangrammar} Terms carry names, so two abstractions that differ only in the name they bind are different terms; $\alpha$-equivalence, in the next section, identifies them. A name is bound by the abstraction that carries it, and free otherwise. \begin{leanexample}[sum=-ZmF1RzDuQ]{Stlc.ex_names}{Names matter} \label{ex:Stlc.ex_names} \LeanProse{$(\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x}) \ne (\lambda \mathtt{y}{:}\mathsf{b}.\, \mathtt{y})$.} \end{leanexample} \begin{leanexample}[sum=58i_iI8ew9]{Stlc.ex_fv}{Bound and free names} \label{ex:Stlc.ex_fv} \LeanProse{(1)~$\mathtt{x} \notin \mathit{fv}{(\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x}\; \mathtt{y})}$ and (2)~$\mathtt{y} \in \mathit{fv}(\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x}\; \mathtt{y})$.} \end{leanexample} \subsection{Names, \texorpdfstring{$\alpha$}{α}-equivalence and substitution} We handle names as Pitts does~\cite{Pitts06}. The basic operation is \emph{swapping}: $(a\ b) \cdot e$ exchanges the names $a$ and $b$ everywhere in $e$, bound, binding and free occurrences alike. Unlike renaming, swapping needs no side condition at a binder, and it is its own inverse; its definition is structural: \begin{center} \begin{leanblock}[view=math, def, sum=kQtdL6J5XN]{Stlc.Tm.swap}{Swapping} \LeanMath{\begin{aligned}(a\ b) \cdot x &= (a\ b)(x) \\ (a\ b) \cdot (\lambda x{:}\tau.\, e) &= \lambda (a\ b)(x){:}\tau.\, (a\ b) \cdot e \\ (a\ b) \cdot (e_{1}\; e_{2}) &= ((a\ b) \cdot e_{1})\; ((a\ b) \cdot e_{2}) \\ (a\ b) \cdot () &= ()\end{aligned}} \end{leanblock} \end{center} Two abstractions are $\alpha$-equivalent when swapping each binder's name with a name $c$ fresh for both, written $c \mathrel{\#} \ldots$, makes their bodies $\alpha$-equivalent: \begin{leanrules}[sum=G1XetiAjYO]{Stlc.Alpha}{Alpha-equivalence} \begin{mathpar} \inferrule[($\alpha$-Var)] { } { x =_{\alpha} x } \and \inferrule[($\alpha$-Lam)] { c \mathrel{\#} a, b, e, e' \\ (a\ c) \cdot e =_{\alpha} (b\ c) \cdot e' } { (\lambda a{:}\tau.\, e) =_{\alpha} (\lambda b{:}\tau.\, e') } \and \inferrule[($\alpha$-App)] { e_{1} =_{\alpha} e_{1}' \\ e_{2} =_{\alpha} e_{2}' } { e_{1}\; e_{2} =_{\alpha} e_{1}'\; e_{2}' } \and \inferrule[($\alpha$-Unit)] { } { () =_{\alpha} () } \end{mathpar} \end{leanrules} The two abstractions below bind their names in opposite orders. Swapping each binder with the fresh name $\mathtt{z}$ makes the bodies equal, so they are $\alpha$-equivalent. \begin{leanexample}[sum=WD7KrnrOnA]{Stlc.ex_alpha}{Two $\alpha$-equivalent terms} \label{ex:Stlc.ex_alpha} \LeanProse{$(\lambda \mathtt{x}{:}\mathsf{b}.\, \lambda \mathtt{y}{:}\mathsf{b}.\, \mathtt{x}) =_{\alpha} (\lambda \mathtt{y}{:}\mathsf{b}.\, \lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{y})$.} \end{leanexample} Substitution $e[u/x]$ is then defined by recursion on $e$. At an abstraction $\lambda a{:}\tau.\, e$ it first swaps $a$ with a name $c$ fresh for $x$, $a$, $e$ and $u$, so that no free name of $u$ is captured, and continues in $(a\ c) \cdot e$\leancheck[stmt=a457f283ff65, sig=3e2ddde53b5b]{Stlc.subst}. Swapping preserves the size of a term\leancheck[stmt=95b8589b3570, sig=c576560f0187]{Stlc.Tm.size_swap}, so the recursion terminates, although $(a\ c) \cdot e$ is not a subterm of the abstraction. The renaming matters when the substituted term has a free name that the binder would capture: here $\mathtt{y}$, so the binder becomes the fresh name $\mathtt{z}$. \begin{leanexample}[sum=RfRJkVYbYV]{Stlc.ex_subst}{Substitution avoids capture} \label{ex:Stlc.ex_subst} \LeanProse{$(\lambda \mathtt{y}{:}\mathsf{b}.\, \mathtt{x})[\mathtt{y}/\mathtt{x}] = (\lambda \mathtt{z}{:}\mathsf{b}.\, \mathtt{y})$.} \end{leanexample} \subsection{Typing} The typing rules are generated from the constructors of \texttt{HasType}. Their labels come from the constructors' docstrings. The well-formedness side conditions of the Lean rules are left implicit, by a convention declared in the notation module. \begin{leanrules}[sum=nDDgEQ1-Ha]{Stlc.HasType}{Typing} \begin{mathpar} \inferrule[T-Var] { \Gamma(x) = \tau } { \Gamma \vdash x : \tau } \and \inferrule[T-Abs] { \Gamma, x{:}\tau_{1} \vdash e : \tau_{2} } { \Gamma \vdash (\lambda x{:}\tau_{1}.\, e) : \tau_{1} \to \tau_{2} } \and \inferrule[T-App] { \Gamma \vdash e_{1} : \tau_{1} \to \tau_{2} \\ \Gamma \vdash e_{2} : \tau_{1} } { \Gamma \vdash e_{1}\; e_{2} : \tau_{2} } \and \inferrule[T-Unit] { } { \Gamma \vdash () : \mathsf{b} } \end{mathpar} \end{leanrules} In the first example $\mathtt{f}$ is a function in the context, applied to the bound variable, so every rule but T-Unit takes part in the derivation. The second is a non-example: the unit value has only the base type, so T-App cannot apply it, and the term has no type at all. \begin{leanexample}[sum=9sob_x5VgU]{Stlc.ex_typing}{A typing derivation} \label{ex:Stlc.ex_typing} \LeanProse{$\mathtt{f}{:}\mathsf{b} \to \mathsf{b} \vdash (\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{f}\; \mathtt{x}) : \mathsf{b} \to \mathsf{b}$.} \end{leanexample} \begin{leanexample}[sum=dDOa2hR2cX]{Stlc.ex_untypable}{An ill-typed term} \label{ex:Stlc.ex_untypable} \LeanProse{$\neg (\exists \tau,\ \vdash ()\; () : \tau)$.} \end{leanexample} \subsection{Reduction} Reduction is call by value. A premise that a term is a value is left implicit: the value is written $\val$ instead. Each rule is labelled from its constructor's name, and can be referred to: rule~\ref{rule:AppLeft} reduces the function of an application. \begin{leanrules}[sum=V5YXLse5tR]{Stlc.Step}{Reduction} \begin{mathpar} \rulelabel{Beta}{($\longrightarrow$-Beta)}% \inferrule[($\longrightarrow$-Beta)] { } { (\lambda x{:}\tau.\, e)\; \val \longrightarrow e[\val/x] } \and \rulelabel{AppLeft}{($\longrightarrow$-App Left)}% \inferrule[($\longrightarrow$-App Left)] { e_{1} \longrightarrow e_{1}' } { e_{1}\; e_{2} \longrightarrow e_{1}'\; e_{2} } \and \rulelabel{AppRight}{($\longrightarrow$-App Right)}% \inferrule[($\longrightarrow$-App Right)] { e_{2} \longrightarrow e_{2}' } { \val\; e_{2} \longrightarrow \val\; e_{2}' } \end{mathpar} \end{leanrules} The identity applied to the unit value $\beta$-reduces at once. When the argument is itself an application, rule~\ref{rule:AppRight} reduces it first: the outer $\beta$-reduction waits until the argument is a value. \begin{leanexample}[sum=iLycR2llh0]{Stlc.ex_beta}{A $\beta$-reduction} \label{ex:Stlc.ex_beta} \LeanProse{$(\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x})\; () \longrightarrow ()$.} \end{leanexample} \begin{leanexample}[sum=Au9X2TsAWI]{Stlc.ex_cbv}{Call by value} \label{ex:Stlc.ex_cbv} \LeanProse{$(\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x})\; ((\lambda \mathtt{y}{:}\mathsf{b}.\, \mathtt{y})\; ()) \longrightarrow (\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x})\; ()$.} \end{leanexample} \subsection{Results} A result can be generated, as a sentence; its key can be a title, declared in the notation module: \begin{leantheorem}[sum=zzIi1wbp85]{Swapping is involutive}{Swapping is involutive} \label{thm:Swapping-is-involutive} \LeanProse{Let $a, b \in \mathit{Name}$ and $e \in \mathit{Term}$. Then $(a\ b) \cdot ((a\ b) \cdot e) = e$.} \end{leantheorem} \begin{leantheorem}[sum=Llwby7f-kQ]{Values are final}{Values are final} \label{thm:Values-are-final} \LeanProse{Let $\val \in \mathit{Val}$ and $e \in \mathit{Term}$. Then $\neg (\val \longrightarrow e)$.} \end{leantheorem} Or as a rule, from a theorem whose hypotheses become its premises: \begin{center} \begin{leanblock}[view=math, rule, sum=fpyxtM_nmj]{Stlc.step_app}{Congruence} \LeanMath{\inferrule{e_{1} \longrightarrow e_{1}'}{e_{1}\; e_{2} \longrightarrow e_{1}'\; e_{2}}} \end{leanblock} \end{center} Or the prose can be written by hand and checked: the unit value has only the base type, that is, if $\Gamma \vdash () : \tau$ then $\tau = \mathsf{b}$\leancheck[stmt=a39c03ca314b, sig=59daca2b7dd5]{Stlc.unit_type}. Should the Lean statement of \verb|unit_type| change, \texttt{imprimatur check} reports this sentence. Instances of these results are examples too. Swapping renames the binder along with the free occurrence, and swapping again (Theorem~\ref{thm:Swapping-is-involutive}) gives the term back. The unit value's only type is $\mathsf{b}$, so it has no function type. \begin{leanexample}[sum=Kp3J3ralk_]{Stlc.ex_swap}{Swapping a binder} \label{ex:Stlc.ex_swap} \LeanProse{$(\mathtt{x}\ \mathtt{y}) \cdot (\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{y}) = (\lambda \mathtt{y}{:}\mathsf{b}.\, \mathtt{x})$.} \end{leanexample} \begin{leanexample}[sum=vrAVDD3vBM]{Stlc.ex_unit_not_arrow}{The unit value is not a function} \label{ex:Stlc.ex_unit_not_arrow} \LeanProse{$\neg (\vdash () : \mathsf{b} \to \mathsf{b})$.} \end{leanexample} \subsection{Type safety} The substitution lemma is proved as Pitts's paper suggests. Typing is equivariant: swapping two names throughout a term and its context preserves its type. \begin{leantheorem}[sum=T-GyIH9gSH]{Equivariance}{Equivariance} \label{thm:Equivariance} \LeanProse{Let $a, b \in \mathit{Name}$, $\Gamma \in \mathit{Context}$, $e \in \mathit{Term}$ and $\tau \in \mathit{Type}$. Assume $\Gamma \vdash e : \tau$. Then $(a\ b) \cdot \Gamma \vdash (a\ b) \cdot e : \tau$.} \end{leantheorem} Applied to Example~\ref{ex:Stlc.ex_typing}, swapping $\mathtt{f}$ and $\mathtt{x}$ throughout the context and the term, the function is now called $\mathtt{x}$ and the bound variable $\mathtt{f}$. \begin{leanexample}[sum=Ab7S8d4Yhx]{Stlc.ex_equivariance}{Equivariance at work} \label{ex:Stlc.ex_equivariance} \LeanProse{$\mathtt{x}{:}\mathsf{b} \to \mathsf{b} \vdash (\lambda \mathtt{f}{:}\mathsf{b}.\, \mathtt{x}\; \mathtt{f}) : \mathsf{b} \to \mathsf{b}$.} \end{leanexample} Typing also depends on the context only at the term's free names, which gives weakening and shadowing at once\leancheck[stmt=8f91408eb45c, sig=a65d051214fc]{Stlc.HasType.agree}. So substitution preserves types: if $\Gamma, x{:}\tau_1 \vdash e : \tau$ and $\Gamma \vdash u : \tau_1$, then $\Gamma \vdash e[u/x] : \tau$. At an abstraction, substitution renames the binder to a fresh name by swapping, and equivariance carries the typing of its body across the renaming; the induction is on the size of $e$, which swapping preserves\leancheck[stmt=6842915c5069, sig=105ed38d10fd]{Stlc.subst_typing}. Type safety follows. \begin{leantheorem}[sum=VQLUk38uFC]{Preservation}{Preservation} \label{thm:Preservation} \LeanProse{Let $e, e' \in \mathit{Term}$, $\Gamma \in \mathit{Context}$ and $\tau \in \mathit{Type}$. Assume $e \longrightarrow e'$ and $\Gamma \vdash e : \tau$. Then $\Gamma \vdash e' : \tau$.} \end{leantheorem} A closed, well-typed application of a function to the identity reduces by rule~\ref{rule:Beta}, and the result has the same type. \begin{leanexample}[sum=LuQF7rf3rY]{Stlc.ex_preservation}{A step preserves the type} \label{ex:Stlc.ex_preservation} \LeanProse{(1)~$\vdash (\lambda \mathtt{f}{:}\mathsf{b} \to \mathsf{b}.\, \mathtt{f}\; ())\; (\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x}) : \mathsf{b}$, (2)~$(\lambda \mathtt{f}{:}\mathsf{b} \to \mathsf{b}.\, \mathtt{f}\; ())\; (\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x}) \longrightarrow (\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x})\; ()$ and (3)~$\vdash (\lambda \mathtt{x}{:}\mathsf{b}.\, \mathtt{x})\; () : \mathsf{b}$.} \end{leanexample} \begin{leantheorem}[sum=CxgvvaS6H8]{Progress}{Progress} \label{thm:Progress} \LeanProse{Let $e \in \mathit{Term}$ and $\tau \in \mathit{Type}$. Assume $\vdash e : \tau$. Then $e \in \mathit{Val} \vee (\exists e',\ e \longrightarrow e')$.} \end{leantheorem} Progress needs the term to be closed. An open term can be well typed and yet stuck: neither a value nor able to reduce, since no rule applies to a variable. \begin{leanexample}[sum=atC6biB2FK]{Stlc.ex_stuck}{An open term may be stuck} \label{ex:Stlc.ex_stuck} \LeanProse{(1)~$\mathtt{x}{:}\mathsf{b} \to \mathsf{b} \vdash \mathtt{x}\; () : \mathsf{b}$, (2)~$\mathtt{x}\; () \notin \mathit{Val}$ and (3)~$\forall e : \mathit{Term},\ \neg (\mathtt{x}\; () \longrightarrow e)$.} \end{leanexample} \begin{thebibliography}{1} \bibitem[Pitts(2006)]{Pitts06} Andrew~M. Pitts. \newblock Alpha-structural recursion and induction. \newblock \emph{Journal of the ACM}, 53(3):459--506, 2006. \newblock \url{https://doi.org/10.1145/1147954.1147961}. \end{thebibliography} \appendix \section{Index of notation}\label{app:notation} Metavariables range over the types below; a variable with a subscript or a prime ranges over the same type. imprimatur generates the table from the categories the notation declares, and checks that every variable printed with a metavariable has its type. \begin{leanconventions}[sum=orTYyOUD6_, dflt=hLiHzj5na2]{Conventions}{Metavariables and the types they range over} \begin{longtable}{@{}l@{\quad}l@{\quad}p{.4\linewidth}@{\quad}l@{}} \textit{Variable} & \textit{Type} & & \textit{Shown in}\\ \hline\endhead $\tau$ & $\mathit{Type}$ & \leanslot{Stlc.Ty}{types} & \textit{Ty}, p.~\pageref{gram:Stlc.Ty}\\ $e$ & $\mathit{Term}$ & \leanslot{Stlc.Tm}{terms, with names} & \textit{Tm}, p.~\pageref{gram:Stlc.Tm}\\ $\val$ & $\mathit{Val}$ & \leanslot{Stlc.IsValue}{Values} & \textit{Step}\\ \end{longtable} A variable with a prime or a subscript ($\tau'$, $\tau_{1}$) ranges over the same type. \end{leanconventions} The notation, grouped by where it is defined: the paper's own (\textit{Stlc}) and Lean's. Each is written as the paper writes it, with the Lean constant it stands for. \begin{leannotation}[sum=YrVE7ph_x5, dflt=VgTVkeFcO1]{Notation}{The notation of the paper} \begin{longtable}{@{}l@{\quad}l@{\quad}p{.45\linewidth}@{}} \multicolumn{3}{@{}l}{\textit{Lean}}\\ $\Gamma, x{:}\tau$ & \texttt{List.cons} & \leanslot{List.cons/0}{The list whose first element is \LeanCodeInline{head}, where \LeanCodeInline{tail} is the rest of the list}\\ \multicolumn{3}{@{}l}{\textit{Stlc}}\\ $e =_{\alpha} e'$ & \LeanSourceRef{Stlc/Lang.lean}{89}{\texttt{Alpha}} & \leanslot{Stlc.Alpha/0}{α-equivalence}\\ $x{:}\tau$ & \LeanSourceRef{Stlc/Lang.lean}{14}{\texttt{Atom}} & \leanslot{Stlc.Atom/0}{Names of variables}\\ $\mathit{Name}$ & \LeanSourceRef{Stlc/Lang.lean}{14}{\texttt{Atom}} & \leanslot{Stlc.Atom/1}{Names of variables}\\ $\mathit{Context}$ & \LeanSourceRef{Stlc/Lang.lean}{122}{\texttt{Ctx}} & \leanslot{Stlc.Ctx/0}{Contexts: names with their types, the most recent first}\\ $(a\ b) \cdot \Gamma$ & \LeanSourceRef{Stlc/Safety.lean}{82}{\texttt{Ctx.swap}} & \leanslot{Stlc.Ctx.swap/0}{Swapping two names in a context}\\ $\Gamma \vdash e : \tau$ & \LeanSourceRef{Stlc/Lang.lean}{131}{\texttt{HasType}} & \leanslot{Stlc.HasType/0}{Typing}\\ $\vdash e : \tau$ & \LeanSourceRef{Stlc/Lang.lean}{131}{\texttt{HasType}} & \leanslot{Stlc.HasType/1}{Typing}\\ $v \in \mathit{Val}$ & \LeanSourceRef{Stlc/Lang.lean}{117}{\texttt{IsValue}} & \leanslot{Stlc.IsValue/0}{Values}\\ $v \notin \mathit{Val}$ & \LeanSourceRef{Stlc/Lang.lean}{117}{\texttt{IsValue}} & \leanslot{Stlc.IsValue/1}{Values}\\ $\mathit{Val}$ & \LeanSourceRef{Stlc/Lang.lean}{117}{\texttt{IsValue}} & \leanslot{Stlc.IsValue/2}{Values}\\ $\mathtt{f}$ & \LeanSourceRef{Stlc/Examples.lean}{17}{\texttt{Names.f}} & \leanslot{Stlc.Names.f/0}{The name $\mathtt{f}$}\\ $\mathtt{x}$ & \LeanSourceRef{Stlc/Examples.lean}{11}{\texttt{Names.x}} & \leanslot{Stlc.Names.x/0}{The name $\mathtt{x}$}\\ $\mathtt{y}$ & \LeanSourceRef{Stlc/Examples.lean}{13}{\texttt{Names.y}} & \leanslot{Stlc.Names.y/0}{The name $\mathtt{y}$}\\ $\mathtt{z}$ & \LeanSourceRef{Stlc/Examples.lean}{15}{\texttt{Names.z}} & \leanslot{Stlc.Names.z/0}{The name $\mathtt{z}$, fresh for $\mathtt{x}$ and $\mathtt{y}$}\\ $e \longrightarrow e'$ & \LeanSourceRef{Stlc/Lang.lean}{143}{\texttt{Step}} & \leanslot{Stlc.Step/0}{Small-step reduction, call by value}\\ $e_{1}\; e_{2}$ & \LeanSourceRef{Stlc/Lang.lean}{30}{\texttt{Tm.app}} & \leanslot{Stlc.Tm.app/0}{an application}\\ $c \mathrel{\#} a, b, e, e'$ & \LeanSourceRef{Stlc/Lang.lean}{49}{\texttt{Tm.atoms}} & \leanslot{Stlc.Tm.atoms/0}{The names that occur in a term, bound or free}\\ $a \notin \mathit{fv}{(e)}$ & \LeanSourceRef{Stlc/Safety.lean}{16}{\texttt{Tm.fv}} & \leanslot{Stlc.Tm.fv/0}{The free names of a term}\\ $\mathit{fv}(e)$ & \LeanSourceRef{Stlc/Safety.lean}{16}{\texttt{Tm.fv}} & \leanslot{Stlc.Tm.fv/1}{The free names of a term}\\ $\lambda x{:}\tau.\, e$ & \LeanSourceRef{Stlc/Lang.lean}{28}{\texttt{Tm.lam}} & \leanslot{Stlc.Tm.lam/0}{an abstraction, binding $x$ in $e$}\\ $(a\ b) \cdot e$ & \LeanSourceRef{Stlc/Lang.lean}{42}{\texttt{Tm.swap}} & \leanslot{Stlc.Tm.swap/0}{Swapping two names throughout a term: bound, binding and free occurrences alike}\\ $()$ & \LeanSourceRef{Stlc/Lang.lean}{32}{\texttt{Tm.unit}} & \leanslot{Stlc.Tm.unit/0}{the unit value}\\ $x$ & \LeanSourceRef{Stlc/Lang.lean}{26}{\texttt{Tm.var}} & \leanslot{Stlc.Tm.var/0}{a variable}\\ $\tau_{1} \to \tau_{2}$ & \LeanSourceRef{Stlc/Lang.lean}{21}{\texttt{Ty.arrow}} & \leanslot{Stlc.Ty.arrow/0}{functions}\\ $\mathsf{b}$ & \LeanSourceRef{Stlc/Lang.lean}{19}{\texttt{Ty.base}} & \leanslot{Stlc.Ty.base/0}{the base type}\\ $\Gamma(x) = \tau$ & \LeanSourceRef{Stlc/Lang.lean}{128}{\texttt{lookup}} & \leanslot{Stlc.lookup/0}{The type of a name in a context}\\ $e[u/x]$ & \LeanSourceRef{Stlc/Lang.lean}{101}{\texttt{subst}} & \leanslot{Stlc.subst/0}{Capture-avoiding substitution of \LeanCodeInline{u} for \LeanCodeInline{x} in \LeanCodeInline{e}}\\ $(a\ b)(c)$ & \LeanSourceRef{Stlc/Lang.lean}{38}{\texttt{swapAtom}} & \leanslot{Stlc.swapAtom/0}{Swapping two names: \LeanCodeInline{a} becomes \LeanCodeInline{b}, \LeanCodeInline{b} becomes \LeanCodeInline{a}, and other names are unchanged}\\ \end{longtable} \end{leannotation} \end{document}