Corrado Böhm

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.{{Cite web|url=http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.html|title=Boehm-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 T₁ and T₂ which have different βη-normal forms, there exists a term Δ where Δ T₁ and Δ T₂ 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.

• {{Cite journal

|last= Böhm

|first= Corrado

|year= 1954

|title= Calculatrices digitales. Du déchiffrage des formules mathématiques par la machine même dans la conception du programme

|url= https://e-collection.library.ethz.ch/eserv/eth:32719/eth-32719-02.pdf

|journal= Annali di Mat. pura e applicata

|volume= serie IV

|issue= tomo XXXVII

|pages= 1–51

|doi=

}} {{Cite web

|last= Böhm

|first= Corrado

|author-mask= 0

|date= 2016-05-04

|title= Böhm: Digital computers. On encoding logical-mathematical formulas using the machine itself during program conception

|url= https://www.itu.dk/people/sestoft/boehmthesis/

|translator-last= Sestoft

|translator-first= B.

}}

• {{Cite journal

|last= Böhm

|first= Corrado

|author-mask= 1

|year= 1964

|title= On a family of Turing machines and the related programming language

|journal= ICC bulletin

|volume= 3

|pages= 185–194

|doi= 10.2307/2270680

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

• {{cite journal

|last1=Böhm

|first1= Corrado

|author1-mask= 1

|author-link1= Corrado Böhm

|last2= Jacopini

|first2= Giuseppe

|author-link2= :it:Giuseppe Jacopini

|date=May 1966

|title=Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules

|journal=Communications of the ACM

|volume=9

|issue=5

|pages=366–371

|doi=10.1145/355592.365646

|citeseerx=10.1.1.119.9119

|s2cid=10236439

}}

• {{Cite journal

|last= Böhm

|first= Corrado

|author-mask= 1

|year= 1968

|title= Alcune proprietà delle forme β-η-normali nel λ-K-calcolo

|lang= it

|journal= Pubbl. INAC

|location= Roma

|volume= 696

|pages=

|doi=

}}

• {{Cite journal

|last1= Böhm

|first1= Corrado

|author1-mask= 1

|last2= Berarducci

|first2= A.

|year= 1985

|title= Automatic Synthesis of typed Lambda-programs on Term Algebras

|journal= Theoretical Computer Science

|volume= 39

|pages= 135–154

|doi= 10.1016/0304-3975(85)90135-5

}}

• {{Cite conference

|last= Böhm

|first= Corrado

|author-mask= 1

|chapter= Functional Programming and Combinatory Algebras

|title= MFCS

|editor1-last= Chytil

|editor1-first= M.P.

|editor2-last= Janiga

|editor2-first= L.

|editor3-last= Koubek

|editor3-first= V.

|series= LNCS 324

|pages= 14–26

|year= 1988

|location= Carlsbad, Czechoslovakia

}}

• P′′, a minimal computer programming language
• Structured program theorem
• List of pioneers in computer science
• Böhm tree
• Böhm's theorem

{{Reflist}}

• [http://www.dsi.uniroma1.it/~boehm/ Vitae (University of Rome)]

• {{MathGenealogy|id=54451}}
• [http://www.informatik.uni-trier.de/~ley/db/journals/tcs/tcs121.html "A Collection of Contributions in Honour of Corrado Böhm on the Occasion of his 70th Birthday"], Theoretical Computer Science, Volume 121, Numbers 1&2, 1993.
• [http://www.corradobohm.eu Corrado Böhm's personal page].

{{EATCS Award laureates}}

{{Authority control}}

{{DEFAULTSORT:Bohm, Corrado}}

Category:1923 births

Category:2017 deaths

Category:Italian computer scientists

Category:Academic staff of the Sapienza University of Rome

Category:Italian people of German descent

Category:École Polytechnique Fédérale de Lausanne alumni

Category:20th-century Italian scientists

Category:21st-century Italian scientists

Category:Scientists from Milan

{{compu-scientist-stub}}