Welcome to Functional & Logic Programming
Until now, almost every program you have written has been imperative — a sequence of commands that change variables step by step. This course introduces two radically different paradigms:
- Functional programming (Haskell): a program is a collection of mathematical functions. There are no assignment statements, no loops, and no changing state — only expressions that are evaluated.
- Logic programming (Prolog): a program is a collection of facts and rules. You don't tell the computer how to compute an answer — you describe what is true, ask a question, and the system searches for the answer itself.
The paradigm map
How this course is organised
| Syllabus block | Lessons that cover it |
|---|---|
| Intro to FP, Haskell & GHCi, basic types, designing programs | Unit 1 → "The Functional Paradigm" and "Basic Types & Definitions" |
| Data types, tuples, lists, input/output, control structures | Unit 1 → "Tuples, Lists, I/O & Control Structures" |
| Lambda calculus: syntax, conversions, normal forms, Church–Rosser, combinators | Unit 1 → "The Lambda Calculus" |
| Graph reduction, Three Instruction Machine | Unit 1 → "How Haskell Runs: Graph Reduction & the TIM" |
| Programming with lists, building vocabulary, functions over lists | Unit 2 → "Programming with Lists" |
| Pattern matching and recursion | Unit 2 → "Pattern Matching & Recursion" |
| Overloading, type classes, type checking | Unit 2 → "Overloading, Type Classes & Type Checking" |
| Algebraic types | Unit 2 → "Algebraic Data Types" |
| Intro to logic programming, basic constructs | Unit 3 → "Introduction to Logic Programming" |
| Database & recursive programming | Unit 3 → "Database & Recursive Programming" |
| Computation model, theory & applications of logic programs | Unit 3 → "The Computation Model of Logic Programs" |
| Prolog: introduction, programming, arithmetic, structure inspection | Unit 4 → "Programming in Prolog" and "Structure Inspection" |
| Second-order programming, logic grammars, search techniques | Unit 4 → "Second-Order Programming" and "Logic Grammars & Search" |
| Lab experiments (Haskell + Prolog) | "Lab Practicals" lesson at the end |
Why learn paradigms you may never "use at work"?
- They change how you think. Recursion, immutability and pattern matching — once they click in Haskell — make you a better Java/Python programmer too.
- Mainstream languages are absorbing them. Lambdas in Java, list comprehensions in Python,
Option/Resulttypes in Rust, LINQ in C# — all came from functional programming. - They power real systems. Haskell runs in banking and compilers; Prolog-style logic powers SQL query planners, type checkers, expert systems and parts of AI reasoning.
- Exams love them. The questions are predictable — evaluate a lambda expression, write a recursive list function, trace a Prolog query — and every one of them is practised in these lessons.
How to study this course
- Install GHC (Haskell) and SWI-Prolog in week one. Both are free; both run on Windows/Linux/Mac. Every concept sticks 10× better after you type it into the REPL yourself.
- Evaluate by hand first. Lambda-calculus reductions and Prolog query traces are pen-and-paper skills; the interpreter is only there to confirm your manual answer.
- Do the lab experiments alongside the theory units — the lab lesson at the end of this course maps each experiment to the unit that explains it.
- Trace every diagram. The Mermaid diagrams in this course show evaluation orders and search trees step by step — walk through them before moving on.
The three paradigms side by side (a favourite exam comparison)
| Aspect | Imperative (C, Java) | Functional (Haskell) | Logic (Prolog) |
|---|---|---|---|
| A program is... | a sequence of commands | a set of function definitions | a set of facts and rules |
| Basic computation step | assignment / state change | expression evaluation (reduction) | unification + resolution |
| Repetition | loops (for, while) | recursion | recursive rules + backtracking |
| "Variable" means | a mutable memory cell | a name bound once to a value | a logical unknown, bound by unification |
| Control flow | written by the programmer | follows the structure of expressions | supplied by the search strategy |
| Result of a run | the final machine state | the value of an expression | answer substitution(s) for the query |
| Typical exam task | trace these statements | evaluate this expression | trace this query |
A 5-mark "compare the programming paradigms" question is answered perfectly by reproducing this table and adding one two-line code sample per paradigm (e.g. factorial as a loop, as a recursive equation, and as a pair of clauses).
How the end-term exam typically samples this course
| Question style | Typical weight | Where it is practised here |
|---|---|---|
| Define / differentiate (referential transparency, currying, MGU, cut...) | 2–3 marks each | "exam definition" boxes inside every lesson |
| Evaluate / reduce by hand (Haskell trace, β-reduction, fold expansion) | 5 marks | worked traces in Units 1 & 2 |
| Write a small program (list function, ADT + interpreter, Prolog predicate) | 5–8 marks | classic-code sections in Units 2–4 |
| Trace a Prolog query / draw the SLD search tree | 5–8 marks | Unit 3 computation model + Unit 4 |
| State a theorem / explain a model (Church–Rosser, TIM, negation as failure) | 5 marks | Unit 1 & Unit 3 theory lessons |
Two habits pay the most: always show every intermediate step in a trace (markers are awarded per step), and always give the type signature before a Haskell definition — both signal mastery instantly.
Self-check before you begin
- Can you name two differences between declarative and imperative programming?
- Which two language families sit under the declarative branch of the paradigm map above?
- What does each unit of this course cover, in one phrase per unit?
- Which tools should be installed in week one, and what are their REPL commands called?