An interactive course
Learn Prolog by running it.
A notebook for logic programming. Start with facts and queries, finish with grammars, puzzles and meta-interpreters. Every idea comes with live code you can edit and execute in your browser, real SWI-Prolog, no install.
Foundations
Hello, logicFacts, queries, and what “false” really means.Terms: the building blocksAtoms, numbers, variables and compound terms.Syntax and execution modelTerms, atoms, clauses, goals, SLD resolution and backtracking, precisely.Logic vs. imperative programmingThe same problem, permutations, in Java, in Prolog and in Scala.RulesDeriving new knowledge with :- (if), commas (and) and semicolons (or).The parent/child knowledge baseFour ground facts, then rules for grandparents and siblings, and what they can answer.UnificationThe one mechanism behind pattern matching, assignment and parameter passing.Terms, substitutions and the MGUTerms as trees, substitutions, most general unifiers, and the unification algorithm.Search & backtrackingHow Prolog actually finds answers: depth-first, left-to-right, with undo.Resolution, step by stepResolvents, resolution trees, and resolution with unification and substitutions.
Data & computation
Natural numbers and PeanoNumbers as terms: z and s/1, the nat/1 and sum/3 relations, and equations that run both ways.Peano arithmeticsucc, sum, mul, dec and factorial on zero and s/1, plus predicates as boolean functions.Booleans as a data typePropositional logic as universal facts, then improved with rules.A program as a databaseQuerying facts, existential and universal queries, records and the wildcard variable.ArithmeticWhy `X = 1 + 2` is not 3, and how `is` fixes it.Built-in operators and mathOperators as predicates, evaluation with is/2, comparison, and the resolution of sum/2.ListsThe workhorse data structure: [Head|Tail] patterns and the standard library.Lists from scratchLists as cons/nil terms, the built-in [H|T] syntax, and member, find, position, concat and count.Full relationalityOne predicate, many functions: variables anywhere, and the pitfalls of enumeration.RecursionBase case, recursive case, and accumulators for speed.Performance, tail recursion and immutabilityCounting resolution steps, tail and non-tail recursion, and how terms are shared.Generating combinations and searchingExploration as a generator: join, permutation, combinations of solutions, and grid links.Structures & treesCompound terms as records, and a binary search tree from scratch.Algorithms on other data typesDatabase tables, binary and n-ary trees, bidirectional lists and lazily expanding lists.Inspecting and managing termsType checks, comparison, copy_term, terms as strings, univ, functor, arg, and console output.Text & outputAtoms, strings, character lists, and printing with format/2.
Control & the database
Cut & if-then-elseControlling backtracking: !, once/1 and ( If -> Then ; Else ).Negation as failureWhat `\+` really means, and why goal order matters.Collecting all solutionsfindall, bagof, setof, aggregate_all and forall.The dynamic databaseassert, retract, counters and memoisation.Higher-order predicatescall/N, maplist, foldl, filters, and lambdas.Errors & exceptionscatch/3, throw/1, and writing predicates that fail gracefully.
Advanced
Grammars with DCGsParse and generate language with Definite Clause Grammars.Difference listsLists with an open end: constant-time append and queues.Generate & test: puzzlesSolving puzzles by describing them, and making the search smarter.Constraints: CLP(FD)Arithmetic that runs backwards, and puzzles that solve themselves.Constraints in practiceis vs #=, N queens, sudoku and knapsack: arithmetic that runs in any direction, residual constraints, labeling and optimisation.Graphs & searchPaths, cycles, shortest routes, and breadth-first search.Everything is a term: operators and DSLsSurface syntax that denotes plain terms, op/3, and Prolog as the host of a small language.Solving goals as termscall, once and not, building goals with univ, findall, filter and the disjunction operator.Meta-interpretersWrite Prolog in Prolog: inspect, trace and extend the language itself.Symbolic computationDifferentiate and simplify expressions, programs as algebra.Capstone: solve a SudokuPut it together: a 9×9 Sudoku solver in a dozen lines.