The Lambda Calculus: Practice and Principle

Abstract

The Lambda Calculus has perplexed students of computer science for millennia, rendering many incapable of understanding even the most basic precepts of functional programming. This paper gently introduces the core concepts to the lay reader, assuming only a minimum of background knowledge in category theory, quantum chromodynamics, and paleomagnetism.

In addition, this paper goes on to its main results, showing how the Lambda Calculus can be used to easily prove the termination of Leibniz’ Hailstone numbers for all $n > 0$, to show that matrix multiplication is possible in linear time, and to guarantee Scottish independence.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The fascinating story of the discovery of the Lambda Calculus is well known to all school children, but we here recount the essentials of the story for completeness. In the $27^{th}$ century BC, Egyptian slaves were quarrying stone for the Pyramid of Djoser, northwest of Memphis. Buried deep in the sand, they unearthed a rare stele, complete with the full Lambda Calculus, written in hieroglyphics. At the time, none of the finest scholars of the ancient world could decipher the tablet and for many years it lay forgotten, a relic of a bygone era.

All that changed, however, when in 1929 Alonzo Church came upon the Djoser stele in the British Museum. In the decade before, Church had been working as a chorus girl in a music hall production of the Social Network during its long and infamous tour of the Middle East. There he had developed a passion for hieroglyphics and early Egyptian history. Thus it was that when he first laid eyes on the stone carvings, he instantly knew the significance of the markings and began fervently to decode them. He completed the work in 1932 with the paper, “A set of postulates for the foundation of logic”. His article was an instant success, reaching number one on the New York Times best seller list for twelve weeks running, and earning him a much coveted Turing Award¹. The rest, as they say, is history.

1.1 Lambda Calculus Defined

But, what is the Lambda Calculus? Despite the usual confusion that surrounds it, this dainty and delightful logic can be perfectly described in one short sentence:

“The square of the hypotenuse is the sum of the squares of the other two sides.”

Or more formally:

$$\begin{aligned} E=mc^2 \end{aligned}$$

(1)

Now that the reader is fully conversant with the calculus, the next section describes the importance of Lambda Calculus to circadian rhythm biology.

2 Conclusion and Further Work

This paper has two major contributions. The first is that we are the first researchers to the best of our knowledge to have found a bonefide use for Comic Sans in a scientific paper². The second, arguably more important contribution, is that we have wished Phil Wadler a very happy sixtieth birthday. In the future we hope that while we are exploring more uses for Comic Sans, that Phil has a jolly good time.

We would also strongly recommend that, no matter how much Phil wants to have a washboard stomach and to fight crime, he does not experiment trying to make a radioactive ethernet cable. And, under no circumstances should he go inserting ethernet cables anywhere other than ethernet sockets.