Lambda calculus on javascript

Hello! In this article I want to once again look at the lambda calculus. The theoretical side of the question has already been discussed many times in Habré, so let's take a look at how lambda calculus can look in practice, for example, in JavaScript (so that examples can be performed directly in the browser).

So, the basic idea: everything is a function. Therefore, we limit ourselves to a very narrow range of language possibilities: any expression will be either an anonymous function with one argument ( x => expr ), or a function call ( f (x) ). That is, the whole code will look similar:

 id = x => x double = f => x => f (f (x)) 

Since the result of the functions will be other functions, we will need a way to interpret the result. This is the only place where the non-trivial JavaScript features come in handy.

Basic things

We begin, as is customary, with conditional branching. We introduce two constants:
')

 True = t => f => t False = t => f => f 

These are functions of “two arguments”, True returns the first argument, False returns the second argument. That is, the following statements are true:

 console.assert(1 == True (1) (2)) console.assert(2 == False (1) (2)) 

These constants represent logical truth and false, and allow you to write an If function:

 If = b => t => f => b (t) (f) console.assert(1 == If (True) (1) (2)) console.assert(2 == If (False) (1) (2)) 

This already looks like a traditional if , just syntactically looks a little different. With conditional branching, standard boolean operators can be easily implemented:

 Not = x => If (x) (False) (True) And = x => y => If (x) (y) (False) Or = x => y => If (x) (True) (y) 

Next, we introduce the first "data structure" - a pair. The definition is as follows:

 Pair = x => y => (f => f (x) (y)) Fst = p => p (True) Snd = p => p (False) p = Pair (1) (2) console.assert(1 == Fst (p)) console.assert(2 == Snd (p)) 

It looks a little weirder, but it makes sense. A pair in this case is a function that encapsulates 2 values ​​inside itself and is able to transfer them to its parameter when it is called. Similarly, a tuple of any length can be described:

 Triplet = x => y => z => (f => f (x) (y) (z)) Pentuplet = x => y => z => u => v => (f => f (x) (y) (z) (u) (v)) 

Generally speaking, with a similar arsenal, we could already define Byte as a tuple of 8 logical values, Int as a tuple of 4 Byte and implement machine arithmetic on them, but this is a routine matter and will not bring any pleasure. There is a more beautiful way to describe natural numbers - Church arithmetic.

Arithmetic

Church arithmetic describes a set of natural numbers with zero as functions of two arguments:

 Zero = s => z => z One = s => z => s (z) Two = s => z => s (s (z)) Three = s => z => s (s (s (z))) 

The first argument is a function, the second argument is something to which the function is applied n times. For their construction, in essence, only zero and the function +1 are needed:

 Succ = n => (s => z => s (n (s) (z))) 

Succ throws another call s on the left of the existing call chain, thereby returning to us the next in order natural number. If this function seems complicated, there is an alternative option. The result of his work will be exactly the same, but the s sling here takes place on the right:

 Succ = n => (s => z => n (s) (s (z))) 

Here it is also worth describing the way to convert Church numbers in all of us familiar int is exactly the application of the function x => x + 1 to zero n times:

 toInt = n => n (x => x + 1) (0) console.assert(0 == toInt (Zero)) console.assert(1 == toInt (One)) console.assert(2 == toInt (Two)) 

The operations of addition, multiplication, etc are defined similarly:

 Add = n => m => m (Succ) (n) Mul = n => m => m (Add (n)) (Zero) Pow = n => p => p (Mul (n)) (One) //⇈ = n => m => m (Pow (n)) (One) 

In this way, you can continue to implement the switch notation , but there is no point in this: at this point, the principle of working with numbers should be clear.

The next step is subtraction. Following the tradition that has just appeared, its implementation will be like this:

 Sub = n => m => m (Pred) (n) 

but the implementation of the Pred function remains a problem. Fortunately, Wedge invented it for us.

 Pred = n => Fst (n (p => Pair (Snd (p)) (Succ (Snd (p)))) (Pair (Zero) (Zero))) 

History says that this idea came to him during a dentist appointment, and anesthesia was then stronger than it is now. I will not argue with that, but I will explain what is going on here. To obtain the previous number, we construct the pair (n-1, n) as follows: apply the function (x, y) -> (y, y+1) to the pair (0, 0) n times and extract the left component from the result. As a consequence, it is easy to see that the number previous to zero will also be zero. It saves from uncertainty and gives many other advantages.

