Prolog Foundations

Why this matters

Suppose we have a family database. We could write a different function for “find children” and “find parents,” or describe the parent relationship once and ask it different questions. Prolog lets us do the latter.

🎯 You will learn to

• Apply facts to record a relationship with a precise argument order.
• Analyze the bindings returned by forward and reverse queries.

The big picture

This is the first of two tutorials based on the CS 131 logic-programming lectures, homework, quizzes, and past finals. Allow 75–100 minutes for these eight steps. You should know variables, function calls, and basic recursion in one language; no Prolog or installation is needed.

A knowledge base contains facts and rules. A query asks the inference engine to prove a goal using that knowledge base. Here is one fact:

parent(tom, bob).

Here we define it to mean Tom is a parent of Bob. Prolog does not supply that English meaning; we document the argument order and use it consistently. parent(bob, tom) asks a different question. The period ends a clause; % starts a comment.

tom and bob are atoms: names for specific things. A name beginning with an uppercase letter, such as Child, is a variable whose value Prolog can discover.

Thinking time

With the starter’s single fact, predict parent(Who, bob): does it find Who = tom, fail, or complain that Who has no value? Write a prediction and one reason in a % comment before running it.

Enter the goal in Query ?-, then select Run. Type the goal itself; the prompt is already supplied. A final period is optional here. This workspace requests successive answers for you; it does not require the semicolon key used by some Prolog consoles.

Facts are tried from top to bottom. With several matching facts, this workspace displays each answer in that order. A successful query with no variables reports true; if its search finishes without a proof, it reports false.

Try parent(ann,tom) before adding any facts. Failure means this database cannot prove the relationship, not that it has settled who Ann’s parents are in the real world. This is the closed-world assumption applied to this program’s knowledge.

Your task

Keep the existing fact. Extend the database to say that Bob is a parent of Ann and of Pat, with no other parent relationships. Then investigate parent(bob, Child), parent(Parent, ann), and parent(Parent, Child). Explain why one database answers all three.

Use Test My Work to check the task. Hints provide increasing help; the knowledge check follows Next. Mistakes are useful evidence: compare the relationship you intended with the one your arguments actually describe.

The course uses SWI-Prolog. This workspace uses Tau Prolog and supports the course features exercised here; implementation-specific extensions and error wording can differ. Program text runs in a browser worker.

Why this matters

A query can match an entire structured value, not just a name. Once you can track that matching, nested data and repeated variables stop looking like special cases.

🎯 You will learn to

• Analyze unification of compound terms and repeated variables.
• Apply anonymous variables when individual names do not need to agree.

Names, structures, and mappings

A term can be an atom, a number, a variable, or a compound such as pet(dog, koda). A compound has a functor (pet) and an arity (two arguments). pet/2 names that functor and arity; pet/3 has a different shape. A nested term might be owns(carey, pet(dog, koda)).

Unification asks whether two terms can be made identical by consistently binding variables. In the Query field, try:

owns(carey, pet(dog, koda)) = owns(Person, pet(Kind, Name))

The mappings are Person = carey, Kind = dog, and Name = koda. No arithmetic or function call happens inside these terms.

An uppercase name or a name beginning with _ is a variable. Lowercase x is an atom. Repeated occurrences of X in one clause share a binding. Each plain _ is a fresh anonymous variable; two occurrences of _Name still share one variable. Variables in separate clauses are independent.

Thinking time

Predict these two queries separately: pair(X,X) = pair(dog,cat) and pair(_,_) = pair(dog,cat). Which can succeed? Record the bindings that would be required, then run both.

Your task

The worked fact pet_name(pet(_, Name), Name). extracts a name while ignoring the species. A fact with variables describes every instance of its pattern.

Define same_species(Pet1, Pet2). A pattern fact is sufficient; derive its structure from the worked example. It should relate two pet(Species, Name) terms exactly when their species unify; their names may differ. It must work when a species is unknown, too. Do not enumerate individual dogs and cats.

Try matching two dogs with different names, a dog and a cat, and same_species(pet(Kind, ada), pet(cat, max)). Explain which positions must share a variable and which can vary independently.

Why this matters

Facts give us individual relationships. Rules let us derive new relationships without recording every case by hand, and shared variables specify how those facts connect.

🎯 You will learn to

• Apply conjunction to connect two relationships through one intermediate value.
• Analyze the difference between a rule body and alternative clauses.

From facts to rules

Consider this worked rule:

has_child(Person) :- parent(Person, Child).

Read :- as “if”: Person has a child if a matching parent fact exists. The part before :- is the head; the part after it is the body. The body contains goals to prove. The variable Child need not appear in the head: finding some matching child is enough.

A comma means and, with goals tried left to right. The same variable name connects occurrences within the clause. The engine gives variables fresh identities each time it tries a clause, so separate calls do not share a hidden global Child.

