Lambda Calculus Part 1

In mathematical logic and computer science, lambda calculus, also written as λ-Calculus, is a formal system designed to investigate function defination, functiona application and recursion. Is is a useful tool in the investigation of problems in computability or recursion theory, anf forms the basis of a paradigm of computer programming called functional programming.

The key concept of lambda calculus is that of a lambda expression - a reification of the concept of a procedure without side effects. The lambda calculus can be thought of as an idealized, minimalistic programming language. It is capable of expressing any algorithm, and it is this fact that makes the model of functional programming an important one. Functional programs are stateless and deal exclusively with functions that accept and return data (including other functions), but they produce no side effects in 'state' and thus make no alterations to incoming data. Modern functional languages, building on the lambda calculus, include Erlang, Haskell,Lisp, ML, and Scheme, as well as more recent languages like F#, Nemerle, and Scala.

The lambda calculus derives its usefulness from having a sparse syntax and

a simple semantics, and yet it retains sufficient power to represent all computable

functions. Lambda expressions come in four varieties:

1. Variables, which are usually taken to be any lowercase letters.
   
2. Predefined constants, which act as values and operations are allowed in an impure or applied lambda calculus .
   
3. Function applications (combinations).
   
4. Lambda abstractions (function definitions).
   

The simplicity of lambda calculus syntax is apparent from a BNF specification

of its concrete syntax:

<expression> ::= <variable> ; lowercase identifiers

| <constant>  ; predefined objects

| ( <expression> <expression> ) ; combinations

| ( λ <variable> . <expression> ) ; abstractions.