Introduction To World Of Lambdas.
Lambda expression is appearing in every other programming language and gaining a popularity amongs the developers. So what is the lambda expression? Why should we use it? Is it just anonymous function? what powers does it gives to programmer? Lets discuss all this in details in this series of posts.
In this post, we will see the brief introduction to lambda expressions and how to express them in programming language independent way.
Lambda expressions or if I say lambda functions are anonymous functions with no names. They only accept one input variable, with certain operations used to implement a function with several variables.
Lambda expressions are powerfull because we can create a higher order function using them. Here by higher order function I mean a function which can accept a another function as argument or return a function as output.
But to able to able to create and use lambda expressions in meaningfull manner we should know the “Lambda Calculus”.
Lambda Caluclus is a language of lambda terms(expressions) which is defined by certain formal syntax and set of transformation rules, which manipulate the lambda terms.
- Lambda calculus was first introduced by mathematician Alonzo Church in 1930s as part of his research.
- Lambda calculus is a universal model of computation that can be simulated by any Turing Machine.
Basics of Lambda Calculus
To be able to understand the power of lambda, we must know the basics of it so that we will be a able to form lambda expressions by our own to use in any of our favourite programming language.
Expressing Lambda Terms
Lets see how to express lambda terms in programming language independent form. There are three forms of lambda terms.
Lets discuss each them in brief.
Variable can be a character or String representing a parameter or mathematical(numerical)/logical value. Example: X, 1, var, True, False
x 1 True False
Abstraction is function defination. It can be thought as just constructing any other function with arguments. Example: To construct a increment function which accepts one parameter and returns adding one to it.
(λx.x + 1)
In above expression, before the (.) dot “λx” is where we are declaring an anonymous function with parameter ‘x’ and after the (.) dot “x+1” is a function body where are writing a logic of a function.
Please note that ‘+’ operator used in above expression and below one also is not a lambda term. But I am using it just for intuition. It can be think of as another lambda abstraction for plus operation.
Another example of addtion of two numbers can be constructed as:
(λxy.x + y)
Application is applying one function to an argument. Where argument is another lambda term. Example:
In above expression we are applying a variable(lambda term) “2” to another lambda term “λx.x + 1” which is a lambda Abstraction.
So this is how we construct lambda expressions in three forms. Variable, Abstraction, Application. To summurise the inductive defination of lambda expressions with three rules which can be use to construct valid lambda terms:
- A variable, x, is itself a valid lambda term
- If ‘t’ is a lambda term, and ‘x’ is a variable, then “(λx.t)” is a lambda term (called a lambda abstraction);
- if ‘t’ and ‘s’ are lambda terms, “(ts)” is a lambda term (called an application).
This was just introduction to lambda calculus to give you an idea what lambda expressions are and how to construct valid lambda expressions. In the next post we will discuss about free and bound variables and evaluating a lambda terms with alpha-conversion and beta-reduction.
Please comment below for any queries, suggestions and also if you find any mistake in above post. Thank You!
2018-05-22 16:55 +0530