Prelude This is an article about Typescript and Functional Programming. It is not an article about Lambda calculus theory. We will implement Lambda calculus in Typescript as a way to exercise Functional Programming. We will do this solving a simple problem using only Lambda calculus constructs. In the end, maybe, also the basics of the theory may result clearer. The problem and the language The problem to solve is simple: . if 2 numbers n and m are equal, then return n + m otherwise, return m — n But we have a language that allows us only to use the following construct x => y  // anonymous function with 1 parameter (i.e. unary function) where x and y can be everything. x and y can even be functions, so that also the following is a valid construct in our language x => y => z => z(x)(y)  // x is the parameter and the value returned is y => z => z(x)(y) In other words, to solve the problem we have just anonymous functions (a.k.a. “fat arrow” functions). No Javascript native numbers, no == or === operators, no if then else. Just functions. Remember, for the rest of the article, that we have just functions. Lambda calculus Lambda calculus gives us the theoretical basis to solve this problem using just functions. Actually, Lambda calculus solves any computable problem using just functions. What is Lambda calculus? There are many sources which provide good descriptions. For the purpose of this article, Lambda calculus is simply the fact that we can use just anonymous functions to solve our problem. Here we want to see how we can make concrete this concept, implementing Lambda calculus with Typescript and solving, through it, our problem. In the process, we will use extensively, or better, exclusively techniques, since functional programming we have just functions. Considering that Lambda calculus is also at the basis of Functional Programming, then yes, we can say we are going to code the roots Functional Programming in Typescript. The complete code for the solution of the problem and additional Lambda calculus constructs can be found . here Numbers without numbers Our problem starts with 2 numbers but we can not use Javascript numbers since we have just functions. So we need to invent a way to define the concept of a using functions. number Let’s start saying that the numbers ZERO, ONE and TWO are represented respectively by ZERO = f => x => x        // in lambda calculus this is λf.λx.x
 ONE = f => x => f(x)     // in lambda calculus this is λf.λx.fx
 TWO = f => x => f(f(x))  // in lambda calculus this is λf.λx.f(fx) If f is a function and x is any value, ZERO ONE So basically this is our convention: a is represented by how many times a function f is applied to the argument x. returns x never applying f to it while returns the result of applying f to x once and TWO the result of applying f to x twice . number So the mechanism is clear. A number represents the application of a function f to an argument x . Remember this concept, we will use it later. By the way, this is called Church encoding of numbers. It is the convention used by the inventor of Lambda calculus, Alonzo Church, to represent natural numbers. n n-times The Successor function So far we have hardcoded the first 3 numbers, but we need to find a more flexible way, a smarter way to define numbers. This way is provided to us by the Successor function SUCC = n => f => x => f(n(f)(x)) // equivalent to λn.λf.λx.f(nfx) It does not look immediate, right? But let’s reason about it. Let’s start with the case of n equal to ZERO. If n is ZERO (remember that ZERO has been defined as f => x => x) than applying SUCC(n) to ZERO, i.e. substituting n with the definition of ZERO, we get Substitutions in SUCC(ZERO) to reach ONE If we try SUCC(ONE) applying the same mechanical substitution we obtain TWO. Then SUCC(TWO) is THREE and so on and so forth. Few words about currying We just defined SUCC = n => f => x => f(n(f)(x)) To be pedantic we can say that SUCCis a that takes , n, and returns a that takes , f, and returns a that takes , x, and eventually does something with n f and x. function one parameter function one parameter function one parameter So we can actually say that SUCC is a function of 3 parameters, n f and x and that these parameters are applied one at the time. This partial application of single parameters is called . currying From now on we will freely talk about functions of parameters, with , even if behind this concept there is always the mechanism since Lambda functions by definition are unary, i.e. accept only 1 parameter. m m ≥ 1 currying Let’s add some Types If we look at the structure of a number, as defined by our convention, we see 2 things a number is a function that takes 2 parameters, f and x, and returns something the first parameter f must itself be a unary function since it can be applied to x in the body of each number So we can start defining some types in Typescript type uF = (x: any) => any;                 // unary function
