Skip to content

Instantly share code, notes, and snippets.

@techtheriac
Last active December 28, 2020 20:19
Show Gist options
  • Save techtheriac/d0daa646b45fed7fba7c061bfc3154ee to your computer and use it in GitHub Desktop.
Save techtheriac/d0daa646b45fed7fba7c061bfc3154ee to your computer and use it in GitHub Desktop.
A subtle introduction to Lambda Calculus for the JavaScript Developer

Lambda (λ) Calculus For Javascript Developers

This article aims at explaining lambda calculus in a more approachable less 'mathy' manner.

Terms That Are Good To Know

  • Memoization: Memoization is an optimization technique used primarily to speed up computer programs by caching the result of expensive function calls and returning the cached result when fed with the same input.

  • Pure Function: A pure function is a function whose computation does not depend on globally declared variables, it does no I/O or mutations. All it does is return a value after doing a bunch of computations on the arguments it recieves. For a given set of arguments, a pure function will always return the same value. Thus, a pure function is one that is memoizable.

  • Functional Programming: This is a programming paradigm that employs the composition of pure functions in solving problems.

  • Arity - This refers to the number of arguments a function accepts.

  • Unary Function - A unary function is one that accepts only one argument. Lambda functions are unary.

Lambda Calculus is a formal system for expressing computation. Lambda Calculus encapsulates a formalization of the basic aspects of functions' constructions and their uses.

The Grammer rules are divided into two parts namely: Function Absraction and Function Application.

Function Abstraction:

This defines what the function does. Below is a lambda function mapping x to x2 + 1

λx.x2 + 1

Don't overthink the "λ" symbol. It is only a Greek letter. A Javascript Equivalent should look something like this 👇

let res = x => x * x + 1;

Having expressed the λ expression in Javascript, it is clear that all it does is take an argument 'x' and return the result of increasing the square of 'x' by 1.

Function Application:

Function application computes a function. This can be thought of as calling a JavaScript function with a particular arugument. Application of λx.x2 + 1 to 3 gives:

(λx.x2 + 1) (3)

In JS

let res = (x => x * x + 1)(3)

The formalization of a function evaluation process is called 'β - reduction' (pronounced 'beta reduction'). β-reduction makes use of substitution. I like to think of this as peeling off of layers. Thinking of β-reduction in terms of peeling off of layers will prove effective when we start dealing with curried functions which as you will see look like an onion of brackets.

Currying

As aforementioned, lambda functions are unary functions. This might seem counterintuitive as we might want to do computations on multiple arguments (variables). This is where Currying comes to play. Lambda functions are powerful enough to not only return simple expressions. They can return Lambdas too!

Supposing we want to write a function that takes two arbitrary numbers, you might be tempted to write a function that looks like this:

λxy.x*y

This violates the grammer rule, as lambda functions can only handle one argument at a time.

Here's how that computation can be expressed:

(λx.(λy.x*y))

This is starting to look like an onion, but don't be dismayed. The above function is a lambda that accepts an argument 'x' and returns another lambda that accepts an argument 'y' that returns the product of x and y.

Note that these brackets can be ommited and the function can be written as:

λx.λy.x*y

To help visualize what is really going on we'll employ those pretty brackets.

How do we go about doing the maths anyways? Supposing we want to supply arguments 5 and 7 for x and y repectively, we do so by peeling off the onion, layer by layer.

We are going to employ β reduction one step at a time.

Supplying '5' as the first argument:

(λx.(λy.x*y)) (5)

The expression is reduced to:

(λy.5*y)

One onion layer has been dealt with.

Supplying '7' as the second argument:

(λy.5*y) (7)

We now have:

5 * 7

And finally with nothing left to peel off:

35

Let us see how this technique plays out in a similar Javascript program. A function that returns the product of two numbers.

  function product(x, y) {
    return x * y;
  }

  product(5, 7) //retuns 35

This function can be rewritten as a generalized curried function.

  function product (x) {
    return function (y) {
      return x * y;
    }
  }

Let's for clarity sake rewrite the above function employing ES6 explicit return.

