Prolog Programming Mastery: Logic Programming from First Principles

Goal: Master the logic programming paradigm through Prolog, fundamentally rewiring how you think about computation. Instead of writing step-by-step instructions, you will learn to describe problems declaratively—stating what you know and what you want to find, then letting Prolog’s inference engine discover solutions automatically. By completing these projects, you will internalize unification, backtracking, and recursive reasoning patterns that make seemingly complex problems trivial to solve.

Why Prolog Matters

Prolog (Programming in Logic) represents one of the most radical departures from conventional programming thinking. Created in 1972 by Alain Colmerauer and Philippe Roussel, it emerged from research in artificial intelligence and computational linguistics. While mainstream languages ask “how do I compute this?”, Prolog asks “what is true about this problem?”

This paradigm shift has profound implications:

┌─────────────────────────────────────────────────────────────────────────────┐
│                    IMPERATIVE vs. DECLARATIVE THINKING                      │
├─────────────────────────────────────┬───────────────────────────────────────┤
│        IMPERATIVE (Python/Java)      │        DECLARATIVE (Prolog)          │
├─────────────────────────────────────┼───────────────────────────────────────┤
│                                     │                                       │
│  def find_path(graph, start, end):  │  edge(a, b).                          │
│      visited = set()                │  edge(b, c).                          │
│      queue = [start]                │  edge(c, d).                          │
│      while queue:                   │                                       │
│          node = queue.pop(0)        │  path(X, X, [X]).                     │
│          if node == end:            │  path(X, Y, [X|P]) :-                 │
│              return True            │      edge(X, Z),                      │
│          visited.add(node)          │      path(Z, Y, P).                   │
│          for neighbor in graph[node]│                                       │
│              if neighbor not in     │  % Query: ?- path(a, d, Path).        │
│                  visited:           │  % Answer: Path = [a, b, c, d]        │
│                  queue.append(...)  │                                       │
│                                     │                                       │
│  YOU write the search algorithm     │  YOU describe relationships;          │
│  YOU manage state explicitly        │  PROLOG searches automatically        │
│  YOU handle edge cases              │  PROLOG handles backtracking          │
│                                     │                                       │
└─────────────────────────────────────┴───────────────────────────────────────┘

Real-World Applications

Prolog is not just an academic curiosity. It powers:

  • Expert Systems: IBM’s Watson, medical diagnosis systems, legal reasoning engines
  • Natural Language Processing: Parsing, grammar checking, machine translation
  • Constraint Solving: Scheduling, resource allocation, logistics optimization
  • Database Systems: Datalog (a subset of Prolog) underlies many modern query systems
  • Compiler Design: Type inference, semantic analysis
  • Automated Theorem Proving: Formal verification, proof assistants

The Execution Model: How Prolog Thinks

┌─────────────────────────────────────────────────────────────────────────────┐
│                        PROLOG EXECUTION MODEL                               │
│                                                                             │
│  QUERY: ?- grandparent(X, charlie).                                         │
│                                                                             │
│  KNOWLEDGE BASE:                    EXECUTION:                              │
│  ┌──────────────────────┐          ┌──────────────────────────────────┐    │
│  │ parent(alice, bob).  │          │ 1. Try to prove grandparent(X,   │    │
│  │ parent(bob, charlie).│             charlie)                         │    │
│  │ parent(bob, diana).  │          │                                   │    │
│  │                      │          │ 2. Find rule: grandparent(G,C) :- │    │
│  │ grandparent(G, C) :- │             parent(G, P), parent(P, C)       │    │
│  │   parent(G, P),      │          │                                   │    │
│  │   parent(P, C).      │          │ 3. Unify: G=X, C=charlie          │    │
│  └──────────────────────┘          │                                   │    │
│                                    │ 4. Now prove: parent(X, P),       │    │
│                                    │               parent(P, charlie)  │    │
│  ┌─────────────────────────────────┴──────────────────────────────────┐    │
│  │                        SEARCH TREE                                  │    │
│  │                                                                     │    │
│  │              ?- grandparent(X, charlie)                             │    │
│  │                          │                                          │    │
│  │              ?- parent(X, P), parent(P, charlie)                    │    │
│  │                    /              \                                 │    │
│  │      X=alice, P=bob         X=bob, P=charlie                        │    │
│  │              │                     │                                │    │
│  │   ?- parent(bob, charlie)    ?- parent(charlie, charlie)            │    │
│  │              │                     │                                │    │
│  │           SUCCESS               FAIL (backtrack)                    │    │
│  │                                                                     │    │
│  │  RESULT: X = alice                                                  │    │
│  └─────────────────────────────────────────────────────────────────────┘    │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

After Completing These Projects, You Will:

  1. Think declaratively - Describe what you want, not how to get it
  2. Master unification - The powerful pattern-matching that drives Prolog
  3. Harness backtracking - Let the engine explore solution spaces for you
  4. Build expert systems - Encode knowledge and reason automatically
  5. Parse natural language - Using Definite Clause Grammars (DCGs)
  6. Solve constraint problems - From Sudoku to scheduling
  7. Write meta-interpreters - Programs that manipulate programs
  8. Interface with other languages - Embed Prolog in larger systems

Prerequisites & Background Knowledge

Essential Prerequisites

  • Basic programming experience in any language (variables, functions, conditionals)
  • Recursion fundamentals - Understanding how functions call themselves
  • Comfort with the command line - Running programs, editing files

Helpful But Not Required

  • Discrete mathematics - Sets, relations, graph theory
  • Propositional logic - AND, OR, NOT, implication
  • First-order logic - Predicates, quantifiers (helpful for understanding the theory)
  • Functional programming exposure - Lisp, Haskell, or similar (similar mindset)

Self-Assessment Questions

Before starting, can you answer these?

  1. What is recursion, and how does a base case prevent infinite loops?
  2. What is a graph, and what does it mean to traverse one?
  3. Given f(x) = x + 1, what is f(f(2))?
  4. What does “pattern matching” mean in programming?

If you struggle with #1, review recursion basics first. The others will be covered.

Development Environment Setup

Recommended: SWI-Prolog (https://www.swi-prolog.org/)

# macOS
brew install swi-prolog

# Ubuntu/Debian
sudo apt-get install swi-prolog

# Windows
# Download installer from swi-prolog.org

# Verify installation
swipl --version

Alternative Implementations:

  • GNU Prolog - Faster for constraint solving
  • Scryer Prolog - Modern, standards-compliant
  • Tau Prolog - JavaScript-based, runs in browser

Editor Setup:

  • VS Code + “VSC-Prolog” extension
  • Emacs + prolog-mode
  • Vim + prolog syntax highlighting

Time Investment Expectations

Experience Level Total Time Per Project
Beginner programmer 8-12 weeks 3-5 days
Experienced (new to logic prog) 4-6 weeks 2-3 days
Familiar with Prolog 2-3 weeks 1-2 days

Reality Check

Prolog requires a mental shift that can be frustrating initially. You will:

  • Try to write loops (Prolog doesn’t have them—use recursion)
  • Fight the urge to explicitly control execution order
  • Be amazed when complex problems solve themselves
  • Eventually internalize a new way of thinking about computation

Core Concept Analysis

1. Facts: The Foundation of Knowledge

Facts are unconditionally true statements about your domain. They form the database that Prolog reasons over.

% Basic facts (arity-1: single argument)
human(socrates).
mortal(socrates).

% Binary facts (arity-2: two arguments)
parent(homer, bart).
parent(marge, bart).
parent(homer, lisa).

% Facts with more arguments
flight(aa100, chicago, miami, 1400).  % flight(ID, From, To, DepartureTime)

Key insight: Facts end with a period. Arguments can be atoms (lowercase), numbers, or compound terms.

2. Rules: Defining Relationships

Rules derive new knowledge from existing facts and other rules. The :- symbol reads as “if” or “is true when”.

% X is mortal if X is human
mortal(X) :- human(X).

% X is a sibling of Y if they share a parent and are different
sibling(X, Y) :-
    parent(P, X),
    parent(P, Y),
    X \= Y.

% X is an ancestor of Y (recursive definition)
ancestor(X, Y) :- parent(X, Y).                    % Base case
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).    % Recursive case

Key insight: The comma , means AND. Rules can call themselves recursively.

3. Queries: Asking Questions

Queries ask Prolog to prove something is true, potentially binding variables to values.

?- human(socrates).           % Is socrates human?
true.