type NUMBER = (f: uF) => (x: any) => any;  // the type of numbers And then also the function SUCC can be typed SUCC = (n: NUMBER): NUMBER => (f: uF) => (x: any) => f(n(f)(x)); Typescript gives us the opportunity to add types to function definitions, which can be of great help in guiding us, via Intellisense and type checking, specifically when the problems we want to solve get complicated. But if these are “numbers” can we see them as normal numbers? Church encoding for numbers is about applying a function to an argument n-times. This is all good, but … Can we see them as normal numbers, as 0, 1, 2, 36, 49, 112? Yes, we can. If we pass as f a function that increments by 1 a Javascript number and as x the JavaScript number 0, we obtain the Javascript number corresponding to the Church encoded number, as we can see in the following example. <a href="https://medium.com/media/77261fbb7fdee1e7b8140a6d2b5228c7/href">https://medium.com/media/77261fbb7fdee1e7b8140a6d2b5228c7/href</a> At the same time, if we change the function f and the initial value, then we can see our Church encoded numbers with different formats. Here, for instance, a Church number is turned into a string of n characters *. n <a href="https://medium.com/media/be5016fdea3f14b53596285aa0d9d0a0/href">https://medium.com/media/be5016fdea3f14b53596285aa0d9d0a0/href</a> Booleans without booleans With booleans, we have to face the same problem as with numbers. We need to define True and False in a language that does not have such concepts, a language where we have just functions. Again we revert to a convention. Here the intuition: in the Javascript ternary operator, condition ? first : second, means to choose the first option and means to choose the second. True False We use the same convention here, the Church encoding for Booleans, i.e. // TRUE and FALSE are binary functions, they expect 2 parameters
TRUE  =  x => y => x   // TRUE returns the first parameter
FALSE =  x => y => y   // FALSE returns the second parameter We will now see how this convention actually turns out to work well with boolean operators. The AND function Now let’s see how we can build a function which behaves like AND, i.e. it has to expect 2 Church encoded boolean arguments, p and q, and returns TRUE only if both arguments are TRUE. AND must have the following form AND = p => q => ....   // p and q are Church encoded booleans p and q are the only things we have, so we better use them in the body of the function. We try to start the implementation of the body with p , which itself is a binary function since it is a Church encoded boolean. AND = p => q => p(_)(_)  // p expects 2 arguments If p is FALSE , by definition of FALSE it chooses the second argument. But if p is FALSE, then the result of AND has to be FALSE and therefore the second argument after p must be FALSE. AND = p => q => p(_)(FALSE) // if p is false it selects the 2nd arg If p is TRUE then by definition of TRUE the first argument after p is chosen. But in this case the result of AND depends on the value of q. If q is TRUE then the result is TRUE , FALSE otherwise. But this means that the first argument after p is q itself. AND = p => q => p(q)(FALSE) // if p is true it selects q as result We can now make the last simplification. The second argument of p is FALSE and is chosen only when p is FALSE. Which means that we can substitute FALSE with p for the final version of the function AND = p => q => p(q)(p) Even the symmetric version works AND = p => q => q(p)(q) With similar methods, all other Boolean operators can be found. We can add types to the Church encoded Booleans and test the correctness of our logic as in this example. <a href="https://medium.com/media/4f39743032023adaed9b994a69d405f7/href">https://medium.com/media/4f39743032023adaed9b994a69d405f7/href</a> Comparisons without comparison operators Our problem asks us to compare 2 numbers, but we do not have comparison operators like == or ===, we have just functions. We need to find a different strategy. Bear with me on this journey. One way to check whether 2 numbers n and m are is to check whether n is to m and m is to n. Assuming we have a function LEQ(m)(n) that returns TRUE if mis n, we can then define the EQ function as equal lessThanOrEqual lessThenOrEqual lessThanOrEqual EQ(m)(n) = AND (LEQ(m)(n)) (LEQ(m)(n)) Now we need to define LEQ. Let’s assume we have 2 functions, SUB and ISZERO, defined as follows: SUB(m)(n) subtracts n from m so that, if n is greater than m , the result is always ZERO otherwise, it is m-n ISZERO(n) returns TRUE if n is ZERO, FALSE otherwise We can now express LEQ as LEQ(m)(n) = ISZERO(SUB(m)(n)) Well, we are now left with the problem of defining ISZERO and SUB. Check if a number is ZERO ISZERO is a function which expects a Church encoded number as its parameter. A Church encoded number n is itself a binary function, and it is the only thing we are given so we better use it somehow ISZERO(n) = n(x)(y) // we need to find the right x and y Let’s start with the case where n is ZERO, i.e. n = f => x => x. ZERO by definition always returns the second parameter, therefore must be TRUE. y ISZERO(n) = n(x)(TRUE) // we need to find the right x for n not ZERO Now let’s consider n = ONE, i.e. n = f => x => f(x). In this case, f must return always FALSE for any value of x. Which means that f = x => FALSE. So eventually ISZERO is ISZERO(n) = n(x => FALSE)(TRUE) We can test this with the following code <a href="https://medium.com/media/c52c59a10d776a04b27899b0645cb532/href">https://medium.com/media/c52c59a10d776a04b27899b0645cb532/href</a> Subtract n from m If we had a function PRED(n) which returns the predecessor of n then we could say that to subtract n from m is equivalent to apply n-times the PRED function to m. But, if you remember what we said at the beginning when we introduced Church encoding for numbers, itself represents the application of a function f to an argument x . In other words n n-times SUB(m)(n) = n(PRED)(m) Now, with a leap of faith, let’s accept the following definition of PRED const PRED = n => f => x => n(g => h => h(g(f)))(u => x)(u => u) For those interested, there is an explanation of PRED at the end of this article. Sum n to m Similarly to how we have constructed SUB we can construct SUM using the Successor function as SUM(n)(m) = n(SUCC)(m) Now we can construct the solution Do we still remember the initial problem? if (n = m) {
  return n + m;  // return the sum if n and m are equal
} else {
  return n — m;  // return the difference if not equal
} Now we have all the tools to solve it with a language where we have just functions.. Look at this EQ(n)(m)      // returns TRUE if n and m are equal, FALSE otherwise
(SUM(n)(m))   // argument picked if EQ returns TRUE
(SUB(n)(m))   // argument picked if EQ returns FALSE This is exactly the solution to our problem, as can be proved running the following code <a href="https://medium.com/media/49b5b159cf0e2ecf35d0aaf9a7d8c394/href">https://medium.com/media/49b5b159cf0e2ecf35d0aaf9a7d8c394/href</a> More details and tests can be seen in the . repo By the way, if we substitute EQ SUM SUB and all the rest of the definitions we have added as a convenience, the code for our solution is this <a href="https://medium.com/media/6b0aa36f72609a05ded3a0f34699a2b8/href">https://medium.com/media/6b0aa36f72609a05ded3a0f34699a2b8/href</a> Finally: What’s in it for a Functional Programmer? We have been playing just with functions. We have defined them, passed them as arguments, expected as parameters, evaluated them. We have become more familiar with them to be used as first-class citizens in our code. We have done some exercises which have helped us understand the dynamics and mechanics of using functions with a functional programming approach. For instance, if we see this FLIP = f => a => b => f(b)(a) we understand that it is a way to use f with the order of parameters reversed. And a FLIP equivalent can be found in and libraries. Other magics implemented by FP libraries should now be more clear. If this is the case, we have reached the objective of this article. lodash rambda For those really interested: how to build PRED function using Pairs What is this? x => y => f => f(x)(y) This is a , a 2-dimensional vector., actually the way to encode a with functions. pair pair Consider the following const PAIR = x => y => f => f(x)(y);
const myPair = PAIR(1)(2); myPair is a structure which contains 1 and 2 as its immutable values. We just need to pass a function to myPair to specify what we want to do with its values. A pair of n and m can be defined using the notation (n, m). If we want to get hold of the second value of a , we can just pass the FALSE function to the pair pair SECOND = p => p(FALSE)    // where p is a pair as we can test with the following code <a href="https://medium.com/media/8c72c636ccd892a149316b185aad532d/href">https://medium.com/media/8c72c636ccd892a149316b185aad532d/href</a> Similarly, the function FIRST is FIRST = = p => p(TRUE)    // where p is a pair We can now define another function, PHI, as follows PHI = p => PAIR(SECOND(p))(SUCCESSOR(SECOND(p)))  // p is a PAIR PHI transforms the (m, n) into a new (n, n + 1). pair pair So, PHI(0,0) returns (0,1) PHI(PHI(0,0)) equals PHI(0,1) which returns (1,2) PHI(PHI(PHI(0,0) equals PHI(1,2) which returns (2,3) Extrapolating we can say that n applications of PHI to (0,0) return the (n-1, n). Which leads to the definition of PRED as pair PRED = n => FIRST(n(PHI)(PAIR(ZERO)(ZERO))) There are other ways to construct the PRED function, but this is probably the more natural to follow. Acknowledgments This article takes inspiration from 2 great talks from Gabriel Lebec (@glebec) and . I really recommend anybody interested in the argument to watch them carefully. “Lambda Calculus” “A flock of functions”

Too Long; Didn't Read

Making security fun one episode at a time

Let’s code the roots of Functional Programming: Lambda calculus implemented in Typescript

Too Long; Didn't Read

Enrico Piccinin

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Let’s code the roots of Functional Programming: Lambda calculus implemented in Typescript

Too Long; Didn't Read

Enrico Piccinin

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES