Assignment 1

Lists & Operators in Prolog

Recursion, unification, backtracking, and custom operators

Language: SWI-PrologMarks: 305 Problems

What Was Given

Write a Prolog source file implementing 5 predicates. No template code was provided — you write everything from scratch.

#	Predicate	Task
1	`my_flatten/2`	Flatten a nested list into a flat list
2	`translate/2`	Convert digit list [3,5,1] to words [three,five,one]
3	Operators	Define operators so `joe was the head of the department` is valid Prolog
4	`subsum/3`	Find subset of list summing to a target
5	`my_between/3`	Generate integers in a range via backtracking

How to Compile & Run

Terminal Commands

# Navigate to the assignment directory
cd /Users/hansrajpatel/Dev-IITG/cs331/cs331_a1_170101025

# Start SWI-Prolog and load the file
swipl assignment1_170101025.pl

# Now you're in the Prolog REPL. Try queries:
?- my_flatten([a, b, [c, d], [e, [f]]], F).
?- translate([3, 5, 1, 3], L).
?- joe was What.
?- subsum([1, 2, 7, 3, 6], 6, P).
?- my_between(1, 5, 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.

Problem 1: my_flatten/2 — Flatten Nested Lists

What it does

Takes a list that may contain nested sublists and produces a single flat list with all elements.

% Example:
?- my_flatten([a, b, [c, d], [e, [f]]], F).
F = [a, b, c, d, e, f]

Code walkthrough

my_flatten([], []).                                % 1. Empty list → empty result
my_flatten([Head | Tail], FlatList) :-
    is_list(Head), !,                               % 2. Head IS a list?
    my_flatten(Head, FlatHead),                     %    Flatten the head recursively
    my_flatten(Tail, FlatTail),                     %    Flatten the tail recursively
    append(FlatHead, FlatTail, FlatList).            %    Concatenate both results
my_flatten([Head | Tail], [Head | FlatTail]) :-
    \+ is_list(Head),                               % 3. Head is NOT a list (atom/number)
    my_flatten(Tail, FlatTail).                     %    Keep Head, recurse on Tail

Line-by-line explanation

Base case: An empty list flattens to an empty list. Recursion stops here.
Head is a list: If is_list(Head) succeeds, we flatten Head separately, flatten Tail separately, then append them. The ! (cut) prevents Prolog from trying clause 3 after clause 2 succeeds.
Head is an atom: If Head is not a list, keep it in the result and recurse on the Tail.

Viva: Why the cut?

Without the cut, if is_list(Head) succeeds in clause 2, Prolog would also try clause 3 on backtracking (since \+ is_list(Head) would fail, but the pattern [Head|Tail] still matches). The cut is a green cut — it removes redundant work without changing the set of answers.

Problem 2: translate/2 — Digit-to-Word Translation

What it does

?- translate([3, 5, 1, 3], L).
L = [three, five, one, three]

Code walkthrough

% Lookup table: digit → word
means(0, zero).  means(1, one).  means(2, two).
means(3, three). means(4, four). means(5, five).
means(6, six).   means(7, seven). means(8, eight).
means(9, nine).

% Recursive translation
translate([], []).                                  % Empty → empty
translate([Num | RestNums], [Word | RestWords]) :-
    means(Num, Word),                               % Look up Num in the table
    translate(RestNums, RestWords).                  % Recurse on rest

Viva: How does the lookup work?

means(Num, Word) uses unification. If Num=3, Prolog searches all means/2 facts until it finds means(3, three), which unifies Word with three.
This is the "process head, recurse on tail" template — the most common Prolog pattern.

Problem 3: Custom Operators

What it does

Define operators so natural language-like queries work:

?- joe was the head of the department.
true.

?- Who was the head of the department.
Who = joe

Code walkthrough

:- op(300, xfx, was).    % 'was' is infix, non-associative, precedence 300
:- op(200, xfx, of).     % 'of' is infix, precedence 200 (binds tighter)
:- op(100, fx, the).      % 'the' is prefix, precedence 100 (tightest)

the(X, the(X)).           % 'the X' wraps X into the(X)

joe was the head of the department.  % A fact using our operators

Viva: How does operator precedence work?

Lower number = higher priority (binds tighter). So the (100) binds before of (200) before was (300).
xfx = infix, non-associative (can't chain: a was b was c is invalid)
fx = prefix (like unary minus: the head)
The parsing: joe was ((the head) of (the department))

Problem 4: subsum/3 — Subset Sum

What it does

?- subsum([1, 2, 7, 3, 6], 6, P).
P = [1, 2, 3] ;
P = [6] ;
P = [3, 3]   % (if duplicates exist)

Code walkthrough

subsum(_, 0, []).                            % Base: sum=0, take nothing
subsum([Head | Tail], Sum, [Head | Part]) :- % CHOICE A: Include Head
    Sum > 0,
    Remaining is Sum - Head,
    Remaining >= 0,
    subsum(Tail, Remaining, Part).
subsum([_ | Tail], Sum, Part) :-             % CHOICE B: Skip Head
    Sum > 0,
    subsum(Tail, Sum, Part).

Viva: How does backtracking find all subsets?

For each element, Prolog creates a choice point between "include" (clause 2) and "skip" (clause 3).
Prolog first tries including. If the search succeeds, it returns a solution. When you press ;, it backtracks and tries skipping instead.
This explores all 2^N possible subsets. No explicit loop needed — backtracking IS the loop.
Sum > 0 and Remaining >= 0 are pruning conditions that cut off impossible branches early.

Problem 5: my_between/3 — Integer Generator

What it does

?- my_between(1, 5, X).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5

Code walkthrough

my_between(Low, High, Low) :-    % Yield Low itself
    Low =< High.
my_between(Low, High, X) :-      % Then try Low+1
    Low < High,
    Next is Low + 1,
    my_between(Next, High, X).

Viva: Why two clauses?

Clause 1 yields the current Low value. Clause 2 increments and recurses. On backtracking, Prolog tries clause 2, generating the next integer.
This is the generator pattern — produces values lazily via backtracking instead of building a list eagerly.
Note =< (Prolog's "less-or-equal") — NOT <= which means something different in Prolog.

Full Expected Output

?- my_flatten([a, b, [c, d], [e, [f]]], F).
F = [a, b, c, d, e, f].

?- my_flatten([[1, [2]], 3, [4, [5, [6]]]], F).
F = [1, 2, 3, 4, 5, 6].

?- translate([3, 5, 1, 3], L).
L = [three, five, one, three].

?- joe was the head of the department.
true.

?- Who was the head of the department.
Who = joe.

?- subsum([1, 2, 7, 3, 6], 6, P).
P = [1, 2, 3] ;
P = [6] ;
false.

?- my_between(1, 5, X).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5.

Key Concepts for Viva

Concept	Where Used	One-liner Explanation
Unification	translate (`means(Num, Word)`)	Pattern matching that binds variables to make terms equal
Recursion	All 5 problems	Base case (empty list) + recursive case (head+tail)
Backtracking	subsum, my_between	Prolog automatically tries alternatives at choice points
Cut (!)	my_flatten	Commits to current clause, prevents backtracking
Operators	was/of/the	Custom syntax via `:- op(Prec, Type, Name)`
`is` vs `=`	subsum, my_between	`is` evaluates arithmetic; `=` unifies structurally