Implement all the procedures using swipl Prolog.
Budget: $30 – $250 USD
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.
Hints-:
Exercise #1: dept_employees()
Simply recurse through the list of employees. Deal with 3 cases:
The list of employees is empty.
The department in the head of the list of employees matches the required department.
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.
If the original employee list is empty, the final sum should simply match the accumulated sum.
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:
The Indexes list is empty.
The Indexes list is not empty, but the List list is empty.
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.
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()
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:
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.
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.
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.
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()
Attached in pdf.
The procedures are described in the pdf file attached.
Hints-:
Exercise #1: dept_employees()
Simply recurse through the list of employees. Deal with 3 cases:
The list of employees is empty.
The department in the head of the list of employees matches the required department.
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.
If the original employee list is empty, the final sum should simply match the accumulated sum.
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:
The Indexes list is empty.
The Indexes list is not empty, but the List list is empty.
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.
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()
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:
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.
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.
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.
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()
Attached in pdf.
The procedures are described in the pdf file attached.