1 \documentclass[10pt]{article}
\r
3 \title{B\"ohm's Theorem in Abella}
\r
4 \author{Andrea Condoluci}
\r
7 \newcommand{\lc}[0]{{$\lambda$-calculus}}
\r
8 \newcommand{\bohm}[0]{{B\"ohm}}
\r
9 \newcommand{\TODO}[1]{\textcolor{red}{\textbf{TODO} #1}}
\r
10 \newcommand{\fire}[0]{$\lambda_{\operatorname{fire}}$}
\r
12 \newcommand{\conv}[1]{=_{#1}}
\r
13 \newcommand{\convb}[0]{\conv{\beta}}
\r
14 \newcommand{\convbe}[0]{\conv{\beta\eta}}
\r
17 \usepackage{amsmath, amsthm, amssymb}
\r
18 \usepackage{verbatim, hyperref}
\r
19 \usepackage[normalem]{ulem}
\r
20 \usepackage{cleveref}
\r
22 \theoremstyle{definition}
\r
23 \newtheorem{theorem}{Theorem}
\r
24 \newtheorem*{theoren}{Theorem}
\r
25 \newtheorem{lemma}[theorem]{Lemma}
\r
26 % \newtheorem{corollary}[theorem]{Corollary}
\r
27 \newtheorem*{corollary}{Corollary}
\r
28 \newtheorem*{notation}{Notation}
\r
29 \newtheorem*{definition}{Definition}
\r
30 \newtheorem{fact}[theorem]{Fact}
\r
37 Segue una presentazione del progetto di ricerca che effettuerei presso il \textit{Laboratoire d'informatique de l'\'Ecole polytechnique} di Parigi nel gruppo di ricerca \textit{Parsifal} (\url{https://team.inria.fr/parsifal/}), con il supporto economico del programma Marco Polo.
\r
40 \bohm's theorem is a celebrated theorem in untyped lambda-calculus, and it states that lambda-terms behave differently if they are syntactically different. The proof of this statement is well-known, and consists of a separation algorithm manipulating the syntax of lambda-terms. The proof assistant Abella (co-developed at LIX, Paris) is particularly suited to handle proofs which manipulate lambda-terms. Formalizing \bohm's theorem in Abella would both challenge Abella's underlying logic, and assist us proving correct a much harder separation algorithm for a different calculus that we are studying.
\r
43 \section*{Background}
\r
45 % \subsubsection*{Lambda Calculus}
\r
46 \textit{Pure lambda calculus} (which we call \lc) was originally conceived by Alonzo Church, being intended as a general theory of functions which could serve as foundation for mathematics.
\r
47 Its syntax is based on two basic conceptual operations: $\lambda$-abstraction and application. Since \lc{} can represent computable functions, it is considered an idealized functional programming language, where $\beta$-reduction corresponds to a computational step.
\r
49 In the following, we say that $M \convb N$ if $M$ and $N$ are $\alpha\beta$-convertible ($\alpha$ being the renaming of bound variables). $\eta$-conversion allows expansion and contraction of the arguments of functions, and corresponds to function extensionality. A term is in \textit{normal form} when no more $\beta$-reductions are viable.
\r
51 \subsubsection*{Separation Theorem}
\r
52 Among the most important results for \lc{} (like fixpoint, Church-Rosser, and normalization theorems) is the \textit{separation theorem} (also known as \bohm's theorem \cite{bohm}).
\r
54 Even though this theorem may seem a basically syntactical property, its importance lays on showing that the syntactical constructions and the reduction rules of \lc{} work well together \cite{DBLP:conf/lics/Saurin05}. In particular, two essential consequences are:
\r
57 \item any non-trivial model of the \lc{} cannot identify $\beta\eta$-different normal forms;
\r
58 \item normal forms can be explored by the only means of computational rules.
\r
61 Intuitively, \bohm's theorem states that when two $\lambda$-terms are syntactically different, then one can put them in the context of a bigger $\lambda$ program such that they reduce to two clearly different terms. By \textit{context} (denoted by $E[\,]$) we mean a $\lambda$-term with a hole ($[\,]$ is the hole), such that $E[M]$ is the $\lambda$-term obtained by replacing in $E[\,]$ the hole $[\,]$ with $M$.
\r
63 \begin{theoren}[\bohm{} theorem]
\r
64 Let $M$, $N$ be $\beta\eta$-distinct $\lambda$-terms in normal form; then there exists a context $E[\,]$ such that:
\r
66 E[M] & \convb \operatorname{true} \text{, and}\\
\r
67 E[N] & \convb \operatorname{false}, \\
\r
69 where $\operatorname{true}:=\lambda x\,y.\,x$ and $\operatorname{false}:=\lambda x\,y.\,y$.
\r
71 The proof of this theorem is carried out by induction on so-called \textit{\bohm{} trees} (syntax trees computed from the normal forms), and by means of \textit{\bohm{} transformations}. The technique used in the proof is called ``\bohm-out'', and is a powerful tool that was applied to separation problems in other $\lambda$-theories.
\r
73 Let us now make some remarks which will be useful in the last section.
\r
75 Firstly, note that an easy consequence of the theorem is the following:
\r
78 Let $M$, $N$ be $\beta\eta$-distinct $\lambda$-terms in normal form; then there exists a context $E[\,]$ such that $E[M]$ has a normal form, and $E[N]$ has no normal form.
\r
81 This last formulation of \bohm's theorem is clearly related to the \textit{observational} or \textit{contextual equivalence} \cite{morris}, which was born at the times of the \bohm's theorem. Two terms are said to be \textit{observationally equivalent} if, when put in the same context, either they both converge to a normal form, or they both diverge. Intuitively, terms are observationally equivalent if they behave in the same way, when ``observed'' from the outside.
\r
83 It is now clear that \bohm's theorem actually states that, in the case of terms with a normal form, observational equivalence coincides with $\beta\eta$-convertibility.
\r
85 Note that the original proof of \bohm's theorem is \textit{constructive}: it consists of an actual algorithm which, given two $\beta\eta$-distinct $\lambda$-terms, constructs a corresponding discriminating context. Such algorithm was implemented in CAML in \cite{DBLP:journals/tcs/Huet93}, but to my knowledge it was never formalized in a \textit{proof assistant}.
\r
86 A formalization would not only yield a verified implementation of the algorithm (which is actually a well-known result and beyond doubt), but mainly:
\r
88 \item probe the proof assistant in which it will be formalized and push it to its limits (see section Outcome);
\r
89 \item be a starting point to help us prove correct other separation algorithms which we are currently working on (see section Future Work).
\r
91 % A formalization would yield a verified implementation (proven to be correct, and to comply with its specification) of the algorithm; in addition, it would add up to the pile of formalized mathematical knowledge, allowing other researchers to build on top of it.
\r
93 \subsubsection*{Abella}
\r
94 The plan is to formalize \bohm's theorem in Abella. \textit{Abella} is an interactive theorem prover based on $\lambda$-tree syntax \cite{DBLP:conf/cade/Gacek08}, and it is intended for reasoning about object languages whose syntactic structure is presented through recursive rules.
\r
96 The strength of Abella is how it treats \textit{binding} in object languages: in fact, object-level bindings are represented in Abella using \textit{meta-level abstractions}. This makes the encoding of object languages much more straightforward, since usual notions related to binding (such as $\alpha$-equivalence and capture-avoiding substitutions) are already built into the logic and need not be implemented again at the specification level.
\r
98 To reason over $\lambda$-tree syntax, Abella uses the $\nabla$ (\textit{nabla}) quantifier, which allows one to move binders from the object-logic to the meta-logic. $\nabla$-bound variables are instantiated with \textit{nominal constants}, and indeed the intuition is that the formula $\nabla x.\,F$ holds iff $F$ holds for whatever $x$, but in a ``generic'' way.
\r
100 As a matter of fact, Abella has been used effectively to formalize proofs in which objects with bindings must be manipulated in a fundamental way: for example, some results in \lc{} (subject reduction, uniqueness of typing, normalizability \`a la Tait) and proof theory (cut-admissibility).
\r
104 As a consequence of Abella's successful handling of binding, and of the syntactic nature of \bohm's theorem, Abella may be particularly well-suited to host its formalization. But this is not completely straightforward: let's see one possible obstacle. One $\nabla$ quantifier handles one binder at the object level, but $\lambda$-terms in strong normal form in \fire{} have the form $\lambda x_1\ldots x_n.\,x_j\,f_1\ldots f_m$ ($f$'s are fireballs), where the normal form begins with $n$ $\lambda$-abstractions. In order to handle iterated binders, it would seem natural for $\nabla$ to quantify over ``vectors'' of variables, but this is not possible at the moment. In the light of this and other technical complications, the formalization of \bohm's theorem won't be trivial, and will hopefully shed some light on possible drawbacks/improvements in Abella's logic; this is also the reason why the hosting research group at LIX, Paris is interested in this project.
\r
106 \section*{Future work}
\r
107 As we noted, the computer formalization of \bohm{}'s theorem would be a convenient result on its own
\r
108 sake; nevertheless, it poses a solid starting point to provide formal proofs of similar separation results in other $\lambda$-theories and other $\lambda$-calculi. %, for example in extensions of \lc, or according to different evaluation strategies.
\r
110 For example, the problem of separating $\lambda$-terms popped up inevitably while working with Claudio Sacerdoti Coen and Beniamino Accattoli on the observational equality of the \textit{fireball calculus} \fire{} \cite{DBLP:conf/lics/AccattoliC15}. Our goal there is to provide a suitable notion of \textit{bisimulation} in order to characterize syntactically the equivalence of programs (i.e. contextual equivalence).
\r
112 \subsubsection*{The Fireball Calculus}
\r
114 \fire{} is an \textit{open} call-by-value \lc{}. Recall that \textit{call-by-value} is an evaluation strategy for the \lc{} in which - intuitively - functions' arguments are evaluated before the function call. \fire{} is similar to Plotkin's call-by-value \lc{}, which is at the foundation of programming languages (OCaml) and proof assistants (Coq), but \fire{} (as a \textit{weak calculus}, when reductions occur only outside abstractions) is particularly elegant because:
\r
116 \item it is \textit{strongly confluent};
\r
117 \item normal forms have a clean syntactic description as \textit{fireballs}: a fireball is either an abstractions (like values in Plotkin), or a variable possibly applied to other fireballs.
\r
120 Strong evaluation may be obtained as usual by iterating the weak one under abstractions. But, mainly because fireballs are not closed under substitutions, the strong calculus has some issues:
\r
122 \item it is \textit{not} confluent;
\r
123 \item contextual equivalence is not closed under reduction.
\r
124 % a term and its strong normal form may not be contextual equivalent (in the usual sense).
\r
125 For example: \[(\lambda y.\,z) \, (x\, x) \to_{\beta} z ,\] but in a context replacing the free variable $x$ with $\lambda x.\, x\, x$, the term on the left diverges, and the one on the right converges.
\r
129 Therefore, it is not easy to give a syntactic characterization of contextually equivalent terms. We are working on a separation algorithm which departs non-trivially from \bohm's theorem and other separation algorithms \cite{BOHM1979271}, and it would be the first (working) separation algorithm in call-by-value. After a couple of months of trial and errors, we now understand quite well the problem, and we are done with designing the separation algorithm. It still remains to prove termination, which seems a difficult task.
\r
130 In fact, while the \bohm-out technique is ``completely described in less than a page of ML code'' \cite{DBLP:journals/tcs/Huet93}, our algorithm (as of now) consists of more than one-thousand lines of OCaml code; additionally, our procedure relies on the careful repetition of basic trasformations in a certain order, that when altered brings easily to looping and non-termination. Proving termination for such a long algorithm \textit{on paper} is a long and error-prone job, which would profit the support of a proof assistant.
\r
132 The formalization of \bohm's theorem would hence be the first step in formalizing our own separation algorithm, and facilitate us proving that the algorithm terminates and is indeed correct.
\r
135 \bibliographystyle{plain}
\r
136 \bibliography{statement}
\r
projects / fireball-separation.git / blob