- To implement a finite-domain constraint solver
To integrate this aformentioned constraint solver into
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
Make sure to stay within the interface provided by
ConstraintStore; your solver's external interface should consist only of
SAT, and the method signatures
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
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
First download the specification for
mini-prolog-fd, our constraint logic programming version of
Note the similarities to the original
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
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
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
Xto equal 2.
For full credit, you need only implement the constraint solver in
The solver component will be tested independently of the rest of the code.
This, incidentally, is why you must stick to the provided
SAT interface: these are the entry points we will be using for testing.
For up to 30% bonus, you can integrate your solver with
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.
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