Functional

by Alonzo Church

Origin

Functional programming is based on the work of Alonzo Church, who developed λ-calculus (lambda calculus) in the 1930s, a mathematical framework that serves as the foundation of functional programming.

Historical Context

Church’s lambda calculus laid the groundwork for languages like Lisp (developed by John McCarthy in 1958) and later functional languages such as Haskell and ML.

The functional programming paradigm views computation as the evaluation of functions in the mathematical sense, where functions are treated as first-class objects. Functional programming emphasizes a declarative approach, where the result is defined through the evaluation of expressions rather than the execution of commands.

Computation as Function Evaluation in the Mathematical Sense (Contrasting Procedural Subroutines)

Functional programming treats functions as mathematical objects that take inputs and produce outputs. These functions are pure, meaning they have no side effects and always return the same result given the same inputs.

Ideal for Hoare Triples

Functional programs are easier to formally verify and test, as they do not modify the program state or depend on the sequence of instructions. This makes them ideal for use with formal methods like Hoare triples, which allow for proving the correctness of programs.

Support for Recursion and Higher-Order Functions

Functional languages make heavy use of recursion and higher-order functions (functions that take other functions as arguments or return them as results), providing powerful tools for solving complex problems.

Immutability and Expression Evaluation

In functional programming, the program’s state does not change; new values are created as a result of evaluating expressions. This simplifies parallelism and makes code more predictable and secure.

Examples of Languages

• Haskell
• Lisp
• Erlang
• Elixir

functional paradigm hoare-triples