The maieutics of lambda-calculus

Do you think humans discovered or invented computing?

I lean towards discovery, because the Turing Machine and Church's Lambda-Calculus were formalized independently of each other in 1936, and yet both are also universally expressive (allowing you to calculate everything). Very different, but 100% equivalent.

I'm not talking about the invention of the hardware computer, which can take all forms and generally implement these concepts thanks to electronic circuits and their transistors. I'm talking here about computational logic and the computational thinking that goes with it: that one was floating in the air waiting to be caught and caged.

Like in high school

Let's remember our math lessons, in particular the functions:
Let f(x) = 2*x, a function which multiplies by 2 the value passed to it. Let's name it Double.

So Double(3) = 2*3 = 6
And Double(4) = 2*4 = 8.
Easy.

Same for f(x) = x 1, or Increment.

Increment(3) = 3 1 = 4
Increment(4) = 4 1 = 5
Very easy.

The lambda calculation

The lambda calculation can be written in the same way:
f(x) = x is for example a function which returns the value passed to it.
This function is called I, or Idiot or Identity, and is one of the foundations of lambda calculus.

So Identity(3) = 3
And Identity(4) = 4.
Too easy.

There are others, less obvious, but whose utility lambda-calculus has discovered:
f(x, y) = x is K, Kestrel, or Constant: a function that returns its first argument.

Constant(3, foo) = 3
Constant(foo, 5) = foo

Here’s another one:
f(x) = x(x) is M, Mockingbird or Self-Apply.

But it's too twisted to use it with a number:
f(3) = 3(3) = 3 makes no sense, argument 3 should be a function to be used in turn with an argument.

g(x) = foo here is a function that returns foo every time! Cool, let's call her Dummy.

So if Self-Apply is f(x) = x(x)
And Dummy is g(x) = foo

So Self-Apply(Dummy) = Dummy(Dummy) = foo
Well yes, Dummy applies to itself, and as Dummy always returns foo, we obtain foo in fine.

The magic begins

The combinatorial nature of lambda calculation makes it very simple to understand and manipulate, but also to rediscover.
Just test all the possible associations and combinations, with a certain number of terms, to find all the really different and useful functions.

For example, we discovered that f(x, y, z) = x(y(z)) was a very useful function, and we called it B, Bluebird or Compose.
All you have to do is pass 2 functions and a value to obtain the result of this chain of operations carried out on this 3rd argument.

Compose(Increment, Increment, 3) = Increment(Increment(3)) = Increment(4) = 5
Compound(Double, Double, 10) = Double(Double(10)) = Double(20) = 40
Compound(Compose(Increment, Increment), Double, 10) = (Compose(Increment, Increment))(Double(10)) = Increment(Increment(20)) = Increment(21) = 22

A slightly crazy project

I am embarking on the project of rediscovering all the useful functions of lambda-calculus and implementing them in JavaScript.
I'm going to get help from a friend, Claude, to move forward more quickly by generating all the possible combinations and testing them.

Will he succeed? And we, will we relive and feel what Alonzo Church went through in 1936?

Even crazier hope: can we discover new things by searching for the completeness of these combinations?

The above is the detailed content of The maieutics of lambda-calculus. For more information, please follow other related articles on the PHP Chinese website!