Write a Prolog source file implementing 3 predicates that demonstrate mastery of the cut operator and negation as failure. No template code was provided — you write everything from scratch.
| # | Predicate | Marks | Task |
|---|---|---|---|
| 1 | split/3 | 10 | Split a list of numbers into positives (including zero) and negatives — two versions: one with cut, one without |
| 2 | route/3 | 10 | Find train routes between Indian cities (NE India) with cycle prevention |
| 3 | number_of_parents/2 | 10 | Identify and fix a buggy predicate using negation as failure instead of cut |
# Navigate to the assignment directory cd /Users/hansrajpatel/Dev-IITG/cs331/cs331_a2_170101025/solution # Start SWI-Prolog and load the file swipl assignment1_170101025.pl # Now you're in the Prolog REPL. Try queries: ?- split([3, -1, 0, 5, -2], P, N). ?- split_cut([3, -1, 0, 5, -2], P, N). ?- split_nocut([3, -1, 0, 5, -2], P, N). ?- route(aizawl, guwahati, R). ?- number_of_parents(adam, X). # Press ; after each result to get more solutions # Press . or Enter to accept current solution # Type halt. to exit Prolog
Prolog doesn't have a separate compile step — swipl file.pl loads and compiles it in one step. You interact via the ?- query prompt.
Takes a list of numbers and splits it into two lists: positives (including zero) and negatives.
% Example: ?- split([3, -1, 0, 5, -2], P, N). P = [3, 0, 5], N = [-1, -2]
split_cut([], [], []). % 1. Base case: empty list → two empty lists split_cut([H | T], [H | Pos], Neg) :- H >= 0, !, % 2. H is non-negative? Commit (cut)! split_cut(T, Pos, Neg). % Put H in Pos list, recurse on T split_cut([H | T], Pos, [H | Neg]) :- split_cut(T, Pos, Neg). % 3. Otherwise H is negative → put in Neg list
H >= 0. If this succeeds, the ! (cut) fires, which commits Prolog to this clause. H is placed in the positives list, and we recurse on the tail T. The cut prevents Prolog from ever trying clause 3 for this particular H.H >= 0 failed, or the cut prevented reaching here), this clause handles the remaining case: H must be negative, so it goes into the negatives list. Note there is no explicit guard like H < 0 — the cut in clause 2 already ensured we only reach clause 3 when H is negative.split_nocut([], [], []). % 1. Base case: same as above split_nocut([H | T], [H | Pos], Neg) :- H >= 0, % 2. H is non-negative? split_nocut(T, Pos, Neg). % Put H in Pos, recurse split_nocut([H | T], Pos, [H | Neg]) :- H < 0, % 3. H is negative? (explicit guard!) split_nocut(T, Pos, Neg). % Put H in Neg, recurse
H >= 0 succeeds, H goes into positives and we recurse. However, without a cut, Prolog remembers that clause 3 is still an alternative.H < 0. Without it, after Prolog finds a solution via clause 2, backtracking would try clause 3 and incorrectly place a non-negative number into the negatives list.% Default: delegates to the cut version
split(Numbers, Positives, Negatives) :-
split_cut(Numbers, Positives, Negatives).
H >= 0 succeeds, the ! prunes the choice point for clause 3. Prolog will never try putting a non-negative H into the negatives list.split_cut is a green cut because both versions produce identical results.H >= 0 test but kept the cut, it would become a red cut (the third clause would be unreachable regardless of H's value).H < 0 guard, querying split_nocut([3], P, N) would give both P=[3], N=[] and P=[], N=[3] — wrong!Given direct train connections between cities in Northeast India, find a route (list of towns visited) between any two cities.
% Example: ?- route(aizawl, guwahati, R). R = [aizawl, agartala, silchar, haflong, lumding, nagaon, guwahati]
directTrain(guwahati, tezpur). % Guwahati ↔ Tezpur directTrain(nagaon, guwahati). % Nagaon ↔ Guwahati directTrain(lumding, nagaon). % Lumding ↔ Nagaon directTrain(haflong, lumding). % Haflong ↔ Lumding directTrain(silchar, haflong). % Silchar ↔ Haflong directTrain(agartala, silchar). % Agartala ↔ Silchar directTrain(aizawl, agartala). % Aizawl ↔ Agartala
These facts form a linear chain of 7 NE Indian cities: Aizawl → Agartala → Silchar → Haflong → Lumding → Nagaon → Guwahati, with Tezpur branching off Guwahati.
connected(A, B) :- directTrain(A, B). % Forward direction connected(A, B) :- directTrain(B, A). % Reverse direction
The problem states that trains run both ways. Instead of doubling the facts, we write connected/2 which checks both directions. If directTrain(guwahati, tezpur) exists, then both connected(guwahati, tezpur) and connected(tezpur, guwahati) succeed.
route(From, To, Route) :-
route_helper(From, To, [From], RevRoute), % Start with From already visited
reverse(RevRoute, Route). % Helper builds route in reverse
This is a thin wrapper. It initializes the visited list with [From], calls the recursive helper, then reverses the result (because the helper accumulates the path in reverse order for efficiency).
route_helper(To, To, Visited, Visited). % 1. Destination reached → done route_helper(From, To, Visited, Route) :- connected(From, Next), % 2. Find a neighbor of From \+ member(Next, Visited), % 3. NOT already visited? Good. route_helper(Next, To, [Next | Visited], Route).% 4. Recurse from Next
From) equals the destination (To), unify the Route with the current Visited list. We are done.connected(From, Next) finds a city directly connected to From. On backtracking, Prolog will try other neighbors.\+ member(Next, Visited) uses negation as failure to ensure we have not already visited Next. If Next is in the Visited list, this goal fails and Prolog backtracks to try a different neighbor.\+ member prevents cycles: \+ is Prolog's "negation as failure" operator. \+ member(Next, Visited) succeeds only if member(Next, Visited) fails — i.e., Next has not been visited. This ensures we never revisit a city.[Next | Visited]. This is O(1) and efficient, but builds the path backwards. reverse/2 flips it to the correct order at the end.connected/2 is bidirectional, without the visited list check Prolog would endlessly bounce between two neighbors: Guwahati → Nagaon → Guwahati → Nagaon → ... until it runs out of stack. The visited list is essential for termination in any graph with bidirectional edges.This was given in the problem statement and is intentionally broken:
% BUGGY VERSION (from the problem sheet) number_of_parents(adam, 0) :- !. % adam has 0 parents, cut number_of_parents(eve, 0) :- !. % eve has 0 parents, cut number_of_parents(X, 2). % everyone else has 2
The intent is: adam and eve have 0 parents, everyone else has 2. But there are two problems:
X in number_of_parents(X, 2) matches any atom — including adam and eve. So the query number_of_parents(adam, 2) succeeds by skipping the first clause and unifying directly with the third clause. This is wrong: adam should not have 2 parents.number_of_parents(adam, X), Prolog tries clause 1 first, which succeeds with X = 0 and the cut prevents trying clause 3. So you get the right answer for that query. But if you ask number_of_parents(adam, 2) directly, Prolog tries clause 1 (fails because 2 ≠ 0), tries clause 2 (fails because adam ≠ eve), then tries clause 3 (succeeds because X unifies with adam and 2 matches 2). The cut in clause 1 never fired because clause 1 never succeeded!% FIXED VERSION number_of_parents(adam, 0). % 1. adam has 0 parents (no cut needed) number_of_parents(eve, 0). % 2. eve has 0 parents (no cut needed) number_of_parents(X, 2) :- X \= adam, % 3. X must NOT be adam X \= eve. % X must NOT be eve
number_of_parents(adam, 0) succeeds by unification. No cut is needed.number_of_parents(eve, 0) succeeds by unification.X \= adam, X \= eve explicitly excludes adam and eve using structural inequality (\=). Now number_of_parents(adam, 2) will fail at the X \= adam check, which is the correct behavior.?- number_of_parents(adam, X). X = 0 % Correct: adam has 0 parents ?- number_of_parents(adam, 2). false. % Correct: adam does NOT have 2 parents ?- number_of_parents(john, X). X = 2 % Correct: john (not adam/eve) has 2
X in the third clause is completely unconstrained — it unifies with anything, including adam and eve. The cut in clauses 1 and 2 only helps when those clauses are entered and succeed. For the query number_of_parents(adam, 2), clause 1 fails at head unification (0 ≠ 2), so the cut never fires, and clause 3 happily matches.X \= adam succeeds only when X cannot unify with adam. This is a hard guard that works regardless of which query is asked or in what order clauses are tried. It is declaratively correct: "X has 2 parents if X is not adam and X is not eve."\= operator: X \= Y is shorthand for \+ X = Y (negation of unification). It succeeds when X and Y cannot be unified. This is Prolog's standard "not equal" for terms.--- split (with cut) --- ?- split_cut([3, -1, 0, 5, -2], P, N). P = [3, 0, 5], N = [-1, -2]. ?- split_cut([], P, N). P = [], N = []. ?- split_cut([-5, -3], P, N). P = [], N = [-5, -3]. --- split (without cut) --- ?- split_nocut([3, -1, 0, 5, -2], P, N). P = [3, 0, 5], N = [-1, -2]. --- split (default wrapper) --- ?- split([3, -1, 0, 5, -2], P, N). P = [3, 0, 5], N = [-1, -2]. --- route/3 --- ?- route(aizawl, guwahati, R). R = [aizawl, agartala, silchar, haflong, lumding, nagaon, guwahati]. ?- route(guwahati, aizawl, R). R = [guwahati, nagaon, lumding, haflong, silchar, agartala, aizawl]. ?- route(guwahati, tezpur, R). R = [guwahati, tezpur]. ?- route(lumding, tezpur, R). R = [lumding, nagaon, guwahati, tezpur]. --- number_of_parents/2 (fixed) --- ?- number_of_parents(adam, X). X = 0. ?- number_of_parents(eve, X). X = 0. ?- number_of_parents(john, X). X = 2. ?- number_of_parents(adam, 2). false.
| Concept | Where Used | One-liner Explanation |
|---|---|---|
Cut (!) | split_cut (clause 2) | Commits to current clause, prunes alternative clauses for this call |
| Green cut vs Red cut | split_cut | Green = no change in answers (optimization only); Red = changes meaning |
Negation as failure (\+) | route_helper, number_of_parents | Succeeds when the enclosed goal fails; Prolog's way of expressing "not" |
\= (not unifiable) | number_of_parents (fixed) | Shorthand for \+ X = Y; true when X and Y cannot be unified |
| Cycle prevention | route_helper (visited list) | Track visited nodes to avoid infinite loops in bidirectional graphs |
| Accumulator pattern | route_helper (Visited list) | Build result incrementally via an extra argument; reverse at the end |
| Bidirectional wrapper | connected/2 | Two clauses checking directTrain(A,B) and directTrain(B,A) |
| Backtracking | route (trying different neighbors) | Prolog automatically explores alternatives at choice points |
| Explicit guards vs cut | split_nocut vs split_cut | Without cut, each clause must explicitly state its condition to be correct |