Session 14: Programming Paradigms & Functional Programming

Overview

The three main paradigms and how they came about, then functional programming in more detail: purity, higher-order functions, and fold as the general list recursion.

Lecturer

Daniel Dia — Primary Instructor & Organizer (dmd13@mail.aub.edu)

Session Information

Core Concepts

  • Historical exposition (1936-2005): λ-calculus vs Turing machines, the software crisis, structured programming, OOP, Hoare’s null reference (1965), and the concurrency wall (2005)
  • Imperative paradigm: state, mutation, sequencing
  • OOP paradigm: encapsulation, inheritance, dynamic dispatch
  • Functional paradigm: purity, referential transparency, absence of observable side effects
  • First-class and higher-order functions; map, filter, fold, and compose as building blocks
  • Fold as the universal list recursion: deriving map, filter, length, sum, and reverse from it
  • Monoids as the structure fold requires
  • Currying and partial application
  • A short demonstration of Lean4 syntax

Slides

Session 14 Slides: Download PDF

Readings

Exercises & Extra Steps

  • Practice (not collected): define map and filter in terms of fold, then prove your map agrees with the direct definition by induction
  • Practice (not collected): give three examples of monoids and verify the laws
  • Practice (not collected): rewrite five imperative loops as map/filter/fold expressions
  • Problem Set 4 due today — hand it in on paper at the start of the session

Questions? Reach out on the course WhatsApp!