UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 6.10 Free with a free account
Prolog: A Logic-Based Programming Language for AI
Introduction to Artificial Intelligence · Chapter 6: Logic, Reasoning, and Knowledge SystemsSection 6.10 · lesson 48 of 6916 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Introduction to Artificial Intelligence.
Lesson complete
Earn the 3 college credits for Introduction to Artificial Intelligence
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Learning from Labeled Data: Supervised Techniques →← Backward Chaining: Reasoning from Goals to EvidenceNext lesson: Learning from Labeled Data: Supervised Techniques →
In this lesson
How Prolog answers queries from facts and rules with built-in backtracking.
- Write Prolog facts, rules and queries with correct syntax
- Trace how Prolog proves a goal using unification and depth-first backtracking
- Write recursive list predicates with the base case first
- Distinguish green cuts from red cuts and use safer alternatives
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (2,439 words). Read along, or search it.
Opening Question
Programming by Stating What Is True
Most programming languages ask you to say how to compute something: do this, then that, and repeat until done. Prolog, short for programming in logic, asks for something different. You describe what's true about a problem, as facts and rules, and then you ask questions. Prolog works out how to find the answers. Created in the early 1970s, it became one of the main languages of symbolic AI. It's been used for expert systems, language, planning, and puzzles. So what does a program look like, when it only states what's true?
Syntax
Atoms, Variables and Compound Terms
A Prolog program is a knowledge base: facts and rules in a text file, usually ending in dot p l. Every statement ends with a full stop. An atom starts with a lowercase letter, like tom or parent. A number starts with a digit. A variable starts with an uppercase letter or an underscore, like X or Person. A compound term is an atom with arguments, like parent of tom, bob. A list sits in square brackets. And a percent sign starts a comment. Case matters: capital X is a variable, but lowercase x is an atom.
Facts
A Family Stated as Facts
Here's a small family, stated as facts. Tom is a parent of Bob and Liz. Pam is also a parent of Bob. Bob is a parent of Ann and Pat, and Pat is a parent of Jim. Then come the female and male facts. In parent of tom, bob, the word parent is the predicate: the relation. Its number of arguments is its arity, so we write it as parent slash two. And notice that every fact ends with a full stop.
Queries
Asking Questions at the Prompt
A query asks a question. At the prompt, a question mark and a dash, you type a goal. Parent of tom, bob, is a yes or no question: this query answers true. If the goal contains variables, Prolog looks for values that make it true. Parent of tom, X asks for Tom's children. This query answers X equals bob. Typing a semicolon asks for the next answer: X equals liz. Parent of X, jim, answers X equals pat. And parent of jim, X, answers false. False means no more answers can be found, not false in the real world. Prolog only knows what's in its program.
Rules
Heads, Bodies and the If Operator
A rule says something is true if other things are true. Its head is the conclusion, and its body is the conditions, joined by colon dash, read as if. X is the mother of Y if X is a parent of Y, and X is female. The comma means and. Father is the same, with male. In the grandparent rule, Y links the two goals: the child of X must be the same person who's a parent of Z. Each variable means the same thing everywhere in one rule. And in the sibling rule, X backslash equals Y says X and Y aren't the same. That stops anyone from being their own sibling.
Two Readings
Declarative and Procedural Meaning
Read as logic, colon dash is implication, with the conclusion on the left. A comma is and, a semicolon is or, and several clauses with one head are alternatives. Backslash plus, before a goal, means not, by failure: it succeeds when Prolog can't prove the goal. That treats everything missing from the program as false, the closed-world assumption. Every program has two readings. Declaratively, X is a grandparent of Z if X is a parent of some Y, and Y is a parent of Z. Procedurally, to prove grandparent, first prove parent of X, Y, then parent of Y, Z. That's backward chaining, from lesson six point nine, in a fixed order.
Worked Example
Answers from the Family Program
Running the rules on the family program, mother of X, bob answers X equals pam. Father of X, bob answers tom. Grandparent of tom, W answers ann, then pat. Grandparent of X, jim answers bob. Sibling of X, bob answers liz, and sibling of ann, Y answers pat. Each answer follows from the facts and rules together.
Quick Check
Ann's Mother Is Not in the Program
Quick check, on the same program. What does the query mother of X, ann answer? X equals bob, ann's parent? X equals pam, a female? Or no answer at all? Pause, and decide. No answer at all: it answers false. The only parent of ann is bob, so parent of X, ann binds X to bob. Then female of bob has to be proved, and it can't be. Bob is male, so that answer fails, and nothing else is left. Pam is ann's grandmother, not her mother. And ann's mother simply isn't in the program, so Prolog can't find her.
Unification
How the Equals Sign Matches Terms
Every step runs on unification, from lesson six point six. The equals sign asks Prolog to unify its two sides. Identical atoms unify. A variable unifies with anything, and becomes bound. Compound terms need the same name and arity, then each argument unifies. Anything else fails. So bob equals bob is true, and bob equals tom is false. Parent of X, bob, equals parent of tom, Y, binds X to tom and Y to bob. Matching reaches inside nested terms. f of X, X can't match f of a, b, since X can't be both. And H bar T, against the list one, two, three, gives H as one, and T as the list two, three.
Search
Choice Points and Built-In Backtracking
To prove a goal, Prolog looks from top to bottom for a clause whose head unifies with it, and remembers the others for later: a choice point. If the clause is a fact, the goal is proved. If it's a rule, its body's goals become the new goals, proved left to right. If a goal can't be proved, Prolog backtracks: it goes back to the latest choice point, undoes the bindings made since, and tries the next clause. When every goal is proved, it reports the answer. It's depth-first search, and you never write the loop that tries alternatives: it's built in.
Worked Trace
Finding Tom's Grandchildren Step by Step
Watch it on grandparent of tom, W. The rule gives two goals: parent of tom, Y, then parent of Y, W. The first matching fact is parent of tom, bob, so Y is bob. Then parent of bob, W matches parent of bob, ann: W is ann, the first answer. Backtracking finds parent of bob, pat: W is pat, the second answer. Then Prolog backs up to the first goal. The next fact there is parent of tom, liz, so Y is liz. But no fact starts with liz, so that branch fails. No choices remain, so it ends with false: no more answers. Prolog's tracer shows this as four kinds of event: call, exit, redo, and fail.
Clause Order
Order Changes Answers and Termination
Because Prolog tries clauses top to bottom, and goals left to right, the order you write things changes the behavior, even the order of answers. With these good ancestor rules, ancestor of X, jim answers pat, tom, pam, then bob. The one-step clause comes first, and then Tom's side of the tree is searched before Bob's. Order can even decide whether a program finishes. The bad version calls itself with the same arguments before doing any work, so it never reaches a fact. Prolog eventually stops with a stack error. That's left recursion, and the cure is to do a step of real work first, and put the recursive goal last.
Quick Check
One Binding Applies Everywhere
Quick check, on unification. Unify h of X, f of X, with h of a, Y. Is it X equals a, and Y equals f of a? X equals a, and Y equals f of X? Or false? Pause, and decide. It answers X equals a, and Y equals f of a. The first arguments bind X to a. That binding applies everywhere, so the second arguments become f of a against Y, and Y takes the value f of a. Prolog shows bindings with their values filled in. Nothing clashes, so it doesn't fail: one variable, X, gets one value.
Lists and Recursion
Head, Tail and Recursive Predicates
A list sits in square brackets, and the empty list is just the brackets. The vertical bar splits a list into its head, the first item, and its tail, the rest. Prolog has no loops. Repetition is recursion: a base case that stops, and a recursive case that calls itself on a smaller problem. My member: X is a member of a list that starts with X. Or else, it's a member of the tail. The underscore is a blank we don't need. My length: the empty list has length zero. Otherwise, take the tail's length, M, and N is M plus one. My sum works the same way. And my append joins lists: the empty list plus L is L, and otherwise the head carries over.
Relations
Asking a Relation from Several Directions
My member of b, in a, b, c, answers true, and my member of X answers a, then b, then c. My length of a, b, c is three, and my sum of four, five, six is fifteen. Now my append. Appending one, two, to three answers X equals one, two, three. Ask what joins with three to make one, two, three, and it answers one, two. And with both lists unknown, it lists all three ways to split one, two. A function runs one way, but a Prolog relation can often be asked from several directions.
Arithmetic
Is Versus Equals for Calculation
Unification doesn't calculate. X equals two plus three binds X to the structure two plus three, not to five. To calculate, use is: X is two plus three evaluates the right side, and gives five. Equals, colon, equals compares the values of two expressions, so two plus three against five is true. But double equals checks whether two terms are identical, and two plus three isn't the term five. And less than or equal is written equals, less than: the reverse of most languages.
The Cut
Green Cuts and Red Cuts
The cut, written as an exclamation mark, commits to choices. Past a cut, Prolog won't backtrack into this predicate's other clauses. My max of X, Y is X if X is at least Y, and the cut says stop. Otherwise, the answer is Y. My max of three and five answers five, and my max of seven and two answers seven. But ask whether two is the maximum of seven and two, and it answers true. That's wrong. The first clause's head can't match: it needs the third argument to be seven. So Prolog skips the test and the cut, and reaches the second clause, which accepts any Y. A green cut only saves work: removing it changes no answer. A red cut, like this one, changes the meaning. Avoid it.
Quick Check
When the Max Query Correctly Fails
Quick check, with the same two clauses. What does my max of two, seven, two answer? True, because the cut is skipped again? False? Or an error? Pause, and decide. It answers false, which is correct this time. The first head matches: X is two, Y is seven, and the third argument is two, like X. But the test, two at least seven, fails. The second clause needs the second and third arguments to be equal: seven and two. They aren't, so it fails too. It is not an error, just a no.
Safer Alternatives
Explicit Conditions, If-Then-Else and Once
Safer alternatives exist. State both conditions explicitly, with no cut. Then safe max of seven, two, two correctly fails. Or use if then else: a condition, an arrow, then the then part, and a semicolon before the else. Sign of five, minus three, and zero gives positive, negative, and zero. And once of a goal keeps only its first answer: once of member X, in a, b, c, gives just a. So write it correctly without cuts first, and add a cut only to save work.
Workflow
Loading, Querying and Printing in SWI-Prolog
The workflow is a cycle: write a dot p l file, load it, ask queries, and check the answers. You start SWI-Prolog with the file, type a goal, and finish it with a full stop. Listing shows a predicate's clauses. Make reloads your files after you edit them. And halt leaves Prolog. To print, use write, nl for a new line, and format. Forall acts on every answer, and findall collects every answer into a list. This main prints Tom's grandchildren, ann and pat, then Bob's parents, tom and pam. Then it prints: tom has two children, bob and liz.
Debugging
Symptoms That Point to Causes
When something goes wrong, the symptom points to the cause. A singleton variables warning usually means a typo. Unknown procedure means a misspelled or undefined predicate. A query that hangs, or ends with a stack error, means left recursion or a missing base case. False when you expect an answer means a missing fact, or the wrong case. Strange syntax errors usually mean a missing full stop. And typing trace before a query shows every step.
Worked Program
Cheapest Route for a Delivery Robot
Now a worked program: routes on a delivery robot's map. Corridors, with travel times in minutes, are edge facts, and connected works in either direction. A route from X to X costs zero. Otherwise, step to a connected junction Z that hasn't been visited, find a route from Z, and add the costs. Backslash plus member stops revisits. And best collects every route with findall, sorts them by cost, and takes the cheapest. Asked for a route from m to g, the first answer is m, a, c, g, costing thirteen, because it takes the first corridor listed. Findall finds thirteen routes in all. And best answers m, b, a, d, c, g, costing ten minutes. The first answer isn't necessarily the best one.
Strengths and Limits
Where Prolog Fits in AI
Where does Prolog fit? Its programs read almost like the knowledge itself, and search is built in. It suits expert systems, parsing, and planning, and relations work in several directions. The limits: careless rules can loop. It can't learn from data or handle uncertainty, it's slower on number-heavy work, and it's less common today. But its ideas run throughout AI: facts and rules, unification, and backtracking, often combined today with learned components.
Recipe
Writing a Last-Item Predicate
A recipe for writing a predicate. Say it in words: X is the last item of a list. Find the base case: a list with exactly one item, X. Write the recursive case: drop the head, and look at the tail. Check the order: base case first, recursion last, no left recursion. Then test several queries. Last of X in a, b, c answers c, and in the one-item list a, it answers a.
Key Takeaways
Facts, Queries, Unification and Backtracking
To sum up. A Prolog program is facts and rules. You ask queries, and Prolog searches for values that make them true. Unification binds variables, and backtracking is built in: depth first, top to bottom, left to right. Repetition is recursion over lists split into head and tail, with the recursive goal last. And the cut can silently change meaning, so prefer explicit conditions, if then else, and once.
About Introduction to Artificial Intelligence at UPI Study
Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: AI vs Current Trends in CS and IT
Why take it here
Why students take Introduction to Artificial Intelligence with UPI Study
Where the credit goes
Universities that work with NCCRS
Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Prolog: A Logic-Based Programming Language for AI
How does Prolog answer a query?
What is the difference between = and is in Prolog?
What is a red cut in Prolog?
How does recursion over lists work in Prolog?
About the Introduction to Artificial Intelligence course
How many college credits is Introduction to Artificial Intelligence?
How much does Introduction to Artificial Intelligence cost and what is included?
Which universities accept UPI Study credits?
How long does Introduction to Artificial Intelligence take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.
69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →