 |
 |
Special Issue Memorizing Corrado Böhm
Editors: Henk Barendregt, Mariangiola Dezani, Benedetto Intrigila
1. A Forgotten Theory of Proofs ?
Looking at MacLane's thesis on proof theory in the light of combinatory logic
2. Revisiting Call-by-value Böhm trees in light of their Taylor expansion
The call-by-value lambda calculus can be endowed with permutation rules, arising from linear logic proof-nets, having the advantage of unblocking some redexes that otherwise get stuck during the reduction. We show that such an extension allows to define a satisfying notion of Böhm(-like) tree and a theory of program approximation in the call-by-value setting. We prove that all lambda terms having the same Böhm tree are observationally equivalent, and characterize those Böhm-like trees arising as actual Böhm trees of lambda terms. We also compare this approach with Ehrhard's theory of program approximation based on the Taylor expansion of lambda terms, translating each lambda term into a possibly infinite set of so-called resource terms. We provide sufficient and necessary conditions for a set of resource terms in order to be the Taylor expansion of a lambda term. Finally, we show that the normal form of the Taylor expansion of a lambda term can be computed by performing a normalized Taylor expansion of its Böhm tree. From this it follows that two lambda terms have the same Böhm tree if and only if the normal forms of their Taylor expansions coincide.
3. Fixed point combinators as fixed points of higher-order fixed point generators
Corrado Böhm once observed that if $Y$ is any fixed point combinator (fpc), then $Y(\lambda yx.x(yx))$ is again fpc. He thus discovered the first "fpc generating scheme" -- a generic way to build new fpcs from old. Continuing this idea, define an $\textit{fpc generator}$ to be any sequence of terms $G_1,\dots,G_n$ such that \[ Y \in FPC \Rightarrow Y G_1 \cdots G_n \in FPC \] In this contribution, we take first steps in studying the structure of (weak) fpc generators. We isolate several robust classes of such generators, by examining their elementary properties like injectivity and (weak) constancy. We provide sufficient conditions for existence of fixed points of a given generator $(G_1,\cdots,G_n)$: an fpc $Y$ such that $Y = Y G_1 \cdots G_n$. We conjecture that weak constancy is a necessary condition for existence of such (higher-order) fixed points. This statement generalizes Statman's conjecture on non-existence of "double fpcs": fixed points of the generator $(G) = (\lambda yx.x(yx))$ discovered by Böhm. Finally, we define and make a few observations about the monoid of (weak) fpc generators. This enables us to formulate new a conjecture about their structure.
4. Gems of Corrado Böhm
The main scientific heritage of Corrado Böhm consists of ideas about computing, concerning concrete algorithms, as well as models of computability. The following will be presented. 1. A compiler that can compile itself. 2. Structured programming, eliminating the 'goto' statement. 3. Functional programming and an early implementation. 4. Separability in {\lambda}-calculus. 5. Compiling combinators without parsing. 6. Self-evaluation in {\lambda}-calculus.
5. Solvability = Typability + Inhabitation
We extend the classical notion of solvability to a lambda-calculus equipped with pattern matching. We prove that solvability can be characterized by means of typability and inhabitation in an intersection type system P based on non-idempotent types. We show first that the system P characterizes the set of terms having canonical form, i.e. that a term is typable if and only if it reduces to a canonical form. But the set of solvable terms is properly contained in the set of canonical forms. Thus, typability alone is not sufficient to characterize solvability, in contrast to the case for the lambda-calculus. We then prove that typability, together with inhabitation, provides a full characterization of solvability, in the sense that a term is solvable if and only if it is typable and the types of all its arguments are inhabited. We complete the picture by providing an algorithm for the inhabitation problem of P.
6. Encoding many-valued logic in $\lambda$-calculus
We will extend the well-known Church encoding of Boolean logic into $\lambda$-calculus to an encoding of McCarthy's $3$-valued logic into a suitable infinitary extension of $\lambda$-calculus that identifies all unsolvables by $\bot$, where $\bot$ is a fresh constant. This encoding refines to $n$-valued logic for $n\in\{4,5\}$. Such encodings also exist for Church's original $\lambda\mathbf{I}$-calculus. By way of motivation we consider Russell's paradox, exploiting the fact that the same encoding allows us also to calculate truth values of infinite closed propositions in this infinitary setting.
7. Covariance and Controvariance: a fresh look at an old issue (a primer in advanced type systems for learning functional programmers)
Twenty years ago, in an article titled "Covariance and contravariance: conflict without a cause", I argued that covariant and contravariant specialization of method parameters in object-oriented programming had different purposes and deduced that, not only they could, but actually they should both coexist in the same language. In this work I reexamine the result of that article in the light of recent advances in (sub-)typing theory and programming languages, taking a fresh look at this old issue. Actually, the revamping of this problem is just an excuse for writing an essay that aims at explaining sophisticated type-theoretic concepts, in simple terms and by examples, to undergraduate computer science students and/or willing functional programmers. Finally, I took advantage of this opportunity to describe some undocumented advanced techniques of type-systems implementation that are known only to few insiders that dug in the code of some compilers: therefore, even expert language designers and implementers may find this work worth of reading. This is a corrected version of the paper arXiv:1809.01427v7 published originally on Feb. 13, 2020.
8. On sets of terms having a given intersection type
Working in a variant of the intersection type assignment system of Coppo, Dezani-Ciancaglini and Venneri [1981], we prove several facts about sets of terms having a given intersection type. Our main result is that every strongly normalizing term M admits a *uniqueness typing*, which is a pair $(\Gamma,A)$ such that 1) $\Gamma \vdash M : A$ 2) $\Gamma \vdash N : A \Longrightarrow M =_{\beta\eta} N$ We also discuss several presentations of intersection type algebras, and the corresponding choices of type assignment rules. Moreover, we show that the set of closed terms with a given type is uniformly separable, and, if infinite, forms an adequate numeral system. The proof of this fact uses an internal version of the Böhm-out technique, adapted to terms of a given intersection type.