Due Date
Description
- To implement a finite-domain constraint solver
-
To integrate this aformentioned constraint solver into
mini-prolog
The specification for the constraint solver is available here.
First take some time to familiarize yourself with the constraint solver, and to fully understand the psuedocode.
Once you are comfortable with the specification, download the code template provided here.
Implement the solver in the file solver.scala.
Make sure to stay within the interface provided by ConstraintStore; your solver's external interface should consist only of insert and SAT, and the method signatures insert and SAT should not change.
It is fine (and encouraged) to introduce additional methods, but it should not be necessary to call them externally.
Once you have your solver implemention complete, you can test and debug using the provided tests in small_solver_tests.scala.
These tests can be run like so:
scala -cp scala-parser-combinators.jar:. SolverTestsNote that these tests are provided only as convenience and are by no means complete; we recommend writing your own tests in addition to our own.
Once you have achieved high confidence that your solver implementation is working correctly, you may move on to applying your solver to mini-prolog.
First download the specification for mini-prolog-fd, our constraint logic programming version of mini-prolog, here.
Note the similarities to the original mini-prolog specification.
The mini-prolog-fd specification has only the following major differences:
- There is an additional syntactic form for comparing values symbolically, along with a rule to semantically handle this syntactic form.
-
The language has been augmented with a constraint store (
constraintStore), a new basic data structure. This stores the current constraints added via symbolic operations (e.g.,X #= 7). -
A new type of value is available, namely symbolic placeholders (
SymPlaceholder). These represent variables used internally by the constraint solver. - Unification has been updated to work with symbolic placeholders in addition to the previously existing values. There is also a special case now for unifying a non-symbolic placeholder with an integer, which must add a constraint to the constraint solver.
Once you're confident in your understanding of the specification, finish implementing the template code provided in interpreter.scala.
Feel free to copy code over from your previous implementation of mini-prolog; there will likely be a lot of reuse here.
Note that whenever you want to abort the interpreter, you should call abortInterpreter.
You may compile this interpreter like so:
scalac -cp scala-parser-combinators.jar *.scalaYou may run this interpreter like so:
scala -cp scala-parser-combinators.jar:. miniprologfd.interpreter.Interpreter <filename> <query>...where
<filename> is a path to a file containing clauses, and <query> is a query to run.
One such example query is the following:
X #< 3, X #> 1....which should constraint
X to equal 2.
Grading
For full credit, you need only implement the constraint solver in solver.scala.
The solver component will be tested independently of the rest of the code.
This, incidentally, is why you must stick to the provided insert and SAT interface: these are the entry points we will be using for testing.
For up to 30% bonus, you can integrate your solver with mini-prolog-fd in interpreter.scala.
The bonus heavily relies on the constraint solver, and so you should focus on getting your solver implementation working completely first, and then optionally move on to integration.
Deliverables
All files required to compile your interpreter implementation must be turned in, including the files you did not modify. On our end, this simplifies testing your code. We may dock points if files are missing, so please include everything relevant! The following command should turn in everything, assuming you have not added any new files:
turnin assign7@cs162 interpreter.scala parser.scala syntax_high.scala syntax_low.scala translator.scala solver.scala