Assignment 6

CS 162 Programming Languages
University of California, Santa Barbara

Due 11:59:59pm Monday, March 9

The goal of this assignment is to learn how to implement a language from a specification, and to get a better feel for how Prolog works by implementing a subset of it.

The specification for the subset you will be implementing can be found here. It is recommended that you take some time to understand the specification before trying to implement it; having an in-depth understanding of what needs to be implemented before implementing it can significantly reduce the implementation time. Once you feel that you have a good grasp on the specification, download the code template here. The template contains the following components:

• The definition for the high-level language syntax (syntax_high.scala)
• The parser for the high-level language syntax (parser.scala)
• The definition for the low-level language syntax (syntax_low.scala)
• The automatic translator from the high-level language syntax to the low-level language syntax (translator.scala)
• The interpreter implementing the semantics behind the low-level syntax (interpreter.scala)
• Two example files which can be run (append.pl and prolog_test_suite.pl)
• A .jar file containing necessary library code for the parser (scala-parser-combinators.jar)
• A script to run a provided test suite with (small_test_suite.pl)

For this assignment, you should only need to modify interpreter.scala, specifically at the lines marked with ??? // FILL ME IN. Once these are filled in with correct implementations, the interpreter should run as-is. Note that whenever you want to abort the interpreter, you should call abortInterpreter.

For this assignment, you will need to put scala-parser-combinators.jar onto your classpath if you are on the CSIL machines. With this in mind, you can compile your code like so:

scalac -cp scala-parser-combinators.jar *.scala

The interpreter can be run like so, after being compiled:

scala -cp scala-parser-combinators.jar:. miniprolog.interpreter.Interpreter append.pl 'append([1,2,3], [4,5,6], X), write(X).'

...where append.pl is the name of a file holding clauses, and the second parameter is a query to run on those clauses. Note that the query must end with a period (.) and should be in quotes to avoid conflicting with the shell. Additionally, in this subset of Prolog write can be used only on a variable (X in this example), and all other uses of write will result in a syntax error.

You can run the provided test suite like so:

./small_test_suite.pl

The following is a listing of notes which are relevant but inappropriate for the specification. The specification is intended to be fairly generic, but a few liberties have been taken in the implementation which are specific to our purposes.

The syntax in the specification is implemented via use of Scala's traits and case classs. For example, in syntax_low.scala, Body is implemented as a trait, from which multiple case classs inherit (e.g., check, true, false, etc.). Components that are represented in the specification using special characters (e.g. ∧, ∨, etc.) have been named according to their English counterparts (e.g., And, Or, etc.).

We assume that other than the few bits of mutability we've included (e.g., the vars defined in the run() method in interpreter.scala), no mutability will be used. Use of additional vars or mutable data structures will result in points lost. Additionally, this design can actually break if mutable data structures were used. For example, if the goal stack were mutable, then it would need to be copied before being put onto the choice stack. Otherwise, the all-important information it holds could be erroneously changed out from under it.

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 assign6@cs162 interpreter.scala parser.scala syntax_high.scala syntax_low.scala translator.scala