Skip to content

Lambda Calculus

Introduction

Functional programming is an approach to programming based on function class as the primary programming construct.

  • imperative programming: variables as changeable association between name and value
  • called imperative because they consist of sequences of commands
  • order in which commands are executed is crucial
<command1>;
<command2>;
<command3>;
...
  • commands consist of assignments that change a variables' value
<name> := <expression>

In imperative languages, the same name may be associated with different values.

  • functional programmig: based on structured functional calls (composition)
<function1>(<function2>(<function3> ... ) ... ))

In functional languages, a name is only ever associated with one value.

  • function calls cannot change the values associated with common names
  • the order in which nested functions are executed does not matter
F( A(D), B(D), C(D) )
  • it does not matter in which order A(D), B(D), C(D) are carried out, since they cannot change their common parameter D

In functional languages, there is no necessary execution order.

  • instead of command repitition, recursive calls are used for looping
  • functions may construct new functions and pass them to other functions

Functional languages allow functions to be treated as values.

  • \(\lambda\)-calculus is a simple yet powerful system
  • based on function abstraction (generalise expressions through giving them names) and function application (evaluate generalised expressions by giving values to names)
  • can be treated as a universal machine code for programming languages
  • is order independent

Functional languages originate in mathematical logic and the theory of computation, in recursive function theory and \(\lambda\)-calculus.

References


Last update: November 23, 2020