Introduction and Background

Course Outline

See the Dateline

What is Functional Programming (FP)?

  • It is a style of programming where functions are the centerpiece
  • A key dimension is functions-as-data: functions can be passed and returned
  • It emphasizes immutability: data structures that cannot be changed after being created
  • Mathematical functions are implicitly immutable so FP aligns much more closely with math
    • It is much easier to write completely correct programs in an FP style for that reason

History in brief

  • λ-calculus, 1930’s - developed by logicians (Church, Turing, Kleene, Curry, etc)
    • Logic proofs are formal constructions, expressed as programs in the λ-calculus
    • The 1930’s λ-calculus is the core of a modern functional programming language
    • But before computers existed so no running, only hand-calculation - !
  • Lisp, 1960’s (McCarthy)
    • λ-calculus is elegant, build a PL around it
    • Goal application space: artificial intelligence programming
    • Added list data to λ functions: List Processing
  • Typed functional languages, 70’s & 80’s: Milner’s ML and its descendents Haskell and OCaml
    • We will be using OCaml
  • Modern era: add FP as possibility in mainstream PLs: Python, JavaScript, Java, C++, etc.

Imperative vs Object-Oriented vs Higher-Order Functional

  • Oversimplifying but these are the three modern schools
  • More oversimplifying: “Imperative = C, OO = Java, FP = OCaml”
  • Note many O-O languages now have functions, often called lambdas for the historical reference
  • Goal of this course is to get deeply into the FP mode of programming, which can then be used in your favorite PL - Java, Python, C++, JavaScript, OCaml, etc.


  • Imperative also has functions, but there functions often have side effects (e.g. mutate some shared data structures)
  • C has function pointers to pass around functions as data but they are not widely used and lack needed expressiveness (which we will cover later).

Object-Oriented (OO)

  • Objects tend to have “their” state encapsulated within their boundary
  • It is usually a mutable state - changes over time
  • A function is similar to an object with one method, call, and with no fields
  • That doesn’t fully capture higher-order functions which is why lambda added to Java.

Functional (FP)

  • As mentioned above, key aspect is lack of mutation: more like a mathematical function, the output only depends on the input and it’s only output is the codomain value, not any side effects like printing, mutating, raising exceptions, etc.
  • Lack of side effects is called “referential transparency” - variable values don’t change out from under you (follows how math behaves).
  • Standard data structures not too different from imperative case: dictionaries, lists, etc, but often will themselves be immutable - instead of mutating, make a fresh copy.
  • Key advantage is higher-order-ness: code is data, make new functions, accept functions as parameters.
  • Allows for powerful new programming paradigms using functions as data.
    • Simple example is function composition operation: g o f (x) = g(f(x)): o takes two functions and returns a new function
  • Less good at supporting extension, no notion of subclass in common functional paradigms

Who wins?


  • Imperative wins for low-level code: underlying machine instructions are in the imperative domain, will run faster.
  • O-O wins for super large apps with fairly shallow logic: UI’s, many apps, etc.
  • Functional wins for complex algorithms with deep inner logic, and also for data manipulation focus
  • Gets too confusing with mutation, and better composition of functions makes code easier to understand.
  • Of course this choice is never made in a vacuum: existing codebases and libraries, programmer experience, etc.

Typed Functional vs Untyped Functional

  • OK we arm-wrestled over OO vs FP, now we get to arm-wrestle in FP over whether types are good (OCaml, Haskell, etc) or bad (Scheme, Clojure, (Python, JavaScript))
  • We are clearly in the “types are good” camp here but there are trade offs
    • With types we have type-directed programming: often once all the type errors are fixed the code just works.
      • this is because types are lightweight invariants on program behavior
    • The downside is types can get in the way both in terms of code maintenance and in terms of expressiveness.

Which Typed Functional Language? ML vs Haskell

  • The final wrestling match in the typed FP world is which typed FP is your favorite.
  • I was “born and raised” in the ML camp so we are in ML.