CSCI 162 Lab 5: logic programming and prolog


Schedule:

In the labs of weeks 9 and 10 (Mar. 20 and 27) we'll introduce prolog programming using swi prolog.

The lab exercise is due at 5pm on Tuesday April 3rd.


Reference material:

       Practice: quick intro to prolog

Organization: a file of facts and rules, which you query interactively

In prolog, rather than trying to "program a solution",
   we establish a file full of facts and rules that describe
      how things work for the system we're interested in,
   then we ask prolog questions (queries) by making statements
      which it attempts to verify as true or false, based on
      the facts and rules available.

For instance, we might create a set of facts and rules describing
   how the end time for a movie is related to its length and
   its start time, and store these in a file.

We could then run prolog, load the file, and ask queries by making
   statements like:

   A movie that starts at 10:23 and is 92 minutes long
      has some valid end time E.
   (to which it hopefully replies true, E is 11:55)

   A movie that starts at 7:01 and is 82 minutes long
      ends at 8:03.
   (to which it hopefully replies false)


Creating and organizing facts and rules Of course, we need to express the facts, rules, and queries in a way that prolog understands. Variables in prolog start with uppercase letters, and named entities (non-variables) with lowercase. We can state facts about entities using a syntax that looks something like a function call in C, e.g. if we wanted to make up a fact that we like bob we could state it as weLike(bob). Note that facts/statements in prolog end in a period, and single-line comments begin with a percent. Below we create another comment and a fact: % fact: we like 3, we decided it is a good number goodNumber(3). We can also create rules, that allow us to say things like X is true about Y if facts A, B, and C are true. The syntax has the following form, where :- means if fact(X) :- someOtherFact. For example, let's come up with a rule that says N is a good number if it is a number, it is bigger than 3, and it is a multiple of 3. Note the mod is for modulo, and the =:= is like == in C++ goodNumber(N) :- number(N), N > 3, N mod 3 =:= 0.
Queries: asking questions by making statements To ask questions, we fire up prolog in a terminal/command window using the command prolog Once it's ready, it will display a prompt something like ?- First, we'll load the file of facts and rules we want to use. To use the myfacts.pl from earlier, the command (after the ?- prompt) looks like this: ?- ['myfacts,pl']. If there are no syntax errors, it will respond with true and a prompt. Asking queries looks a lot like the facts in our file, because essentially we're making a statement and asking prolog "is there a way this is true?" e.g. Let's say 5 is a good number, to which it should respond false, since there is no way to combine the facts and rules available to regard 5 as a good number. ?- goodNumber(5). false Let's say 3 is a good number, to which it should respond true ?- goodNumber(3). true Let's say we can fill in variable X with a good number, to which it should respond with true, X = 3 ?- goodNumber(X). X = 3 When we're ready to quit, the command is halt: ?- halt.
Now let's try an example for finding flights. First we can set up a file of flight facts/rules: Note that X \= Y means X cannot be the same thing as Y and that prolog's format(" ... ~w ... ~n",[X]) acts much like lisp's (format " ... ~A ... ~%" X)
% simple flight-planning system % airport(City,Code) % ------------------ % matches a city name with an airport code, e.g. "nanaimo" with "ycd" airport('Nanaimo', 'YCD'). airport('Vancouver', 'YVR'). airport('Victoria', 'YYJ'). airport('Calgary', 'YYC'). airport('Lethbridge', 'YQL'). airport('Kamloops', 'YKA'). % flight(DeptAC, ArrAC) % --------------------- % as a fact, states there is a direct flight between the % departure airport and arrival airport, % under the given flight code (e.g. "AC123") flight('YCD', 'YYC'). flight('YCD', 'YVR'). flight('YKA', 'YQL'). flight('YKA', 'YYC'). flight('YQL', 'YKA'). flight('YQL', 'YVR'). flight('YQL', 'YYC'). flight('YYJ', 'YVR'). flight('YYJ', 'YYC'). flight('YVR', 'YYC'). flight('YVR', 'YQL'). flight('YVR','YCD'). flight('YVR','YYJ'). flight('YYC', 'YQL'). flight('YYC', 'YKA'). flight('YYC','YCD'). flight('YYC', 'YYJ'). flight('YYC', 'YVR'). % flights(DeptAC, ArrAC) % ---------------------- % as a rule, finds a sequence (list) of flights connecting % the departure airport to the arrival airport % direct flight flights(D,A) :- airport(Dname,D), airport(Aname,A), flight(D,A), format("Direct flight ~w(~w) to ~w(~w)~n",[Dname,D,Aname,A]). % one-stop flights(D,A) :- flight(D,I), I \= A, flight(I,A), airport(Dname,D), airport(Iname,I), airport(Aname,A), format("Flight ~w(~w) to ~w(~w) via ~w(~w)~n", [Dname,D,Aname,A,Iname,I]). % two-stop flights(D,A) :- flight(D,I), I \= A, flight(I,J), J \= A, J \= D, flight(J,A), airport(Dname,D), airport(Aname,A), airport(Iname,I), airport(Jname,J), format("Flight ~w(~w) to ~w(~w) via ~w(~w) and ~w(~w)~n", [Dname,D,Aname,A,Iname,I,Jname,J]). % flights(DeptCity, ArrCity) % -------------------------- % run a flights query, but starting with the city name (translate to airport codes) flights(DC,AC) :- airport(DC,D), airport(AC,A), flights(D,A).
Now let's load our file and try a query that has multiple answers. If we simply hit return after the first answer then we'll be dropped back to the prolog prompt, but if we keep pressing the semi-colon (;) after each answer then it will keep trying to come up with new answers. Eventually it will run out of options and return false.
?- ['flights.pl']. true ?- flights('Nanaimo','Lethbridge'). Flight Nanaimo(YCD) to Lethbridge(YQL) via Calgary(YYC) true ; Flight Nanaimo(YCD) to Lethbridge(YQL) via Vancouver(YVR) true ; Flight Nanaimo(YCD) to Lethbridge(YQL) via Calgary(YYC) and Kamloops(YKA) true ; Flight Nanaimo(YCD) to Lethbridge(YQL) via Calgary(YYC) and Vancouver(YVR) true ; Flight Nanaimo(YCD) to Lethbridge(YQL) via Vancouver(YVR) and Calgary(YYC) true ; false. ?- halt.


Lab exercises:

Obtain the lab 5 repository using the same techniques as previous labs, i.e.

The remaining instructions for lab 5 are in the README file.

Once you have completed all parts of the lab, be sure to add, commit, and push your updates:

REMEMBER: if you miss the add, the commit, or the push then your changes never make it back to the central repository, so they'll never get marked!