Disclaimer: The notes below are fully/partially NOT created by myself. They are from slides and/or wikipedia and/or textbook. The purpose of this post is simply to learn and review for the course. If you think something is inappropriate, please contact me at “ryan_yrs [at] hotmail [dot] com” immediately and I will remove it as soon as possible.
- “PROgrammation en LOGique”
- Prolog is a general-purpose logic programming language associated with artificial intelligence and computational linguistics.
- Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of relations, represented as facts and rules. A computation is initiated by running a query over these relations.
- Specify WHAT to compute rather than HOW to compute it.
- Dutch: Sociaal Wetenschappelijke Informatica (“Social Science Informatics”)
End of a Query
Load a file
- Uncapitalized: Term
- Capitalized: Variable
How to get the next result?
- ; (Search for a NEW value with which to instantiate var to make goal succeed)
- Instead of
- . (Period)
- If there is no match, simply return “false.”
- Can take multiple
student(X), taking(X, csc324).
- Can take different
- Variable in Facts
same(X, X)as being UNIVERSALLY QUANTIFIED: “For all X, same(X, X) holds.”
- Variable C in:
taughtBy(X, Y) :- taking(X, C), teaching(Y, C).
child(alice, bob). child(bob, charlie). child(charlie, daenerys). descendant(X, Y) :- child(X, Y). % Base Case descendant(X, Y) :- child(X, Z), descendant(Z, Y). % Recursive Case
Head & Tail
- [a|[b, c]]
- A name
- e.g. a
- A LIST
- e.g. [b, c]
member(X, [X|_]). % X is a member of a list when X is the head of the list. member(X, [_|Tail]) :- member(X, Tail). % X is a member of a list when X is a member of the tail of the list.
Match any term that we do not need to reuse
How to implement append?
myAppend(, Y, Y). myAppend([X|Xs], Y, [X|Zs]) :- myAppend(Xs, Y, Zs).
- When one enters a query, it attempts to UNIFY query with facts or rules, which is analogous to type inference, except acting on literal values and predicate structure rather than types.
- Each goal attempts unfication with facts and rules in source code, one at a time, TOP-TO-BOTTOM.
a = a. % true, don't have to be initialized. =(a,a). % same as above a = b. % false student(a) = student(a). % true, don't have to be initialized. student(bob) = student(lily). % false taking(lily, csc324) = taking(csc324, lily). % false, Order in predicates and lists matters. [1, 2, 3] = [3, 2, 1]. % false f(a, b(c)) = f(a, b(c)). % true, Nested predicates are supported.
Prolog short-circuits its goal-checking, meaning that it will halt and output false the FIRST time a goal fails.
- Denoted by “!”
- A special goal in Prolog that ALWAYS SUCCEEDS.
- Cut goal prevents Prolog from backtracking to BEFORE cut took place for current goal.
- Cut prevents backtracking on choice of current rule, meaning initial goal is never unified with second rule.
- One very useful tool for EXPLICITLY CONTROLLING Prolog backtracking.
- It enables us to make more EFFICIENT Prolog program.
- Cut does NOT prevent ALL the goals, it only prevents CURRENT GOAL.
- Goal “fail” fails, and since cut restricts backtracking, Prolog cannot choose a different fact/fule to use, and so it fails.
- Use for negation.
- Important: It behaves DIFFERENTLY from logical negation.