LEARN PROLOG DEEP DIVE

Learn Prolog: From Zero to Logic Programming Master

Goal: Deeply understand the logic programming paradigm by mastering Prolog. Shift your thinking from “how to do” (imperative) to “what is true” (declarative), and learn to solve complex problems in areas like AI, constraint solving, and natural language processing with surprisingly elegant code.

Why Learn Prolog?

Prolog (Programming in Logic) is not just another programming language; it’s a different way of thinking about problems. While languages like Python or Java require you to write a step-by-step algorithm, Prolog asks you to describe the world through facts and rules. You define what you know and what you want to find, and Prolog’s powerful “inference engine” does the work of finding the solution.

This paradigm shift is mind-expanding. Learning Prolog will make you a better programmer in any language by teaching you to think about problems from a higher, more abstract level.

After completing these projects, you will:

Think declaratively, describing problems instead of procedures.
Harness the power of unification and backtracking to explore complex solution spaces automatically.
Solve logic puzzles and constraint-satisfaction problems with elegant code.
Build simple expert systems and artificial intelligence applications.
Understand how parsers and compilers can be built using logic rules.

Core Concept Analysis

The Prolog Mindset: Declarative vs. Imperative

In an imperative language, you are the chef, giving the kitchen staff (the computer) a detailed, step-by-step recipe. In Prolog, you are the detective, providing clues (facts) and deduction methods (rules), then asking who the culprit is (a query). Prolog finds the answer.

┌──────────────────────────────────────┐  ┌─────────────────────────────────────┐
│    IMPERATIVE (e.g., Python)         │  │     DECLARATIVE (Prolog)            │
│                                      │  │                                     │
│  def find_grandfather(person):       │  │  father(homer, bart).               │
│      p = find_father(person)         │  │  father(abe, homer).                │
│      return find_father(p)           │  │                                     │
│                                      │  │  grandfather(G, C) :-               │
│  You write the SEARCH ALGORITHM.     │  │      father(G, P),                  │
│                                      │  │      father(P, C).                  │
│                                      │  │                                     │
│                                      │  │  You describe the RELATIONSHIP.    │
└──────────────────────────────────────┘  └─────────────────────────────────────┘

Fundamental Concepts

Facts: Unconditionally true statements about the world. They are the foundation of your knowledge base. In Prolog, they end with a period. human(socrates). parent(homer, bart).
Rules: Statements that are true if certain conditions are met. The :- symbol means “is true if”. A comma , means “and”. mortal(X) :- human(X). (X is mortal if X is human). sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y. (X is a sibling of Y if they share a parent P and are not the same person).
Queries: Questions you ask the Prolog system. Prolog tries to prove your query is true based on its facts and rules. ?- mortal(socrates). -> true. ?- parent(homer, Who). -> Who = bart.
Unification: The heart of Prolog. It’s a powerful form of pattern matching, not just variable assignment. capital(france, X) can be unified with capital(Y, paris) to make Y = france and X = paris.
Backtracking: Prolog’s built-in search mechanism. When one path in a rule fails, Prolog automatically goes back to the previous choice and tries a different option. This allows it to explore all possible solutions without you writing any loops or recursion control.
Atoms and Variables:
- homer, socrates, red: these are atoms (constants). They start with a lowercase letter.
- X, Who, Parent: these are variables. They start with an uppercase letter or an underscore.
Lists and Recursion: The primary data structure is the list. Recursion, especially with the [Head|Tail] list syntax, is the primary way to iterate and process data.

Project List

These projects are designed to build your Prolog intuition, starting with simple knowledge bases and progressing to classic AI and computer science problems where Prolog shines.

Project 1: A Genealogical Database

File: LEARN_PROLOG_DEEP_DIVE.md
Main Programming Language: Prolog
Alternative Programming Languages: (N/A, this is about learning the Prolog way)
Coolness Level: Level 2: Practical but Forgettable
Business Potential: 1. The “Resume Gold”
Difficulty: Level 1: Beginner
Knowledge Area: Logic Programming / Knowledge Representation
Software or Tool: SWI-Prolog (or any other Prolog interpreter)
Main Book: “Programming in Prolog” by W.F. Clocksin and C.S. Mellish