For completeness, here is the implementation of comparison operations:

 IsZero = n => n (_ => False) (True) Lte = n => m => IsZero (Sub (n) (m)) Lt = n => m => Lte (Succ (n)) (m) Eq = n => m => And (Lte (n) (m)) (Lte (m) (n)) Max = n => m => If (Lte (n) (m)) (m) (n) Min = n => m => If (Lte (n) (m)) (n) (m) 

Lists

Lists are encoded in almost the same way as natural numbers - these are also functions of two arguments.

 Nil = f => x => x L1 = f => x => f (a0) (x) L2 = f => x => f (a0) (f (a1) (x)) L3 = f => x => f (a0) (f (a1) (f (a2) (x))) //... 

It is interesting to note that False , Zero and Nil are the same functions.

If you are familiar with the functional operations on lists, then you probably already noticed that this structure describes the right convolution . Therefore, it is implemented trivially:

 Foldr = f => z => l => l (f) (z) 

Now we implement standard operations for persistent lists — adding to the beginning, getting the head and tail of the list.

 Append = a => l => (f => x => f (a) (l (f) (x))) Head = l => l (a => _ => a) () list = Append (1) (Append (2) (Nil)) console.assert(1 == Head (list)) 

The empty brackets at the end of the description. Head is the head of an empty list. In the correct program, this value should never be used, so I chose the syntactically smallest value. Generally speaking, within these brackets you can write anything. Later in the article there will be another place where I will use empty brackets for the exact same reason.

The function of receiving the tail of the list almost completely repeats the function of obtaining the previous natural number. For the same reason, the tail of an empty list will be an empty list.

 Tail = l => Fst ( l (a => p => Pair (Snd (p)) (Append (a) (Snd (p)))) (Pair (Nil) (Nil)) ) console.assert(2 == Head (Tail (list))) 

As an example of use, I will give an implementation of the map function and some more others:

 Map = m => l => (f => x => l (a => f (m (a))) (x)) Length = l => Foldr (_ => Succ) (Zero) (l) IsEmpty = l => IsZero (Length (l)) //      JavaScript toList = l => Foldr (x => y => [x].concat(y)) ([]) (l) toIntList = l => toList (Map (toInt) (l)) function arraysEqual(a,b) { return !(a < b) && !(b < a); } //    

Map replaces each list item with the result of calling function f on it.
Length and IsEmpty speak for themselves. toList and toIntList will be useful for testing and for displaying lists in the console.

Recursion

By this time, working exclusively with functions has become suspiciously similar to “normal” programming. It's time to spoil everything. Since we have limited ourselves only to declare and call functions, we completely lack any syntactic sugar, which means that we will have to write down many simple things in a complex way.

For example, I want to write the OnNonEmpty : fun => list => result function OnNonEmpty : fun => list => result , which will call the fun function on the list only if it is not empty. Let's try:

 OnNonEmpty = f => l => If (IsEmpty (l)) (Nil) (f (l)) 

See a mistake? If f does not stop on an empty list, then OnNonEmpty will not stop, although it should. The fact is that JavaScript provides us with an applicative order of calculations, that is, all the arguments of a function are evaluated before it is called, no laziness. And the If statement should calculate only one branch, depending on the condition. Therefore, the function must be rewritten, and it will not become more beautiful from it.

 OnNonEmpty = f => l => (If (IsEmpty (l)) (_ => Nil) (_ => f (l))) () 

Now If , depending on the condition, returns the function to be evaluated. And only after that the calculation is made, only in this way can we guarantee laziness.

The second problem is recursion. Inside a function, we can refer only to its formal arguments. This means that the function cannot refer to itself by name.

But there is a solution, this is the notorious "Fixed Point Combinator." Usually, after these words, the description of the combinator Y is given , but it is not suitable for the applicative order. Instead, we will use the combinator Z , shamelessly peeped in this wonderful article .

 Z = f => (x => f (y => x (x) (y))) (x => f (y => x (x) (y))) 

A combinator is a function selected on the basis of exactly one property: Z (f) == f (Z (f)) , that is, Z(f) is such a value of x that x == f (x) . Hence the term "fixed point". But one should not think that by some miracle the combinator is capable of solving equations, instead it represents an infinite recursive call Z(f) = f (f (f (f ( ... )))) .

