Assignment Five
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 on submit.cs.
For both part A and part B, 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.
For example, with part B, if there is only one solve clause, this is fine.
Part A: Tutorial
The first part of this assignment is to go through a tutorial covering Prolog, available here.
You needn’t read chapters 7, 13, 14, and 15.
We have provided a set of companion exercises for the tutorial (in the attachments), indexed by tutorial chapter, which must be completed as part of the assignment.
In addition to the tutorial itself, you should also take a look at graph.pl, which implements a simple graph and graph traversal in Prolog.
This may prove useful in implementing the ontology portion later in the assignment.
Part B: List Operations
This part of the assignment involves you implementing a series of operations over lists.
You must fill in all the portions labeled —FILL ME IN— in list_routines.rb.
PART C: ONTOLOGIES
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 (you may wish to review graphs.pl again from the tutorial).
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.
Your task is to complete missing procedures in ontology.pl.
Over the mentioned 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 Cto 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 subconceptto determine if a given concept C1 is a subconcept of some concept C2.
This is true if at least one of the following holds:- C1is a part_of C2
- C1is_a C2
- There exists some concept C3that 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
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 expected, which reflect the fact that there were different ways to derive the same information.
RUBRIC
- Tutorial: 20%
- List Operations: 40%
- Ontology:
-
- toisaroot: 20%
- subconcept: 20%
Submitting
You will submit on submit.cs, which will become available a day before the deadline
Deadline
The dealine for this assignment is Tuesday, 20th of March.
Skeleton Code
You can find everything you need here: https://piazza.com/class_profile/get_resource/jch6mk7pf3y43i/jejm7z7zfky6wb
The companion directory contains exercises for the tutorial part. The other files are there for other parts of the assignment.