Perhaps the most important development emerging from mathematics in the last century is the advent of computers. One important topic that laid the foundations for functional programming languages, together with the perhaps more celebrated lambda calculus, is combinatory logic, invented by Moses Schönfinkel in 1920.

In combinatory logic, we have combinators, which can be combined to simulate any computer program. Theoretically, various instances of the two combinators called S and K suffice to do this. However, additional combinators are usually employed to simplify and shorten the program. One set of combinators that is amenable to a simple conversion from any intended behaviour to combinatory logic is the one containing the six combinators S, K, I, B, C and Y, each having a very specific, but very simple, definition.

Remarkably, these six combinators can simulate mathematical objects like numbers, as well as operations on numbers like addition and multiplication. They can also simulate the logic constructs TRUE and FALSE, besides standard Boolean operations like AND, OR and NOT. Incredibly, they can additionally simulate data structures like pairs and lists.

Last summer, Alexander Farrugia and Giorgio Grigolo participated in the second edition of the Summer of Math Exposition, organised by the well-known YouTuber Grant Sanderson (a.k.a. 3Blue1Brown) and James Schloss. Farrugia and Grigolo’s submission was a YouTube video explaining the basics of combinatory logic. This video may be watched here. 

This is an impressive feat, considering that the numbers to be sorted,

Subsequently, Farrugia used the functional programming language Haskell to write software that converts a program, written in a very crude language, to combinatory logic, then the resulting combinatory logic expression is evaluated to obtain the required output.

The techniques used to successfully create this software are explained in the YouTube video mentioned beforehand. Rudimentary constructs like truth values, numbers, pairs and lists were programmed using combinatory logic as well, so the execution time is slow.

However, the crude language is expressive enough to allow for the implementation of algorithms like Quicksort, a sorting method that is usually first learned in computing courses at advanced level.

This is an impressive feat, considering that the numbers to be sorted, the natural ordering of numbers, and the list they were in, had to be simulated using combinatory logic before even implementing the algorithm.

Even though combinatory logic is mostly of theoretical interest, this work is proof that mathematics it at the heart of any computation.

Sound Bites

•        Locally: The polynomial reconstruction problem asks if the eigenvalues of a graph – important in theoretical chemistry – can be reconstructed from those of its vertex-deleted subgraphs. In a 2021 paper, Alexander Farrugia of the University of Malta Junior College showed that this problem is solved for those graphs having more than half of their eigenvalues shared by just one of their vertex-deleted subgraphs.

•        Internationally: The problem on how to minimise the surface area of a cluster of bubbles was posed by John Sullivan in 1999. According to leading mathematicians, this problem required at least a century to crack. However, in June 2022, Emanuel Milman of the Technion in Haifa, Israel, and Joe Neeman of the University of Texas published a groundbreaking paper in which they solved Sullivan’s problem for three bubbles in at least three dimensions, and for four bubbles in at least four dimensions.

For more soundbites, listen to Radio Mocha Malta https://www.fb.com/RadioMochaMalta/.

DID YOU KNOW?

•        In a month since the deadline of this year’s Summer of Math Exposition, the submitted videos collectively generated more than seven million YouTube views.

•        Although functional programming languages are not as commonly used as imperative languages like Python, they are still used in industry. Indeed, the functional language Erlang was used to implement some features of Facebook and WhatsApp.

•        Schönfinkel published only two papers in his life. This was because of mental health issues, which he endured for more than 15 years until his untimely death in 1942.

•        Haskell Curry rediscovered combinatory logic a few years after Schönfinkel and continued Schönfinkel’s work. Curry initially focused on showing that combinatory logic could be used as a foundation for mathematics.

For more trivia, see: www.um.edu.mt/think.