Combinatory logic: from philosophy and mathematics to computer science

Abstract

In 1920, Moses Schönfinkel provided the first rough details of what later became known as combinatory logic. This endeavour was part of Hilbert’s program to formulate mathematics as a consistent logic system based on a finite set of axioms and inference rules. This program’s importance to the foundations and philosophical aspects of mathematics is still celebrated today. In the 1930s, Haskell Curry furthered Schönfinkel’s work on combinatory logic, attempting – and failing – to show that it can be used as a foundation for mathematics. However, in 1947, he described a high-level functional programming language based on combinatory logic. Research on functional programming languages continued, reaching a high point in the eighties. However, by this time, object-oriented programming languages began taking over and functional languages started to lose their appeal. Lately, however, a resurgence of functional languages is being noted. Indeed, many of the commonly-used programming languages nowadays incorporate functional programming elements in them, while functional languages such as Haskell, OCaml and Erlang are gaining in popularity. Thanks to this revival, it is appropriate to breathe new life into combinatory logic by presenting its main ideas and techniques in this paper.