As an aspiring programmer, the basic theory of the computer must have some understanding. In recent years, with the development of distributed, cloud computing and other technologies, functional programming languages have become popular. If you’re going to learn functional programming, it’s important to understand the theory behind it. From a benefit perspective, these basic theories remain the same for decades and are well worth the time to learn. Lambda Calculus is as fundamental to functional programming as Newton’s law of gravitation. The rest of this article will focus on the basics of lambda calculus, and finally I’ll try to use es6’s arrow functions to demonstrate how lambda calculus can be used to implement the basic building blocks of a programming language.
What is the lambda calculus?
To understand something, it must be important to understand its history first. The lamda expression was originally developed in 1932 by Alonzo Church, a mathematician at Princeton University. He was also the doctoral supervisor of Alan Turing, the father of computer science.
We all know that modern computers are basically based on Turing machines. In a Turing machine, all computation is actually state-based, which is why we usually declare and use variables in our code: the main purpose of variables is to store state. The Lamda calculus (Lamda Calcus) model proposed by Alonzo Church is actually based on functions. Although the Turing machine model and Lambda calculus model are two different theoretical models, they are virtually equivalent, which means that any computer program based on a Turing machine can be translated equivalently into a program based on a Lambda calculus model.
Lambda calculus is a formal system that studies function definition, function application, and recursion. Its basic components are three expressions: 1. Function definition 2. Identifier reference 3. Function application.
So what exactly is a LAMda expression, and what are its basic components? We all know that in a functional programming language, the basic unit of composition is the function. Lambda expressions are, by definition, anonymous pure functions. ES6 introduced arrow functions, which are essentially what we call lambda expressions:
const lambda = x= > x + 1;
Copy the codeIn fact, most programming languages today have introduced lambda expressions, such as Java, c#, and es6. We tend to think of lambda expressions as black boxes and only care about their inputs and outputs. With no internal state, writing code with functional programming in mind is very different from writing code in imperative languages. As a pure function, the result should be the same every time you run a defined lambda expression.
There are virtually no built-in data structures and logical control statements in pure lambda calculus, but we can use functions to construct all elements of the entire programming language.
Some basic rules in the lambda calculus can be compared to the familiar ES6 syntax:
| Lambda expressions | ES6 arrow function | |
|---|---|---|
| Define a function | Lambda 7.0.x.x | x => x |
| Currie curry | Lambda x. lambda y.x + y | x => y => x + y |
| Application of application | (lambda x. Lambda y.x + y) 5 to 1 | (x => y => x + y) (5) (1) |
How to implement
Before implementing the concrete logic, we need to be clear about one thing: In lambda calculus, lambda expressions themselves can be either operands or functions, like a chicken (lambda expression) that can either eat bugs (another lambda expression) or be eaten by a fox (another lambda expression) (forgive the bad analogy), Collectively, they are called animals (lambda expressions). The bottom line is that in this closed conceptual world, there is only one kind of thing, lambda expressions (functions), and we can use this most basic concept to generate other concepts and operational logic.
In the world of purely functional programming, there are no numbers like 1,2,3 or basic operators such as +-*/, so we need to implement these ourselves manually.
digital
First of all, as a computer design language, numbers are the key, the so-called “number is the origin of everything” in the computer world is simply true. So how do we use lamda expressions to represent numbers? Here, we use the number of function calls to represent the natural numbers, which are also called high odd numbers.
With theory as our guide, we can easily write the following code:
const ZERO = f= > x => x;
const ONE = f= > x => f(x);
const TWO = f= >x => f(f(x)); .Copy the codeOnce you have the numbers, you then need to define a conversion function that converts functional definitions like ZERO and ONE into familiar numbers for easy debugging.
const toNumber = n= > n(i= > i+1) (0);
console.log(toNumber(ONE));
/ / 1
Copy the codeTo calculate
After the above steps, we have defined the most basic numbers. Given these numbers, how do we do some simple addition, subtraction, multiplication and division? Since numbers represent the number of times a function is called, we can define addition here as the sum of the number of times a function is called. For example, to represent the procedure 1+2 equals 3, the input function should be called three times.
const add = n= > m => fn= > x => m(fn)(n(fn)(x));
const TWO = add(ONE)(ONE);
const THREE = add(ONE)(TWO);
toNumber(THREE);
/ / 3
Copy the codeWhere n and m represent the two operands of the add operation.
And then we’re going to do multiplication, and we’re going to review how you learned multiplication as a child. A naive definition of n * m can be expressed as the sum of n m. So in this case, all we need to do is call the function n times and call its result m times. To the code, it looks like this:
const multiply = n= > m => fn= > x => m(n(fn))(x);
const result = toNumber(multiply(TWO)(THREE));
console.log(result);
/ / 6
Copy the codeAs for subtraction and division, the implementation is relatively complex, if you are interested, you can refer to other materials to learn.
Control statements
Let’s take a closer look at implementing conditional branch statements. An important element of conditional branching is booleans. Let’s define the two basic Boolean types TRUE and FALSE:
const TRUE = first= > second => first;
const FALSE = first= > second => second;
Copy the codeIt means choosing one of two things, TRUE means choosing the first, and FALSE is the opposite, choosing the second.
With basic Boolean types defined, it’s easy to implement conditional branching statements:
const ifElse = boolFn= > first => second= > boolFn(first)(second);
// ifElse(TRUE)(x)(y) ===> x
// ifElse(FALSE)(x)(y) ===> y
Copy the codeAdd another conversion function:
const toBoolean = boolFn= > boolFn(true) (false);
console.log(toBoolean(TRUE));
// true
Copy the codeAnd you’re done, Bingo!
logic
Using the Boolean values defined above, it is logical to derive three logical operations: and, or, and not. The reverse logic is easiest, just reverse the logic that defines the conditional branch statement above. This is also strongly related to the definition of Boolean values. If TRUE means choosing the first branch condition, then not reverses this logic:
const not = boolFn= > first => second= > boolFn(second)(first);
toBoolean(not(TRUE));
// false
Copy the codeThe or operator is essentially an operation with two operands, so we need to define a higher-order function that is called twice and receives one operand each time. From our previous definition, we know that TRUE returns the first variable and FALSE returns the second. The or operation means that if one of the operands is TRUE, it returns TRUE. So we can make sure that when TRUE is used as the first argument, it is applied exactly to the TRUE function, and when FALSE is used as the first argument, the function returns the value of the second argument.
const or = first= > second => first(first)(second);
toBoolean(or(TRUE)(FALSE)); // true
toBoolean(or(FALSE)(FALSE)); // false
toBoolean(or(TRUE)(FALSE)) // true
Copy the codeSimilar to the and or operation, we make sure that we return TRUE only when both operands are TRUE. Inverting the implementation logic above yields the following code:
const and = first= > second => first(second)(first);
toBoolean(and(FALSE)(FALSE)); // false
toBoolean(and(FALSE)(TRUE)); // false
toBoolean(and(TRUE)(TRUE)); // true
Copy the codeThis logic may be more round, you can experience the heart.
Recursion (Y combinator)
Let’s start with the simplest definition of recursion, which you’ve all heard of:
Once upon a time there was a mountain, and there was a temple in the mountain. There were an old monk and a young monk in the temple. One day the old monk told the young monk a story. Once upon a time, there was a mountain, and there was a temple in the mountain, and there was an old monk and a young monk in the temple…
Such a concept that keeps referring to itself is a simple definition of recursion.
With the definition of recursion, let’s think about how to use lambda expressions to implement the basic logic of recursion.
Here is an example of a simple Fibonacci sequence (1, 2, 6, 24…). If the language already supports recursion, it’s easy to write code like this:
const factrial => n= > n == 0 ? 1 : n * factrial(n - 1);
Copy the codeIf recursion is not supported in the language, then the name factorial cannot be used directly to refer to itself in a lambda expression.
We can pass the function definition as an argument, since we can’t use an undefined function name in a function declaration:
const makeFactorial = factroial= > n => n == 0 ? 1 : n * factroial(n - 1);
Copy the codeNow that I have a makeFactorial, how do I use it? Suppose we have a seed function now:
const seed = n= > n;
Copy the codeIt doesn’t actually do anything, but we can use the seed function to generate factorial0:
const factorial0 = makeFactorial(seed)
Copy the codeIt is easy to see that the factorial0 function expands like this:
const factorial0 = n= > n == 0 ? 1 : n * (n= > n)(n - 1);
Copy the codeWe know that this function is correct when n is equal to 0, but it is not correct when n is equal to some other number. However, don’t worry, we can use factorial0 to construct factorial1 further:
const factorial1 = makeFactorial(factorial0)
Copy the codeWhen it unfolds:
const factorial1 = n= > n == 0 ? 1 : n * factorial0(n - 1);
Copy the codeThis function is equal to 1 * factorial0(0) when n is equal to 1. We know that factorial0 is correct when n is equal to 0, so factorial1 also works when n is equal to 0 and when n is equal to 1.
Factorail2, Factorial3, Factorial4… .
So the general definition of factorial would look something like this:
constfactorialn = makeFactorial(makeFactorial(...) );// Infinite makeFactorial
Copy the codeAt this point, let’s think further about 🤔, is there any way to make the makeFactorial function keep recursing?
Let’s start by defining a basic loop function:
const loop = x= > x(x);
Copy the codeSo when I call makeFactorial with this function, it’s going to call makeFactorial(makeFactorial), but that definition seems to lack momentum. To keep it going, we can make it call itself one more time:
const loop = (x= > x(x))(x= > x(x))
Copy the codeYou can see that when you plug x = x => x(x) into the loop function, the result is as follows:
const loop = (x= > x(x))(x= > x(x))
Copy the codeStudent: Does it go back to the definition?
However, such a function cannot be used in javascript, because in javascript parameters are passed to the function after the calculation, so we need to delay the calculation of the parameters and change the code to the following:
const loop = (x= > x(x))(y= > x(x)(y))
Copy the codeAfter the parameter y is introduced, the value will be calculated only when it is finally expanded to the last layer, which is also the idea of delayed calculation.
With this loop function, our final factorial is easy to construct:
const factorial = loop(makeFactorial);
Copy the codeLet’s try it on the console:
factorial(4) = 24
Copy the codeIn fact, the loop function defined above is called a Y combinator. This is also a very famous concept in lambda calculus, which is the key to implementing recursion in programming languages that do not support recursion, and is also a difficulty in learning the theory of lambda calculus. It may take a little more thought to fully understand.
conclusion
At this point, we have implemented data, computation, logical and control statements and, most importantly, recursion. These are the core components of a programming language. The magic of lambda calculus is that from one basic building block, a function, a few laws can be used to build the core elements of an entire computer programming language.
Of course, it is not easy to thoroughly understand the whole theory of lambda calculus, and this article is just some thoughts sorting after personal study, which will inevitably have mistakes and omissions. If you find something wrong in the reading process, please contact us to correct it.
— Reprint please specify source —
The resources
Cgnail. Making. IO/academic/la…
Mindhacks. Cn / 2006/10/15 /…
mvanier.livejournal.com/2897.html
zh.wikipedia.org/wiki/ chiu odd? Wp…
zh.wikipedia.org/wiki/ fixed point combinator…
zh.wikipedia.org/wiki/ fixed point? Wp…