Table of Contents

Archive eFLP 2011: Prolog Tutorial 1: Basic Prolog

Initial code

Pasebin code with latest changes 

connected(bond_street,          oxford_circus,        central).
connected(oxford_circus,        tottenham_court_road, central).
connected(bond_street,          green_park,           jubilee).
% Isn't there a missing connection?
% Yes, indeed! From 'green_park' to 'charing_cross'...
connected(green_park,           piccadilly_circus,    piccadilly).
connected(piccadilly_circus,    leicester_square,     piccadilly).
connected(green_park,           oxford_circus,        victoria).
connected(oxford_circus,        piccadilly_circus,    bakerloo).
connected(piccadilly_circus,    charing_cross,        bakerloo).
connected(tottenham_court_road, leicester_square,     northern).
connected(leicester_square,     charing_cross,        northern).

Objectives

  1. Install Prolog
  2. Learn the syntax: Add the missing underground link into the initial code.1)
  3. Basic predicates: Define the nearby/2 predicate = stations on the same line, distant at most 2 stops.2)
  4. Recursion: Define reachable/2 = stations reachable via any number of intermediate stops, not necessarily on the same line.3) You may have to add connected('Mustek', 'Muzeum', 'A'). fact for testing purposes.
  5. Debug trace: Try debugging the code to see the order of execution.

Tutorial slides 4)

Prolog Tutorial 2: Lists

Initial code

Pasebin code with latest changes 

connected(bond_street,          oxford_circus,        central).
connected(oxford_circus,        tottenham_court_road, central).
connected(bond_street,          green_park,           jubilee).
connected(green_park,           charing_cross,        jubilee).
connected(green_park,           piccadilly_circus,    piccadilly).
connected(piccadilly_circus,    leicester_square,     piccadilly).
connected(green_park,           oxford_circus,        victoria).
connected(oxford_circus,        piccadilly_circus,    bakerloo).
connected(piccadilly_circus,    charing_cross,        bakerloo).
connected(tottenham_court_road, leicester_square,     northern).
connected(leicester_square,     charing_cross,        northern).
 
reachable(X,Y) :- connected(X,Y,_).
reachable(X,Y) :- connected(X,Z,_), reachable(Z,Y).

Objectives

  1. Understand the unification algorithm
  2. Recall the list representation: Relate LISP's cons and nil to Prolog's dot and [] functions
  3. Learn how to construct lists: Define predicate journey/3 which returns a list of visited stations on a journey.5)
  4. Parse lists: Define your own implementation of the member/2 predicate.6)
  5. Limitations of Prolog lists: Understand how append/3 works and implement your own my_append/3 predicate.

Tutorial slides7)

Prolog Tutorial 3: Code efficiency

  1. Arithmetics: Learn the difference between X = 1 + 1 and X is 1 + 1.
  2. Programming challenge: As an experienced Prolog programmer, define factorial.
  3. Benefits of tail recursion:
    1. Compare and contrast two exemplary implementations.8)
    2. Evaluate efficiency of both implementations by computing 10000!: time(factorial(10000,_))
  4. Understand the cut: Play with the supplied code. 9)
  5. Use cut in your code: With and without the cut, define max/3 = maximum of two numbers.10)

Tutorial slides11)

Check you understand: Compare the factorial_1 predicate with factorial_3 that uses the cut. What difference in behaviour can you spot? 

factorial_3(1,1):- !.
factorial_3(N,F):-
  NN is N - 1,
  factorial_3(NN,FF),
  F is N * FF.

Prolog Tutorial 4: Searching a graph

Initial code

h(a,b). h(a,c). h(a,d).
h(b,e). h(b,f). h(b,g).
h(c,h). h(c,i).
h(d,j). h(d,k). h(d,l).
h(e,m). h(e,n).
h(f,n).
h(g,p). h(g,q). h(g,r). h(i,i).
h(i,s). h(i,t).
h(j,t).
h(k,u). h(k,v).
h(l,w). h(l,x).
h(n,y).
h(t,z). h(t,z).
h(p,a).
 
goal(f).
goal(r).
goal(u).

Objectives

  1. Implement a basic depth-first-search (DFS) algorithm.12)
  2. Avoid infinite looping by creating a closed list.13)
  3. Implement a bredth-first-search (BFS) algorithm. 14)

Pastebin code with solutions

Prolog Tutorial 5: Searching a state-space

Initial code

% Obstacles - find path from initial to goal position on 8x8 board
% Possible moves: up, down, left, right
% Position of obstacles defined by obstacle/1
step(1, 0, r).
step(0, 1, u).
step(-1, 0, l).
step(0, -1, d).
 
obstacle(pos(2,1)).
obstacle(pos(2,2)).
obstacle(pos(3,3)).
obstacle(pos(4,3)).
obstacle(pos(3,4)).
 
correct(pos(X,Y)) :-
  X > 0, Y > 0, X =< 8, Y =< 8,
  not(obstacle(pos(X,Y))).

Objectives

  1. Implement a BFS:15) Find a path from initial to goal position on 8×8 board s.t:
    % Using compound term state: state(pos(X,Y),D,F,Moves)
% search(InitState, GoalPosition, Solution) 
?- search([state(pos(1,1),0,0,[])], pos(4,1), S).

Prolog Tutorial 6: Constraint logic programming

Initial code

Pastebin code with latest changes 

% alldiff([A,B,C,D,...]): All A,B,C,D,... are mutually different.
alldiff([X|Tail]) :- ...


% Plots the given matrix.
plot([]).
plot([[]|T]) :- nl, plot(T).
plot([[X|T1]|T2]) :- write(X), plot([T1|T2]).


