A Sneaky Lambda (Part 1)

Terms and concepts such as $\lambda$-calculus, combinators and tail recursion optimization might seem foreign or even straight up crazy for some software programmers and engineers. However, these terms are, in a sense, where the whole art of programming (shout-out to Don Knuth!) originates. It is not easy to study a massive beastly language like C or Java. In fact, I would dare to say that formally studying complete languages with all their libraries and APIs is a near impossible task for a bunch of slaves PhD students. Hence, programming language researchers and their minions students, usually decide to study small “core” programming languages, which contain all the traits that are important for their research.

One of such languages is the $\lambda$-calculus and, in fact, it was invented even before digital computers, as we know them, came to be. Invented by Alonzo Church in the 1930s, initially, the $\lambda$-calculus was used only as a formalism to study the foundation of mathematics and the notion of computation. However, it was not until the 1960s when people like Peter Landin realized it could be used to model programming languages. From there on, research was aimed at understanding this relation and from this research functional programming languages such as Scheme, Scala, Haskell and OCaml originated.

In this post I want to give a small introduction to the $\lambda$-calculus using Python, a sneaky programming language (forgive the pun!). Use the following roadmap to give yourself an idea of the topics that I will touch:

  1. Functions galore: the $\lambda$-calculus.
  2. Anonymous functions and lambdas in Python.

Functions galore: the $\lambda$-calculus.

Functions

'Functions are black boxes that convert things in other things by using arcane magical symbols... '
—The author...

While the previous sentence might not be the way to start a serious topic, it is not entirely wrong. In the computational sense, a function can be interpreted as black box that takes a certain amount of elements as an input and, after executing a certain number of operations, returns a unique element. Using my outstanding ASCII drawing techniques, I will graphically describe a function that receives two elements and return a single element as:

	-------------------
in1--->	|	BLACK 	  | -----> Out1
in2---> |	MAGIC     |
	-------------------

Formally, it is common to define functions in terms of its domain and range, meaning the set of inputs and the set of expected outputs, commonly written as $f: \mathsf{IN} \mapsto \mathsf{OUT}$, where $f$ is a convenient name for the function and $\mathsf{IN}$ corresponds to the set of inputs (domain) and $\mathsf{OUT}$ to the set of outputs (range) that the function will have. For example, if we want to define a function that takes an integer and returns the same integer with its sign changed, we formally say that $f: \mathbb{Z}\mapsto\mathbb{Z}$, where the domain and range are the integers. Procedurally, the function can be declared as $f(x)= -x$, where $x$ is an integer.

$\lambda$-calculus

The $\lambda$-calculus is a language in which the expressions are formed only using the following terms:

  1. Variables: e.g., $x,y,z$.
  2. Function abstractions: e.g., $\lambda x.M$, where $M$ is a term.
  3. Function applications: e.g., $M\,\,N$, where $M,N$ are terms.

Expressions in the $\lambda$-calculus “execute” according to the following rules, commonly known as reduction rules:

The previous two rules do not conform the complete set of reduction rules for the $\lambda$-calculus. Howver, I will not enter into details of the third rule, known as $\text{$\eta$-reduction}$, since it is not my objective to give a full treatment of all the formalities involved in the calculus, but rather try to provide an interactive-not-so-boring introduction. I will provide some extra links at the end for the interested reader.

The first presented rule, known as $\text{$\beta$-reduction}$, indicates that a function abstraction applied to a term can reduce to the term inside the abstraction $M$, substituting variable $x$ with the term that was applied (i.e., $N$). Using a tool from the academic repertoire, abuse of notation, consider the following application: $(\lambda x. -x)\,\,4$. By using the $\text{$\beta$-reduction}$ rule we observe that

which is the result of our function. So technically, one can use the function abstraction notation (or $\lambda$ notation) to write any kind of imaginable function.

The second rule on the other hand, $\text{$\alpha$-reduction}$ allows you to change the name of the variable in the abstracted function and inside the scope of the abstraction. It is mainly used to avoid clashes between variables, but, by assuming all our input variables are different, we can simply avoid using it. For those of you who like names, this convention is commonly called the Barendregt’s convention, in honour to an important Dutch logician (shout-out to all my Dutch readers!).

Anonymous functions and lambdas in Python

From this section onwards I suggest opening your favorite python editor (in case you do not have it at hand click here) and fiddle with the code I write.

In Python, our example function would be commonly defined as:

def f(x):
  return(-x)

this representation would correspond to what mathematically we wrote as $f(x)=x$. However, Python has its own name for a function abstraction, which, curiously is called lambda. Using lambdas, we could write the previous function as:

g = lambda x: -x

there are two things worth emphasizing: first of all, this is a one-liner that reads easy and, second of all, we are doing some interesting magic such as assigning a function to a variable! This means that every time you call g(1) the Python equivalent of a $\text{$\beta$-reduction}$ will kick in, and you will end up with the result: -1.

Now you might be wondering what is the usefulness of Python lambdas. Indeed, while they may appear like fancy tools, they serve the purpose of helping to better organize the code, to reduce the number of defined functions in a single file and in general to express in a much succinct form some of the daily operations that we, as programmers need. Furthermore, as per this tutorial, I think that lambdas in Python are useful for teaching the basics of the $\lambda$-calculus to the interested reader!

Addendum: This post was part of a larger post published here, but due to time constraints I decided to split it in several posts.

Published: June 24 2017

blog comments powered by Disqus