What you’ll build: A simple database of facts representing a family tree (e.g., The Simpsons, your own family). You will then write rules to query complex relationships like sibling, uncle, aunt, or ancestor.

Why it teaches Prolog: This is the canonical “first steps” project. It forces you to internalize the core concepts of facts, rules, and queries. You’ll immediately see how a few simple rules can answer questions you never explicitly programmed.

Core challenges you’ll face:

Defining facts → maps to representing your base knowledge (e.g., parent(homer, bart).)
Writing simple rules → maps to defining new concepts from old ones (e.g., father(X,Y) :- parent(X,Y), male(X).)
Writing recursive rules → maps to defining concepts of arbitrary depth (e.g., ancestor)
Formulating queries with variables → maps to asking Prolog to find answers for you

Key Concepts:

Facts and Rules: “Programming in Prolog”, Chapter 2 - Clocksin & Mellish
Unification and Queries: “The Art of Prolog”, Chapter 3 - Sterling & Shapiro
Recursion: “Learn Prolog Now!”, Chapter 3 - Blackburn, Bos, & Striegnitz

Difficulty: Beginner Time estimate: 1-2 hours Prerequisites: None. This is the starting point.

Real world outcome: You’ll load your Prolog file and ask it complex questions about your family tree. Prolog will feel like a magical oracle.

% Your knowledge base (family_tree.pl)
male(homer).
male(bart).
female(marge).
female(lisa).
parent(homer, bart).
parent(homer, lisa).
parent(marge, bart).
parent(marge, lisa).

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

% Your queries in the SWI-Prolog console
?- consult('family_tree.pl').
true.

?- parent(homer, Who).
Who = bart ;  % You press ';' to ask for more solutions
Who = lisa.

?- sibling(bart, lisa).
true.

?- sibling(bart, X).
X = lisa.

Implementation Hints:

Start with a small set of individuals.
Define base facts: male/1, female/1, parent/2. The /1 and /2 denote the “arity” (number of arguments).
Build rules on top of these facts. A father is a parent who is male.
For the ancestor/2 rule, think recursively: A is an ancestor of B if A is a parent of B. OR, A is an ancestor of B if A is a parent of some person P, and P is an ancestor of B.
Use \= for “not equal to”.

Learning milestones:

Your father and mother rules work → You understand combining simple facts.
Your sibling rule works → You can express more complex, multi-part conditions.
Your ancestor rule works → You’ve mastered recursion, the key to powerful Prolog programs.

Project 2: Logic Puzzle Solver

File: LEARN_PROLOG_DEEP_DIVE.md
Main Programming Language: Prolog
Alternative Programming Languages: Python with constraint libraries
Coolness Level: Level 4: Hardcore Tech Flex
Business Potential: 1. The “Resume Gold”
Difficulty: Level 2: Intermediate
Knowledge Area: Constraint Logic Programming / AI
Software or Tool: SWI-Prolog with CLP(FD) library
Main Book: “The Art of Prolog” by Leon Sterling and Ehud Shapiro

What you’ll build: A program that solves a classic logic puzzle, like the “Zebra Puzzle” (Einstein’s Puzzle). You will describe the constraints of the puzzle as Prolog rules, and Prolog will find the single correct solution.

Why it teaches Prolog: This project perfectly showcases Prolog’s declarative power. In an imperative language, you’d write a monstrous, nested loop structure to brute-force the solution. In Prolog, you simply state the rules of the puzzle, and the backtracking engine does the brute-force search for you, but in a smart, guided way.

Core challenges you’ll face:

Structuring the data → maps to representing the houses, nationalities, pets, etc. as a list of terms
Expressing constraints → maps to writing rules like “the Englishman lives in the red house”
Using the member/2 predicate → maps to checking for existence within a list of possibilities
Combining all constraints into a single query → maps to letting Prolog’s unification and backtracking do the heavy lifting

