<h1> PrologCheatSheet </h1>

Basics of relational programming with Prolog —PROgramming in LOGic ^_^

Try Prolog online

The listing sheet, as PDF, can be found here, while below is an unruly html rendition.

This reference sheet is built around the system https://github.com/alhassy/CheatSheet.

Table of Contents

1. Administrivia
2. Syntax
   1. name and atom_chars
3. Facts & Relations
4. Mixfix Syntax
5. Trace & Backtracking
6. What is a Prolog Program Exactly?
   1. One point rule
   2. Overloading
7. Modus Ponens — Computation ≈ Deduction
8. Conjunction ≈ Constraints — Disjunction ≈ Alternatives
9. Unification
   1. Operational Semantics
   2. 'symbol' = symbol
   3. Unification performs no simplification, whence no arithmetic
10. Algebraic Datatypes
11. Arithmetic with is —Using Modules
    1. Using Modules
12. Lists
13. Declaration Ordering Matters —Recursion
14. The Cut
    1. Examples
    2. Disjoint Clauses
    3. Conditional
    4. Cut-fail Combination
    5. Good Exercise
15. Higher-order Support with call
16. Meta-Programming
    1. Print, var, nonvar, arg
17. Reads

<a id="org944e9a2"></a>

Administrivia

Everything is a relation! —I.e., a table in a database!

Whence programs are unidirectional and can be ‘run in reverse’: Input arguments and output arguments are the same thing! Only perspective shifts matter.

For example, defining a relation append(XS, YS, ZS) intended to be true precisely when ZS is the catenation of XS with YS, gives us three other methods besides being a predicate itself! List construction: append([1, 2], [3, 4], ZS) ensures ZS is the catenation list. List subtraction: append([1,2], YS, [1, 2, 3, 4]) yields all solutions YS to the problem [1, 2] ++ YS = [1, 2, 3, 4]. Partitions: append(XS, YS, [1, 2, 3, 4]) yields all pairs of lists that catenate to [1,2, 3, 4]. Four methods for the price of one!

<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides"> <colgroup> <col class="org-left" /> </colgroup> <tbody> <tr> <td class="org-left">Prolog is PROgramming in LOGic.</td> </tr> </tbody> </table>

In Prolog, the task of the programmer is simply to describe problems —write down, logically, the situation— rather than telling the computer what to do, then obtains information by asking questions —the logic programming system figures out how to get the answer.

• Prolog is declarative: A program is a collection of ‘axioms’ from which ‘theorems’ can be proven. For example, consider how sorting is performed:

  • Procedurally: Find the minimum in the remainder of the list, swap it with the head of the list; repeat on the tail of the list.

  • Declaratively: B is the sorting of A provided it is a permutation of A and it is ordered.

  Whence, a program is a theory and computation is deduction!

• swipl -s myprogram.pl –Load your program into a REPL, ?-….

• make. –Reload your program.

• halt. –Exit the REPL.

• consult('CheatSheet.pl'). –Load the contents of the given file as the new knowledge base.

• assert((⋯)). –Add a new rule to the knowledge base, from within the REPL. Use retract((⋯)) to remove rules from the knowledge base.

  • assert is useful when we want to cache computations.

• listing. –Display the contents of the current knowledge base; i.e., what Prolog ‘knows’.

• listing(name). –List all information in the knowledge base about the name predicate.

<a id="org1631a81"></a>

Syntax

There are three types of terms:

• Constants: Numbers such as -24, and atoms such as jasim, 'hello world', '&^%&#@$ &*', and ' ' —a space in quotes.

• Variables: Words starting with a capital letter or an underscore.

  • The variable _ is called the anonymous variable.

    It's for when we need a variable, say when pattern matching, but don't care about the value.

• Structures: Terms of the form functor(term₁,...,termₙ).

<a id="org01cff87"></a>

name and atom_chars

The characters between single quotes are the name of an atom and so Prolog admits symbol = 'symbol' as true.

• Atoms, or nullary predicates, are represented as a lists of numbers; ASCII codes.

• We can use this to compare two atoms lexicographically.

• We can obtain the characters in an atom by using the built-in atom_chars.

  ?- name(woah, X). %⇒ X = [119,111,97,104] ?- atom_chars(nice, X). %⇒ X = [n, i, c, e].

<a id="org11a6a80"></a>

Facts & Relations

