Programmer's Guide To Theory - Lambda Calculus
Written by Mike James
Monday, 01 January 2024
Article Index
Programmer's Guide To Theory - Lambda Calculus
Reduction
More than one function
The role of lambda in programming

## The role of lambda in programming

Now we get to a difficult part. Why is this very theoretical idea turning up in highly practical programming languages? It turns up in functional languages because the ideas fit together - Lambda calculus is a functional programming language. In other languages it turns up because it provides a simple way of defining anonymous functions that can be passed to other functions.

In a language that has functions as first class objects, i.e. where functions are objects and can be passed as parameters to other functions, then there is no real need of anything like a lambda expression. Even languages as simple as JavaScript don't really need to call anything a lambda expression, because all functions are first class objects and an anonymous function is just one you don't bother assigning to a variable.

In languages such as Java and C# functions only occur as members of objects. There aren't such things as free floating functions that don't belong to some object, hence there cannot be anything like an anonymous function. To avoid adding functions as objects in their own right you have to introduce something that looks like a lambda expression with a function head that defines the parameters and a function body that defines what to do with the parameters to obtain a result. Notice that any lambda expression defined as part of a programming language goes well beyond what we have discussed here - in particular the variables store complex data types and the standard operations are defined. While it is true that all of these things could be reduced to formal lambda expressions, this isn't of much interest to the practicing programmer, nor should it be.

So the lambda expressions that you meet in object-oriented languages really don't have that much to do with the Lambda calculus, and not that much to do with the grammar of lambda expressions. They are just anonymous functions that you can pass to other functions and a way of avoiding the need to implement functions as objects.

## Summary

• Turing invented a machine definition of what computation is all about, whereas Church invented a logical system that captured the essence of computation – Lambda calculus.

• Lambda calculus is Turing-equivalent or the Turing machine is lambda-equivalent depending on your point of view – they both have the same computational power.

• The Church-Turing thesis is that anything that can be computed can be done so either by a Turing machine or by Lambda calculus.

• A basic lambda term can be defined by a simple grammar.

• Computation in Lambda calculus is mainly via beta reduction, which is analogous to function evaluation.

• This can be extended to multiple parameters and to multiple “functions”, making Lambda calculus more powerful than you might expect.

• Lambda calculus can be used to model the integers and from here arithmetic and once you have arithmetic the rest follows and it can be used to do everything a Turing machine or a real computer can.

• For reasons that have little to do with computational theory, lambda expressions have become known as a way to include simple functions into programming languages which otherwise don’t support them.

#### Related Articles

Lambda Expressions

Javascript Jems - Lambda expressions

## A Programmers Guide To Theory

#### Contents

1. What Is Computer Science?
Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
Extract 1: Numbers
Extract 2: Aleph Zero The First Transfinite
Extract 3: In Search Of Aleph-One
Extract 4: Transcendental Numbers
7. Kolmogorov Complexity and Randomness
Extract 1:Kolmogorov Complexity
8. The Algorithm of Choice
9. Gödel’s Incompleteness Theorem
10. Lambda Calculus ***NEW!
Part II Bits, Codes and Logic
11. Information Theory
12. Coding Theory – Splitting the Bit
13. Error Correction
14. Boolean Logic
Part III Computational Complexity
15. How Hard Can It Be?
Extract 1: Where Do The Big Os Come From
16. Recursion
Extract 1: What Is Recursion
Extract 2: Why Recursion
17. NP Versus P Algorithms
Extract 1: NP & Co-NP
Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

 Azul Intelligence Cloud Expands Support02/05/2024Azul has announced that its cloud analytics solution, Azul Intelligence Cloud, now supports Oracle JDK and any OpenJDK-based distribution. More DevOps teams will now benefit from its ability to b [ ... ] + Full Story Google Reduces Support For Python, Dart And Flutter01/05/2024There are many reports that Google has removed people from its Python, Dart and Flutter teams and possibly more. What does this say about relying on Google as a source of technology for your projects? [ ... ] + Full Story More News