Introduction
ver. 1.0.0
An introduction to functional programming principles, its historical theoretical roots in mathematical logic and lambda calculus, and its contrasts with imperative programming.
This document constitutes the introductory chapter and front matter of a book on functional programming by Greg Michaelson. It contrasts functional and imperative programming paradigms across name-value associations, execution ordering, repetition, and data structures. It also traces the theoretical origins of functional computation from mathematical logic, computability theory (Turing, Kleene, and Church’s \(\lambda\) calculus), and reviews functional languages, denotational semantics, and the role of \(\lambda\) calculus as a foundational framework for the rest of the text.
Overview and Acknowledgements
The text opens with acknowledgements by Greg Michaelson (Edinburgh, 1988), detailing educational and collegial influences at the University of Essex, St Andrew’s University, Napier College, Glasgow University, and Heriot-Watt University, alongside publishing credits to Addison-Wesley.
Functional vs. Imperative Programming
The introduction systematically contrasts imperative and functional paradigms: * Names and Values: Imperative languages rely on variables as changeable associations modified via assignment sequences. Functional languages bind names strictly as formal function parameters upon function calls, meaning a name is only ever associated with a single value during its scope. * Execution Order: Imperative programs require fixed execution orders due to state dependencies. Functional languages are evaluation-order independent because nested function calls do not modify shared global state. * Repetition: Imperative repetition relies on loops modifying existing variables. Functional repetition operates via recursive function nesting, generating new local instances of parameters. * Data Structures: Functional languages lack in-place assignment, relying instead on explicit recursive nested structures (like lists) rather than modifiable arrays, and explicitly pass data structures rather than relying on global variables. * Functions as First-Class Values: Functional languages treat functions as values that can be passed to and returned from other functions.
Historical Origins and Theory of Computing
The text details the development of computation theory from mid-19th-century formal logic (propositional and predicate calculus by Boole, De Morgan, Peano, Frege, Russell, Whitehead, and Gödel) to 1936 computability models: Turing machines, Kleene’s recursive function theory, and Church’s \(\lambda\) calculus. It highlights the Church-Rosser theorem regarding evaluation order and termination.
Evolution of Functional Languages and λ Calculus
The chapter reviews major functional language milestones and formal methods: * Early developments: LISP (McCarthy), Landin’s SECD machine and ISWIM, Strachey and Scott’s denotational semantics. * Modern functional languages: POP-2/POPLOG, SASL, KRC, Miranda, Hope, Standard ML, and Backus’s FP system. * Role of \(\lambda\) Calculus: Serves as a foundational, minimal, and evaluation-order independent framework for modeling computation, prototyping, and program verification.
Outline of the Book
The chapter concludes with an outline of upcoming chapters, covering pure \(\lambda\) calculus syntax, data representations (booleans, numbers, lists, trees), recursion, evaluation orders, and practical applications in Standard ML and LISP.
Materials
Source document
- An Introduction To Functional Programming Through Lambda Calculus, Greg Michaelson, Dover Publications, 1989, 2011 — Page 3-11