====== Archive eFLP 2011: Prolog Tutorial 1: Basic Prolog ======

===== Initial code =====

[[http://pastebin.com/fpPtR2kn|Pasebin code with latest changes]]

<code prolog>
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).
</code>

===== Objectives =====

  - **Install Prolog**
  - **Learn the syntax:** Add the missing underground link into the initial code.((Solution from [[http://pastebin.com/w6MXjdnC|pastebin]]: <code prolog>connected(green_park,           charing_cross,        jubilee).</code>))
  - **Basic predicates:** Define the ''nearby/2'' predicate = stations on the same line, distant at most 2 stops.((Solution from [[http://pastebin.com/e97TxFxd|pastebin]]: <code prolog>nearby(X,Y) :- connected(X,Y,_).
nearby(X,Z) :- connected(X,Y,L), connected(Y,Z,L).</code>))
  - **Recursion:** Define ''reachable/2'' = stations reachable via any number of intermediate stops, not necessarily on the same line.((Solution from [[http://pastebin.com/N2uun7Fz|pastebin]]: <code prolog>reachable(X,Y) :- connected(X,Y,_).
reachable(X,Y) :- connected(X,Z,_), reachable(Z,Y).</code>)) You may have to add ''connected('Mustek', 'Muzeum', 'A').'' fact for testing purposes.
  - **Debug trace:** Try debugging the code to see the order of execution.

[[https://docs.google.com/present/edit?id=0AUhT50rgdR0KZGNrOTNxODRfOTYyaG1rMmNjdw|Tutorial slides]] (({{flp_tutorial_1.pdf|Archived version in a PDF file}}))

====== Prolog Tutorial 2: Lists ======

===== Initial code =====

[[http://pastebin.com/VKN1Yksq|Pasebin code with latest changes]]

<code prolog>
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).
</code>

===== Objectives =====

  - **Understand the unification algorithm**
  - **Recall the list representation:** Relate LISP's ''cons'' and ''nil'' to Prolog's //dot// and ''[]'' functions
  - **Learn how to construct lists:** Define predicate ''journey/3'' which returns a list of visited stations on a journey.((Firstly print the list to STDOUT ([[http://pastebin.com/0waXKGCb|pastebin]]):<code>reachable(X,Y) :- connected(X,Y,_).
reachable(X,Y) :- connected(X,Z,_), write(X), nl, reachable(Z,Y).</code>

The add the third argument which creates a list ([[http://pastebin.com/0waXKGCb|pastebin]]):
<code>reachable(X,Y, [Y]) :- connected(X,Y,_).
reachable(X,Y, [Z|List]) :- connected(X,Z,_), reachable(Z,Y, List).</code>

You can include the very first station on the journey ([[http://pastebin.com/2dBT1xh1|pastebin]]):
<code>reachable(X,Y, [X,Y]) :- connected(X,Y,_).
reachable(X,Y, [X|List]) :- connected(X,Z,_), reachable(Z,Y, List).</code>))
  - **Parse lists:** Define your own implementation of the ''member/2'' predicate.((Solution from [[http://pastebin.com/cvFNXL1V|pastebin]]:<code prolog>my_member(X, [X|_]).
my_member(X, [_|T]) :- my_member(X, T).</code>))
  - **Limitations of Prolog lists:** Understand how ''append/3'' works and implement your own ''my_append/3'' predicate.


[[https://docs.google.com/present/edit?id=0AUhT50rgdR0KZGNrOTNxODRfMTAwZnJ2N3A1Z3c|Tutorial slides]](({{flp_tutorial_2.pdf|Archived version in a PDF file}}))




====== Prolog Tutorial 3: Code efficiency ======

  - **Arithmetics:** Learn the difference between ''X = 1 + 1'' and ''X is 1 + 1''.
  - **Programming challenge:** As an experienced Prolog programmer, define factorial.
  - **Benefits of tail recursion:**
    - Compare and contrast [[http://pastebin.com/iqNJBKBu|two exemplary implementations]].((Archived version:<code>
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).
</code>))
    - Evaluate efficiency of both implementations by computing 10000!: ''time(factorial(10000,_))''
  - **Understand the //cut//:** Play with the [[http://pastebin.com/bGM9FnCF|supplied code]]. ((Archived version: <code prolog>
q(b).
q(c).

p(a).
p(X) :- q(X), !.
p(d).
</code>))
  - **Use //cut// in your code:** With and without the cut, define ''max/3'' = maximum of two numbers.((Solution ([[http://pastebin.com/HRu33y9e|pastebin]]):<code prolog>max1(A,B,A) :- A >= B.
max1(A,B,B) :- A < B. 

max2(A,B,A) :- A >= B, !.
max2(A,B,B).</code>))

[[https://docs.google.com/present/edit?id=0AUhT50rgdR0KZGNrOTNxODRfMTAxdnhjZjRrMjc|Tutorial slides]](({{flp_tutorial_3.pdf|Archived version in a PDF}}))

**Check you understand:** Compare the ''factorial_1'' predicate with ''factorial_3'' that uses the //cut//. What difference in behaviour can you spot?
<code>
factorial_3(1,1):- !.
factorial_3(N,F):-
  NN is N - 1,
  factorial_3(NN,FF),
  F is N * FF.
</code>

====== Prolog Tutorial 4: Searching a graph ======

===== Initial code =====

<code prolog>
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).
</code>

===== Objectives =====

  - Implement a basic depth-first-search (DFS) algorithm.((Solution: <code prolog>dfs1(X,X,[]) :- goal(X).
dfs1(X,G,[X|P]) :-
   h(X,Y), X\=Y, dfs1(Y,G, P).</code>))
  - Avoid infinite looping by creating a //closed list//.((Solution: <code prolog>dfs2(X,X,Path,Path) :- goal(X).
dfs2(X,G,Closed,Path) :-
   h(X,Y),
   \+ member(Y,Closed),
   dfs2(Y,G, [Y|Closed], Path).</code>))
  - Implement a bredth-first-search (BFS) algorithm. ((Solution: <code>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).</code>))

[[http://pastebin.com/tDkfJQuK|Pastebin code with solutions]]

====== Prolog Tutorial 5: Searching a state-space ======

===== Initial code =====

<code prolog>
% 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))).
</code>

===== Objectives =====

  - **Implement a BFS:**((Solution ([[http://pastebin.com/WwQMPrmd|pastebin]]):<code>
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).
</code>)) Find a path from initial to goal position on 8x8 board s.t:<code prolog>% 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).</code>


====== Prolog Tutorial 6: Constraint logic programming ======

===== Initial code =====

[[http://pastebin.com/BxA4PV21|Pastebin code with latest changes]]
<code>
% 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!
</code>

===== Objectives =====

  - **Study the theory:** [[http://en.wikipedia.org/wiki/Sudoku|Sudoku on Wikipedia]].
  - **Train your skills:** Define a helper predicate ''alldiff/1''.
  - **Naïve Sudoku:** Implement a naïve implementation of Sudoku generator and solver in a //generate-and-test// fashion. Measure computation time.
  - **Optimize:** Push the //test// conditions up inbetween the //generate// calls to increase the efficiency. Measure the computation time.
  - **CSP:** Return to the naïve implementation and convert it into a CSP problem. Measure the computation time.