Skip to content
LumenaryAcademy

Lumenary CS · Programming languages

Prolog

Programming in logic: describe what is true, ask questions, and let unification and backtracking find the answers, from a first query to constraint solving.

Prolog (PROgrammation en LOGique) was created in 1972 by Alain Colmerauer and Philippe Roussel in Marseille, building on Robert Kowalski's insight that logical statements can be read as procedures. A Prolog program is a set of facts and rules; running it means asking a question, and the system searches for every way of making the question true. Two mechanisms do the work: unification, which matches patterns containing variables, and backtracking, which tries alternatives in order. Prolog shaped artificial intelligence, natural-language processing and expert systems, inspired Datalog and today's rule and query engines, and is still used for parsing, scheduling, verification, configuration and teaching how computation and logic meet.

This course is for anyone who already knows what a variable, a loop and a function are: the Start level of Lumenary CS or equivalent experience in any language. Prolog will ask you to unlearn some habits (there are no loops and no assignment), so no logic background is assumed beyond 'and', 'or' and 'not'. It covers facts, rules and queries, unification, backtracking, recursion over lists, arithmetic, the cut and negation, grammars for parsing, constraint solving, the dynamic database, where Prolog is used today, and a complete puzzle-solving project.

To run the code, install SWI-Prolog, the most widely used free Prolog system, from swi-prolog.org (Linux distributions package it as swi-prolog; Homebrew as swi-prolog). Save a program as main.pl and run it with swipl main.pl, or start the interactive toplevel with swipl. You can also try Prolog without installing anything in SWISH, SWI-Prolog's official online notebook. Every complete program in these lessons starts with :- initialization(main, main)., was run with SWI-Prolog 10.1 by Lumenary's test suite, and shows the output it printed. The lessons were drafted with AI assistance and are awaiting review by a human computer scientist.

AI-draftedAwaiting review by a computer scientist
  • Chloe · The Designer
    “Why is the language built this way?”
  • Margaret · The Profiler
    “What does it print, and what does it cost?”
  • Gideon · The Language Lawyer
    “What exactly does the language guarantee?”

Foundations · 3 lessons

Facts, unification and search

What logic programming is and where it came from, facts, rules and queries, the unification that matches terms, and the backtracking search that finds every answer.

  1. 1First steps in PrologWhat logic programming is, how Prolog came out of Marseille and Edinburgh, and a first program of facts, rules and queries. 50 min
  2. 2Terms and unificationEvery Prolog value is a tree, and one operation, unification, matches trees with variables in both directions. 50 min
  3. 3Backtracking and searchHow Prolog actually finds answers, depth first, left to right, backing up on failure, and how to collect, count and steer the search. 55 min

Practice · 3 lessons

Lists, arithmetic, control and grammars

Recursion over lists with accumulators, arithmetic that is not reversible, the cut and negation as failure, and definite clause grammars for parsing text.

  1. 4Recursion and listsProlog has no loops, so repetition is recursion; lists are its everyday data structure, and accumulators make list code fast. 55 min
  2. 5Arithmetic, the cut and negationWhere pure logic meets the machine, evaluating numbers with is, committing to a choice with the cut, and saying "not" in a closed world. 55 min
  3. 6Grammars and parsingDefinite clause grammars turn a grammar into a parser, and a generator, with no extra code, from a fragment of English to an arithmetic language. 55 min

Professional · 2 lessons

Constraints, state and real programs

Solve puzzles with constraint logic programming, manage a dynamic database and tabling, and build a tested, modular puzzle solver while seeing where Prolog and Datalog are used today.

  1. 7Constraints, tabling and the databaseArithmetic that runs in every direction and prunes the search for you, memoised predicates that survive left recursion and cycles, and facts that change while the program runs. 60 min
  2. 8Project: a puzzle solverRead puzzles with a grammar, solve them with constraints, organise the code as tested modules, and see where Prolog and its descendants work today. 65 min

Further reading and resources