Assignment #6: Lazy Evaluation and Logic Programming Prolog

Problem 2. We can represent the internal walkways between buildings on UB’s north campus by a simple Prolog relation walkway(Building1, Building2), which expresses the fact that there is an internal walkway connecting Building1 and Building2. Examples: walkway(jarvis, furnas). walkway(furnas, bell). walkway(bell, studentunion). etc. The full walkway database is posted on Piazza under ResourcesHomeworkswalkway.pl. Note that walkway(B1, B2) means that we can walk from B1 to B2 as well as from B2 to B1. Part 2a. Define a predicate path(B1, B2, Path) which, given two buildings B1 and B2, returns in Path the list of buildings on a path from B1 to B2 going only through permissible walkways. There could be more than one path between a pair of buildings. By repeated backtracking, your program should return all solutions. On any reported path, no building should occur more than once. For the walkway database given, the paths from Slee to Capen (for example) are obtained by executing the query shown below, assuming that the path predicate is kept in a file called [login to view URL]: ?- [walkway, path]. ?- path(slee, capen, P). P = [slee, baird, clemens, lockwood, studentunion, knox, norton, capen] ; P = [slee, baird, clemens, lockwood, baldy, obrian, norton, capen] ; false. ? - (Note: you need to type the semi-colon after each solution in order to see the next solution.) As a starting point for your solution, consider the following definition of the path predicate. path(Start, End, [Start | P]) :- path2(Start, End, P). path2(X, Y, [Y]) :- walkway(X, Y). path2(X, Y, [Z|P]) :- walkway(X, Z), path2(Z, Y, P). There are two problems with the above program: 1. It treats all walkways as one-way walkways, e.g., it permits going from Jarvis to Furnas, but not vice versa. Correct the program so that it treats the walkways as two-way walkways. 2. It can go into an infinite loop because of cycles in the walkway graph. Correct this problem by adding an extra parameter to the path2 predicate so that it maintains a list of all buildings seen en route from the ‘Start’ building. Use this list to ensure that no building occurs more than once on any path. Hint: The predicate, member(X, List), will be helpful for this purpose. This is a built-in predicate of Prolog, hence you do not have to define it. Test your program with different inputs (building names) for the first two arguments of path, and observe the paths that are computed. Part 2b. Making use of the path predicate defined in part (a), define a predicate pathvia(BList, B1, B2, Path), which, given two buildings B1 and B2 and a list of buildings BList, returns in Path the list of buildings on a path from B1 to B2 that goes through all buildings in BList. As before, no building should occur more than once in any reported path. By repeated backtracking, the predicate pathvia should return all possible solutions. Below is a sample use of this predicate. ?- pathvia([furnas,studentunion], jarvis, capen, Path). Path = [jarvis, furnas, bell, studentunion, knox, norton, capen] ; Path = [jarvis, furnas, bell, studentunion, lockwood, baldy, obrian, norton, capen] ; false. Hint: Again, the member predicate would be useful in helping carry out the required check.