?- parent(homer, Who).        % Who is homer a parent of?
Who = bart ;                  % Press ; for more solutions
Who = lisa ;
false.                        % No more solutions

?- ancestor(X, bart).         % Who are bart's ancestors?
X = homer ;
X = marge ;
X = grandpa ;                 % If such facts exist
...

4. Unification: Pattern Matching on Steroids

Unification is Prolog’s core mechanism. It finds substitutions that make two terms identical.

┌─────────────────────────────────────────────────────────────────────────────┐
│                           UNIFICATION EXAMPLES                              │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  foo(a, b)  =  foo(a, b)        ✓ Same terms, trivially unify               │
│                                                                             │
│  foo(X, b)  =  foo(a, b)        ✓ Unify with X = a                          │
│                                                                             │
│  foo(X, X)  =  foo(a, b)        ✗ Fails! X can't be both a and b            │
│                                                                             │
│  foo(X, Y)  =  foo(Y, a)        ✓ X = a, Y = a                              │
│                                                                             │
│  [H|T]      =  [1,2,3]          ✓ H = 1, T = [2,3]                          │
│                                                                             │
│  point(X,Y) =  point(3,4)       ✓ X = 3, Y = 4                              │
│                                                                             │
│  f(g(X))    =  f(g(5))          ✓ X = 5 (nested unification)                │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

When Prolog makes a choice and later fails, it automatically backtracks to try alternatives.