Key Concepts:

Constraint Logic Programming: The Puzzler, A Puzzle Solver in Prolog - by Markus Triska
List Manipulation: “Learn Prolog Now!”, Chapter 4
Unification of Structures: “Programming in Prolog”, Chapter 3

Difficulty: Intermediate Time estimate: Weekend Prerequisites: Project 1, understanding of lists.

Real world outcome: You will write a single query, ?- solve(Houses), ..., and Prolog will instantly print the fully specified solution, including who owns the zebra.

% A simplified version of the logic
% There are five houses.
% The Englishman lives in the red house.

% Your data structure might look like:
% Houses = [house(Nationality, Color, Pet), ...]

solve(Houses) :-
    length(Houses, 5),                                       % There are 5 houses
    member(house(englishman, red, _), Houses),               % The Englishman is in the red house
    member(house(spaniard, _, dog), Houses),                 % The Spaniard owns the dog
    member(house(_, green, _), Houses),                      % Someone lives in the green house
    % ... more constraints
    % Finally, the question:
    member(house(Who, _, zebra), Houses),                    % Who owns the zebra?
    member(house(WhoDrinksWater, _, _), Houses).             % Who drinks water?

% Your query
?- solve(Houses).
Houses = [house(norwegian, yellow, cat), house(dane, blue, horse), ...],
Who = japanese,
WhoDrinksWater = norwegian.

Implementation Hints:

Represent the set of houses as a list of 5 house(...) terms.
Use variables for the unknown properties, e.g., house(Nationality, Color, Pet, Drink, Smoke).
The member(Element, List) predicate is your best friend. member(house(englishman, red, _), Houses) succeeds if a term matching that pattern exists anywhere in the Houses list.
For positional clues like “the green house is immediately to the right of the ivory house,” you’ll need more advanced list manipulation, perhaps by defining a right_of(A, B, List) predicate.
Start with a simpler version of the puzzle (3 houses, 3 attributes) to get the structure right before moving to the full 5x5 version.

Learning milestones:

You can represent a single constraint, like “the Englishman lives in the red house” → You understand how member/2 and unification work.
You can combine multiple constraints → You see how Prolog narrows down the possibilities.
Your program solves the entire puzzle with a single query → You have fully grasped the power of declarative constraint solving.

Project 3: Graph Pathfinding

File: LEARN_PROLOG_DEEP_DIVE.md
Main Programming Language: Prolog
Alternative Programming Languages: Python, Java
Coolness Level: Level 3: Genuinely Clever
Business Potential: 1. The “Resume Gold”
Difficulty: Level 2: Intermediate
Knowledge Area: Graph Theory / Algorithms
Software or Tool: SWI-Prolog
Main Book: “Prolog Programming for Artificial Intelligence” by Ivan Bratko

What you’ll build: A program that can find a path between two nodes in a graph. You’ll represent a directed or undirected graph (like a city map or subway system) using facts and then write a rule to discover a path.

Why it teaches Prolog: This project is a masterclass in Prolog’s elegant handling of recursion and its relationship to graph traversal algorithms like Depth-First Search (DFS). Prolog’s backtracking engine is a DFS engine. You’ll also confront the classic problem of avoiding cycles.

Core challenges you’ll face:

Representing a graph with facts → maps to e.g., edge(a, b). edge(b, c).
Writing a recursive path-finding rule → maps to a path exists if there’s a direct edge, OR a path to an intermediate node
Avoiding infinite loops in cyclic graphs → maps to keeping track of visited nodes to not revisit them
Returning the path itself → maps to using an accumulator to build up the list of nodes in the path

Key Concepts:

Graph Traversal: “The Art of Prolog”, Chapter 16
Accumulators: A common Prolog pattern for collecting results during recursion.
Cycle Detection: Tracking visited nodes in an extra argument.

Difficulty: Intermediate Time estimate: Weekend Prerequisites: Project 1, understanding of recursion.

Real world outcome: You’ll be able to ask your program for a path between any two points and have it return the list of nodes that form the path.

