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