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
      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.

Banner


PNG Gets First Update In Over Twenty Years
07/07/2025

PNG, the Portable Network Graphics specification, has been updated to add support for HDR (High Dynamic Range) images and for animated PNGs.



Google Introduces Gemini CLI Open-Source Agent
08/07/2025

Google is introducing Gemini CLI, an open-source AI agent that offers lightweight access to Gemini, Google's conversational chatbot that is based on Google's multimodal large language model  [ ... ]


More News

pico book

 

Comments




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



Last Updated ( Wednesday, 24 January 2024 )