% Knowledge base for a simple graph
edge(a, b).
edge(b, c).
edge(c, d).
edge(b, e).
edge(e, d).

% Your path-finding rule
path(Start, End, [Start,End]) :- edge(Start, End).
path(Start, End, [Start|Rest]) :- edge(Start, Next), path(Next, End, Rest).

% Query
?- path(a, d, Path).
Path = [a, b, c, d] ; % Backtracking finds another path!
Path = [a, b, e, d] ;
false.

(Note: The simple rule above has a bug! It will get stuck in infinite loops on graphs with cycles. The project is to fix this.)

Implementation Hints:

Your initial path(A, B) rule will be simple, but it will fail on cyclic graphs. For example, if you add edge(b, a). to the facts above, your query will never terminate.
The solution is to add a third argument to track visited nodes: path(Start, End, Visited, Path).
The base case is when there’s an edge from Start to End.
The recursive case is: find an edge from Start to some Next node, check that Next is not in the Visited list, and then recursively call path from Next to End, adding Start to the Visited list.
Use the not(member(X, List)) pattern to check for visited nodes.

Learning milestones:

Your simple path/2 rule works on an acyclic graph → You understand basic recursion for traversal.
You add cycle detection using a Visited list → You’ve solved a classic graph algorithm problem the “Prolog way.”
Your program can return not just true but the actual path taken → You understand how to use accumulators to build results during recursion.

Project 4: Symbolic Mathematics

File: LEARN_PROLOG_DEEP_DIVE.md
Main Programming Language: Prolog
Alternative Programming Languages: Lisp, Haskell
Coolness Level: Level 4: Hardcore Tech Flex
Business Potential: 1. The “Resume Gold”
Difficulty: Level 3: Advanced
Knowledge Area: Symbolic Computation / Compilers
Software or Tool: SWI-Prolog
Main Book: “Structure and Interpretation of Computer Programs” (for concepts)

What you’ll build: A program that can perform symbolic differentiation of mathematical expressions. You won’t be calculating numeric results; you’ll be applying the rules of calculus to transform one expression into another.

Why it teaches Prolog: This is a quintessential Prolog problem. It’s about manipulating symbols and structures according to a set of rules, which is trivial in Prolog but incredibly cumbersome in most other languages. It showcases Prolog’s strength in “meta-programming” (programs that manipulate other programs or data structures).

Core challenges you’ll face:

Representing expressions as Prolog terms → maps to x^2 becomes pow(x, 2), 2*x becomes 2 * x
Defining rules for differentiation → maps to the product rule, sum rule, power rule, etc.
Handling base cases → maps to the derivative of a constant is 0; the derivative of x with respect to x is 1
Simplifying the resulting expression → maps to writing rules like 1 * X simplifies to X, and X + 0 simplifies to X

Key Concepts:

Symbolic Manipulation: A core strength of Lisp and Prolog families.
Recursive Structure Decomposition: Applying rules recursively to parts of a structure.
Operator Overloading/Definitions: Using op/3 to make expressions look more natural.

Difficulty: Advanced Time estimate: Weekend Prerequisites: Project 1, basic knowledge of calculus rules.

Real world outcome: You’ll be able to ask Prolog for the derivative of a complex expression and get a correct, simplified result.

% Your program would contain rules like:

% d(Expression, Var, Derivative)
d(C, _, 0) :- number(C).      % derivative of a constant is 0
d(X, X, 1).                    % d/dx(x) = 1
d(X, Y, 0) :- X \= Y.           % d/dy(x) = 0

% Sum rule: d(U+V) = dU + dV
d(U+V, X, DU+DV) :- d(U, X, DU), d(V, X, DV).

% Product rule: d(U*V) = U*dV + V*dU
d(U*V, X, U*DV + V*DU) :- d(U, X, DU), d(V, X, DV).

% Power rule: d(x^n) = n*x^(n-1)
d(Var^N, Var, N*Var^N1) :- integer(N), N1 is N - 1.

