A Flock of Functions: Combinators, Lambda Calculus, & Church Encodings in JS - Part II

The speaker begins by introducing the concept of Church numerals, a way of representing numbers in lambda calculus without using traditional arithmetic operators or equality. They explain how to represent the numbers 0, 1, 2, and 3 using adverbs like 'once', 'twice', and 'thrice', which apply a function a certain number of times to an argument. The speaker also demonstrates how to use these numerals to perform basic operations like identity and negation, setting the stage for building a number system within lambda calculus.

The speaker discusses the challenge of dynamically generating numbers in lambda calculus and introduces the successor function, which takes a Church numeral and returns the next number in the sequence. They illustrate how the successor function works by incrementing the numerals, showing that it adds an extra application of a function to the argument. The concept of function composition is touched upon, and the speaker begins to build a system for converting Church numerals to JavaScript numbers for practical demonstration.

The speaker delves into function composition, a fundamental concept in functional programming, and introduces the Bluebird (B) Combinator, which represents right-to-left function composition. They demonstrate how function composition can be used to create new functions by chaining existing ones. The speaker also shows how the successor function can be expressed as a composition of functions and how this concept can be applied to create more complex operations.

Exploring the theme of adding two Church numerals together, the speaker constructs a lambda calculus function for addition. They explain that adding two numbers can be achieved through n-fold successive applications of the successor function on the other number. The concept of using a combinator to express this addition is introduced, and the speaker provides examples of adding different Church numerals, showcasing the power of function composition in creating arithmetic operations.

The speaker tackles multiplication by explaining how it can be seen as a series of function compositions, specifically the two-fold composition of a three-fold composition of a function. They extend this idea to exponentiation, showing how it can be represented as a nested composition of functions, and introduce a new combinator for exponentiation. The speaker emphasizes the elegance of representing complex arithmetic operations through simple function compositions.

In this section, the speaker introduces the concept of inversion in lambda calculus, focusing on creating a predecessor function using the Phi combinator. They demonstrate how the Phi combinator can shift and increment elements of a pair, effectively allowing for the subtraction of one from a Church numeral. The speaker provides a step-by-step explanation of how this combinator can be used to build a predecessor function, showcasing the depth of lambda calculus in performing arithmetic operations.

The speaker advances the discussion to subtraction and the creation of data structures in lambda calculus. They explain how subtraction can be achieved by applying the predecessor function a certain number of times and introduce the concept of equality and inequality using these arithmetic operations. The speaker also touches on the creation of simple data structures like pairs using the Vireo combinator, laying the groundwork for more complex data structures.

In the concluding part, the speaker reflects on the implications of using lambda calculus for arithmetic and data structure representation. They discuss how real functional programming languages utilize the backbone of lambda calculus while taking shortcuts for practicality. The speaker encourages further exploration of these concepts, emphasizing their value in understanding functional programming paradigms and the potential for creating new functional languages.

The speaker wraps up the session by acknowledging the audience's engagement and interest in the topic. They highlight the importance of understanding the foundational concepts of lambda calculus and its role in enhancing one's ability to think functionally. The speaker also invites questions and further discussion, emphasizing the interactive and exploratory nature of learning functional programming and lambda calculus.