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

Now available as a paperback and ebook from Amazon.

cover600

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>

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.

Banner


CSS Test of Time Award 2023
18/02/2024

The ACM CCS Test-of-Time Award honors research with long-lasting influence, which have had significant impacts on systems security and privacy. The 2023 award in respect of a paper by Marten van Dijk  [ ... ]



Microsoft's Visual Studio With Git And GitHub Tutorials
13/02/2024

Microsoft has released a short series of video tutorials on using Git and Github from within Visual Studio. Given that Git is nowadays the defacto version control tool with most code hosted on Gi [ ... ]


More News

raspberry pi books

 

Comments




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



Last Updated ( Wednesday, 24 January 2024 )