Corrado Böhm

Corrado Böhm (17 January 1923 – 23 October 2017) was an Italian computer scientist and Professor Emeritus at the University of Rome "La Sapienza", known especially for his contributions to the theory of structured programming, constructive mathematics, combinatory logic, lambda calculus, and the semantics and implementation of functional programming languages.

Work In his PhD dissertation (in Mathematics, at ETH Zurich, 1951; published in 1954), Böhm describes for the first time a full meta-circular compiler, that is a translation mechanism of a programming language, written in that same language. His most influential contribution is the so-called structured program theorem, published in 1966 together with Giuseppe Jacopini. Together with Alessandro Berarducci, he demonstrated an isomorphism between the strictly-positive algebraic data types and the polymorphic lambda-terms, otherwise known as Böhm–Berarducci encoding.

In the lambda calculus, he established an important separation theorem between normal forms, known as Böhm's theorem, which states that for every two closed λ-terms T1 and T2 which have different βη-normal forms, there exists a term Δ where Δ T1 and Δ T2 evaluate to different free variables (i.e., they may be taken apart internally). This means that, for normalizing terms, Morris' contextual equivalence, which is a semantic property, may be decided through equality of normal forms, a syntactic property, as it coincides with βη-equality.

A special issue of Theoretical Computer Science was dedicated to him in 1993, on his 70th birthday. He is the recipient of the 2001 EATCS Award for a distinguished career in theoretical computer science.

Selected publications Introduced P′′, the first imperative language without GOTO to be proved Turing-complete.