Show description
Prolog Cheat Sheet | CSE 240
Prolog Cheat Sheet | CSE 240
Prolog Cheat Sheet
Logic Programming Fundamentals
Prolog Fundamentals
Key Concepts
Declarative Programming: You describe what you want, not how to get it
Logic-Based: Programs are sets of facts and rules, queries ask questions about them
Pattern Matching: Prolog uses unification to match patterns
Backtracking: Automatically tries different possibilities to satisfy goals
Facts
Facts are basic assertions about the world. Always end with a period.
% Facts about people
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
% Facts about food
likes(john, pizza).
likes(mary, sushi).
likes(bob, pizza).
Rules
Rules define relationships based on other facts and rules.
% X is a grandparent of Z if X is parent of Y and Y is parent of Z
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
% X is a sibling of Y if they share a parent
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.
% X is an ancestor of Y if X is parent of Y (base case)
% OR if X is parent of Z and Z is ancestor of Y (recursive)
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
Queries
Ask questions at the ?- prompt.
?- parent(tom, bob).
true.
?- parent(bob, ann).
true.
?- parent(tom, ann).
false.
% Find all children of bob (X is a variable)
?- parent(bob, X).
X = ann ;
X = pat.
% Find all grandchildren of tom
?- grandparent(tom, X).
X = ann ;
X = pat.
% Find who likes pizza
?- likes(X, pizza).
X = john ;
X = bob.
Unification & Variables
Variables
Variables start with uppercase or underscore: X, Person, _Result
Atoms (constants) start with lowercase: tom, pizza, value
Anonymous variable: _ (don't care about the value)
% Find if tom is parent of anyone (don't care who)
?- parent(tom, _).
true.
% Match patterns
?- parent(tom, Child).
Child = bob ;
Child = liz.
% Unification operator =
?- X = 5.
X = 5.
?- [1,2,3] = [H|T].
H = 1,
T = [2, 3].
% Checking inequality
?- 5 \= 10.
true.
?- X = 5, X \= 10.
X = 5.
Lists
List Syntax
[] - empty list
[1, 2, 3] - list with elements
[H|T] - head and tail pattern (H is first element, T is rest)
[X, Y|Rest] - first two elements and the rest
List Operations
Member
% Check if X…
Prolog Cheat Sheet | CSE 240
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Prolog Cheat Sheet | CSE 240</title>
<style>
* {
margin: 0;
padding: 0;
box-sizing: border-box;
}
body {
font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
background: #0a0a0a;
color: #e0e0e0;
line-height: 1.6;
padding: 40px 20px;
}
.container {
max-width: 1200px;
margin: 0 auto;
}
.header {
text-align: center;
margin-bottom: 50px;
padding-bottom: 20px;
border-bottom: 3px solid #ff6b35;
}
.header h1 {
color: #ff6b35;
font-size: 3em;
margin-bottom: 10px;
}
.header p {
color: #888;
font-size: 1.2em;
}
.section {
background: #1a1a1a;
border-radius: 8px;
padding: 30px;
margin-bottom: 30px;
border-left: 4px solid #ff6b35;
}
.section h2 {
color: #ff6b35;
font-size: 2em;
margin-bottom: 20px;
padding-bottom: 10px;
border-bottom: 2px solid #333;
}
.section h3 {
color: #ff8c5a;
font-size: 1.4em;
margin: 25px 0 15px 0;
}
.subsection {
background: #0f0f0f;
padding: 20px;
border-radius: 6px;
margin: 15px 0;
border: 1px solid #333;
}
.subsection h4 {
color: #ff6b35;
font-size: 1.1em;
margin-bottom: 10px;
}
pre {
background: #0a0a0a;
border: 1px solid #444;
border-radius: 6px;
padding: 20px;
overflow-x: auto;
margin: 15px 0;
font-family: 'Courier New', monospace;
}
code {
font-family: 'Courier New', monospace;
font-size: 0.95em;
line-height: 1.5;
color: #e0e0e0;
}
.inline-code {
background: #1a1a1a;
color: #ffa366;
padding: 2px 8px;
border-radius: 3px;
font-family: 'Courier New', monospace;
font-size: 0.9em;
}
.tip {
background: #1a2a1a;
border-left: 4px solid #4caf50;
padding: 15px;
margin: 15px 0;
border-radius: 4px;
}
.tip strong {
color: #4caf50;
}
.warning {
background: #2a1a1a;
border-left: 4px solid #ff6b35;
padding: 15px;
margin: 15px 0;
border-radius: 4px;
}
.warning strong {
color: #ff6b35;
}
.grid {
display: grid;
grid-template-columns: repeat(auto-fit, minmax(300px, 1fr));
gap: 20px;
margin: 20px 0;
}
.card {
background: #0f0f0f;
padding: 20px;
border-radius: 6px;
border: 1px solid #333;
}
.card h4 {
color: #ff8c5a;
margin-bottom: 10px;
}
table {
width: 100%;
border-collapse: collapse;
margin: 20px 0;
}
th, td {
padding: 12px;
text-align: left;
border: 1px solid #333;
}
th {
background: #0f0f0f;
color: #ff6b35;
font-weight: bold;
}
td {
background: #1a1a1a;
}
tr:hover td {
background: #222;
}
::-webkit-scrollbar {
width: 10px;
height: 10px;
}
::-webkit-scrollbar-track {
background: #1a1a1a;
}
::-webkit-scrollbar-thumb {
background: #ff6b35;
border-radius: 5px;
}
::-webkit-scrollbar-thumb:hover {
background: #ff8c5a;
}
</style>
</head>
<body>
<div class="container">
<div class="header">
<h1>Prolog Cheat Sheet</h1>
<p>Logic Programming Fundamentals</p>
</div>
<!-- BASICS -->
<section class="section">
<h2>Prolog Fundamentals</h2>
<div class="subsection">
<h4>Key Concepts</h4>
<p><strong>Declarative Programming:</strong> You describe <em>what</em> you want, not <em>how</em> to get it</p>
<p><strong>Logic-Based:</strong> Programs are sets of facts and rules, queries ask questions about them</p>
<p><strong>Pattern Matching:</strong> Prolog uses unification to match patterns</p>
<p><strong>Backtracking:</strong> Automatically tries different possibilities to satisfy goals</p>
</div>
<h3>Facts</h3>
<p>Facts are basic assertions about the world. Always end with a period.</p>
<pre><code>% Facts about people
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
% Facts about food
likes(john, pizza).
likes(mary, sushi).
likes(bob, pizza).</code></pre>
<h3>Rules</h3>
<p>Rules define relationships based on other facts and rules.</p>
<pre><code>% X is a grandparent of Z if X is parent of Y and Y is parent of Z
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
% X is a sibling of Y if they share a parent
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.
% X is an ancestor of Y if X is parent of Y (base case)
% OR if X is parent of Z and Z is ancestor of Y (recursive)
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).</code></pre>
<h3>Queries</h3>
<p>Ask questions at the <span class="inline-code">?-</span> prompt.</p>
<pre><code>?- parent(tom, bob).
true.
?- parent(bob, ann).
true.
?- parent(tom, ann).
false.
% Find all children of bob (X is a variable)
?- parent(bob, X).
X = ann ;
X = pat.
% Find all grandchildren of tom
?- grandparent(tom, X).
X = ann ;
X = pat.
% Find who likes pizza
?- likes(X, pizza).
X = john ;
X = bob.</code></pre>
</section>
<!-- UNIFICATION -->
<section class="section">
<h2>Unification & Variables</h2>
<div class="subsection">
<h4>Variables</h4>
<p>Variables start with uppercase or underscore: <span class="inline-code">X</span>, <span class="inline-code">Person</span>, <span class="inline-code">_Result</span></p>
<p>Atoms (constants) start with lowercase: <span class="inline-code">tom</span>, <span class="inline-code">pizza</span>, <span class="inline-code">value</span></p>
<p>Anonymous variable: <span class="inline-code">_</span> (don't care about the value)</p>
</div>
<pre><code>% Find if tom is parent of anyone (don't care who)
?- parent(tom, _).
true.
% Match patterns
?- parent(tom, Child).
Child = bob ;
Child = liz.
% Unification operator =
?- X = 5.
X = 5.
?- [1,2,3] = [H|T].
H = 1,
T = [2, 3].
% Checking inequality
?- 5 \= 10.
true.
?- X = 5, X \= 10.
X = 5.</code></pre>
</section>
<!-- LISTS -->
<section class="section">
<h2>Lists</h2>
<div class="subsection">
<h4>List Syntax</h4>
<p><span class="inline-code">[]</span> - empty list</p>
<p><span class="inline-code">[1, 2, 3]</span> - list with elements</p>
<p><span class="inline-code">[H|T]</span> - head and tail pattern (H is first element, T is rest)</p>
<p><span class="inline-code">[X, Y|Rest]</span> - first two elements and the rest</p>
</div>
<h3>List Operations</h3>
<div class="grid">
<div class="card">
<h4>Member</h4>
<pre><code>% Check if X is in list
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).
?- member(2, [1,2,3]).
true.</code></pre>
</div>
<div class="card">
<h4>Length</h4>
<pre><code>% Find length of list
len([], 0).
len([_|T], N) :-
len(T, N1),
N is N1 + 1.
?- len([1,2,3], N).
N = 3.</code></pre>
</div>
<div class="card">
<h4>Append</h4>
<pre><code>% Append two lists
append([], L, L).
append([H|T1], L2, [H|T3]) :-
append(T1, L2, T3).
?- append([1,2], [3,4], X).
X = [1, 2, 3, 4].</code></pre>
</div>
<div class="card">
<h4>Reverse</h4>
<pre><code>% Reverse a list
reverse([], []).
reverse([H|T], R) :-
reverse(T, RT),
append(RT, [H], R).
?- reverse([1,2,3], X).
X = [3, 2, 1].</code></pre>
</div>
</div>
<h3>More List Examples</h3>
<pre><code>% Sum of list elements
sum([], 0).
sum([H|T], Sum) :- sum(T, RestSum), Sum is H + RestSum.
% Find maximum in list
max([X], X).
max([H|T], Max) :- max(T, TMax), (H > TMax -> Max = H ; Max = TMax).
% Get last element
last([X], X).
last([_|T], X) :- last(T, X).
% Get nth element (0-indexed)
nth(0, [H|_], H).
nth(N, [_|T], E) :- N > 0, N1 is N - 1, nth(N1, T, E).</code></pre>
</section>
<!-- ARITHMETIC -->
<section class="section">
<h2>Arithmetic & Comparison</h2>
<div class="tip">
<strong>Important:</strong> Use <span class="inline-code">is</span> for evaluation, <span class="inline-code">=</span> for unification
</div>
<h3>Arithmetic Operators</h3>
<table>
<tr>
<th>Operator</th>
<th>Meaning</th>
<th>Example</th>
</tr>
<tr>
<td><span class="inline-code">+</span></td>
<td>Addition</td>
<td><span class="inline-code">X is 5 + 3</span></td>
</tr>
<tr>
<td><span class="inline-code">-</span></td>
<td>Subtraction</td>
<td><span class="inline-code">X is 10 - 4</span></td>
</tr>
<tr>
<td><span class="inline-code">*</span></td>
<td>Multiplication</td>
<td><span class="inline-code">X is 6 * 7</span></td>
</tr>
<tr>
<td><span class="inline-code">/</span></td>
<td>Division (float)</td>
<td><span class="inline-code">X is 10 / 3</span></td>
</tr>
<tr>
<td><span class="inline-code">//</span></td>
<td>Integer division</td>
<td><span class="inline-code">X is 10 // 3</span></td>
</tr>
<tr>
<td><span class="inline-code">mod</span></td>
<td>Modulo</td>
<td><span class="inline-code">X is 10 mod 3</span></td>
</tr>
<tr>
<td><span class="inline-code">**</span></td>
<td>Power</td>
<td><span class="inline-code">X is 2 ** 8</span></td>
</tr>
</table>
<h3>Comparison Operators</h3>
<table>
<tr>
<th>Operator</th>
<th>Meaning</th>
<th>Example</th>
</tr>
<tr>
<td><span class="inline-code">=</span></td>
<td>Unification</td>
<td><span class="inline-code">X = 5</span></td>
</tr>
<tr>
<td><span class="inline-code">\=</span></td>
<td>Not unifiable</td>
<td><span class="inline-code">X \= Y</span></td>
</tr>
<tr>
<td><span class="inline-code">==</span></td>
<td>Identical</td>
<td><span class="inline-code">X == 5</span></td>
</tr>
<tr>
<td><span class="inline-code">\==</span></td>
<td>Not identical</td>
<td><span class="inline-code">X \== Y</span></td>
</tr>
<tr>
<td><span class="inline-code"><</span></td>
<td>Less than</td>
<td><span class="inline-code">X < 10</span></td>
</tr>
<tr>
<td><span class="inline-code">></span></td>
<td>Greater than</td>
<td><span class="inline-code">X > 5</span></td>
</tr>
<tr>
<td><span class="inline-code">=<</span></td>
<td>Less or equal</td>
<td><span class="inline-code">X =< 10</span></td>
</tr>
<tr>
<td><span class="inline-code">>=</span></td>
<td>Greater or equal</td>
<td><span class="inline-code">X >= 5</span></td>
</tr>
</table>
<pre><code>% Factorial
factorial(0, 1).
factorial(N, F) :-
N > 0,
N1 is N - 1,
factorial(N1, F1),
F is N * F1.
% Fibonacci
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.</code></pre>
</section>
<!-- BACKTRACKING & CUT -->
<section class="section">
<h2>Backtracking & Cut</h2>
<div class="subsection">
<h4>How Backtracking Works</h4>
<p>Prolog tries to satisfy goals from left to right. If it fails, it backtracks and tries alternative clauses.</p>
</div>
<pre><code>% Prolog will try each clause in order
color(red).
color(green).
color(blue).
?- color(X).
X = red ; % First answer, user types ;
X = green ; % Second answer, user types ;
X = blue. % Third answer
% Backtracking example
likes(mary, food).
likes(mary, wine).
likes(john, wine).
likes(john, mary).
?- likes(mary, X), likes(john, X).
X = wine. % Only wine satisfies both conditions</code></pre>
<h3>The Cut Operator (!)</h3>
<div class="warning">
<strong>Cut (!):</strong> Prevents backtracking past this point. Use carefully!
</div>
<pre><code>% Without cut - tries all solutions
max_no_cut(X, Y, X) :- X >= Y.
max_no_cut(X, Y, Y) :- X < Y.
% With cut - stops after first match
max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).
% Cut prevents unnecessary backtracking
member_check(X, [X|_]) :- !.
member_check(X, [_|T]) :- member_check(X, T).
% Negation using cut and fail
not_member(_, []).
not_member(X, [H|T]) :- X \= H, not_member(X, T).</code></pre>
</section>
<!-- CONTROL STRUCTURES -->
<section class="section">
<h2>Control Structures</h2>
<h3>Conjunction (AND)</h3>
<pre><code>% Both conditions must be true (comma means AND)
?- parent(tom, bob), parent(bob, ann).
true.
happy(Person) :- healthy(Person), wealthy(Person).</code></pre>
<h3>Disjunction (OR)</h3>
<pre><code>% Either condition can be true (semicolon means OR)
?- parent(tom, bob); parent(tom, liz).
true.
eligible(Person) :- student(Person); veteran(Person).</code></pre>
<h3>Negation</h3>
<pre><code>% \+ means NOT
?- \+ parent(tom, ann).
true.
different(X, Y) :- \+ X = Y.
% Not a member
not_in(_, []).
not_in(X, [H|T]) :- X \= H, not_in(X, T).</code></pre>
<h3>If-Then-Else</h3>
<pre><code>% Syntax: (Condition -> ThenPart ; ElsePart)
max(X, Y, Max) :- (X >= Y -> Max = X ; Max = Y).
absolute(X, Abs) :- (X >= 0 -> Abs = X ; Abs is -X).
grade(Score, Grade) :-
( Score >= 90 -> Grade = a
; Score >= 80 -> Grade = b
; Score >= 70 -> Grade = c
; Score >= 60 -> Grade = d
; Grade = f
).</code></pre>
</section>
<!-- BUILT-IN PREDICATES -->
<section class="section">
<h2>Common Built-in Predicates</h2>
<div class="grid">
<div class="card">
<h4>Type Checking</h4>
<pre><code>atom(X) % X is atom
number(X) % X is number
integer(X) % X is integer
is_list(X) % X is list
var(X) % X is unbound
nonvar(X) % X is bound</code></pre>
</div>
<div class="card">
<h4>List Operations</h4>
<pre><code>length(L, N) % length
append(L1, L2, L3) % concatenate
member(X, L) % membership
reverse(L, R) % reverse
sort(L, S) % sort
nth0(I, L, E) % get nth</code></pre>
</div>
<div class="card">
<h4>Finding Solutions</h4>
<pre><code>findall(X, Goal, L)
% Find all X satisfying Goal
bagof(X, Goal, L)
% Like findall, groups
setof(X, Goal, L)
% Sorted unique results</code></pre>
</div>
<div class="card">
<h4>I/O</h4>
<pre><code>write(Term)
writeln(Term)
read(X)
nl % newline
tab(N) % N spaces</code></pre>
</div>
</div>
<h3>Finding All Solutions</h3>
<pre><code>% Given these facts:
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
% Get all children of tom
?- findall(Child, parent(tom, Child), Children).
Children = [bob, liz].
% Get all parents and their children as pairs
?- findall([Parent, Child], parent(Parent, Child), Pairs).
Pairs = [[tom, bob], [tom, liz], [bob, ann], [bob, pat]].
% Count how many children bob has
?- findall(Child, parent(bob, Child), Children), length(Children, N).
Children = [ann, pat],
N = 2.</code></pre>
</section>
<!-- RECURSION PATTERNS -->
<section class="section">
<h2>Common Recursion Patterns</h2>
<h3>Processing Lists</h3>
<pre><code>% Base case: empty list
% Recursive case: process head, recurse on tail
% Count elements
count([], 0).
count([_|T], N) :- count(T, N1), N is N1 + 1.
% Double each element
double([], []).
double([H|T], [H2|T2]) :- H2 is H * 2, double(T, T2).
% Filter even numbers
evens([], []).
evens([H|T], [H|T2]) :- 0 is H mod 2, !, evens(T, T2).
evens([_|T], T2) :- evens(T, T2).</code></pre>
<h3>Accumulator Pattern</h3>
<pre><code>% More efficient with accumulator
% Sum with accumulator
sum(List, Sum) :- sum_acc(List, 0, Sum).
sum_acc([], Acc, Acc).
sum_acc([H|T], Acc, Sum) :-
NewAcc is Acc + H,
sum_acc(T, NewAcc, Sum).
% Reverse with accumulator (tail recursive)
reverse(List, Rev) :- reverse_acc(List, [], Rev).
reverse_acc([], Acc, Acc).
reverse_acc([H|T], Acc, Rev) :-
reverse_acc(T, [H|Acc], Rev).</code></pre>
<h3>Tree Traversal</h3>
<pre><code>% Binary tree: node(Value, Left, Right) or nil
% Count nodes
count_nodes(nil, 0).
count_nodes(node(_, L, R), Count) :-
count_nodes(L, CL),
count_nodes(R, CR),
Count is CL + CR + 1.
% Tree height
height(nil, 0).
height(node(_, L, R), H) :-
height(L, HL),
height(R, HR),
H is max(HL, HR) + 1.
% Search tree
search(Val, node(Val, _, _)).
search(Val, node(_, L, _)) :- search(Val, L).
search(Val, node(_, _, R)) :- search(Val, R).</code></pre>
</section>
<!-- PRACTICAL EXAMPLES -->
<section class="section">
<h2>Practical Examples</h2>
<h3>Family Tree</h3>
<pre><code>% Facts
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
male(tom).
male(bob).
male(jim).
female(liz).
female(ann).
female(pat).
% Rules
father(X, Y) :- parent(X, Y), male(X).
mother(X, Y) :- parent(X, Y), female(X).
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
grandmother(X, Z) :- grandparent(X, Z), female(X).
grandfather(X, Z) :- grandparent(X, Z), male(X).
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.
brother(X, Y) :- sibling(X, Y), male(X).
sister(X, Y) :- sibling(X, Y), female(X).
uncle(X, Y) :- brother(X, P), parent(P, Y).
aunt(X, Y) :- sister(X, P), parent(P, Y).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).</code></pre>
<h3>Graph Traversal</h3>
<pre><code>% Graph edges
edge(a, b).
edge(b, c).
edge(b, d).
edge(c, d).
edge(d, e).
edge(a, e).
% Path exists between two nodes
path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).
% Path with visited nodes (avoid cycles)
path(X, Y, Visited, [X,Y]) :-
edge(X, Y),
\+ member(Y, Visited).
path(X, Y, Visited, [X|Path]) :-
edge(X, Z),
\+ member(Z, Visited),
path(Z, Y, [X|Visited], Path).</code></pre>
<h3>Quicksort</h3>
<pre><code>% Quicksort implementation
quicksort([], []).
quicksort([Pivot|T], Sorted) :-
partition(Pivot, T, Less, Greater),
quicksort(Less, SortedLess),
quicksort(Greater, SortedGreater),
append(SortedLess, [Pivot|SortedGreater], Sorted).
% Partition list around pivot
partition(_, [], [], []).
partition(Pivot, [H|T], [H|Less], Greater) :-
H =< Pivot, !,
partition(Pivot, T, Less, Greater).
partition(Pivot, [H|T], Less, [H|Greater]) :-
partition(Pivot, T, Less, Greater).</code></pre>
</section>
<!-- TIPS -->
<section class="section">
<h2>Important Tips</h2>
<div class="tip">
<strong>Always include a base case:</strong> Every recursive predicate needs a stopping condition
</div>
<div class="tip">
<strong>Variables vs Atoms:</strong> X (uppercase) is variable, x (lowercase) is atom
</div>
<div class="tip">
<strong>Use is for arithmetic:</strong> X is 5 + 3 evaluates. X = 5 + 3 just unifies X with the term 5+3
</div>
<div class="warning">
<strong>Cut (!) prevents backtracking:</strong> Use only when you're sure you want to commit to a choice
</div>
<div class="tip">
<strong>Trace your code:</strong> Use trace. and notrace. to debug
</div>
<div class="tip">
<strong>Think declaratively:</strong> Describe relationships, not procedures
</div>
</section>
</div>
</body>
</html>