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

Now available as a paperback and ebook from Amazon.

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
   Extract 2: Turing Thinking ***NEW!
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
    Part II Bits, Codes and Logic
11. Information Theory 
12. 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

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info