Functional Programming Fundamentals

1Introduction

This lecture explains functional programming, which organizes computation primarily through function application and expression evaluation. It defines pure functions, immutability, higher-order functions, and referential transparency and explains why these concepts support local reasoning.

Functional and imperative programming are not mutually exclusive categories. Practical languages often combine features from both, and effective designs place state updates and pure computations according to the needs of the problem.

2Basic Terms

A pure functionPure function is a function whose return value is determined only by its arguments and whose evaluation produces no externally observable state change.

A side effectSide effect is an externally observable change that occurs in addition to computing a return value. Updating a shared variable, performing I/O, and raising an exception are examples.

ImmutabilityImmutability is the property that a value's contents do not change after the value is created. When updated information is required, a new value is created without modifying the existing value.

A first-class functionFirst-class function is a function value that can be used like other values, including as an argument, return value, or element of a data structure. A higher-order functionHigher-order function is a function that receives a function as an argument or returns a function as its result.

Referential transparencyReferential transparency is the property that replacing an expression with its value does not change the program's observable behavior.

3Pure Functions and Immutability

For example, a pure function that increments an integer by one can be written as follows.

increment(n) = n + 1

Every evaluation of increment(3) produces $$4$$4, and the evaluation does not modify shared state. By contrast, a function that updates and returns a shared counter is not pure because its result depends on the counter's current state.

An operation that prepends $$x$$x to an immutable list xs constructs a new list from $$x$$x and xs without modifying xs. Consequently, the meaning of other expressions that refer to the old list does not change.

4Referential Transparency and Equational Reasoning

Suppose expression $$e$$e evaluates to value $$v$$v and $$e$$e is referentially transparent. Replacing $$e$$e with $$v$$v in the program then leaves its observable result unchanged. This property enables equational reasoningEquational reasoning, in which transformations of expressions can be verified as equations.

This does not make I/O unnecessary. Functional languages handle required I/O through types or syntax that make effects explicit, or by separating pure computations from boundaries that perform effects.

5Higher-Order Functions

map(f, [])       = []
map(f, x :: xs)  = f(x) :: map(f, xs)

map is a higher-order function because it receives function $$f$$f as an argument. It centralizes the traversal of a list while separating the operation on each element as $$f$$f. This separation facilitates reuse and composition.

6Relationship to Imperative Programming

Imperative programming describes computation primarily through state transitions caused by instructions such as assignments. Functional programming describes computation primarily through expression evaluation and function application. This distinction concerns emphasis; it does not imply that either approach is always preferable.

For example, an implementation may expose a pure function while using a mutable array local to each call, provided that no reference to the array escapes and no call history affects the observable result.

7Summary

• A pure function determines its return value only from its arguments and produces no observable side effects.
• Immutability and referential transparency provide a basis for local reasoning about expressions.
• Higher-order functions separate common computational structure from specific operations.
• Practical programs integrate pure computations and necessary effects at explicit boundaries.

8Next Lecture