Assignment 7

CS 162 Programming Languages
University of California, Santa Barbara

Due 11:59:59pm Friday, March 24

The goal of this assignment is to better understand the semantics of Prolog. To this end, you will implement a small-step interpreter for a subset of Prolog (mini-prolog), according to the rules in handout 8. Download the code template provided here. The template consists of the following files:

• syntax_high.scala: The Scala code implementing the abstract syntax tree for the subset of Prolog we handle.
• parser.scala: The parser for the subset of Prolog we handle.
• scala-parser-combinators.jar: Scala library code necessary for the aforementioned parser to work.
• syntax_low.scala: The Scala code implementing the abstract syntax tree for mini-prolog, which we use as a lower-level intermediate representation of Prolog.
• translator.scala: The Scala code implementing a translation from the Prolog syntax defined in syntax_high.scala to the mini-prolog syntax defined in syntax_low.scala.
• interpreter.scala: The actual interpreter definition, which you will define.
• tester.scala: Scala code used for automatically running a sizable provided test suite.
• tests.pl: Prolog code used by the provided test suite.

For this assignment, you should modify only interpreter.scala. In interpreter.scala, there are a multitude of positions marked with ??? // FILL ME IN, which you must replace with concrete implementations. (Recall that ??? throws an exception at runtime, but at compile time is automatically of whatever type you desire. This will allow you to compile your code incrementally.) Each of the implementations for ??? should model something from handout 8.

If there is a point in the implementation where you encounter behavior that is not specified in handout 8, you should throw a StuckException to indicate that the interpreter got stuck.

For this assignment, you will need to put scala-parser-combinators.jar onto your classpath if you are on one of the CSIL machines. With this in mind, you can compile and run your code like so, where tests.pl is a valid Prolog program in the subset of Prolog we handle and myLength([1,2,3], X). is a query to run on tests.pl:

scalac -cp scala-parser-combinators.jar *.scala
scala -cp scala-parser-combinators.jar:. miniprolog.interpreter.Interpreter tests.pl "myLength([1,2,3], X)."

You can also compile and run your code using sbt like so, where again, tests.pl is a valid Prolog program in the subset of Prolog we handle and myLength([1,2,3], X). is a query to run on tests.pl:

sbt compile
sbt "run-main miniprolog.interpreter.Interpreter tests.pl \"myLength([1,2,3], X).\""

For testing your code, you can run the test suite in the provided tester.scala file, like so:

scala -cp scala-parser-combinators.jar:. miniprolog.tester.Tests

The provided test suite is not complete, so you are encouraged to add additional tests.

For ease of debugging, your code should be as close to the small-step transition rules as possible. Code that deviates from the mathematical definition is generally difficult to reason about, since it becomes less clear where bugs are relative to the transition rules.

Be sure to turnin your interpreter. The command to turn it in is below:

turnin assign7@cs162 interpreter.scala