Functional Programming

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s