68 • Propositions as Types by Philip Wadler

2023-11-18

Listen in your podcast player by searching for Future of Coding, or via Apple Podcasts | Overcast | RSS

The subject of this episode’s paper — Propositions as Types by Philip Wadler — is one of those grand ideas that makes you want to go stargazing. To stare out into space and just disassociate from your body and become one with the heavens. Everything — life, space, time, existence — all of it is a joke! A cosmic ribbing delivered by the laws of the universe or some higher power or, perhaps, higher order. Humanity waited two thousand years, from the time of the ancient Greeks through until the 1930s, for a means to answer questions of calculability, when three suddenly arrived all at once:

General recursive functions by Gödel in 1934, with functions of sets of natural numbers.
Lambda calculus by Alonzo Church in 1936, with anonymous single-variable functions.
Turing machines by Alan Turing in 1937, with a process for evaluating symbols on a tape.

Then it was discovered that these three models of computation were, in fact, perfectly equivalent. That any statement made in one could be made in the others. A striking coincidence, sure, but not without precedent. But then it was quietly determined (in 1934, again in 1969, and finally published in 1980) that computation itself is in a direct correspondence with logic. That every proposition in a given logic corresponds with a type in a given programming language, every proof corresponds with a program, and the simplification of the proof corresponds with the evaluation of the program.

The implications boggle the mind. How could this be so? Well, how could it be any other way? Why did it take so long to discover? What other discoveries like this are perched on the precipice of revelation?

Philip Wadler is here to walk us through this bit of history, suggest answers to some of these questions, and point us in a direction to search for more.

And we are here, dear listener, to level with you that a lot of this stuff is miserably hard to approach, presented with the symbols and language of formal logic that is so often inscrutable to outsiders. By walking you through Wadler’s paper (and the much more approachable Strange Loop talk), and tying it in with the cultural context of modern functional programming, we hope you’ll gain an appreciation for this remarkable, divine pun that sits beneath all of computation.

68 • Propositions as Types by Philip Wadler

Links