Prolog Programming Language
Prolog is a declarative programming language
it's primarily used as a rational agent, classical AI
A rational agent uses search algorithms to decide actions.
Prolog percepts queries as input and perform search using DFS with backtracking
its based on predicate logic
its execution model makes recursion the most natural way to express repetition and search
DFS (Depth-first search) is a Stack (LIFO) based algorithm
Top-to-bottom, left-to-right node traversal
therefore, DFS is structurally optimal for recursion
this execusion model aligns perfectly with how the call stack in recursion works :
function call = visit node
recursive call = go deeper
return from function = backtrack
call stack frames = path tracking
Memory efficiency (Linear space complexity)
Incompleteness (can stuck in infinite loop)
(more later)
parent(mary, moss).
parent(moss, leen).
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).
facts and rules.
fact: mary is parent of moss.
fact: moss is parent of leen.
rule: X is grandparent of Y, if (represented by ":-") X is parent of Z and (represented by ",") Z is parent of Y.
Now let's try a query:
grandparent(mary, leen).
-> true
Trace:
DFS search tree with 3 levels
Depth 0: grandparent(X, Y)
Depth 1: parent(X, Z)
Depth 2: parent(Z, Y)
-> grandparent(X, Y).
unifies X with mary and Y with leen.
expand
-> parent(X, Z).
which became
parent(mary, Z).
check first branch:
parent(mary, moss).
unifies Z with moss
true
expand
-> parent(Z, Y).
which became
parent(moss, leen).
check first branch:
parent(mary, moss).
false
check second branch:
parent(moss, leen).
true
both conditions are true
return true.
Prolog returns true without ever backtracking to the second branch at depth 1
parent(mary, john). % new fact
parent(mary, moss).
parent(moss, leen).
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).
query: grandparent(mary, leen).
DFS Trace:
Depth 0: grandparent(X, Y)
Depth 1: parent(X, Z)
Depth 2: parent(Z, Y)
-> grandparent(X,Y) & grandparent(mary,leen) -> X = mary, Y = leen.
expand
-> parent(X, Z).
parent(mary, Z) & parent(mary, john) -> Z = john.
true.
expand
-> parent(Z, Y).
parent(john,leen) & parent(mary, john) -> false.
& parent(mary, moss) -> false.
& parent(moss, leen) -> false.
-- backtrack --
check the second branch at depth 1
-> parent(X, Z).
parent(mary, Z) & parent(mary, moss) -> Z = moss.
true.
expand
-> parent(Z, Y).
parent(moss,leen) & parent(mary, john) -> false.
& parent(mary, moss) -> false.
& parent(moss, leen) -> true.
Prolog returns true.
parent(mary, moss).
parent(moss, leen).
parent(leen, john).
ancestor(X, Y) :- parent(X, Y). % base case
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y). % recursive case
while the grandparent predicate could always be represented by a tree with 3 levels
ancestor is not fixed,
only way to implement it is using recursion
Query:
?- ancestor(mary, john).
true.
DFS Trace:
% Depth 0: ancestor(X, Y).
% Depth 1: base case: parent(X, Y).
% recursive case: parent(X, Z).
% Depth 2: ancestor(Z, Y)
% ...
Depth 0:
ancestor(X, Y).
ancestor(mary, john).
X = mary, Y = john.
expand
Depth 1:
Base Case
parent(X, Y).
parent(mary, john).
returns false with the 3 branches.
-- backtrack --
Depth 1:
Recursive Case
parent(X, Z)
parent(mary, Z)
unifies Z with moss in the first branch.
expand
Depth 2:
ancestor(moss, john).
expand
Depth 3:
Base Case
parent(moss, john).
return false with the 3 branches.
-- backtrack --
Depth 3:
Recursive Case
parent(moss, Z2).
since this is the second stack call of ancestor,
this is the second copy of Z, let's name it Z2.
Z2 unifies with leen in the second branch.
expand
Depth 4:
ancestor(Z2, john).
ancestor(leen, john).
expand
Depth 5:
Base Case
parent(leen, john).
true.
Infinie loop:
bad_ancestor(X, Z) :- bad_ancestor(X, Y), parent(Y, Z).
bad_ancestor(X, Z) :- parent(X, Z).
parent(john, mary).
parent(mary, leen).
Stack Overflow.
Rule Ordering constraint in non tail recursive.
I highly recommend this course
Programming Paradigms - Chapter 8 - Prolog
Programming Paradigms - Chapter 9 - Prolog Recursion
cool math video : https://youtu.be/EVwQsvof7Hw?si=wLYos_zdWe7TuCvr
- BFS (Breadth-first seach) explores the search space level by level
it expands all nodes at Depth x before moving to Depth x+1
uses Queue (FIFO)
Unlike DFS, it's complete (if finite branching), it doesn't get stuck in a loop
it's typically faster and optimal (if the all steps have equal)
BFS fixes DFS’s incorrectness (non-optimal, incomplete) but at a huge memory cost (higher Space Complexity).
- IDS (Iterative-Deepening Search)
Combine DFS’s low memory with BFS’s optimality
Traversal is FIFO, expanding is LIFO
this comes with a cost of redundancy and revisiting shallow nodes
but it's cheap comparing to exploring deep levels
-
UCS (Uniform-Cost Search)
informed search, based on lowest cost
f(n)=g(n) where g(n) is the cumulative cost of n -
A*
informed search f(n)=g(n)+h(n)
where h(n) is heuristic function.
at each node, heuristics make an informed estimation to guide the search toward the goal efficiently
Heuristic requirements to guarantee optimality:
Admissible: h(n) <= true cost to goal
Consistent (monotonic): h(n) <= cost(n, n') + h(n')
A* is both complete and optimal provided that the heuristic is admissible and preferably consistent, but like BFS,
it can require substantial memory since it stores all generated nodes in its frontier.
https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/
Prolog's built-in DFS (depth-first search) is efficient for many problems
but implementing other search algorithms in Prolog on top of it comes with great benefits in cases such as:
Infinite Search Spaces
Finding Shortest/Least Cost Path
Rule Order Independence
Stack Overflow
High Branching Factors
Heuristics
Solving Constraint Satisfaction Problems (CSPs)
https://stackoverflow.com/questions/36235348/prolog-and-limitations-of-backtracking
graph_search.pl
left_recursive_ancestor.pl
deep_maze.pl
chess_search.pl
https://stoics.org.uk/~nicos/sware/chess_db/
Run Prolog online: https://swish.swi-prolog.org/
creep.