Separate clauses offer alternatives. These say someone can play if they like chess or they like go:

can_play(Person) :- likes(Person, chess).
can_play(Person) :- likes(Person, go).

A semicolon also expresses alternatives inside a body: (likes(Person,chess); likes(Person,go)). Parentheses make the grouping clear. Someone satisfying both alternatives can have two proofs; Prolog does not automatically remove duplicates.

Thinking time

The starter defines has_child/1. Predict whether has_child(Person) will report Bob once or twice. Run it, then connect each reported binding to the parent fact that proves it.

Your task

Define grandparent(Grandparent, Grandchild) using parent/2. The person connecting the two parent relationships must be the same person. A grandparent is exactly two parent links away, not any ancestor.

The starter’s fail goal always fails; it is a placeholder to replace. Keep the supplied facts. Try grandparent(tom, Who) and the reverse query grandparent(Who, ann). Before testing, explain why Tom should not be his own grandparent and why Bob should not count as Tom’s grandchild.

Why this matters

A relation can have the right possible answers and still surprise you about which answer appears first. Following the pending goals and variable mappings explains the course’s execution-tracing questions.

🎯 You will learn to

• Analyze clause order, goal order, and binding rollback during resolution.
• Repair a relation and predict its complete ordered answer sequence.

How a proof is built

Resolution repeatedly takes the leftmost pending goal, tries clauses from top to bottom, and unifies the goal with a clause head. A matching fact discharges that goal. A matching rule replaces it with its body goals, ahead of the remaining work. No pending goals means one complete proof.

On failure, Prolog backtracks to the most recent available alternative and undoes bindings made since that choice. A clause that does not unify is skipped; it does not end the whole search. This is depth-first search through possible proofs.

For example, suppose parent(tom,bob), parent(tom,mia), and parent(mia,ren) are the only facts. In parent(tom,P), parent(P,C), the first goal initially binds P = bob. If Bob has no child, the second goal fails. Prolog returns to the first goal, tries P = mia, and then discovers C = ren. The failed attempt’s Bob binding does not stick.

Thinking time

Read the directed link/2 facts. On paper, find every place reachable from a by exactly two links. Work through each possible intermediate place in fact order. Is d reached once or twice?

Run the starter’s two_hops(a, End). Its second goal follows the final link in the wrong direction. A mismatch between your prediction and the output is the bug to diagnose.

Your task

Repair two_hops(Start, End). Keep the facts in their given order and search the first link before the second link. Report one answer for each two-link proof, including duplicates; do not sort or remove duplicates.

A direct a-to-b link does not qualify as a two-link route. Compare your repaired program with the trace below after writing your prediction.

Finally, swap the two body goals temporarily and predict whether the answer sequence changes. If it stays the same, compare the intermediate choices: could the arrangement of these facts explain that coincidence? Restore the specified goal order before testing. Goal order is an execution decision even when the finite relation has the same possible endpoint pairs.

Why this matters

“Exactly two links” is useful for grandparents. “Any positive number of links” needs recursion, and in Prolog the order of recursive work can decide whether the search ever finishes.

🎯 You will learn to

• Apply a base case and recursive case to define ancestry.
• Evaluate whether recursive goals make progress before calling themselves.

One link or more links

An ancestor is either a direct parent, or a parent of somebody who is an ancestor. Those are two alternative clauses. For this exercise, the family is finite and has no cycles; a person is not their own ancestor.

The direct-parent case is already written. In the recursive case, consuming one parent link before recurring moves the search down this finite family. The starter instead recurs on the same unconstrained starting person before consuming that link.

Thinking time

Predict ancestor(tom, Person) in the starter: no answers, some answers followed by unfinished search, or all answers followed by normal completion? Explain which recursive subgoal fails to make progress.

Run it. The workspace bounds search so an unfinished proof search reports a limit instead of requiring an endless wait. Stop also cancels a running program. A limit is not the same as false: the search has not finished establishing whether more answers exist.

The direct clause can produce answers before the bad recursive branch keeps expanding. Seeing a correct early answer does not establish termination.

Your task

Repair ancestor/2 so that a parent goal constrains the intermediate person before recursion. Keep the direct-parent clause first and the supplied facts unchanged. It must find every ancestor–descendant pair reachable by one or more links and terminate on this family, including when there is no match.

Predict the complete answers for ancestor(tom, Person), keeping the direct-parent clause first and exploring parent facts in their given order.

Then try ancestor(Person, lena) and ancestor(pat, Person). Explain why “move the recursive clause last” alone would not fix a body that recurs before making progress. With cyclic facts, even the repaired rule would need additional cycle handling.

Why this matters