let product = x => y => x * y;

We are going to call the function with the argument '2' and assign the return value to a variable 'double'.

  let double = (x => y => x * y)(2);

Every occurence of 'x' in the function body is replaced with '2'. The resulting function is thus:

     double = y => 2 * y

I now have a generalized double function that I can call as many times as I want.

double(4) //8
double(8) //16
double(100) //200

In subsequent posts, more practical applications of this technique will be discussed. Stay tuned. Do not fear the Lambda.

@techtheriac
Copy link
Author

When functions are curried, isn't it a pain to put parentheses around every argument (product(5)(7))? Does currying have advantages to overcome that inconvenience?

The muscles of curried functions tend to be flexed when partial application
is employed in order to make them fit a composition pipeline.

The idea of composition is marrying pure functions together in a way that the return
value of one is supplied as the arugument (input) of the next function in a pipeline.

A Higher order function that composes two unary functions might be expressed as:

const composer = (f, g) => (x) => f(g(x));

If two unary functions are passed in, they're composed in such a way that
The value of the application of g to x is what is passed down to f.

Note that this can only be made possible with unary functions and that is why writing curried functions
is nice.
You're simply writing a function with multiple arguments as a function with a single argument by deferring
computation.
The said function can then be partially applied (with desired argument) and fixed into a composition pipeline. No hassles.

@techtheriac
Copy link
Author

When functions are curried, isn't it a pain to put parentheses around every argument (product(5)(7))? Does currying have advantages to overcome that inconvenience?

The muscles of curried functions tend to be flexed when partial application
is employed in order to make them fit a composition pipeline.

The idea of composition is marrying pure functions together in a way that the return
value of one is supplied as the arugument (input) of the next function in a pipeline.

A Higher order function that composes two unary functions might be expressed as:

const composer = (f, g) => (x) => f(g(x));

If two unary functions are passed in, they're composed in such a way that
The value of the application of g to x is what is passed down to f.

Note that this can only be made possible with unary functions and that is why writing curried functions
is nice.
You're simply writing a function with multiple arguments as a function with a single argument by deferring
computation.
The said function can then be partially applied (with desired argument) and fixed into a composition pipeline. No hassles.

Stringifying an Integer increased by a factor of y (an arbitrary number)...

Inviting the beautiful composer and stringify functions

const composer = (f, g) => (x) => f(g(x));
const stringify = x => x.toString();

A function to increase a given number by a factor of 2

const increaseByTwo = num => num * 2;

Not very useful in my arsenal as I might change my mind and decide to increase by 3, 9, 8999..

Since being DRY is of importance, we might want a more generalized stuff like:

const increase_ = (num, y) => num * y;

More general. Proves useful for a varying Integers but not Composable.

const increase = y => num => num * y; 

👆 A more general increase function that can be partially applied to a desired Int to fit a pipeline of Compostion

Throwing in 3 as the first argument of increase and composing it with the stringify function.

const stringifyNumInc3 = composer(stringify, increase(3))

increase(3) returns num => num * 3, waiting to receive the number that'll be increased by a factor of 3 or whatever is specified.

stringifyNumInc3(9)
// returns "27"

`

@luther9
Copy link

luther9 commented May 20, 2020

Thanks for going over the advantages. Would you recommend currying all functions? If we make curried and uncurried versions of each function, function names would be more cumbersome, so it seems to me that we have to decide whether to curry all functions or none of them, which can lead to bikeshedding.

@techtheriac
Copy link
Author

Thanks for going over the advantages. Would you recommend currying all functions? If we make curried and uncurried versions of each function, function names would be more cumbersome, so it seems to me that we have to decide whether to curry all functions or none of them, which can lead to bikeshedding.

It boils down to preferred style. At the end of the day, regardless of paradigm, we're only trying to solve problems.
In functional languages like Haskell and Purescript, functions are curried by default.
Javascript's treatment of functions as first class entities that can be passed around like values allows for the use of functional abstractions.
Ramda https://ramdajs.com/ (A practical functional library for JavaScript programmers) might interest you.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment