The lambda-calculus builds the functionality of typical languages with only a few (atypical) components.
On November 18, the Math and Computer Science Society continued their monthly lecture series over Zoom with a talk from Dr. Geoff Cruttwell, professor in the math and computer science department. Cruttwell spoke on the lambda-calculus, an abstract programming language that looks very different to the languages students learn in undergraduate computer science courses. “When doing research, I’m always on the lookout for lecture topics that may be accessible and of interest to an audience of undergraduates,” he said. To him, the lambda-calculus seemed like a very different, fascinating topic to cover. First developed in the 1930s by Alonzo Church, the lambda-calculus is just one early mathematical description of what a computer is and does.
“Around twenty, twenty-five minutes into the lecture you might start thinking: ‘What is this nonsense?’” said Cruttwell at the start of the lecture. He promised that once he got into the implementation of the lambda-calculus, it would start to make more sense. Typical programming languages students learn (e.g. Python, Java) have built-in English-like commands that you can combine in various ways to solve complex problems; these components include the use of changeable variables, conditional and true-false (Boolean) logic, repetition through loops, and mathematical operations. “All programs are built up from putting these primitive commands together in various ways,” said Dr. Cruttwell. “Lambda-calculus is no different, but there are only three ways to build up a program.
These rules describe how to apply and reduce lambda-calculus programs. However, they differ from those of typical programming languages. “There is no explicit support for numbers, arithmetic operations, Boolean logic, conditional statements, or loops,” said Cruttwell. The only symbols you will see in a lambda-calculus program are brackets, the lambda (λ) symbol, and variables. The programs consist of many, many terms on a single line, as opposed to typical languages with roughly one command per line. Another weird quality is that one lambda-calculus program can use another program as input, and these two programs can be within another program. Effectively, the data can be the program and the program can be the data. Think of a calculator; you give it an input, and it produces an output. It is difficult to imagine it working any other way, but the lambda-calculus manages to do just that.
If the lambda-calculus seems to lack the functionality needed to create basic computer programs, how can it be a programming language? It turns out, a number of mathematicians and computer scientists have been able to define things within it like the natural numbers, values for “true” and “false,” conditional statements and loops, and even recursion and complex ways to store data. “You might be wondering how you even think of these rules, since it’s not very obvious. It took people working on the lambda-calculus quite a bit of time to come up with all this,” said Cruttwell. But in the end, these rules combine to give the functionality of the standard programming languages we regularly encounter. “You have this language with just a few weird terms and rules, but you have behaviour like normal math and programming languages,” he said. While it isn’t exactly a practical programming language, it is very useful theoretically. For example, one new and exciting area of research is differential programming; this involves trying to differentiate a program like you would a function in calculus. This was first understood theoretically by combining the mathematical rules of differentiation with the lambda-calculus.
Amanda Porter, a third year math student, attended Cruttwell’s lecture. The representation of binary logic in the lambda-calculus was very interesting to her. “This is a simple concept that most programming languages can handle simply, however in lambda-calculus the representation of true and false values are very different from the common understanding of these terms,” she explained. While the lambda-calculus is unconventional by our standards, Porter said Cruttwell made the material accessible by breaking the concept into smaller sections and relating it to more well-known programming languages. “These lectures can expose you to topics that you might have not been introduced to in your regular classes,” she said. “Particularly in math, I think many students forget that there are still big and important questions that need to be solved in the field. These lectures are important reminders about the creative process of math that can often be lost in the computative routine of undergrad.”
Saralin Zassman, a fourth-year math and computer science student, is the president of the Math and Computer Science Society. She found the lecture’s topic quite fascinating. “I like learning about what different profs at Mt. A are interested in. I find that it can be really refreshing to sit down and learn something unrelated to my current course material,” she said. Justin Hughes is also a fourth-year math and computer science student and the VP External for the Math and CS Society. The lecture, he said, covered an interesting combination of mathematics and computer science. “As someone who studies both math and computer science, it was very interesting to see the two of them put together,” he said.
Cruttwell’s lecture is just one in a series the society has arranged. “The Math and CS Society is doing this lecture series to help other math and CS students, along with students from other disciplines, gain exposure to other subjects related to math and computer science, and to learn things not commonly taught in your standard classroom,” said Hughes. They will be continuing the lecture series in the winter semester. “We like to host a good mix of fun and academic activities, so this is one of our academic events,” said Zassman. In addition to the lecture series, they plan to host another Among Us game night in the winter term.
To keep up to date on the Math and CS Society’s events, students can join their Facebook group or follow their Instagram page (@mtamathcssociety), or can be added to the mailing list by emailing Zassman at [email protected]. Cruttwell hopes that lectures like this can help students see there are so many interesting things outside of class that are not covered in an undergraduate degree. “There is a whole wide world of computer science and math, and we give you just a small taste of it,” he said. Interested in learning more about the lambda-calculus? Dr. Cruttwell recommends these links:
Keynote: Why Functional Programming Matters – John Hughes, Mary Sheeran (Lambda Days 2017)
As an example, the two program segments below do the same thing. If the input is 0, the output is 1. If the input is anything else, the output is 2. You can see why the lambda-calculus has not caught on in practical use!
Using Python, a standard language learned by many undergraduate students:
def my_function (n) : if n == 0 : return 1 else : return 2
Using the lambda-calculus:
λn.λp.λM.λN.(p M N)(λn.(n(λx.F)) T n)λf.λx.(f x) λf.λx.(f f x)
