By the time you have completed this work, you should be able to:
The goal of this assignment is to become familiar with Prolog and to gain some experience with logic programming.
While you may develop your code using any Prolog implementation you want for this assignment, we recommend using SWI-Prolog, which is available on CSIL via the swipl command.
We will be testing your solutions using SWI-Prolog, so make sure your solutions work correctly on SWI-Prolog before submitting via turnin.
We use the term “procedure” to refer to the code that you must provide.
A procedure is a non-empty set of clauses which have the same name and arity.
For example, the between0And5 procedure is shown below, which simply unifies its only argument with a number in the range [0, 5]:
between0And5(0). between0And5(1). between0And5(2). between0And5(3). between0And5(4). between0And5(5).
For the sake of this assignment, a single clause also constitutes a procedure. That is, if you are able to write one of the intended procedures using only a single clause, this is still perfectly acceptable.
Download the template code below. There are multiple files you must modify in this template. These are listed below in the order in which you should modify them:
companion/ directorylist_routines.plontology.plairgraph.plsat.plEach one of the above components represents a distinct part of this assignment. These parts are subsequently described.
The first part of this assignment is to go through a tutorial covering Prolog, available here.
You need not read chapters 7, 13, 14, and 15.
Each other chapter has a corresponding file in the companion/ directory which you will need to modify.
This part of the assignment involves you implementing a series of operations over lists, which involves modifications to list_routines.pl.
You must fill in all the portions labeled ---FILL ME IN---.
Once you have implemented the list routines, you can load the file into a SWI-PL REPL like so:
swipl -s list_routines.pl
Once the file is loaded, you can run the test suite with:
runTests.
An ontology is a formal description of the knowledge within a domain, complete with ideas and the relationships between said ideas. Ontologies allow for users to rapidly explore a knowledge base, and well-defined representations allow for even automated exploration.
Within the domain of Biology, an ontology of high importance is that of the Gene Ontology (GO). The GO is intended to be a highly descriptive web of knowledge, specific to biological processes (e.g., cell division), cellular components (e.g., organelles), and the functions of related molecules (e.g., protein binding). This structure allows for scientists to rapidly see which different biological components are related to each other and how, along with relevant paper citations. This allows for questions to be answered easily without doing a full literature search, which is important for a fast-moving field with a vast body of knowledge.
The GO can be, and often is, represented as a series of relations between concepts. This is a rather natural representation, given that a significant amount of information is conveyed through connections between concepts, and that this representation is amenable to the incorporation of new information.
This relational representation lends itself to logic programming.
Not only does logic programming make the problem of representing the ontology simple, it provides a natural mechanism to query this representation.
Overall, the GO can be treated like a large directed acyclic graph, and queries over the GO often behave as various kinds of graph traversals.
(As a hint, you may wish to review the graphs.pl file in the provided template code, which illustrates a basic graph traversal in Prolog.)
For this portion of the assignment, you will be working with a small subset of the GO, already written as part of a partial logical program.
This subset is provided in ontology.pl in the template code.
Over this subset of the GO, you must write the following procedures:
A procedure named toisaroot, which makes a list showing the path from some given concept C to the root, which is always 'cellular component'.
For example, the query:
toisaroot('DNA helicase complex', List).
...should yield only:
List = ['DNA helicase complex', 'catalytic complex', 'protein complex',
'macromolecular complex', 'cellular component']
Not every concept will have a root, reflecting the fact that not every concept can reach 'cellular component' strictly via is_a relationships.
For example, the query:
toisaroot(cytoplasm, List).
...should fail, since there is no way to reach 'cellular component' via is_a relationships from cytoplasm.
A procedure named subconcept to determine if a given concept C1 is a subconcept of some concept C2.
This is true if at least one of the following holds:
C1 is a part_of C2
C1 is_a C2
There exists some concept C3 that either is_a or is part_of C2 such that C1 is a subconcept of C3.
In other words, C1 either is_a or is part_of C2 transitively.
For example, the query:
subconcept('intracellular part', X).
...should yield that X could be one of: 'cell part', intracellular, cell, or 'cellular component'.
Duplicates are ok, and even expected, which reflect the fact that there were different ways to derive the same information.
Once you have implemented the above ontology procedures, you can load the file into a SWI-PL REPL like so:
swipl -s ontology.pl
Once the file is loaded, you can run the test suite with:
runTests.
In this part of the assignment, you will search through flight information in order to find the least time-consuming sequence of flights to get between two points.
This will involve modifications to airgraph.pl.
In airgraph.pl, you will need to implement a procedure named pathMaxCost which takes the following parameters (in order):
For example, consider the following query and engine response:
?- pathMaxCost(lax, ams, 50, Flights, ActualCost). Flights = [tk1726], ActualCost = 40
The above query is asking for a way to get from the lax to the ams airport, with a maximum cost (amount of time spent in the air) of 50 minutes.
The ordered list of flights to take is bound to the Flights variable, and the actual amount of time in the air with this list of flights is stored in the ActualCost variable.
The response from the engine shows that only one flight needs to be taken in this case, that of tk1726, which will be in the air for 40 minutes.
You may introduce helper procedures to implement pathMaxCost, though they are not necessary to implement this.
Note that this problem ultimately boils down to performing a graph traversal, so you may wish to consult the graphs.pl file in the template, which contains an example Prolog-based graph traversal.
In this case, the graph has cycles, so you will need to be careful to ensure you do not loop forever.
As a hint, the maximum amount of time allowed in the air can be used to limit the amount of graph traversal performed: if we ever take too many flights, this number will be exceeded, and this should immediately stop the search.
Your base case should be of the case where exactly one flight will deliver the user from the source to the destination. If the user asks for a list of flights with the same source and destination, this should always result in at least two flights (one to another destination and another back), instead of simply returning an empty list of flights. As another hint, the source code for our solution to this component is 10 lines long; if you start needing lots more code than that, you are likely on the wrong track and should ask us for help.
Once you have implemented pathMaxCost, you can load the file into a SWI-PL REPL like so:
swipl -s airgraph.pl
Once the file is loaded, you can run the test suite with:
runTests.
In this part of the assignment, you will write a simple SAT solver.
This will involve modifications to sat.pl.
In sat.pl, you will need to implement the following procedures:
boolOr, where the first two parameters are input boolean values, and the third parameter is an output boolean valueboolAnd, where the first two parameters are input boolean values, and the third parameter is an output boolean valueboolNot, where the first parameter is an input boolean value, and the second parameter is an output boolean valueeval, where the first parameter is a boolean expression, and the second parameter is the boolean result of the expression
A “boolean” is either the atom true, or the atom false, with the obvious meanings.
While writing a SAT solver might sound like a complex task, thanks to the miracle of Prolog this shouldn't be too difficult.
Specifically, you only need to write an evaluator of boolean expressions, and the actual solver part will come “for free” from the engine.
An informal list of expressions (represented as Prolog atoms and structures) and their meanings follows, in no particular order.
true: Trivially evaluates to truefalse: Trivially evaluates to falsevariable(X): X should be treated as a logic variable holding a boolean value.
With this in mind, this should evaluate to X.
or(E1, E2): E1 and E2 represent nested boolean expressions.
After recursively computing the boolean values of E1 and E2, this should perform a boolean OR operation on the results using the boolOr procedure.
and(E1, E2): E1 and E2 represent nested boolean expressions.
After recursively computing the boolean values of E1 and E2, this should perform a boolean AND operation on the results using the boolAnd procedure.
not(E): E represents a nested boolean expression.
After recursively computing the boolean value of E, this should perform a boolean NOT operation on the result using the boolNot procedure.
To see how this solver can be used, consider the following query and engine result:
?- eval(and(variable(X), true), true). X = true.
The above query asks if the boolean expression X && true can be true.
The engine response shows that this expression can, in fact, be true, as long as the variable X has the boolean value true.
As a hint, you may wish to look at the arith.pl file, which is included with the template.
arith.pl contains a simple interpreter of arithmetic expressions, and overall shares as similar structure to what we expect you to implement for eval.
As another hint, our own implementation is under 30 lines of code; if you start needing lots more code than this, you should ask us for help.
Once you have implemented the above procedures, you can load the file into a SWI-PL REPL like so:
swipl -s sat.pl
Once the file is loaded, you can run the test suite with:
runTests.
toisaroot: 10%subconcept: 10%pathMaxCost): 20%boolOr: 2%boolAnd: 2%boolNot: 1%eval: 25%
You must use turnin to turn in all of your code.
The command below will work for this purpose:
turnin assign6@cs162 companion/*.pl list_routines.pl ontology.pl airgraph.pl sat.pl