% Query
?- d(2*x^3 + 5, x, Result).
Result = 2*(3*x^2) + 6*x*0 + 0.  % Unsimplified result

% After adding simplification rules...
?- d(2*x^3, x, Result), simplify(Result, Simplified).
Simplified = 6*x^2.

Implementation Hints:

Focus on getting the differentiation rules correct first. The output will be messy and unsimplified, which is fine.
Expressions like 2*x are just syntactic sugar for a term like *(2, x). You can use the display/1 predicate to see the “true” structure of a term.
The simplification part is a separate, fun challenge. You’ll write a simplify/2 predicate that recursively applies rules like simplify(X+0, X)., simplify(1*X, X)., etc.
You can use Prolog’s op/3 predicate to define your own operators, but it’s easier to start with the standard +, -, *, /.

Learning milestones:

Your program can differentiate constants and single variables → You’ve got the base cases right.
The sum rule and product rule work correctly → You understand how to recursively apply rules to compound expressions.
You can differentiate a simple polynomial → You’ve combined multiple rules successfully.
You implement a basic expression simplifier → You’re now thinking about programs that transform code, a powerful concept.

Project 5: A Natural Language Parser with DCGs

File: LEARN_PROLOG_DEEP_DIVE.md
Main Programming Language: Prolog
Alternative Programming Languages: Python with NLTK
Coolness Level: Level 5: Pure Magic (Super Cool)
Business Potential: 1. The “Resume Gold”
Difficulty: Level 3: Advanced
Knowledge Area: Natural Language Processing / Parsing
Software or Tool: SWI-Prolog
Main Book: “Prolog and Natural-Language Analysis” by Fernando C. N. Pereira and Stuart M. Shieber

What you’ll build: A parser that can take a simple English sentence (as a list of words) and determine if it’s grammatically valid. As a bonus, you’ll make it produce a parse tree representing the sentence’s structure.

Why it teaches Prolog: Definite Clause Grammars (DCGs) are a killer feature of Prolog. They provide a clean, declarative syntax for writing grammars that Prolog translates into efficient parsing code for you. It feels like you’re just writing down grammar rules, and you get a parser for free.

Core challenges you’ll face:

Learning DCG syntax (-->) → maps to a “syntactic sugar” for writing parsers
Defining a simple grammar → maps to e.g., a sentence is a noun phrase followed by a verb phrase
Building a lexicon → maps to defining which words are nouns, verbs, etc.
Extracting a parse tree → maps to adding arguments to your DCG rules to build up a structure as you parse

Key Concepts:

Definite Clause Grammars (DCGs): “Learn Prolog Now!”, Chapter 8
Parsing: A fundamental concept in computer science.
Difference Lists: The underlying mechanism that makes DCGs efficient.

Difficulty: Advanced Time estimate: 1-2 weeks Prerequisites: Project 1, understanding of lists and recursion.

Real world outcome: You will be able to provide a sentence as a list and get a true/false result, or even better, a full parse tree.

% Your DCG grammar
sentence(s(NP, VP)) --> noun_phrase(NP), verb_phrase(VP).
noun_phrase(np(Det, N)) --> determiner(Det), noun(N).
verb_phrase(vp(V, NP)) --> verb(V), noun_phrase(NP).

determiner(det(the)) --> [the].
determiner(det(a)) --> [a].
noun(n(cat)) --> [cat].
noun(n(mat)) --> [mat].
verb(v(sat)) --> [sat].

% Your query
?- sentence(ParseTree, [the, cat, sat, a, mat], []).
ParseTree = s(np(det(the), n(cat)), vp(v(sat), np(det(a), n(mat)))) ;
false.

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

Implementation Hints:

DCG rules look like normal Prolog rules, but use --> instead of :-.
Terminals (the actual words) are represented in lists: noun --> [cat].
Non-terminals are just the names of other DCG rules: sentence --> noun_phrase, verb_phrase.
To build a parse tree, add an extra argument to your rules. The structure you build is entirely up to you. For noun_phrase(np(D, N)), you’re saying “the parse tree for a noun phrase is the term np containing the parse trees for the determiner (D) and the noun (N)”.
The phrase/2 predicate is used to invoke a DCG: phrase(sentence, [the, cat, sat]). The three-argument version is also common for checking remaining words.

