Chapter 5

Understanding the Role of Lambda Calculus

IN THIS CHAPTER

Check Understanding the need for lambda calculus

Check Using lambda calculus to perform useful work

Check Developing lambda calculus functions

Mention the word calculus and some people automatically assume that the topic is hard or difficult to understand. Add a Greek letter, such as λ (lambda), in front of it and it must be so terribly hard that only geniuses need apply. Of course, using correct terminology is important when discussing a topic for which confusion reigns. The truth is, though, that you’ve probably used lambda calculus at some point if you’ve worked with other languages that support first-class functions such as C or JavaScript. Often, the creators of these languages make things simple by using more approachable terms. This chapter helps you through some of the terms involved in lambda calculus while also helping you understand the use of it. The big takeaway from this chapter should be that lambda calculus really isn’t hard; you’ve likely seen it in a number of places before.

Remember The focus of this chapter is to demonstrate how you can use lambda calculus to solve math problems within an application that relies on the functional programming paradigm. In many cases, the examples look astonishingly simple, and they truly are. When you understand the rules for using lambda calculus, you begin to use it to perform one of three operations — also represented by Greek letters: α (alpha), β (beta), and η (eta). Yes, that’s right; you need only to think about three operations, so the task should already be looking easier.

The final section of this chapter shows you how to create and use functions that rely on lambda calculus in the target languages for this book. However, no matter what programming language you use, you can find examples on how to create and use lambda functions (as long as the language supports first-class functions). That’s because lambda calculus is so incredibly useful and makes performing programming tasks significantly easier rather than harder, as you might initially expect.

Considering the Origins of Lambda Calculus

Alonzo Church originally created lambda calculus in the 1930s, which is before the time that computers were available. Lambda calculus explores the theoretical basis for what it means to compute. Alonzo Church worked with people like Haskell Curry, Kurt Gödel, Emil Post, and Alan Turing to create a definition for algorithms. The topic is far more familiar today, but imagine that you’re one of the pioneers who are trying to understand the very concepts used to make math doable in an automated way. Each person involved in defining what it means to compute approached it in a different manner:

Remember Even through each approach is different, Church and others noted certain equivalences between each of the systems, which isn’t a coincidence. In addition, each system helped further define the others and overcome certain obstacles that each system presents. Precisely who invented what is often a matter for debate because these people also worked with other scientists, such as John von Neumann. It shouldn’t surprise you to know that some of these people actually attended school together at Princeton (along with Albert Einstein). The history of the early years of computing (when modern computers weren’t even theories yet) is fascinating, and you can read more at https://www.princeton.edu/turing/alan/history-of-computing-at-p/.