A list is structured data, so the unification rules you already know still apply. Head–tail patterns expose part of that structure without an index or a loop.

🎯 You will learn to

• Analyze the difference between one element and the remaining list.
• Apply a list pattern that selects a position without restricting later elements.

One element and the rest

[] is an empty list. [chess, uno, go] is a list of three atoms. Lists can contain numbers or nested lists, too.

The pattern [Head | Tail] separates the first element from the remaining list. For [chess, uno, go], Head = chess and Tail = [uno, go]. For [chess], the tail is []. The empty list cannot match a head–tail pattern.

[First, Second | Rest] requires at least two elements. It differs from [First, Second], which requires exactly two. A variable in one element position can bind to a whole nested list.

Thinking time

Predict [Head | Tail] = [[chess,uno],go]. Is Head chess or [chess,uno]? Is Tail go or [go]? Write both bindings, then run the query and check whether the outer list structure stays intact.

The worked first_item/2 fact shows how a pattern connects a list and a selected element. Query it with a known list or a known item.

Your task

Define second_item(Item, List). A pattern fact is sufficient. It must succeed exactly when List has at least two elements and Item unifies with its second element. Later elements must not be dropped or constrained, and a nested second element must stay intact.

Try lists with zero, one, two, and four elements. Then query second_item(uno, [chess, X, go]) and explain how the same fact fills a missing list element. We will add recursion next; this task only needs a pattern.

Why this matters

The second-item pattern visits one fixed position. To ask whether a value occurs anywhere, combine head–tail matching with a recursive relation that makes the list smaller.

🎯 You will learn to

• Apply structural recursion to enumerate list members.
• Analyze why membership can check values or generate them, including duplicates.

Two ways to be a member

An item is in a list if it matches the head, or if it occurs in the tail. The first case is a pattern fact; the second case is a rule.

The starter supplies the head case. On [chess,uno,go], it can currently discover chess but cannot yet reach later elements. Recursing on the tail gives the same question a smaller list. On a finite list, eventually there is no head to match.

There is no success fact for membership in []: no item belongs to an empty list. A base case can be success for one relation and failure for another; choose it from the meaning of the relation.

Thinking time

Once the recursive case is complete, predict list_member(Game, [uno,chess,uno]). Does it report uno twice, remove the repeat, or fail because a value repeats? Commit to the full sequence, then compare after your repair.

Your task

Complete list_member(Item, List). It must enumerate each element of a finite list from head to tail, with one proof per occurrence. It must also check known values and handle a nested list as one element. Keep the supplied head clause first.

Try list_member(uno,[chess,uno]), list_member(go,[]), and list_member(Item,[[a,b],c]). Then explain why the recursive call must use the tail, rather than the original list or its head.

The course’s is_member/2 has this same structure. Names can differ while the underlying relation stays the same. Later we will use the library’s member/2 once this mechanism is no longer a black box.

Why this matters

Now use the pieces together. A small recommendation relation needs structured facts, recursive relationships, and membership, but it can still answer several questions without separate search functions.

🎯 You will learn to

• Create a relation by composing ancestry and list membership.
• Evaluate a solution with missing-answer and extra-answer counterexamples.

Your brief

Tom is planning a game night. A guest is eligible if they are a descendant of Tom by one or more parent links. A game is a match if it appears in both Tom’s favorites and that guest’s favorites. Tom is the host, so he is not an eligible guest.

The starter provides the family, favorite lists, and the two recursive relations you already studied. Define game_guest(Guest, Game) using those facts and relations. Preserve the supplied data. The rule must work whether Guest, Game, both, or neither is already known. Report every matching guest–game pair; their order is not part of this task.

Thinking time

Before writing code, list the expected pairs from the data. Which of these belong, and which fail a condition: Tom’s own games, Pat’s go, Bob’s uno, and Zoe’s uno? Explain each decision from the brief rather than from the code you hope to write.

From brief to relation

Write a % comment that names the conditions a pair must satisfy. Then implement them. No new language construct is needed: connect the conditions using shared variables and already-known predicates. This time the editor gives you no partial body to fill in.

Investigate three modes: game_guest(Guest, Game), game_guest(bob, Game), and game_guest(Guest, uno). A correct definition must also reject pairs that fail one condition. Choose a counterexample that checks eligibility, and a different counterexample that checks a game preference.

For a final ungraded experiment, give Lena a favorite that Tom also likes. Predict the new answer before running it; then restore the supplied data before testing.

After this session

Without looking at the code, explain how a query becomes pending goals, how unification creates mappings, and how backtracking revisits choices. Tomorrow, reconstruct membership on a blank page and trace one grandparent query before checking your work.

Continue with Prolog Lists and Search for relational list construction, arithmetic, negation, accumulators, and a search task. Take a break between the two sessions; bring back these core relations from memory.