┌─────────────────────────────────────────────────────────────────────────────┐
│                         BACKTRACKING VISUALIZATION                          │
│                                                                             │
│  Knowledge Base:                                                            │
│    likes(mary, pizza).                                                      │
│    likes(mary, sushi).                                                      │
│    likes(mary, tacos).                                                      │
│    expensive(sushi).                                                        │
│                                                                             │
│  Query: ?- likes(mary, Food), \+ expensive(Food).                           │
│         (What food does Mary like that isn't expensive?)                    │
│                                                                             │
│  Execution:                                                                 │
│                                                                             │
│    likes(mary, Food)     Food = pizza                                       │
│           │              \+ expensive(pizza)  →  SUCCESS                    │
│           │                                                                 │
│           │  (user asks for more with ;)                                    │
│           │                                                                 │
│           ▼  BACKTRACK                                                      │
│    likes(mary, Food)     Food = sushi                                       │
│           │              \+ expensive(sushi)  →  FAIL (sushi IS expensive)  │
│           │                                                                 │
│           ▼  BACKTRACK automatically                                        │
│    likes(mary, Food)     Food = tacos                                       │
│           │              \+ expensive(tacos)  →  SUCCESS                    │
│           │                                                                 │
│  Results: Food = pizza ; Food = tacos                                       │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

6. Lists: The Primary Data Structure

Lists in Prolog are fundamental. The [Head|Tail] notation is essential for recursive processing.

% List notation
[1, 2, 3]           % A list of three elements
[]                  % The empty list
[a | [b, c]]        % Same as [a, b, c]
[H | T]             % Pattern: H is head, T is tail

% Common list predicates
member(X, [X|_]).                     % X is the head
member(X, [_|T]) :- member(X, T).     % Or X is in the tail

append([], L, L).                     % Empty + L = L
append([H|T], L, [H|R]) :-
    append(T, L, R).                  % Recursive case

length([], 0).                        % Empty list has length 0
length([_|T], N) :-
    length(T, N1),
    N is N1 + 1.                      % Length = 1 + length of tail

7. Arithmetic: The is Operator

Prolog uses is for arithmetic evaluation. The right side must be fully instantiated.

?- X is 3 + 4.
X = 7.

?- X is 2 * (3 + 4).
X = 14.

?- 3 + 4 = 7.
false.           % = is unification, not arithmetic!

?- X = 3 + 4.
X = 3+4.         % X is the TERM 3+4, not the VALUE 7

Key insight: = is unification, is is arithmetic evaluation, =:= is arithmetic equality.

Concept Summary Table

Concept Symbol/Syntax What to Internalize
Fact fact(args). Ground truth in your knowledge base
Rule head :- body. Derived truth; “head is true if body is true”
Query ?- goal. Question asked of the system
Conjunction , AND - both must succeed
Disjunction ; OR - either can succeed
Unification = Make two terms identical by binding variables
Arithmetic is Evaluate arithmetic expression
List head/tail [H\|T] Destructure lists for recursion
Anonymous variable _ “I don’t care about this value”
Negation as failure \+ Succeed if goal cannot be proven
Cut ! Commit to current choice, prevent backtracking

Deep Dive Reading by Concept

Foundational Texts

Concept Book Chapter/Section
Facts, Rules, Queries “Programming in Prolog” (Clocksin & Mellish) Ch. 1-2
Unification “The Art of Prolog” (Sterling & Shapiro) Ch. 3
Backtracking “Programming in Prolog” Ch. 4
Lists & Recursion “Learn Prolog Now!” (Blackburn et al.) Ch. 4-5
Arithmetic “Programming in Prolog” Ch. 5
DCGs “The Art of Prolog” Ch. 17
Cut & Control “Programming in Prolog” Ch. 4.3
Meta-programming “The Art of Prolog” Ch. 17-18
Constraint Logic Programming SWI-Prolog CLP(FD) documentation Full guide
  1. Week 1-2: “Learn Prolog Now!” Chapters 1-6 (free online)
  2. Week 3-4: “Programming in Prolog” Chapters 1-5
  3. Week 5-6: “The Art of Prolog” Chapters 1-8
  4. Advanced: “The Craft of Prolog” by Richard O’Keefe

Quick Start Guide: First 48 Hours

Day 1: Install and Explore

  1. Install SWI-Prolog
  2. Start the REPL with swipl
  3. Try these queries: 
    ?- X = 5.
?- X = Y, Y = 5.
?- [H|T] = [1,2,3].
  4. Create a file family.pl with facts about your family
  5. Consult it: ?- consult('family.pl').

Day 2: Write Your First Rules

  1. Add parent/child relationships
  2. Write a grandparent/2 rule
  3. Write a recursive ancestor/2 rule
  4. Practice queries: “Who are all ancestors of X?”

Path A: Complete Beginner (8-12 weeks)

Projects: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11

Path B: Experienced Programmer (4-6 weeks)

Projects: 1 → 3 → 5 → 7 → 9 → 11 → 14 → 16

Path C: AI/NLP Focus (5-7 weeks)

Projects: 1 → 2 → 4 → 8 → 9 → 10 → 13 → 17

Path D: Constraint Satisfaction Focus (4-5 weeks)

Projects: 1 → 3 → 4 → 6 → 11 → 12 → 15

Project 1: Family Tree Knowledge Base

What you’ll build: A comprehensive genealogical database representing family relationships. Define facts for individuals and their properties, then create rules to derive complex relationships like sibling, cousin, uncle, and ancestor.

Why it teaches the concept: This is the canonical first Prolog project because it perfectly demonstrates the declarative paradigm. You describe what relationships exist (facts) and what they mean (rules), then Prolog answers any question about the family tree without you writing search algorithms.

Core challenges you’ll face:

  • Defining atomic facts → maps to representing base knowledge: parent(homer, bart).
  • Writing conjunctive rules → maps to combining conditions: sibling requires shared parent
  • Recursive rules → maps to ancestor chains of arbitrary depth
  • Avoiding duplicate solutions → maps to understanding how backtracking explores

Key Concepts:

  • Facts and Rules: “Programming in Prolog” Ch. 1-2 (Clocksin & Mellish)
  • Unification: “The Art of Prolog” Ch. 3 (Sterling & Shapiro)
  • Recursion: “Learn Prolog Now!” Ch. 3 (Blackburn, Bos, Striegnitz)

Difficulty: Beginner Time estimate: 2-4 hours Prerequisites: None—this is your starting point

Real World Outcome

You will have a Prolog file that answers questions about family relationships:

% family.pl - Your knowledge base
male(abraham).
male(homer).
male(bart).
female(mona).
female(marge).
female(lisa).
female(maggie).

parent(abraham, homer).
parent(mona, homer).
parent(homer, bart).
parent(homer, lisa).
parent(homer, maggie).
parent(marge, bart).
parent(marge, lisa).
parent(marge, maggie).

% Session
?- consult('family.pl').
true.

?- parent(homer, X).
X = bart ;
X = lisa ;
X = maggie.

?- sibling(bart, lisa).
true.

?- sibling(bart, Who).
Who = lisa ;
Who = maggie.

?- ancestor(abraham, bart).
true.

?- ancestor(X, maggie).
X = homer ;
X = marge ;
X = abraham ;
X = mona.

The Core Question You’re Answering

How do I represent knowledge about the world and let the computer reason about it without explicitly programming the reasoning?

Concepts You Must Understand First

  1. What is a predicate in logic? (A statement that can be true or false)
  2. What does it mean for a variable to be “bound”? (It has a value)
  3. How does recursion terminate? (Base case stops the chain)

Questions to Guide Your Design

Data Representation:

  • How will you represent gender? male(person) or gender(person, male)?
  • Should marriage be represented? How?
  • What if someone has unknown parents?

Rule Design:

  • What makes someone a sibling vs. a half-sibling?
  • How do you prevent someone from being their own sibling?
  • What is the base case for ancestor?

Thinking Exercise

Before coding, trace by hand what happens with this query:

parent(X, bart), parent(X, lisa).
  1. What does Prolog try first for parent(X, bart)?
  2. Once X is bound, what happens with parent(X, lisa)?
  3. If that fails, what does Prolog do?

The Interview Questions They’ll Ask

  1. Explain unification in Prolog. How is it different from assignment?
  2. What is backtracking? When does it occur?
  3. Why does the order of clauses matter in Prolog?
  4. What would happen if you wrote sibling(X, X) in the body of your sibling rule?
  5. How would you find all cousins of a person?

Hints in Layers

Hint 1 - Starting Point: Begin with just parent/2 facts. The sibling rule needs two calls to parent with the same parent variable.

Hint 2 - Next Level:

sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.

The X \= Y prevents someone being their own sibling.

Hint 3 - Technical Details: For ancestor, you need two clauses:

  1. Base case: ancestor(X, Y) :- parent(X, Y).
  2. Recursive case: ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

Hint 4 - Verification: Use trace. before your query to see step-by-step execution. Use nodebug. to turn it off.

Books That Will Help

Topic Book Chapter
Basic syntax “Learn Prolog Now!” Ch. 1-2
First programs “Programming in Prolog” Ch. 1-2
Query execution “The Art of Prolog” Ch. 2

Common Pitfalls & Debugging

Problem Cause Fix
sibling(bart, bart) returns true Missing inequality check Add X \= Y
ancestor runs forever Clauses in wrong order Put base case first
Same answer multiple times Multiple paths to same conclusion Use setof/3 or add constraints
ERROR: Undefined procedure Forgot to consult file consult('file.pl').

Learning Milestones

  1. Basic: Your father/2 and mother/2 rules work correctly
  2. Intermediate: Your sibling/2 handles the inequality constraint
  3. Complete: Your ancestor/2 finds arbitrarily deep ancestors

Project 2: List Processing Library

What you’ll build: A comprehensive library of list predicates from scratch: member/2, append/3, reverse/2, length/2, nth/3, last/2, flatten/2, and more.

Why it teaches the concept: Lists are Prolog’s primary data structure, and the [Head|Tail] pattern is fundamental to recursive processing. Implementing these predicates yourself solidifies the core patterns you’ll use in every Prolog program.

Core challenges you’ll face:

  • Understanding list notation → maps to [H|T] destructuring
  • Accumulator patterns → maps to carrying results through recursion
  • Bidirectional predicates → maps to predicates that work in multiple modes
  • Difference lists → maps to efficient append operations

Key Concepts:

  • List Processing: “Learn Prolog Now!” Ch. 4-5
  • Recursion Patterns: “The Art of Prolog” Ch. 7
  • Accumulators: “Programming in Prolog” Ch. 3

Difficulty: Beginner Time estimate: 3-5 hours Prerequisites: Project 1

Real World Outcome

?- my_member(3, [1,2,3,4,5]).
true.

?- my_append([1,2], [3,4], X).
X = [1, 2, 3, 4].

?- my_append(X, Y, [1,2,3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3] ;
X = [1, 2],
Y = [3] ;
X = [1, 2, 3],
Y = [].

?- my_reverse([1,2,3], R).
R = [3, 2, 1].

?- my_length([a,b,c,d], L).
L = 4.

?- my_flatten([[1,2],[3,[4,5]],6], F).
F = [1, 2, 3, 4, 5, 6].

The Core Question You’re Answering

How do I process sequential data structures recursively without explicit loops?

Questions to Guide Your Design

  • What is the base case for an empty list?
  • How do you “peel off” the first element and recurse on the rest?
  • When do you need an accumulator?
  • Can your predicate work “backwards”? (generate lists that satisfy constraints)

The Interview Questions They’ll Ask

  1. Implement append/3 and explain how it can work in multiple modes.
  2. Why is naive reverse/2 O(n^2)? How do you make it O(n)?
  3. What is a difference list and when would you use one?
  4. Trace the execution of member(3, [1,2,3]).
  5. How would you implement permutation/2?

Hints in Layers

Hint 1: member has two clauses: one where X is the head, one where you recurse on the tail.

Hint 2: append([], L, L). is the base case. The recursive case prepends the head.

Hint 3: Naive reverse is reverse([], []). and reverse([H|T], R) :- reverse(T, RT), append(RT, [H], R). This is slow.

Hint 4: Efficient reverse uses an accumulator: reverse(L, R) :- reverse_acc(L, [], R). reverse_acc([], Acc, Acc). reverse_acc([H|T], Acc, R) :- reverse_acc(T, [H|Acc], R).

Learning Milestones

  1. Basic: member, append, length work correctly
  2. Intermediate: reverse with accumulator, nth element
  3. Complete: flatten for nested lists, predicates work bidirectionally

Project 3: Recursive Arithmetic

What you’ll build: Implement arithmetic operations (addition, multiplication, factorial, Fibonacci, GCD) using Peano arithmetic (representing numbers as zero, s(zero), s(s(zero)), etc.) and then using Prolog’s built-in arithmetic.

Why it teaches the concept: This project demonstrates how logic programming can express mathematical definitions directly. You’ll see how Prolog’s recursion naturally implements mathematical induction.

Core challenges you’ll face:

  • Peano number representation → maps to understanding structural recursion
  • The is operator → maps to evaluating arithmetic expressions
  • Termination conditions → maps to ensuring recursion ends
  • Efficiency concerns → maps to tail recursion and accumulators

Key Concepts:

  • Arithmetic in Prolog: “Programming in Prolog” Ch. 5
  • Recursion Patterns: “The Art of Prolog” Ch. 7
  • Termination: “The Craft of Prolog” Ch. 3

Difficulty: Beginner Time estimate: 3-4 hours Prerequisites: Project 2

Real World Outcome

% Peano arithmetic
?- peano_add(s(s(zero)), s(s(s(zero))), Sum).
Sum = s(s(s(s(s(zero))))).  % 2 + 3 = 5

% Built-in arithmetic
?- factorial(5, F).
F = 120.

?- fibonacci(10, F).
F = 55.

?- gcd(48, 18, G).
G = 6.

?- power(2, 10, P).
P = 1024.

?- sum_list([1,2,3,4,5], S).
S = 15.

The Interview Questions They’ll Ask

  1. What is Peano arithmetic and why is it useful for understanding recursion?
  2. Why does X is 3 + 4 work but 3 + 4 = 7 fails?
  3. Implement factorial with and without an accumulator. What’s the difference?
  4. How would you handle negative numbers in your predicates?

Hints in Layers

Hint 1: Peano addition: add(zero, N, N). and add(s(M), N, s(Sum)) :- add(M, N, Sum).

Hint 2: Built-in factorial: factorial(0, 1). factorial(N, F) :- N > 0, N1 is N - 1, factorial(N1, F1), F is N * F1.

Hint 3: Fibonacci with memoization uses assert to cache computed values.

Hint 4: GCD uses Euclid’s algorithm: gcd(A, 0, A) :- A > 0. gcd(A, B, G) :- B > 0, R is A mod B, gcd(B, R, G).

Learning Milestones

  1. Basic: Peano addition and multiplication work
  2. Intermediate: Factorial and Fibonacci with built-in arithmetic
  3. Complete: Tail-recursive versions with accumulators, memoized Fibonacci

Project 4: Logic Puzzle Solver (Zebra/Einstein Puzzle)

What you’ll build: A solver for the famous “Zebra Puzzle” (also known as Einstein’s Riddle). Given a set of constraints like “The Englishman lives in the red house” and “The green house is immediately to the right of the ivory house”, Prolog finds the unique solution.

Why it teaches the concept: This project showcases Prolog’s declarative power. In an imperative language, you’d write nested loops and backtracking logic. In Prolog, you state the constraints and let unification and backtracking solve it automatically.

Core challenges you’ll face:

  • Structuring the search space → maps to representing houses as a list of terms
  • Expressing constraints declaratively → maps to using unification and member/2
  • Positional relationships → maps to defining “next to” and “right of”
  • Performance optimization → maps to constraint ordering

Key Concepts:

  • Constraint Satisfaction: “The Art of Prolog” Ch. 14
  • Generate and Test: Classic Prolog pattern
  • Search Control: Constraint ordering affects performance

Difficulty: Intermediate Time estimate: 4-6 hours (weekend project) Prerequisites: Projects 1-2

Real World Outcome

?- solve(Houses), member(house(Who, _, _, _, zebra), Houses).
Houses = [house(norwegian, yellow, water, kools, fox),
          house(ukrainian, blue, tea, chesterfields, horse),
          house(englishman, red, milk, oldgolds, snails),
          house(spaniard, ivory, orange_juice, luckystrike, dog),
          house(japanese, green, coffee, parliaments, zebra)],
Who = japanese.

% The Japanese person owns the zebra!

The Core Question You’re Answering

How can I solve constraint satisfaction problems by simply stating the constraints rather than programming a search algorithm?

Questions to Guide Your Design

  • How will you represent a house? house(Nationality, Color, Drink, Smoke, Pet)?
  • How do you represent “the green house is immediately right of the ivory house”?
  • In what order should you apply constraints for best performance?
  • How do you express “the Norwegian lives next to the blue house”?

The Interview Questions They’ll Ask

  1. Explain how Prolog solves the zebra puzzle without explicit backtracking code.
  2. Why does the order of constraints matter for performance?
  3. How is this approach different from writing a recursive backtracking solver in Python?
  4. What is constraint propagation and how does it relate to this problem?

Hints in Layers

Hint 1: Represent the street as Houses = [_,_,_,_,_] (five variables).

Hint 2: Use member(house(englishman, red, _, _, _), Houses) to express “the Englishman lives in the red house”.

Hint 3: Define right_of(L, R, [L,R|_]). right_of(L, R, [_|T]) :- right_of(L, R, T). for positional constraints.

Hint 4: Place fixed constraints first (e.g., “the Norwegian lives in the first house” → Houses = [house(norwegian,_,_,_,_)|_]).

Learning Milestones

  1. Basic: Can express and solve a simplified 3-house puzzle
  2. Intermediate: Full 5-house puzzle solves correctly
  3. Complete: Understand why constraint ordering affects solving time

Project 5: Graph Algorithms Suite

What you’ll build: A comprehensive graph algorithms library: path finding, cycle detection, connected components, topological sort, shortest path (BFS/Dijkstra-style), and spanning trees.

Why it teaches the concept: Graphs are everywhere in computer science, and Prolog’s backtracking makes graph traversal natural. You’ll also confront the challenge of cycle detection—crucial because naive recursion on cyclic graphs loops forever.

Core challenges you’ll face:

  • Graph representation → maps to edge facts vs. adjacency lists
  • Cycle detection → maps to tracking visited nodes
  • Path construction → maps to accumulating the path during traversal
  • Multiple solutions → maps to using backtracking to find all paths

Key Concepts:

  • Graph Traversal: “The Art of Prolog” Ch. 16
  • Accumulators: “Programming in Prolog” Ch. 3
  • Termination: “The Craft of Prolog” Ch. 3

Difficulty: Intermediate Time estimate: 5-7 hours (weekend project) Prerequisites: Projects 1-3

Real World Outcome

% Graph definition
edge(a, b). edge(b, c). edge(c, d). edge(b, e). edge(e, d). edge(d, a).

?- path(a, d, Path).
Path = [a, b, c, d] ;
Path = [a, b, e, d] ;
false.

?- has_cycle([a,b,c,d,e]).
true.

?- connected_components(Components).
Components = [[a, b, c, d, e]].

?- shortest_path(a, d, Path, Length).
Path = [a, b, c, d],
Length = 3.

The Core Question You’re Answering

How do I traverse complex data structures with cycles without infinite loops, while still exploring all possibilities?

The Interview Questions They’ll Ask

  1. Implement path finding that handles cycles. Why is the visited list necessary?
  2. How would you find the shortest path in an unweighted graph using Prolog?
  3. Explain how Prolog’s backtracking relates to depth-first search.
  4. How would you detect if a graph is bipartite?

Hints in Layers

Hint 1: Simple path without cycle detection: path(A, B, [A,B]) :- edge(A, B). path(A, B, [A|P]) :- edge(A, C), path(C, B, P).

Hint 2: Add a visited list: path(A, B, Visited, Path) and check \+ member(C, Visited) before recursing.

Hint 3: For BFS, use a queue of [Node, PathToNode] pairs and expand level by level.

Hint 4: Topological sort: nodes with no incoming edges first, then remove and repeat.

Learning Milestones

  1. Basic: Path finding works on acyclic graphs
  2. Intermediate: Cycle detection prevents infinite loops
  3. Complete: BFS shortest path, topological sort, connected components

Project 6: Sudoku Solver with Constraints

What you’ll build: A Sudoku solver using Prolog’s constraint logic programming library (CLP(FD)). Express the rules of Sudoku declaratively, and let the constraint solver find the solution.

Why it teaches the concept: This project introduces constraint logic programming, where you declare constraints on variables and the system finds satisfying assignments. CLP(FD) is dramatically more efficient than generate-and-test for combinatorial problems.

Core challenges you’ll face:

  • CLP(FD) syntax → maps to domain declarations and constraint operators
  • Modeling the puzzle → maps to rows, columns, and 3x3 boxes
  • Propagation vs. search → maps to understanding when propagation suffices
  • Labeling strategies → maps to how to instantiate constrained variables

Key Concepts:

  • CLP(FD): SWI-Prolog CLP(FD) documentation
  • Constraint Propagation: How domains shrink before search
  • All-Different Constraints: all_different/1 predicate

Difficulty: Intermediate Time estimate: 4-6 hours Prerequisites: Project 4

Real World Outcome

?- sudoku([[5,3,_,_,7,_,_,_,_],
           [6,_,_,1,9,5,_,_,_],
           [_,9,8,_,_,_,_,6,_],
           [8,_,_,_,6,_,_,_,3],
           [4,_,_,8,_,3,_,_,1],
           [7,_,_,_,2,_,_,_,6],
           [_,6,_,_,_,_,2,8,_],
           [_,_,_,4,1,9,_,_,5],
           [_,_,_,_,8,_,_,7,9]], Solution).

Solution = [[5,3,4,6,7,8,9,1,2],
            [6,7,2,1,9,5,3,4,8],
            [1,9,8,3,4,2,5,6,7],
            [8,5,9,7,6,1,4,2,3],
            [4,2,6,8,5,3,7,9,1],
            [7,1,3,9,2,4,8,5,6],
            [9,6,1,5,3,7,2,8,4],
            [2,8,7,4,1,9,6,3,5],
            [3,4,5,2,8,6,1,7,9]].

The Core Question You’re Answering

How can constraint propagation dramatically reduce search space compared to brute-force generate-and-test?

The Interview Questions They’ll Ask

  1. What is constraint propagation and how does it reduce the search space?
  2. Explain the all_different/1 constraint.
  3. What is the role of labeling/2 in CLP(FD)?
  4. How would you solve a harder variant like Killer Sudoku?

Hints in Layers

Hint 1: Load CLP(FD) with :- use_module(library(clpfd)).

Hint 2: Declare domains: Vars ins 1..9 where Vars is a list of all 81 cells.

Hint 3: Use maplist(all_different, Rows) for row constraints, similarly for columns and boxes.

Hint 4: End with maplist(labeling([ff]), Rows) to trigger search with “first-fail” heuristic.

Learning Milestones

  1. Basic: Understand CLP(FD) basics, solve 4x4 Sudoku
  2. Intermediate: Full 9x9 Sudoku solver works
  3. Complete: Understand different labeling strategies and their performance

Project 7: N-Queens Problem

What you’ll build: Solve the classic N-Queens problem: place N queens on an NxN chessboard such that no two queens attack each other. Implement both a naive generate-and-test version and an efficient CLP(FD) version.

Why it teaches the concept: This problem is a benchmark for constraint satisfaction and showcases the difference between naive backtracking and smart constraint propagation. Comparing both approaches is illuminating.

Core challenges you’ll face:

  • Representing board positions → maps to choosing between coordinates or column indices
  • Diagonal constraints → maps to row+col and row-col differences
  • Scaling to large N → maps to understanding exponential vs. polynomial growth
  • Counting all solutions → maps to using findall/3 or aggregate_all/3

Key Concepts:

  • Constraint Satisfaction Problems: Classic AI topic
  • Symmetry Breaking: Reducing redundant solutions
  • Branching Heuristics: Which variable to assign next

Difficulty: Intermediate Time estimate: 3-5 hours Prerequisites: Project 6

Real World Outcome

?- queens(8, Qs).
Qs = [1, 5, 8, 6, 3, 7, 2, 4] ;  % One solution
Qs = [1, 6, 8, 3, 7, 4, 2, 5] ;
...

?- aggregate_all(count, queens(8, _), Count).
Count = 92.  % 8-queens has 92 solutions

?- time(queens(20, Qs)).
% CLP(FD) version: ~0.1 seconds
% Naive version: doesn't terminate in reasonable time

The Interview Questions They’ll Ask

  1. How do you express the diagonal constraint for N-Queens?
  2. Why is the CLP(FD) version so much faster than generate-and-test?
  3. How many solutions exist for N=8? How would you count them?
  4. How would you find a solution that is rotation/reflection unique?

Hints in Layers

Hint 1: Represent solution as a list where Qs[i] is the row of the queen in column i.

Hint 2: Diagonal constraint: for queens at (R1, C1) and (R2, C2), neither R1 - C1 =:= R2 - C2 nor R1 + C1 =:= R2 + C2.

Hint 3: In CLP(FD): Qs ins 1..N, all_different(Qs), safe_diagonals(Qs).

Hint 4: Use all_different on [R+C for each R,C] and [R-C for each R,C] for diagonal uniqueness.

Learning Milestones

  1. Basic: 4-Queens works with naive approach
  2. Intermediate: 8-Queens with CLP(FD) finds all 92 solutions quickly
  3. Complete: 20-Queens or higher solves in seconds

Project 8: Expert System Shell

What you’ll build: A rule-based expert system shell that can be loaded with domain knowledge and answer questions by chaining through rules. Include explanation facilities (“why did you conclude X?”) and user interaction.

Why it teaches the concept: Expert systems were Prolog’s killer app in the 1980s. Building one teaches you about knowledge representation, inference engines, and how Prolog’s built-in inference can be extended and explained.

Core challenges you’ll face:

  • Knowledge representation → maps to facts and rules for domain knowledge
  • Backward chaining → maps to goal-driven reasoning
  • Explanation generation → maps to tracking the proof tree
  • User interaction → maps to asking questions, handling unknown facts

Key Concepts:

  • Expert Systems: “Building Expert Systems in Prolog” by Dennis Merritt
  • Backward Chaining: Goal-driven inference
  • Meta-Interpreters: Programs that interpret Prolog programs

Difficulty: Advanced Time estimate: 8-12 hours Prerequisites: Projects 1-5

Real World Outcome

% Knowledge base for animal identification
rule(mammal, [has_hair]).
rule(mammal, [gives_milk]).
rule(carnivore, [mammal, eats_meat]).
rule(tiger, [carnivore, has_stripes, tawny_color]).

?- diagnose(tiger).
Does it have hair? yes.
Does it eat meat? yes.
Does it have stripes? yes.
Is it tawny colored? yes.
Conclusion: It is a tiger.

?- explain(tiger).
tiger because:
  carnivore because:
    mammal because: has_hair (user confirmed)
    eats_meat (user confirmed)
  has_stripes (user confirmed)
  tawny_color (user confirmed)

The Core Question You’re Answering

How can a system reason about a domain using encoded rules and explain its conclusions to users?

The Interview Questions They’ll Ask

  1. Explain backward chaining vs. forward chaining inference.
  2. How would you handle uncertainty (probabilities) in an expert system?
  3. What is the role of a meta-interpreter in this context?
  4. How do expert systems relate to modern machine learning?

Hints in Layers

Hint 1: Store rules as facts: rule(Conclusion, ListOfConditions).

Hint 2: The inference engine: prove(Goal) :- rule(Goal, Conditions), maplist(prove, Conditions). For base facts, ask the user or check known facts.

Hint 3: Track the proof path in an accumulator to enable explanations.

Hint 4: Use assert/1 to record user answers so they aren’t asked twice.

Learning Milestones

  1. Basic: Can prove goals from rules without user interaction
  2. Intermediate: Asks user for unknown facts
  3. Complete: Provides explanations of reasoning

Project 9: Natural Language Parser with DCGs

What you’ll build: A natural language parser using Definite Clause Grammars (DCGs). Parse simple English sentences, extract grammatical structure, and even generate parse trees.

Why it teaches the concept: DCGs are one of Prolog’s most elegant features—a notation for grammars that compiles directly into Prolog clauses. Natural language processing was a founding motivation for Prolog, and DCGs make it remarkably accessible.

Core challenges you’ll face:

  • DCG notation → maps to understanding --> vs. :-
  • Grammar hierarchy → maps to sentence → noun_phrase verb_phrase
  • Building parse trees → maps to adding arguments to DCG rules
  • Handling ambiguity → maps to multiple parses for ambiguous sentences

Key Concepts:

  • DCGs: “Learn Prolog Now!” Ch. 8
  • Parsing: “The Art of Prolog” Ch. 17
  • Difference Lists: Underlying mechanism of DCGs

Difficulty: Advanced Time estimate: 6-10 hours Prerequisites: Projects 1-3

Real World Outcome

?- sentence(Tree, [the, cat, sat, on, the, mat], []).
Tree = s(np(det(the), n(cat)),
         vp(v(sat),
            pp(prep(on), np(det(the), n(mat))))).

?- sentence(_, [the, sat, cat], []).
false.  % Grammatically incorrect

?- phrase(sentence(T), [every, student, likes, some, professor]).
T = s(np(det(every), n(student)),
      vp(v(likes), np(det(some), n(professor)))).

The Core Question You’re Answering

How can I express grammars declaratively and get a parser for free?

The Interview Questions They’ll Ask

  1. What are DCGs and how do they differ from BNF grammars?
  2. How does Prolog implement DCGs internally?
  3. How would you handle verb conjugation (walks vs. walk)?
  4. What is the role of the implicit difference list in DCGs?

Hints in Layers

Hint 1: Basic DCG structure:

sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun.
verb_phrase --> verb, noun_phrase.
determiner --> [the] | [a].
noun --> [cat] | [dog] | [mat].
verb --> [chases] | [sees] | [sat].

Hint 2: Adding parse trees: sentence(s(NP, VP)) --> noun_phrase(NP), verb_phrase(VP).

Hint 3: Use phrase/2 to invoke DCGs: phrase(sentence(T), [the, cat, sat]).

Hint 4: For prepositional phrases: verb_phrase(vp(V, PP)) --> verb(V), prep_phrase(PP).

Learning Milestones

  1. Basic: Parse simple subject-verb-object sentences
  2. Intermediate: Generate parse trees with correct structure
  3. Complete: Handle prepositional phrases, adjectives, ambiguity

Project 10: Simple Prolog Interpreter (Meta-Interpreter)

What you’ll build: A Prolog interpreter written in Prolog—a meta-interpreter. It will evaluate Prolog-like programs, giving you deep insight into how Prolog itself works.

Why it teaches the concept: Meta-interpreters are a powerful Prolog technique. They let you modify Prolog’s behavior—add tracing, implement alternative search strategies, or create domain-specific languages.

Core challenges you’ll face:

  • Representing programs as data → maps to Prolog’s homoiconic nature
  • Implementing unification → maps to the = predicate
  • Implementing proof search → maps to recursive goal reduction
  • Handling built-ins → maps to arithmetic, I/O, etc.

Key Concepts:

  • Meta-Interpreters: “The Art of Prolog” Ch. 17
  • Prolog Semantics: Understanding how Prolog executes
  • Reflection: Programs that manipulate programs

Difficulty: Advanced Time estimate: 8-12 hours Prerequisites: Projects 1-5, 9

Real World Outcome

% Your meta-interpreter
solve(true) :- !.
solve((A, B)) :- !, solve(A), solve(B).
solve(A) :- clause(A, B), solve(B).

% A sample program to interpret
edge(a, b).
edge(b, c).
path(X, X).
path(X, Y) :- edge(X, Z), path(Z, Y).

?- solve(path(a, c)).
true.

% Extended meta-interpreter with tracing
solve_trace(Goal) :-
    write('Trying: '), writeln(Goal),
    clause(Goal, Body),
    solve_trace(Body),
    write('Proved: '), writeln(Goal).

The Core Question You’re Answering

How does Prolog’s inference engine work internally, and how can I modify or extend it?

The Interview Questions They’ll Ask

  1. What is a meta-interpreter and why is it useful?
  2. How would you add tracing to a meta-interpreter?
  3. How would you implement depth-limited search?
  4. What is the difference between call/1 and a meta-interpreter?

Hints in Layers

Hint 1: The vanilla meta-interpreter is just 3 clauses: handle true, handle conjunctions, and reduce goals using clause/2.

Hint 2: clause(Head, Body) retrieves a clause from the database with the given head.

Hint 3: For tracing, add write/1 calls before and after recursive calls.

Hint 4: For depth-limiting, add a counter that decrements with each recursion and fails at 0.

Learning Milestones

  1. Basic: Vanilla meta-interpreter works for simple programs
  2. Intermediate: Add tracing capabilities
  3. Complete: Implement depth-limited or breadth-first search

Project 11: Scheduling and Resource Allocation

What you’ll build: A constraint-based scheduler for real-world problems: class scheduling (rooms, times, professors), job-shop scheduling, or meeting room allocation.

Why it teaches the concept: Scheduling is a classic constraint satisfaction problem with real-world applicability. You’ll use CLP(FD) and learn about modeling complex constraints: no conflicts, capacity limits, preferences, and optimization.

Core challenges you’ll face:

  • Resource constraints → maps to no two events in same room at same time
  • Temporal constraints → maps to duration, ordering, gaps
  • Capacity constraints → maps to room sizes, professor loads
  • Optimization → maps to minimizing gaps, maximizing preferences

Key Concepts:

  • Constraint Satisfaction: SWI-Prolog CLP(FD)
  • Scheduling Problems: Classic OR topic
  • Optimization: labeling/2 options for optimization

Difficulty: Advanced Time estimate: 10-15 hours Prerequisites: Projects 6-7

Real World Outcome

% Course scheduling
course(cs101, prof_smith, 2, large_room).  % 2 hours, needs large room
course(math201, prof_jones, 1, small_room).
course(phys101, prof_smith, 2, lab).

?- schedule(Timetable).
Timetable = [
  slot(cs101, monday, 9, room101),
  slot(math201, monday, 9, room102),  % Same time, different room - OK
  slot(phys101, tuesday, 10, lab1)    % Prof_smith teaches CS on Mon
].

% No conflicts detected

The Core Question You’re Answering

How can I model complex real-world constraints and let the solver find valid or optimal schedules?

The Interview Questions They’ll Ask

  1. How do you model “no two professors can be in different places at the same time”?
  2. How would you add soft constraints (preferences)?
  3. What is the difference between feasibility and optimization?
  4. How do real scheduling systems handle changes/disruptions?

Hints in Layers

Hint 1: Model time as integers (e.g., 9-17 for 9am-5pm), rooms as domain values.

Hint 2: Use serialized/2 for tasks that can’t overlap on a resource.

Hint 3: For “no conflict” constraints: all_different/1 on simultaneous slots for same resource.

Hint 4: Optimization: use labeling([min(Cost)], Vars) where Cost is computed from the schedule.

Learning Milestones

  1. Basic: Schedule non-conflicting meetings
  2. Intermediate: Handle multiple resources (rooms, people)
  3. Complete: Optimize for minimal gaps or other objectives

Project 12: Database Operations and Deductive Databases

What you’ll build: Implement relational database operations in Prolog: select, project, join, union, difference. Then extend with recursive queries (Datalog-style) that go beyond what SQL can express.

Why it teaches the concept: Prolog and relational databases share deep connections—both are based on first-order logic. This project reveals that connection and shows Prolog’s power for expressing recursive queries that would require complex SQL (or be impossible).

Core challenges you’ll face:

  • Representing relations → maps to facts as tuples
  • Set operations → maps to findall, setof, aggregate
  • Joins → maps to multiple goals sharing variables
  • Transitive closure → maps to recursive queries

Key Concepts:

  • Datalog: Prolog subset for databases
  • Relational Algebra: Select, project, join
  • Recursive Queries: Transitive closure, reachability

Difficulty: Intermediate Time estimate: 5-8 hours Prerequisites: Projects 1-3

Real World Outcome

% Database facts
employee(1, john, 50000, sales).
employee(2, jane, 60000, engineering).
employee(3, bob, 55000, sales).

department(sales, 100).
department(engineering, 200).

% Queries
?- select(employee(_, Name, Salary, _), Salary > 52000, Results).
Results = [(2, jane, 60000), (3, bob, 55000)].

?- project(employee, [name, dept], Results).
Results = [(john, sales), (jane, engineering), (bob, sales)].

?- join(employee, department, dept, Results).
Results = [row(1, john, 50000, sales, 100), ...].

% Recursive query: all reports of a manager
manages(1, 2).
manages(1, 3).
manages(2, 4).

?- all_reports(1, Reports).
Reports = [2, 3, 4].  % Transitive closure!

The Core Question You’re Answering

How does Prolog’s logic foundation relate to relational databases, and what can Prolog express that SQL cannot?

The Interview Questions They’ll Ask

  1. How would you express a SQL JOIN in Prolog?
  2. What recursive queries can Datalog express that standard SQL cannot?
  3. What is the “magic sets” optimization for recursive queries?
  4. How does negation-as-failure relate to NULL handling in SQL?

Hints in Layers

Hint 1: select(Relation, Condition, Results) :- findall(X, (call(Relation), Condition), Results).

Hint 2: A join is just multiple goals: employee(ID, Name, _, Dept), department(Dept, Budget).

Hint 3: Transitive closure: all_reports(M, Rs) :- findall(R, reports_to(M, R), Direct), ... then recurse.

Hint 4: Use setof/3 instead of findall/3 to eliminate duplicates.

Learning Milestones

  1. Basic: Implement select, project using findall
  2. Intermediate: Implement join, union, difference
  3. Complete: Transitive closure queries

Project 13: Text Adventure Game Engine

What you’ll build: A full-featured text adventure game engine (like Zork) with rooms, objects, inventory, NPCs, and a natural language command parser.

Why it teaches the concept: This integrates many Prolog concepts: knowledge representation (world state), DCGs (command parsing), dynamic predicates (state changes), and rule-based reasoning (game logic).

Core challenges you’ll face:

  • World representation → maps to facts for rooms, objects, connections
  • Mutable state → maps to dynamic predicates, assert/retract
  • Command parsing → maps to DCGs for natural language input
  • Game loop → maps to read-eval-print cycle

Key Concepts:

  • Dynamic Predicates: dynamic/1, assert/1, retract/1
  • State Management: Prolog’s approach to mutable state
  • DCGs for Commands: Parsing player input

Difficulty: Advanced Time estimate: 12-20 hours Prerequisites: Projects 1-3, 9

Real World Outcome

Welcome to Prolog Adventure!
You are in a dimly lit cave.
Exits: north, east.
You see: a rusty key, a torch.

> look at the torch
The torch is unlit but looks usable.

> take the torch
You pick up the torch.

> inventory
You are carrying: a torch.

> go north
You are in a narrow passage.
It's too dark to see anything.

> light the torch
The torch flares to life, illuminating the passage.
You can see a locked door to the west.

> unlock the door
You don't have a key.

> go south
You are in a dimly lit cave.
You see: a rusty key.

> take the key
You pick up the rusty key.

> go north then go west
You go north.
You unlock the door with the rusty key.
You enter the treasure room!

*** CONGRATULATIONS! You found the treasure! ***

The Core Question You’re Answering

How do I manage complex, changing state in a declarative language?

The Interview Questions They’ll Ask

  1. How do dynamic predicates break declarative purity? When is this acceptable?
  2. How would you implement save/load game functionality?
  3. How does your command parser handle ambiguity?
  4. What design patterns help manage game state cleanly?

Hints in Layers

Hint 1: Declare dynamic state: :- dynamic at/2, holding/1, lit/1.

Hint 2: Movement: go(Dir) :- at(player, Room), exit(Room, Dir, NewRoom), retract(at(player, Room)), assert(at(player, NewRoom)).

Hint 3: DCG for commands: command(take(X)) --> [take], object(X). command(go(D)) --> [go], direction(D).

Hint 4: Game loop: play :- describe_room, read_command(Cmd), execute(Cmd), (won -> writeln('You win!') ; play).

Learning Milestones

  1. Basic: Navigate between rooms, describe environment
  2. Intermediate: Take/drop objects, manage inventory
  3. Complete: Puzzles with conditions, NPC interactions, win/lose states

Project 14: Planning and Goal Achievement (STRIPS)

What you’ll build: A STRIPS-style planner that can find sequences of actions to achieve goals. Given an initial state, a goal state, and action definitions, find a plan.

Why it teaches the concept: Planning is a fundamental AI problem, and Prolog is exceptionally well-suited to it. You’ll implement forward or backward search through a state space defined by action preconditions and effects.

Core challenges you’ll face:

  • State representation → maps to lists of fluents (what’s true)
  • Action modeling → maps to preconditions, add effects, delete effects
  • Search strategies → maps to forward vs. backward chaining
  • Plan optimization → maps to minimizing plan length

Key Concepts:

  • Classical Planning: STRIPS, PDDL
  • State-Space Search: Forward and backward planning
  • Means-Ends Analysis: Reducing goal differences

Difficulty: Advanced Time estimate: 10-15 hours Prerequisites: Projects 5, 8

Real World Outcome

% Blocks world
action(pickup(X),
    [on(X, table), clear(X), handempty],      % Preconditions
    [holding(X)],                              % Add effects
    [on(X, table), handempty]).                % Delete effects

action(putdown(X),
    [holding(X)],
    [on(X, table), clear(X), handempty],
    [holding(X)]).

action(stack(X, Y),
    [holding(X), clear(Y)],
    [on(X, Y), clear(X), handempty],
    [holding(X), clear(Y)]).

% Initial: A on table, B on table, both clear, hand empty
% Goal: A on B

?- plan([on(a, table), on(b, table), clear(a), clear(b), handempty],
        [on(a, b)],
        Plan).
Plan = [pickup(a), stack(a, b)].

The Core Question You’re Answering

How can a system automatically find a sequence of actions to achieve a goal from a given starting state?

The Interview Questions They’ll Ask

  1. What is the frame problem in planning?
  2. How does backward chaining differ from forward chaining in planning?
  3. What is the relationship between Prolog’s backtracking and planning search?
  4. How would you handle actions with conditional effects?

Hints in Layers

Hint 1: Represent state as a list of ground facts: [on(a, table), clear(a), handempty].

Hint 2: Apply action: check preconditions are subset of state, add adds, remove deletes.

Hint 3: Backward planning: start from goal, find action that achieves part of it, regress.

Hint 4: Use iterative deepening to find shortest plan.

Learning Milestones

  1. Basic: Apply a single action to a state
  2. Intermediate: Find plans for simple blocks world problems
  3. Complete: Handle larger problems with plan optimization

Project 15: Type Inference Engine

What you’ll build: A Hindley-Milner type inference engine for a simple functional language. Given an expression, infer its most general type.

Why it teaches the concept: Type inference is essentially unification—exactly what Prolog does. This project shows how programming language implementation concepts map directly onto Prolog’s mechanisms.

Core challenges you’ll face:

  • Representing types → maps to terms like arrow(int, bool)
  • Type environments → maps to variable-to-type bindings
  • Unification for types → maps to most general unifier
  • Let-polymorphism → maps to generalizing types

Key Concepts:

  • Hindley-Milner Type System: Foundation of ML, Haskell
  • Unification: Core of type inference
  • Type Schemes: Generalization and instantiation

Difficulty: Advanced Time estimate: 10-15 hours Prerequisites: Projects 1-3, some PL theory

Real World Outcome

% Infer types of expressions
?- infer([], abs(x, var(x)), T).
T = arrow(A, A).  % Identity function: a -> a

?- infer([], abs(f, abs(x, app(var(f), var(x)))), T).
T = arrow(arrow(A, B), arrow(A, B)).  % Function application

?- infer([], abs(x, abs(y, app(app(var(add), var(x)), var(y)))), T).
% Assuming add : int -> int -> int in environment
T = arrow(int, arrow(int, int)).

?- infer([], app(var(not), const(5)), T).
% Type error: not expects bool, got int
false.

The Core Question You’re Answering

How can types be automatically determined from code structure without explicit annotations?

The Interview Questions They’ll Ask

  1. What is the occurs check and why is it important in type inference?
  2. Explain let-polymorphism and why it’s useful.
  3. How does Prolog’s unification relate to type unification?
  4. What types of errors can type inference catch?

Hints in Layers

Hint 1: Represent types as Prolog terms: int, bool, arrow(T1, T2), type variables as Prolog variables.

Hint 2: Type rules map to Prolog clauses: infer(Env, const(N), int) :- integer(N).

Hint 3: For application: infer(Env, app(F, X), T) :- infer(Env, F, arrow(T1, T)), infer(Env, X, T1).

Hint 4: Use copy_term/2 for polymorphism when looking up let-bound variables.

Learning Milestones

  1. Basic: Infer types for constants and variables
  2. Intermediate: Handle lambdas and application
  3. Complete: Implement let-polymorphism, detect type errors

Project 16: Constraint Logic Programming for Math Word Problems

What you’ll build: A system that solves math word problems by translating English descriptions into constraints. “John has 3 more apples than Mary. Together they have 15 apples. How many does Mary have?”

Why it teaches the concept: This combines DCGs (parsing), constraint satisfaction (solving), and knowledge representation (understanding the domain). It’s a miniature AI system.

Core challenges you’ll face:

  • Parsing natural language → maps to DCGs for structured extraction
  • Building constraint models → maps to translating phrases to CLP(FD)
  • Solving and presenting → maps to labeling and output formatting
  • Handling variety → maps to multiple phrasings of same concept

Key Concepts:

  • Semantic Parsing: Extracting meaning from text
  • Constraint Modeling: Translating problems to constraints
  • Domain-Specific Languages: Problem representation

Difficulty: Advanced Time estimate: 12-18 hours Prerequisites: Projects 6, 9

Real World Outcome

?- solve_word_problem("John has 3 more apples than Mary. Together they have 15 apples.", Answer).
Parsing...
Constraints: [john = mary + 3, john + mary = 15]
Solving...
Answer = [mary = 6, john = 9].

?- solve_word_problem("A rectangle has perimeter 20. Its length is twice its width.", Answer).
Answer = [width = 10/3, length = 20/3].

The Core Question You’re Answering

How can natural language be parsed into formal constraints that a solver can process?

The Interview Questions They’ll Ask

  1. How do you handle ambiguity in natural language (“he” could refer to different entities)?
  2. What aspects of word problems are hardest to parse?
  3. How would you extend this to handle more complex problems?
  4. Compare this rule-based approach to modern neural approaches.

Hints in Layers

Hint 1: Start with a fixed grammar for simple problems: sentence --> entity, [has], quantity, [more], item, [than], entity.

Hint 2: Build a constraint representation as you parse: parse_sentence(Constraint, S, []).

Hint 3: Translate constraints to CLP(FD) and solve.

Hint 4: Use a symbol table to track entities and their associated variables.

Learning Milestones

  1. Basic: Parse and solve simple “A + B = C” type problems
  2. Intermediate: Handle “more than”, “less than”, “twice as many”
  3. Complete: Multi-sentence problems with entity tracking

Project 17: Interfacing Prolog with Python

What you’ll build: A bridge between Prolog and Python using PySWIP or similar library. Call Prolog from Python for logic tasks, and call Python from Prolog for numeric/ML tasks.

Why it teaches the concept: Real-world systems often need to combine Prolog’s logic capabilities with other languages’ strengths. Learning interop makes Prolog practical for production use.

Core challenges you’ll face:

  • Data marshaling → maps to converting between Python and Prolog types
  • Query interface → maps to calling Prolog goals from Python
  • Handling backtracking → maps to iterating over solutions
  • Error handling → maps to Prolog failures vs. Python exceptions

Key Concepts:

  • Foreign Language Interface: SWI-Prolog’s FFI
  • Interprocess Communication: Alternative approaches
  • Multi-paradigm Programming: Best of both worlds

Difficulty: Intermediate Time estimate: 4-6 hours Prerequisites: Python experience, Projects 1-3

Real World Outcome

# Python code
from pyswip import Prolog

prolog = Prolog()
prolog.consult("family.pl")

# Query Prolog from Python
for result in prolog.query("ancestor(X, bart)"):
    print(f"{result['X']} is an ancestor of Bart")

# Use Prolog for logic, Python for data processing
def find_relatives(person):
    relatives = list(prolog.query(f"sibling({person}, S)"))
    return [r['S'] for r in relatives]

print(find_relatives('bart'))  # ['lisa', 'maggie']

% Prolog code calling Python
:- use_module(library(pce)).  % Or janus for Python interop

analyze_data(Data, Result) :-
    py_call(numpy:mean(Data), Result).

The Core Question You’re Answering

How can I use Prolog’s logic programming strengths as part of a larger, multi-language system?

The Interview Questions They’ll Ask

  1. When would you use Prolog embedded in another application vs. standalone?
  2. How do you handle Prolog’s backtracking in a language without it?
  3. What are the performance implications of cross-language calls?
  4. Compare embedded Prolog to reimplementing the logic in Python.

Hints in Layers

Hint 1: Install pyswip: pip install pyswip

Hint 2: Prolog.consult("file.pl") loads a Prolog file.

Hint 3: prolog.query("goal(X)") returns an iterator of solution dicts.

Hint 4: For complex data, consider JSON serialization between languages.

Learning Milestones

  1. Basic: Call simple Prolog queries from Python
  2. Intermediate: Pass data structures bidirectionally
  3. Complete: Build a hybrid application using both languages’ strengths

Project 18: Modern SWI-Prolog Features

What you’ll build: A showcase project using SWI-Prolog’s modern features: tabling (memoization), engines (coroutines), dicts, HTTP server, and web applications.

Why it teaches the concept: Modern Prolog implementations have features far beyond classic textbook Prolog. Knowing these makes Prolog practical for real applications.

Core challenges you’ll face:

  • Tabling for performance → maps to automatic memoization
  • Dicts for structured data → maps to key-value syntax
  • HTTP services → maps to building web APIs
  • Concurrency → maps to engines and multi-threading

Key Concepts:

  • Tabling: Automatic memoization for recursive predicates
  • Dicts: Modern key-value data structures
  • HTTP Libraries: Building web services in Prolog

Difficulty: Intermediate Time estimate: 6-10 hours Prerequisites: Projects 1-5, basic web knowledge

Real World Outcome

% Tabled Fibonacci - automatically memoized
:- table fib/2.
fib(0, 0).
fib(1, 1).
fib(N, F) :- N > 1, N1 is N-1, N2 is N-2, fib(N1, F1), fib(N2, F2), F is F1 + F2.

?- time(fib(50, F)).
% Instant! Without tabling, this would take forever.
F = 12586269025.

% Dicts for clean data
person{name: "John", age: 30, city: "NYC"}.

?- P = person{name: N, age: A}, N = "John".
P = person{age:A, city:_, name:"John"}.

% HTTP Server
:- use_module(library(http/http_server)).
:- use_module(library(http/http_json)).

:- http_handler(root(api/hello), handle_hello, []).

handle_hello(Request) :-
    http_parameters(Request, [name(Name, [default("World")])]),
    reply_json_dict(_{message: "Hello", name: Name}).

% Start server on port 8080
?- http_server(http_dispatch, [port(8080)]).
% Visit http://localhost:8080/api/hello?name=Prolog

The Core Question You’re Answering

What modern features make Prolog practical for real-world applications?

The Interview Questions They’ll Ask

  1. What is tabling and when would you use it?
  2. How do SWI-Prolog dicts compare to association lists?
  3. What are the advantages of Prolog for web services?
  4. How does Prolog handle concurrency?

Hints in Layers

Hint 1: Add :- table predicate/arity. before any recursive predicate that would benefit from memoization.

Hint 2: Dict syntax: D = point{x: 3, y: 4}, X = D.x.

Hint 3: The http_server library provides a complete web framework.

Hint 4: Engines provide coroutine-like behavior for lazy evaluation.

Learning Milestones

  1. Basic: Use tabling to speed up recursive predicates
  2. Intermediate: Build a simple REST API
  3. Complete: Create a web app with database backend

Project Comparison Table

# Project Difficulty Time Key Concepts Engagement
1 Family Tree Beginner 2-4h Facts, Rules, Queries Medium
2 List Library Beginner 3-5h Recursion, Lists Medium
3 Recursive Arithmetic Beginner 3-4h Arithmetic, Accumulators Medium
4 Zebra Puzzle Intermediate 4-6h Constraint Satisfaction High
5 Graph Algorithms Intermediate 5-7h Traversal, Cycles High
6 Sudoku Solver Intermediate 4-6h CLP(FD), Propagation High
7 N-Queens Intermediate 3-5h CLP(FD), Optimization Medium
8 Expert System Advanced 8-12h Inference, Explanation High
9 NLP Parser Advanced 6-10h DCGs, Parse Trees Very High
10 Meta-Interpreter Advanced 8-12h Reflection, Semantics Very High
11 Scheduler Advanced 10-15h CLP(FD), Optimization High
12 Deductive DB Intermediate 5-8h Datalog, Recursion Medium
13 Text Adventure Advanced 12-20h State, DCGs, Integration Very High
14 STRIPS Planner Advanced 10-15h Planning, Search High
15 Type Inference Advanced 10-15h Unification, Types Very High
16 Word Problems Advanced 12-18h DCGs, CLP, NLP Very High
17 Python Interop Intermediate 4-6h FFI, Integration Medium
18 Modern Features Intermediate 6-10h Tabling, HTTP, Dicts High

Summary

Project Learning Path Expected Outcome
1. Family Tree All paths start here Understand facts, rules, queries
2. List Library Core skill Master list recursion patterns
3. Recursive Arithmetic Core skill Understand Prolog arithmetic
4. Zebra Puzzle Constraint path See power of declarative constraints
5. Graph Algorithms Core skill Handle cycles, build accumulators
6. Sudoku Solver Constraint path Master CLP(FD) basics
7. N-Queens Constraint path Compare naive vs. CLP approaches
8. Expert System AI path Build inference engine
9. NLP Parser AI/NLP path Master DCGs
10. Meta-Interpreter Advanced Understand Prolog internals
11. Scheduler Constraint path Real-world CLP application
12. Deductive DB Core skill Connect Prolog to databases
13. Text Adventure Integration Combine all skills
14. STRIPS Planner AI path Classical AI planning
15. Type Inference PL theory See unification in compilers
16. Word Problems AI/NLP path NLP + constraints
17. Python Interop Practical Use Prolog in larger systems
18. Modern Features Practical Production Prolog

Essential Reading

Book Authors Best For
Programming in Prolog (5th ed.) Clocksin & Mellish Beginners, reference
The Art of Prolog (2nd ed.) Sterling & Shapiro Deep understanding
Learn Prolog Now! Blackburn, Bos, Striegnitz Free online, practical
The Craft of Prolog Richard O’Keefe Efficiency, idioms

Specialized Topics

Topic Book
NLP “Prolog and Natural-Language Analysis” by Pereira & Shieber
AI “Prolog Programming for AI” by Ivan Bratko
Expert Systems “Building Expert Systems in Prolog” by Dennis Merritt
Constraint Programming SWI-Prolog CLP documentation

The Logic Programming Mindset

After completing these projects, you will have internalized a fundamentally different way of thinking about computation:

From Imperative to Declarative

Before: “First do this, then do that, check if X, loop until Y…” After: “These relationships exist. What satisfies these constraints?”

From Algorithms to Specifications

Before: “Implement breadth-first search with a queue…” After: “A path exists if there’s an edge, or if there’s an intermediate node with a path.”

From State to Relations

Before: “Update the user object, save to database…” After: “User has property X. Property changed. Query for current properties.”

The Ultimate Test

You know you’ve internalized logic programming when you find yourself:

  1. Describing problems in terms of what’s true rather than what to do
  2. Thinking about programs as specifications that happen to be executable
  3. Reaching for Prolog (or a Prolog-inspired approach) when facing:
    • Complex constraint satisfaction
    • Symbolic manipulation
    • Knowledge representation and reasoning
    • Natural language parsing
    • Configuration and rule systems

Now go build something declarative.