% Numbers 1..4 are assigned to all variables in the given list.
numbers([]).
numbers([X|Tail]) :-
  member(X,[1,2,3,4]),
  numbers(Tail).


% Solves the SUDOKU and gives the answer.
sudoku([[A1,B1,C1,D1],[A2,B2,C2,D2],[A3,B3,C3,D3],[A4,B4,C4,D4]]) :-
  % Phase 1: Assign 1..4 to variables A1..D4 randomly. 
  %          predicate numbers(...) may help! 
  
  % Phase 2: Check, whether the solution is a valid SUDOKU.
  %          predicate alldiff(...) may help!

Objectives

  1. Study the theory: Sudoku on Wikipedia.
  2. Train your skills: Define a helper predicate alldiff/1.
  3. Naïve Sudoku: Implement a naïve implementation of Sudoku generator and solver in a generate-and-test fashion. Measure computation time.
  4. Optimize: Push the test conditions up inbetween the generate calls to increase the efficiency. Measure the computation time.
  5. CSP: Return to the naïve implementation and convert it into a CSP problem. Measure the computation time.
1)
Solution from pastebin: 
connected(green_park,           charing_cross,        jubilee).
2)
Solution from pastebin: 
nearby(X,Y) :- connected(X,Y,_).
nearby(X,Z) :- connected(X,Y,L), connected(Y,Z,L).
3)
Solution from pastebin: 
reachable(X,Y) :- connected(X,Y,_).
reachable(X,Y) :- connected(X,Z,_), reachable(Z,Y).
4)
Archived version in a PDF file
5)
Firstly print the list to STDOUT (pastebin):
reachable(X,Y) :- connected(X,Y,_).
reachable(X,Y) :- connected(X,Z,_), write(X), nl, reachable(Z,Y).
The add the third argument which creates a list (pastebin): 
reachable(X,Y, [Y]) :- connected(X,Y,_).
reachable(X,Y, [Z|List]) :- connected(X,Z,_), reachable(Z,Y, List).
You can include the very first station on the journey (pastebin): 
reachable(X,Y, [X,Y]) :- connected(X,Y,_).
reachable(X,Y, [X|List]) :- connected(X,Z,_), reachable(Z,Y, List).
6)
Solution from pastebin:
my_member(X, [X|_]).
my_member(X, [_|T]) :- my_member(X, T).
7)
Archived version in a PDF file
8)
Archived version:
factorial_1(1,1).
factorial_1(N,F):-
  N > 1,
  NN is N - 1,
  factorial_1(NN,FF),
  F is N * FF.


factorial_2(1,F,F).
factorial_2(N,T,F):-
  N > 1,
  TT is N * T,
  NN is N - 1,
  factorial_2(NN,TT,F).
9)
Archived version: 
q(b).
q(c).
 
p(a).
p(X) :- q(X), !.
p(d).
10)
Solution (pastebin):
max1(A,B,A) :- A >= B.
max1(A,B,B) :- A < B. 
 
max2(A,B,A) :- A >= B, !.
max2(A,B,B).
11)
Archived version in a PDF
12)
Solution: 
dfs1(X,X,[]) :- goal(X).
dfs1(X,G,[X|P]) :-
   h(X,Y), X\=Y, dfs1(Y,G, P).
13)
Solution: 
dfs2(X,X,Path,Path) :- goal(X).
dfs2(X,G,Closed,Path) :-
   h(X,Y),
   \+ member(Y,Closed),
   dfs2(Y,G, [Y|Closed], Path).
14)
Solution: 
dfs3(X,[X|_],Path,Path) :- goal(X).
dfs3(G,[X|Open],Closed,Path) :-
   findall(Y, h(X,Y), Successors),
   append(Successors, Open, NewOpen),
   dfs3(G, NewOpen, [X|Closed], Path).
15)
Solution (pastebin):
search([state(pos(X,Y),D,F,Moves)|_], pos(X,Y), solution(MovesRev,F)) :-
  reverse(Moves, MovesRev).
search([State|Open], Goal, Solution) :-
        expandstate(State, Goal, Successors),
        insertstates(Successors, Open, NewOpen),
        search(NewOpen, Goal, Solution).

expandstate(State, Goal, Successors) :-
        findall(Successor, move(State, Goal, Successor), Successors).

move(state(pos(X,Y),D,_,Moves), pos(XGoal,YGoal), 
  state(pos(X2,Y2),D2,F2,[Dir|Moves])) :-
        step(DX, DY, Dir), X2 is X + DX, Y2 is Y + DY,
        correct(pos(X2,Y2)),
        D2 is D + 1, F2 is D2 + abs(X2-XGoal) + abs(Y2-YGoal).

step(1, 0, r).
step(0, 1, u).
step(-1, 0, l).
step(0, -1, d).

obstacle(pos(2,1)).
obstacle(pos(2,2)).
obstacle(pos(3,3)).
obstacle(pos(4,3)).
obstacle(pos(3,4)).

correct(pos(X,Y)) :-
        X > 0, Y > 0, X =< 8, Y =< 8,
        not(obstacle(pos(X,Y))).

insertstates([], L, L).
insertstates([H|T], L, L2) :- 
        insertstate(H, L, L1), insertstates(T, L1, L2).

insertstate(X, [], [X]).
insertstate(X, [H|T], [X,H|T]) :- gef(H, X), !.
insertstate(X, [H|T], [H|T2]) :- insertstate(X, T, T2).

gef(state(_,_,F1,_), state(_,_,F2,_)) :- F1 >= F2.

%------------------------------------------------

insertsorted(X, [], [X]).
insertsorted(X, [H|T], [X,H|T]) :- H >= X, !.
insertsorted(X, [H|T], [H|T2]) :- insertsorted(X, T, T2).