Learning milestones:

Your grammar can recognize a simple valid sentence → You understand basic DCG structure.
It correctly rejects an invalid sentence → Your constraints are working.
You can parse multiple valid sentence structures → Your grammar is becoming more robust.
Your parser generates a correct parse tree → You’ve unlocked the true power of DCGs for structural analysis.

Project 6: A Text-Based Adventure Game (Zork-like)

File: LEARN_PROLOG_DEEP_DIVE.md
Main Programming Language: Prolog
Alternative Programming Languages: Python, Inform 7
Coolness Level: Level 3: Genuinely Clever
Business Potential: 2. The “Micro-SaaS / Pro Tool”
Difficulty: Level 3: Advanced
Knowledge Area: Game Development / State Management / AI
Software or Tool: SWI-Prolog
Main Book: “Adventures in Prolog” by Dennis Merritt

What you’ll build: A classic text adventure game where the player can move between rooms, pick up objects, and interact with their environment by typing commands like “go north” or “take key”.

Why it teaches Prolog: This project forces you to deal with a notoriously tricky problem in pure logic programming: managing state. The state of the world (player location, object locations) changes. You’ll learn how to manage this using Prolog’s dynamic predicates, effectively using Prolog’s database-like nature to store and update world state.

Core challenges you’ll face:

Representing the game world → maps to facts for rooms, connections, and object locations (at(key, room1).)
Managing mutable state → maps to using dynamic/1 and assertz/1, retract/1 to change facts
Creating a game loop → maps to a recursive predicate that reads input, processes it, and repeats
Parsing player commands → maps to simple NLP to understand “go north” vs “take lamp”

Key Concepts:

Dynamic Predicates: dynamic/1, assertz/1, retract/1. These are non-logical and break pure declarative programming, but are essential for many real-world applications.
I/O in Prolog: read/1, write/1, nl/0.
State as a Database: Thinking of the world state as a database of facts is a powerful model.

Difficulty: Advanced Time estimate: 1-2 weeks Prerequisites: Project 1, Project 3.

Real world outcome: A fully interactive game playable from the Prolog console.

Welcome to the Prolog Adventure!
You are in the kitchen.
There is a knife here.
You can go east.
> go east
You are in the living room.
There is a lamp here.
You can go west or north.
> take lamp
You have taken the lamp.
> i
You are carrying: [lamp, knife]
>

Implementation Hints:

Declare your dynamic facts at the top of your file: :- dynamic at/2. (object, location) and :- dynamic holding/1. (object).
The at/2 predicate is key. at(key, room1) means the key is in room1. at(key, inventory) could mean the player is holding it.
A “move” action involves: a. Checking if a path exists from the player’s current location in the desired direction. b. If so, retract the fact about the player’s old location. c. assertz a fact about the player’s new location.
A “take” action involves: a. Checking if the object is at the player’s current location. b. If so, retract(at(Object, Location)) and assertz(holding(Object)).
The main game loop is a recursive predicate that never fails. It reads a command, processes it, prints the result, and calls itself again.

Learning milestones:

You can describe the world and look around → You have your static facts and description logic working.
You can move between rooms → You have successfully managed the player’s state.
You can pick up and drop objects → You are managing the state of multiple dynamic objects.
The game has a win/loss condition → You have built a complete, interactive system.

Summary

Project	Main Language	Difficulty	Time Estimate
1. Genealogical Database	Prolog	Beginner	1-2 hours
2. Logic Puzzle Solver	Prolog	Intermediate	Weekend
3. Graph Pathfinding	Prolog	Intermediate	Weekend
4. Symbolic Mathematics	Prolog	Advanced	Weekend
5. Natural Language Parser (DCG)	Prolog	Advanced	1-2 weeks
6. Text-Based Adventure Game	Prolog	Advanced	1-2 weeks