The “main property” of the combinator gives an excellent “side effect”: the possibility of recursion. For example, the entry:

 MyFun = Z (myFun => ...) 

is equivalent to writing:

 MyFun = (myFun => ...) MyFun //       

which means that the first formal parameter of the anonymous function actually coincides with the MyFun function MyFun , and we can make real recursive calls in it. Let's try on the example of finding the remainder of the division:

 Rem = Z (rem => n => m => ( If (Lt (n) (m)) (_ => n) (_ => rem (Sub (n) (m)) (m)) ) ()) console.assert(1 == toInt (Rem (Three) (Two))) console.assert(0 == toInt (Rem (Three) (One))) 

After that, you can implement our first useful algorithm - the Euclidean algorithm . It's funny, but it came out just as easy as finding the remainder of the division.

 Gcd = Z (gcd => n => m => ( If (IsZero (m)) (_ => n) (_ => gcd (m) (Rem (n) (m))) ) ()) 

Sequences

The last data structure I’m going to touch is “endless lists,” or sequences. Functional programming is famous for the opportunity to work with such objects, and I just can not get around them.

The sequences are declared as follows:

 Seq = head => tail => Pair (head) (tail) SeqHead = seq => Fst (seq) SeqTail = seq => (Snd (seq)) () 

The tail of the sequence in the constructor is a function to calculate the new sequence, and not the finished result. This approach provides the ability to generate a tail of infinite length.

To be able to test, we will write a function for getting the first n elements:

 SeqTake = Z (take => n => seq => ( If (IsZero (n)) (_ => Nil) (_ => Append (SeqHead (seq)) (take (Pred (n)) (SeqTail (seq)))) ) ()) 

If you want to exercise, implement SeqTake without recursion. It is possible, I guarantee.

Now it is worth giving an example of some sequence. Let it be natural numbers - you still have to work only with what has already been implemented:

 Nat = (Z (natFrom => n => Seq (n) (_ => natFrom (Succ (n))))) (Zero) console.assert(arraysEqual([0, 1, 2], toIntList (SeqTake (Three) (Nat)))) 

It uses the auxiliary function natFrom (n) , which returns a sequence of natural numbers starting with n . Nat is just the result of natFrom (Zero) .

There are very few, the last 2 functions, and they are the most cumbersome of those in this text. The first is the sequence filtering function. It finds in the transmitted sequence all elements that satisfy the transmitted predicate:

 SeqFilter = Z (filter => cond => seq => ( If (cond (SeqHead (seq))) (_ => Seq (SeqHead (seq)) (_ => filter (cond) (SeqTail (seq)))) (_ => filter (cond) (SeqTail (seq))) ) ()) 

In case the head element does not execute the predicate, the SeqFilter returns the filtered tail. Otherwise, it will be a sequence of the current head and the same filtered tail.

The second is a sequence of prime numbers. Another version of the Sieve of Eratosthenes in my performance:

 Primes = (Z (sieve => nums => Seq (SeqHead (nums)) (_ => sieve (SeqFilter (p => Not (IsZero (Rem (p) (SeqHead (nums))))) (SeqTail (nums))) ))) (SeqTail (SeqTail (Nat))) 

This function can be called the culmination of the article. The principle of its operation will be easier to understand in pseudocode:

 sieve (nums) { p = head (nums) rest = tail (nums) return append (p, sieve (filter (n -> n % p != 0, rest))) } primes = sieve [2, 3, 4, ...] 

Here is the test:

 Ten = Mul (Two) (Add (Two) (Three)) // s => z => s (s (s (s (s (s (s (s (s (s (z)))))))))) console.assert(arraysEqual([2, 3, 5, 7, 11, 13, 17, 19, 23, 29], toIntList (SeqTake (Ten) (Primes)))) 

I do not know about you, but it still surprises me that it is possible to write such things using only pure functions!

Conclusion

As a result, I got this strange introduction to LISP using the example of JavaScript. Hopefully, I was able to show that abstract mathematical ideas are actually very close to the reality of programming. And after such a look, the lambda calculus will no longer look too academic.

And, of course, here is a link to Github with all the code from the article.

Thank!