Simply recurse through the list of employees. Deal with 3 cases: 1. The list of employees is empty.

Prolog project
Aims
The aims of this project are as follows:
● To give you more exposure to recursive programming.
● To expose you to Prolog programming.
Requirements
Implement all the procedures specified in prj3-sol.pro using swipl Prolog. You may
define auxiliary procedures as needed.An example LOG file gives examples of the
use of these procedures as do the tests provided in prj3-sol.pro.You are not allowed
to use any non-logical features of Prolog other than is/2. Non-logical features include
the explicit cut !, implicit cut within ->, assert, retract, record, etc.
Provided Files
You should use the provided prj3-sol directory as a starting point for your project by
copying it into your i571?/submit directory. It contains the following files:
prj3-sol.pro
A skeleton file which contains the specifications for the procedures you are
required to write as well as tests for those procedures.
README
A README file which must be submitted along with your project. It contains an
initial header which you must complete (replace the dummy entries with your
name, B-number and email address at which you would like to receive
project-related email). After the header you may include any content which you
would like read during the grading of your project.
The extras directory contains the following files:
LOG
A sample log file.
do-tests.sh
A trivial shell script to allow running tests from the command line.
Tests
The prj3-sol.pro skeleton file contains unit tests for the procedures you are required
to implement. Note that specifying a test as nondet means that the test may succeed
with more possible answers pending. The all specification specifies a list of all
possible answers after backtracking through the test.
You can run the tests using Prolog’s run_tests/0 or run_tests/1.
$ prolog
…
% load required solution file
1 ?- [‘prj3-sol.pro’].
true.
% run tests for a single procedure
?- run_tests(re_match).
% PL-Unit: re_match ………………….. done
% All 23 tests passed
true.
% run all tests
?- run_tests.
% PL-Unit: dept_employees … done
% PL-Unit: employees_salary_sum … done
% PL-Unit: list_access ………… done
% PL-Unit: count_non_pairs ……. done
% PL-Unit: divisible_by …. done
% PL-Unit: re_match ………………….. done
% PL-Unit: clausal_form ….. done
% All 57 tests passed
true.
You can also use the do-tests.sh shell script to run unit tests from outside prolog:
$ prj3=$HOME/cs571/projects/prj3
$ $prj3/extras/do-tests.sh
usage: do-tests.sh TESTS_FILE [TEST_NAME…]
It can be run for testing a single procedure:
$ $prj3/extras/do-tests.sh prj3-sol.pro re_match
…
% PL-Unit: re_match … done
% All 23 tests passed
% halt
or for testing multiple procedures:
$ prj3/extras/do-tests.sh prj3-sol.pro re_match divisible_by
…
% PL-Unit: re_match ………………….. done
% PL-Unit: divisible_by …. done
% All 27 tests passed
% halt
or for running all tests:
$ $prj3/extras/do-tests.sh prj3-sol.pro
…
% PL-Unit: dept_employees … done
% PL-Unit: employees_salary_sum … done
% PL-Unit: list_access ………… done
% PL-Unit: count_non_pairs ……. done
% PL-Unit: divisible_by …. done
% PL-Unit: re_match ………………….. done
% PL-Unit: clausal_form ….. done
% All 57 tests passed
% halt
Hints
The following points are worth noting:
● Review the class Prolog slides. In particular, review the slides on Prolog
Programming Heuristics.
● If you do not understand the specs for a procedure, please look at the tests or
LOG for examples of the expected use of the procedure.
● Pattern matching of two terms can be done implicitly, or by explicitly using the
= operator. Occasionally, you will need to verify that two terms do not match;
this can be done using the \= operator as in X \= Y.
This will be necessary when your case analysis results in two cases:
Terms match
The matching is usually done implicitly by using the same variable for all
occurrences of the terms.
Terms do not match
The terms are accessed as some variables X and Y and then the
non-matching is enforced by specifying X \= Y, usually as a guard.
Since there are no types or declarations in Prolog, it is very easy to have a bug
resulting from a typo in a variable name. Prolog tries to prevent this by generating
warnings about singleton variables; i.e, any variable which occurs only once within
a Prolog rule. For example, the rule
member(X, [Element|Elements]) :-
member(X, Elements).
would produce a warning that Element is a singleton variable.
If the singleton variable is intentional, then the warning can be avoided by replacing
the name with one starting with an underscore _, as in the code shown below:
member(X, [_Element|Elements]) :-
member(X, Elements).
●
● Prolog has a pretty powerful debugging model. You can turn on tracing using
trace/0 or trace/1 and turn it off using nodebug/0, spying on a particular procedure
using spy/1 and turn off using nospy/1 of nospyall. If running within a graphical
environment, you can turn on GUI debugging using gtrace.
Exercise-Specific Hints
Exercise #1: dept_employees()
Simply recurse through the list of employees. Deal with 3 cases:
1. The list of employees is empty.
2. The department in the head of the list of employees matches the required
department.
3. The department in the head of the list of employees does not match the
required department.
Make sure you set up these 3 cases to be mutually exclusive.
Exercise #2: employees_salary_sum()
Since the procedure is required to be tail-recursive, use an auxiliary procedure with
an additional parameter which accumulates the sum.
1. If the original employee list is empty, the final sum should simply match the
accumulated sum.
2. When the original employee list is non-empty, accumulate the head element
salary into the accumulator and recurse on the cdr.
Use something like Acc1 is Acc + Salary to accumulate salaries.
Exercise #3: list_access()
You will need to handle the following cases:
1. The Indexes list is empty.
2. The Indexes list is not empty, but the List list is empty.
3. Both lists are not empty and the head of the Indexes list is 0. In this case, the
code will need to descend into the head of List using the cdr of the Indexes.
4. Both lists are not empty and the head Index of the Indexes list is > 0. In that
case, the code will need to step over the rest of List with a decremented Indexes
head. Note that something like Index1 is Index – 1 can be used to perform the
decrement.
Exercise #4: count_non_pairs()
See the corresponding Scheme example. Use the \= operator to check that a term is
not a pair.
Exercise #5: divisible_by()
This is an exercise in taking advantage of Prolog’s backtracking.
Use a generate-and-test strategy, using member/2 to generate successive elements X
of the list which are then tested using simply 0 is X mod N.
Exercise #6: re_match()
This exercise also takes advantage of Prolog’s backtracking.
Define re_match/2 as a wrapper around an auxiliary re_match/3 where the additional
argument should represent the leftover suffix after the regex matches a prefix of the
input symbols. For example, given a list of input symbols [a, a, a, b, b], then the
symbols leftover after matching the regex kleene(a) will be [b, b]. Since re_match/2 should
match the entire input list of symbols, it will call re_match/3 with the additional
argument set to [].
Write re_match/3 using case-analysis on the structure of the regex:
1. If the regex is a symbol Sym (checked using atomic(Sym)), then the head of the
input list must match Sym with the rest of the input list leftover.
2. If the regex is concat(Re1, Re2), then Re1 must match a prefix of the input
symbols and Re2 must match a prefix of the symbols leftover after matching
Re1.
3. If the regex is alt(Re1, Re2) then either Re1 or Re2 must match a prefix of the input
symbols. Use separate rules for each alternate.
4. If the regex is kleene(Re), then Re can match successive prefixes of the input
symbols repeatedly, or it can simply match the empty prefix of the input
symbols.
Exercise #7: clausal_form()
This exercise asks you to convert a Prolog program represented as a list of rules into
one which uses explicit logical connectives (/\ for logical-and, \/ for logical-or and ~ for
logical negation):
● The input list of rules [Rule1, Rule2, …, RuleN] represents a logical-and of the rules
in the list. Hence the input list should be converted to RuleZ1 /\ RuleZ2 /\ … /\
RuleZN, where RuleZi is the conversion of each individual rule.
● A rule which is a fact (there is no body) does not need to change.
● A rule which has a body will match the Prolog term Head :- Body. This will need
to be converted into Head \/ BodyZ, where BodyZ is the conversion of Body.
● A Body of the form P1, P2, …, Pn will need to be converted to ~P1 \/ ~P2 \/ … \/ Pn
The conversions for an individual rule follows from the fact that :- stands for logical
implication and Head :- Body is the same as Head \/ ~Body. Specifically,
Head :- P1, P2,…, Pn≡Head \/ ~( P1 /\ P2 /\…/\ Pn )≡Head \/ ~P1 \/ ~P2 \/…\/
~Pnusing De Morgan’s Law
At first glance, this appears to be a fairly straightforward conversion between
different operators. However, there is a problem in that the operators have different
associativities:
● The implicit pair operator [|] used with lists is right-associative whereas /\ is
left-associative. For example, [Rule1, Rule2, Rule3] has the structure:
but the output structure should be:
● Similarly, the comma operator , used between the predicates of a rule body is
right-associative whereas \/ is left-associative. Hence Pred1, Pred2, Pred3 has the
structure
but the desired output structure is
The solution to this problem is to accumulate the output using an accumulating
parameter. Here is a possible start for the code:
clausal_form([Rule|Rules], Form) :- %List of rules specified non-empty
rule_clause(Rule, RuleClause),
clausal_form(Rules, RuleClause, Form).
clausal_form([], AccForm, AccForm).
clausal_form([Rule|Rules], AccForm, Form) :-
rule_clause(Rule, RuleClause),
clausal_form(Rules, AccForm /\ RuleClause, Form).
where rule_clause(Rule, RuleClause) will convert Rule (in Prolog syntax) to RuleClause in
logic syntax.
While writing the code, it is important to keep in mind that Prolog’s :- and , operators
have low precedences. Hence attempting to match :- using something like
rule_clause(Head:-Body, …) will cause a syntax error; instead you must use something like
rule_clause((Head:-Body), …). Similar parenthesization is necessary when matching the
comma operator.
Submission
Before submitting your project, update your README to specify the status of your
project. Document any known issues.
Submit using a procedure similar to that used in your previous project