We declare relations by having them begin with a lowercase letter; variables are distinguished by starting with a capital letter.

<div class="parallel"> /* Some facts of our world */ jasim_is_nice. it_is_raining.

% ?- jasim_is_nice.
% ⇒ true: We declared it so.

eats(fred, mangoes).
eats(bob, apples).
eats(fred, oranges).

% Which foods are eaten by fred?
% ?- eats(fred, what).
     %⇒ false; “what” is a name!
% ?- eats(fred, What). %⇒ mangoes oranges

</div>

Relational constraints are formed using :-, which acts as the “provided”, ⇐, operator from logic. Read P :- Q as P is true, provided Q is true.

<div class="parallel"> % All men are mortal. mortal(X) :- man(X).

% Socrates is a man.
man(socrates).

% Hence, he's expected to be mortal.
% ?- mortal(socrates). %⇒ true

% What about Plato?
?- mortal(plato).
%⇒ false, plato's not a man.

% Let's fix that … in the REPL!
?- assert((man(plato))).

% Who is mortal?
?- mortal(X). % ⇒ socrates plato

</div>

<a id="org7e5c51a"></a>

Mixfix Syntax

<div class="parallel"> It may feel awkward to write `father_of(homer, bart)` and instead prefer `homer father_of bart`. We may declare relations to be prefix, infix, or postfix with patterns `xf`, `xfx`, and `fx` respectively. For left associativity we use pattern `yfx` and use `xfy` for right associativity.

:- op(35,xfx,father_of).

father_of(me, you).
homer father_of bart.
homer father_of lisa.

</div>

• Precedence, or binding power, is lowest at 1200 and highest at 0.
• Note: father_of(X,Y) = X father_of Y is true.

We may learn about existing operators too;

e.g., ?- current_op(Prec, Fixity, =:=) ^_^

<a id="org7b75a05"></a>

Trace & Backtracking

We can see what Prolog does at each step of a computation by invoking trace; we turn off this feature with notrace.

<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides"> <colgroup> <col class="org-left" /> </colgroup> <tbody> <tr> <td class="org-left">*This’ an excellent way to learn how Prolog proof search works! (Debugging!)*</td> </tr> </tbody> </table> <div class="parallel"> Suppose we have the following database.

q(1). q(2). q(3).
r(2). r(3).
p(X) :- q(X), r(X).

With trace, query p(X) and press SPACE each time to see what Prolog is doing. At one point, the goal r(1) will fail and that choice (X = 1) will be redone with the next possibility for q, namely (X = 2).

</div>

The line marked redo is when Prolog realizes its taken the wrong path, and backtracks to instantiate the variable to 2.

Operationally, query p(X) is answered by:

1. Find match for the first goal: q at 1.
2. Then see if matches the second: r at 1.
3. (Redo) If not, find another match for the first: q at 2.
4. See if this matches the second, r.
5. Etc.

• findall(X, Goal, L) succeeds if L is the list of all those X's for which Goal holds.

• fail/0 immediately fails when encountered. Remember: Prolog tries to backtrack when its fails; whence fail can be viewed as an instruction to force backtracking.

  The opposite of forcing backtracking is to block it, which is done with ‘cut’ ! —see below.

<a id="orgd201c75"></a>

What is a Prolog Program Exactly?

A program denotes all true facts derivable from its clauses using modus ponens, unification, term rewriting, and logical or-&-and for the execution model.

Hidden Quantifiers:

<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides"> <colgroup> <col class="org-left" /> <col class="org-left" /> </colgroup> <tbody> <tr> <td class="org-left"><span class="underline">Syntax</span></td> <td class="org-left"><span class="underline">Semantics</span></td> </tr> <tr> <td class="org-left">`head(X) :- body(X,Y).`</td> <td class="org-left">\(∀ X.\, head(X) \,⇐\, ∃ Y.\, body(X,Y)\)</td> </tr> <tr> <td class="org-left">`?- Q(X)`</td> <td class="org-left">\(∃ X.\, Q(X)\)</td> </tr> </tbody> </table>

1. “ head(X) is true provided there's some Y such that body(X,Y) is true ”
   • head. is an abbreviation for head :- true.
   • Indeed, (p ;≡; (p ⇐ true)).
2. “ Is there an X so that Q(X) is true? ”

<a id="org67c9d9a"></a>

One point rule

“One-Point R