COMP 410 Optional Project

According to the syllabus, there is a final exam in the course. However, you may choose to instead do a final course project. This final course project replaces the final exam, and is thus worth 30% in the course overall. There are only three hard requirements for this project:

• It be large enough to be realistic for this class. This should mean that at the very least, it will take several weeks of work. I will give feedback on this at the time of project proposal.
• The size of the project should be proportional to the number of people working on the project. Less is expected of projects from people working alone than from projects from people working in groups.
• It somehow must relate to logic programming. This does not necessarily mean that a logic programming language must be used. For example, it would suffice to implement a logic programming language in a non-logical language, or to implement ideas from logic programming in non-logical languages.

This final project is split up among three components:

• A project proposal
• A project implementation
• A project report

A description of each of the above components follows.

Project Proposal (Due Monday, October 5)

The project proposal discusses exactly what it is you plan to do, and why. This is a graded component, worth 5%. The project proposal requires the following components, though more can be added if it is relevant:

• A title reflecting the project
• Any background necessary to understand the project
• What exactly you need to do for this project, along with a timeline of when you're planning to do it
• The sort of data you're planning to collect for the project for the report. This can include things like:
  • Benchmarking data showing how fast it runs, or how complex of problems it can handle
  • Data comparing code complexity between programming techniques
  • Basically, anything interesting that can be learned by either looking at the implementation or running the implementation
• An explanation of how the project relates to logic programming
• Why this project is sufficiently large

Before submitting a project proposal, it is recommended to speak with me first so I can give some early feedback. This discussion will help prevent any sort of last-minute surprises when I return the project proposals.

Project Implementation (Due Friday, December 11)

It is expected that most (but not all) projects will require you to write code. This implementation is worth 80%. The code needs to be submitted by this date. Along with the code, you need to submit the following:

• Instructions saying how to run the code
• An example which can be easily run on the code (ideally, this can be done with a single command)
• A description of any known problems with the code, along with ideas of how these problems could be fixed. If you're not sure how the problems can be fixed, say so.

Project Report (Due Wednesday, December 16)

The project report should look somewhat reminiscent to a technical report. This should include:

• An introduction to the project and the particular sort of problem the project tries to solve
• Any sort of applicable background for the project, which should cite external, preferably peer-reviewed sources.
• The results of your project, which should include the sort of data you planned to gather in your project proposal
• Conclusions of the project, and potential future improvements which can be made.
• What you have personally learned from the project

The base value for the project report is 15%. However, bonus is available:

• Project reports written with LaTeX will be automatically given a 3% bonus
• Project reports which cite relevant, peer-reviewed literature will be given 0.5% bonus per reference, up to 3% (more may be cited, but only the first six will count towards the bonus)
• Project reports which are in the form of a publishable paper may be awarded up to 15% bonus. To be clear, this is a very high bar which is not related to mere formatting. Such papers are expected to have an abstract, introduction, related work, details of the technique, a description of the implementation, an evaluation with results, and a conclusion with future work. It is expected that such papers would cite dozens of peer-reviewed sources. It is not expected that most reports will get many points in this category; doing this properly will require lots of extra work.

Theoretically, with all the bonus available on the report, it is possible to recieve up to 121% on the final project.

Potential Project Ideas

A list of potential project ideas follows. This list is non-exhaustive and non-binding; you can pick a project that isn't even related to anything on this list. This list is merely intended to get you thinking about potential project ideas.

• An Exploration of a New Logic Programming Feature: there are a number of different operators that can be added to a logic programming setting to acheive certain goals. For example, the literature discusses hypothetical implication as one such feature, which can be useful for answering “what if?” questions. Such features can be explored from theoretical (e.g., a discussion of what this really means at a logical level), implementation (e.g., implement an interpreter which supports this feature), or applications (e.g., use this operation to do something useful) standpoints. Each of these three mentioned standpoints could each be a separate project, or perhaps smaller elements of each could be combined together.
• Implementing a Logic Programming Language Without a Logic Programming Language: implement either an interpreter or a compiler for a logic programming language, without using a logic programming language. As to exactly what langauge is implemented is up to you. For example, Prolog is relatively easy to implement if cut (!) and negation-as-failure is removed. One possible implementation approach is to use Warren's Abstract Machine as a basis, which is the underpinning of most modern Prolog engines.
• Using Logic Programming Ideas in a Non-Logical Language: use ideas from logic programming to solve some sort of non-trivial problem in a non-logical language. For example, there may be benefit in applying nondeterminism and unification to a non-logical language, as through a library or some other mechanism. It is possible to do this project either from scratch, or by taking existing messy code and rewriting it to be cleaner with respect to whatever logic programming idea is used.
• Use Logic Programming to Test Software: logic programming can be used to describe valid test inputs, and these test inputs can be used to test real code. This was the topic of my dissertation. Use logic programming to write a generator of test cases, and test a software system with it.
• Expert Systems: Implement an expert system using a logic programming language.
• Tour Theory: This class does not substantially cover theory, but that doesn't mean theory is uninteresting. Study the theory behind Prolog and write-up your findings. For this project, there is no implementation. However, the project report is expected to be far more dense than usual, and should include at least 20 highly relevant peer-reviewed references.
• Puzzle Solver: Write a solver for a non-trivial kind of puzzle in a logic programming language. The project proposal and report should discuss why the puzzle is hard, and why Prolog is a good fit for this kind of puzzle.