Functional Programming

Functional programming treats computation as the evaluation of mathematical functions, avoiding mutable state and emphasizing higher-order functions, immutability, and equational reasoning.

Definition

Functional programming is a paradigm in which programs are built by composing pure functions over immutable data, so that evaluating an expression depends only on its inputs and produces no observable side effects.

Scope

This topic covers the functional paradigm grounded in the lambda calculus: first-class and higher-order functions, immutability and referential transparency, recursion, lazy evaluation, algebraic data types and pattern matching, and the use of monads and other abstractions to structure effects. It addresses why pure functions aid composition, reasoning, and parallelism.

Core questions

• How do higher-order functions and lazy evaluation improve modularity?
• What does referential transparency buy in terms of reasoning and optimization?
• How are side effects modeled in a purely functional setting?
• How does functional code relate to the lambda calculus and to type theory?

Key theories

Glue from higher-order functions and laziness

Hughes argues that functional programming's modularity advantage comes from higher-order functions and lazy evaluation, which act as 'glue' for composing small, reusable program pieces.

Monads for structuring effects

Wadler showed how monads provide a uniform, compositional way to thread state, exceptions, and other effects through otherwise pure functional programs.

Algebra of functional programs

Backus's function-level programming presents an algebra of combinators with equational laws that support reasoning about and transforming programs.

Clinical relevance

Functional techniques such as immutability and pure functions reduce classes of bugs tied to shared mutable state and make code easier to test and parallelize. These ideas have diffused widely into mainstream languages through lambdas, immutable collections, and stream/map-reduce abstractions.

History

Functional programming traces to Church's lambda calculus and McCarthy's Lisp (1958). The 1970s and 1980s produced ML, Miranda, and Scheme; Backus's 1977 Turing lecture advanced the functional critique of imperative style. Haskell standardized lazy, purely functional programming around 1990, and Wadler's monad-based effect handling made pure functional programming practical for real-world tasks.

Debates

Lazy versus strict evaluation

Functional language designers debate whether lazy (call-by-need) evaluation, which enables elegant infinite structures and modularity, is worth its costs in reasoning about space and performance compared to strict evaluation.

Key figures

• John Hughes
• Philip Wadler
• John Backus
• Richard Bird
• Simon Peyton Jones

Seminal works

• hughes1989
• wadler1992
• backus1978
• bird1998

Frequently asked questions

What is referential transparency?

An expression is referentially transparent if it can be replaced by its value without changing the program's behavior, which holds when functions are pure and data is immutable.

How does functional programming handle input/output and state?

Effects are typically modeled explicitly, for example through monads or effect systems, so that the order and presence of side effects is captured in types rather than arising implicitly from mutation.