Technicalstuff Church’s motivation in creating lambda calculus was to prove that Hilbert’s Entscheidungsproblem, or decision problem (see https://www.quora.com/How-can-I-explain-Entscheidungs-problem-in-a-few-sentences-to-people-without-confusing-people for details) wasn’t solvable Peano arithmetic (see http://mathworld.wolfram.com/PeanoArithmetic.html for details). However, in trying to prove something quite specific, Church created a way of looking at math generally that is still in use today.

The goals of lambda calculus, as Church saw it, are to study the interaction of functional abstraction and function application from an abstract, purely mathematical perspective. Functional abstraction begins by breaking a particular problem into a series of steps. Of course, these breaks aren’t arbitrary; you must create breaks that make sense. The abstraction continues by mapping each of these steps to a function. If a step can’t be mapped to a function, then it isn’t a useful step — perhaps the break has come in the wrong place. Function application is the act of applying the function to an argument and obtaining a value as output. It’s essential to understand the tenets of lambda calculus as set out initially by Church to understand where programming languages stand on the topic today:

  • Lambda calculus uses only functions — no other data or other types (no strings, integers, Booleans, or other types found in programming languages today). Any other type is encoded as part of a function and therefore, the function is the basis of everything.
  • Lambda calculus has no state or side effects. Consequently, you can view lambda calculus in terms of the substitutional model, which is used for biology to describe how a sequence of symbols changes into another set of traits using a particular process.
  • The order of evaluation is irrelevant. However, most programming languages do use a particular order to make the process of evaluating functions easier (not to mention reducing the work required to create a compiler or interpreter).
  • All functions are unary, taking just one argument. Functions that require multiple arguments require the use of currying. You can read about the use of currying in Haskell in the “Using curried functions” section of Chapter 4.

Understanding the Rules

As mentioned in the introduction to this chapter, you use three different operations to perform tasks using lambda calculus: creating functions to pass as variables; binding a variable to the expression (abstraction); and applying a function to an argument. The following sections describe all three operations that you can view as rules that govern all aspects of working with lambda calculus.

Working with variables

When considering variables in lambda calculus, the variable is a placeholder (in the mathematical sense) and not a container for values (in the programming sense). Any variable, x, y, or z, (or whatever identifier you choose to use) is a lambda term. Variables provide the basis of the inductive (the inference of general laws from specific instances) definition of lambda terms. To put this in easier-to-understand terms, if you always leave for work at 7:00 a.m. and are always on time, inductive reasoning says that you will always be on time as long as you leave by 7:00 a.m.

Remember Induction in math relies on two cases to prove a property. For example, a common proof is a property that holds for all natural numbers. The base (or basis) case makes an assumption using a particular number, usually 0. The inductive case, also called the inductive step, proves that if the property holds for the first natural number (n), it must also hold for the next natural number (n + 1).

Variables may be untyped or typed. Typing isn’t quite the same in this case because types are for other programming paradigms; the use of typing doesn’t actually indicate a kind of data. Rather, it defines how to interpret the lambda calculus. The following sections describe how untyped and typed variables work.

Untyped

The original version of Church’s lambda calculus has gone through a number of revisions as the result of input by other mathematicians. The first such revision came as the result of input from Stephen Kleene and J. B. Rosser in 1935 in the form of the Kleene–Rosser paradox. (The article at https://www.quora.com/What-is-the-Kleene–Rosser-paradox-in-simple-terms provides a basic description of this issue.) A problem exists in the way that logic worked in the original version of lambda calculus, and Church fixed this problem in a succeeding version by removing restrictions on the kind of input that a function can receive. In other words, a function has no type requirement.

Tip The advantage of untyped lambda calculus is its greater flexibility; you can do more with it. However, the lack of type also means that untyped lambda calculus is nonterminating, an issue discussed in the “Considering the need for typing” section of the chapter. In some cases, you must use typed lambda calculus to obtain a definitive answer to a problem.

Simply-typed

Church created simply-typed lambda calculus in 1940 to address a number of issues in untyped lambda calculus, the most important of which is an issue of paradoxes where β-reduction can’t terminate. In addition, the use of simple typing provides a means for strongly proving the calculus. The “Abstracting simply-typed calculus” section of the chapter discusses the methodology used to apply type to lambda calculus and makes it easier to understand the differences between untyped and simply-typed versions.

Using application

The act of applying one thing to another seems simple enough. When you apply peanut butter to toast, you get a peanut butter sandwich. Application in lambda calculus is almost the same thing. If M and N are lambda terms, the combination MN is also a lambda term. In this case, M generally refers to a function and N generally refers to an input to that function, so you often see these terms written as (M)N. The input, N, is applied to the function, M. Because the purpose of the parentheses is to define how to apply terms, it’s correct to refer to the pair of parentheses as the apply operator.

Understanding that application infers nesting is essential. In addition, because lambda calculus uses only functions, inputs are functions. Consequently, saying M2(M1N) would be the same as saying that the function M1 is applied as input to M2 and that N is applied as input to M1.

Technicalstuff In some cases, you see lambda calculus written without the parentheses. For example, you might see EFG as three lambda terms. However, lambda calculus is left associated by default, which means that when you see EFG, what the statement is really telling you is that E is applied to F and F is applied to G, or ((E)F)G. Using the parentheses tends to avoid confusion. Also, be aware that the associative math rule doesn’t apply in this case: ((E)F)G is not equivalent to E(F(G)).

To understand the idea of application better, consider the following pseudocode:

inc(x) = x + 1

All this code means is that to increment x, you add 1 to its value. The lambda calculus form of the same pseudocode written as an anonymous function looks like this:

(x) -> x + 1

You read this statement as saying that the variable x is mapped to x + 1. However, say that you have a function that requires two inputs, like this:

square_sum(x, y) = (x2 + y2)

The lambda calculus form of the same function written in anonymous form looks like this:

(x, y) -> x2 + y2

This statement is read as saying that the tuple (x, y) is mapped to x2 + y2. However, as previously mentioned, lambda calculus allows functions to have just one input, and this one has two. To properly apply the functions and inputs, the code would actually need to look like this:

x -> (y -> x2 + y2)

At this point, x and y are mapped separately. The transitioning of the code so that each function has only one argument is called currying. This transition isn't precisely how you see lambda calculus written, but it does help explain the underlying mechanisms that you see explained later in the chapter.

Using abstraction

The term abstraction derives from the creation of general rules and concepts based on the use and classification of specific examples. The creation of general rules tends to simplify a problem. For example, you know that a computer stores data in memory, but you don’t necessarily understand the underlying hardware processes that allow the management of data to take place. The abstraction provided by data storage rules hides the complexity of viewing this process each time it occurs. The following sections describe how abstraction works for both untyped and typed lambda calculus.

Abstracting untyped lambda calculus

In lambda calculus, when E is a lambda term and x is a variable, λx.E is a lambda term. An abstraction is a definition of a function, but doesn’t invoke the function. To invoke the function, you must apply it as described in the “Using application” section of the chapter. Consider the following function definition:

f(x) = x + 1

The lambda abstraction for this function is

λx.x + 1

Remember that lambda calculus has no concept of a variable declaration. Consequently, when abstracting a function such as

f(x) = x2 + y2

to read

λx.x2 + y2

the variable y is considered a function that isn’t yet defined, not a variable declaration. To complete the abstraction, you would create the following:

λx.(λy.x2 + y2)

Abstracting simply-typed calculus

The abstraction process for simply-typed lambda calculus follows the same pattern as described for untyped lambda calculus in the previous section, except that you now need to add type. In this case, the term type doesn’t refer to string, integer, or Boolean — the types used by other programming paradigms. Rather, type refers to the mathematical definition of the function’s domain (the set of outputs that the function will provide based on its defined argument values) and range (the codomain or image of the function), which is represented by A -> B. All that this talk about type really means is that the function can now accept only inputs that provide the correct arguments, and it can provide outputs of only certain arguments as well.

Alonzo Church originally introduced the concept of simply-typed calculus as a simplification of typed calculus to avoid the paradoxical uses of untyped lambda calculus (the “Considering the need for typing” section, later in this chapter, provides details on how this whole process works). A number of lambda calculus extensions (not discussed in this book) also rely on simple typing including: products, coproducts, natural numbers (System T), and some types of recursion (such as Programming Computable Functions, or PCF).

Remember The important issue for this chapter is how to represent a typed form of lambda calculus statement. For this task, you use the colon (:) to display the expression or variable on the left and the type on the right. For example, referring to the increment abstraction shown in the previous section, you include the type, as shown here:

λx:ν.x + 1

In this case, the parameter x has a type of ν (nu), which represents natural numbers. This representation doesn't tell the output type of the function, but because + 1 would result in a natural number output as well, it’s easy to make the required assumption. This is the Church style of notation. However, in many cases you need to define the type of the function as a whole, which requires the Curry-style notation. Here is the alternative method:

(λx.x + 1):ν -> ν

Moving the type definition outside means that the example now defines type for the function as a whole, rather than for x. You infer that x is of type ν because the function parameters require it. When working with multiparameter inputs, you must curry the function as shown before. In this case, to assign natural numbers as the type for the sum square function, you might show it like this:

λx:ν.(λy:ν.x2 + y2)

Note the placement of the type information after each parameter. You can also define the function as a whole, like this:

(λx.(λy.x2 + y2)):ν -> ν -> ν

Tip Each parameter appears separately, followed by the output type. A great deal more exists to discover about typing, but this discussion gives you what you need to get started without adding complexity. The article at http://www.goodmath.org/blog/2014/08/21/types-and-lambda-calculus/ provides additional insights that you may find helpful.

Technicalstuff When working with particular languages, you may see the type indicated directly, rather than indirectly using Greek letters. For example, when working with a language that supports the int data type, you may see int used directly, rather than the less direct form of ν that's shown in the previous examples. For example, the following code shows an int alternative to the λx:ν.x + 1 code shown earlier in this section:

λx:int.x + 1

Performing Reduction Operations

Reduction is the act of expressing a lambda function in its purest, simplest form and ensuring that no ambiguity exists in its meaning. You use one of three kinds of reduction (also called conversion in some cases for the sake of clarity) to perform various tasks in lambda calculus:

  • α (alpha)
  • β (beta)
  • η (eta)

How an application employs these three kinds of reduction is what defines the lambda expression. For example, if you can convert two lambda functions into the same expression, you can consider them β-equivalent. Many texts refer to the process of performing these three kinds of reduction as a whole as λ-reduction. The following sections discuss the reduction operations in detail.

Considering α-conversion

When performing tasks in lambda calculus, you often need to rename variables so that the meaning of the various functions is clear, especially when combining functions. The act of renaming variables is called α-conversion. Two functions are α-equivalent when they have the same result. For example, the following two functions are alpha-equivalent:

λx.x + 1
λa.a + 1

Clearly, both functions produce the same output, even though one function relies on the letter x, while the second relies on the letter a. However, the alpha-conversion process isn't always straightforward. For example, the following two functions aren’t α-equivalent; rather, they’re two distinct functions:

λx.(λy.x2 + y2)
λx.(λx.x2 + x2)

Tip Renaming y to x won't work because x is already a captured variable. However, you can rename y to any other variable name desired. In fact, functional language compilers often perform alpha-conversion even when it's not strictly necessary to ensure variable uniqueness throughout an application. Consequently, when viewing your code, you need to consider the effects of alpha-conversion performed solely to ensure variable uniqueness.

Considering β-reduction

The concept of β-reduction is important because it helps simplify lambda functions, sometimes with the help of α-conversion or η-conversion (sometimes called reductions in some texts, but the use of the term conversion is clearer). The essential idea is easy—to replace the variables in the body of a function with a particular argument. Making the replacement enables you to solve the lambda function for a particular argument, rather than make a general statement that could apply to any set of arguments.

Tip The following sections help you understand how beta-reduction works. The tutorial at http://www.nyu.edu/projects/barker/Lambda/ provides JavaScript aids that can help you to better understand the discussion if you want to feed the examples into the appropriate fields.

Defining bound and unbound variables

When viewing the function, λx.x + 1, the λ part of that function binds the variable x to the succeeding expression, x + 1. You may also see two other binding operators used in some function declarations: backwards E (∃), also called the existential quantifier used in set theory, or upside-down A (∀), which means for all. The examples in this book don't use any of the alternatives, and you don’t need to worry about them for now, but you can find a relatively complete set of math symbols, with their explanations, at https://en.wikipedia.org/wiki/List_of_mathematical_symbols.

You sometimes find expressions containing unbound or free variables. A free variable is one that appears without the λ part of the function. For example, in this expression, x is bound, while y remains free.

λx.x2 + y2

Unbound variables always remain after any sort of reduction as an unsolved part of the function. It doesn't mean that you won’t solve that part of the function — simply that you won’t solve it now.

Understanding the basic principle

The previous section discusses bound and unbound variables. This section moves on to the next step: replacing the bound variables with arguments. By performing this step, you move the lambda function from general to specific use. The argument always appears on the right of the function statement. Consequently, the following lambda expression says to apply every argument z to every occurrence of the variable x.

((λx.x + 1)z)

Notice how the entire function appears in parentheses to separate it from the argument that you want to apply to the function. The result of this reduction appears like this:

(z + 1)[x := z]

The reduction now shows that the argument z has a value of 1 added to it. The reduction appears in square brackets after the reduced expression. However, the reduction isn't part of the expression; it’s merely there for documentation. The whole expression is simply (z + 1).

When performing this task, you need not always use a letter to designate a value. You can use a number or other value instead. In addition, the reduction process can occur in steps. For example, the following reductions require three steps:

(((λx.(λy.x2 + y2))2)4)
(((λx.(λy1.x2 + y12))2)4)
((λy1.22 + y12)4)[x := 2]
(22 + 42)[y1 := 4]
22 + 42
20

This process follows these steps:

  1. Use alpha-conversion to rename the y variable to y1 to avoid potential confusion.
  2. Replace all occurrences of the x variable with the value 2.
  3. Replace all occurrences of the y1 variable with the value 4.
  4. Remove the unneeded parentheses.
  5. Solve the problem.

Considering the need for typing

The previous section makes beta-reduction look relatively straightforward, even for complex lambda functions. In addition, the previous sections rely on untyped variables. However, untyped variables can cause problems. For example, consider the following beta-reduction:

(λx.xx)(λx.xx)

Previous examples don't consider two features of this example. First, they didn't consider the potential for using two of the same variable in the expression, xx in this case. Second, they didn’t use a function as the argument for the sake of simplicity. To perform the beta-reduction, you must replace each x in the first function with the function that appears as an argument, which results in producing the same code as output. The beta-reduction gets stuck in an endless loop. Now consider this example:

L = (λx.xxy)(λx.xxy)

The output of this example is (λx.xxy)(λx.xxy)y, or Ly, which is actually bigger than before, not reduced. Applying beta-reduction again makes the problem larger still: Lyy. The problem is the fact that the variables have no type, so they accept any input. Adding typing solves this problem by disallowing certain kinds of input. For example, you can't apply a function to this form of the first example:

(λx:ν.xx)

The only argument that will work is a number in this case. Consequently, the function will beta-reduce.

Considering η-conversion

The full implementation of lambda calculus provides a guarantee that the reduction of (λx.Px), in which no argument is applied to x and P doesn't contain x as an unbound (free) variable, results in P. This is the definition of the η-conversion. It anticipates the need for a beta-reduction in the future and makes the overall lambda function simpler before the beta-reduction is needed. The discussion at https://math.stackexchange.com/questions/65622/whats-the-point-of-eta-conversion-in-lambda-calculus provides a fuller look at eta-conversion.

Warning The problem with eta-conversion is that few languages actually implement it. Even though eta-conversion should be available, you shouldn't count on its being part of any particular language until you actually test it. For example, the tutorial at http://www.nyu.edu/projects/barker/Lambda/#etareduction shows that eta-conversion isn’t available in JavaScript. Consequently, this book doesn't spend a lot of time talking about eta-conversion.

Creating Lambda Functions in Haskell

The “Seeing a Function in Haskell” section of Chapter 4 shows how to create functions in Haskell. For example, if you want to create a curried function to add two numbers together, you might use add x y = x + y. This form of code creates a definite function. However, you can also create anonymous functions in Haskell that rely on lambda calculus to perform a task. The difference is that the function actually is anonymous — has no name — and you assign it to a variable. To see how this process works, open a copy of the Haskell interpreter and type the following code:

add = x -> y -> x + y

Notice how lambda functions rely on the backslash for each variable declaration and the map (->) symbol to show how the variables are mapped to an expression. The form of this code should remind you of what you see in the “Abstracting untyped lambda calculus” section, earlier in this chapter. You now have a lambda function to use in Haskell. To test it, type add 1 2 and press Enter. The output is 3 as expected.

Obviously, this use of lambda functions isn't all that impressive. You could use the function form without problem. However, lambda functions do come in handy for other uses. For example, you can create specially defined operators. The following code creates a new operator, +=:

(+=) = x -> y -> x + y

To test this code, you type 1+=2 and press Enter. Again, the output is 3, as you might expect. Haskell does allow a shortcut method for defining lambda functions. You can create this same operator using the following code:

(+=) = x y -> x + y

Creating Lambda Functions in Python

The “Seeing a Function in Python” section of Chapter 4 shows how to create functions in Python. As with the Haskell function in the previous section of this chapter, you can also create a lambda function version of the add function in Chapter 4. When creating a lambda function in Python, you define the function anonymously and rely on the lambda keyword, as shown here:

add = lambda x, y: x + y

Notice that this particular example assigns the function to a variable. However, you can use a lambda function anywhere that Python expects to see an expression or a function reference. You use this function much as you would any other function. Type add(1, 2), execute the code, and you see 3 as output.

If you want to follow a more precise lambda function formulation, you can create the function like this:

add = lambda x: lambda y: x + y

In this case, you see how the lambda sequence should work more clearly, but it's extra work. To use this function, you type add(1)(2) and execute the code. Python applies the values as you might think, and the code outputs a value of 3.

Python doesn’t allow you to create new operators, but you can override existing operators; the article at http://blog.teamtreehouse.com/operator-overloading-python tells you how. However, for this chapter, create a new use for the letter X using a lambda function. To begin this process, you must install the Infix module by opening the Anaconda Prompt, typing pip install infix at the command prompt, and pressing Enter. After a few moments, pip will tell you that it has installed Infix for you. The following code will let you use the letter X to multiply two values:

from infix import mul_infix as Infix
X = Infix(lambda x, y: x * y)
5 *X* 6
X(5, 6)

The first statement imports mul_infix as Infix. You have access to a number of infix methods, but this example uses this particular one. The site at https://pypi.org/project/infix/ discusses the other forms of infix at your disposal.

The second statement sets X as the infix function using a lambda expression. The manner in which Infix works allows you to use X as either an operator, as shown by 5 *X* 6 or a regular function, as shown by X(5, 6). When used as an operator, you must surround X with the multiplication operator, *. If you were to use shif_infix instead, you would use the shift operators (<< and >>) around the lambda function that you define as the operator.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.134.79.121