Assignment 7: Metainterpreters in Prolog

Due Friday, April 20 at 11:59 PM

Goals for This Assignment

By the time you have completed this work, you should be able to:

Provided files:

Step-by-Step Instructions

Step 1: Write a Metainterpreter that Performs Automatic Bounding

Download bound_recursion_depth.pl. You will need to implement the interpret procedure in this file, which is a special kind of metainterpreter. This particular metainterpreter allows us to bound the maximum number of times we can call a given series of procedures, in terms of how deeply-nested the call stack can become.

This sort of bounding may sound very abstract, but this is directly related to the idea of bounding the depth in the previous lab. In that lab, in order to generate a variety of expressions, we needed do modify the generation code itself to add in a depth bound. In this lab, we'll instead modify the Prolog interpreter itself to automatically perform this same sort of bounding. This way, we can write unbounded generation code, but it will still work like it's bounded. Phrased another way, instead of modifying the generation code, we'll modify the code that executes the generation code.

The interpret procedure you need to write takes three parameters:

  1. A bound on the maximum stack depth.
  2. A list of procedure name/arity pairs describing what needs to be bounded. For example, the list [exp/1] states that the exp procedure with arity 1 should be bounded. This list is equivalent to [/(exp, 1)]; that is, / is the name of a structure. This notation with / is commonly used to refer to procedures.
  3. A structure representing the query to execute. This is effectively the AST we evaluate.

The central idea with this metainterpreter is that the bound is decremented if (and only if) we make a call to one of the procedures listed in the second parameter. As before, if this exhausts the bound, the failure should occur. Otherwise, the bound should be decremented and execution continue with the decremented bound.

To determine exactly what sort of procedure is being called, you'll likely need to make use of the built-in functor procedure. functor takes a Prolog term (a structure or an atom), and gives the name and arity of it. For example: 

?- functor(append([1, 2, 3], [4, 5, 6], List), Name, Arity).
Name = append,
Arity = 3.

In the above example, append is the name of the structure (Name), and it has arity 3 (Arity), since the structure holds three parameters (namely, [1, 2, 3], [4, 5, 6], and List).

More details are contained in the comments of bound_recursion_depth.pl.

Step 2: Write a Metainterpreter that Handles Variables in Arithmetic Constraints

Download numbers.pl. You will need to implement the interpretBounds procedure in this file, which is a special kind of metainterpreter.

Recall that arithmetic constraints in Prolog can only work with known values. For example, the following queries don't work correctly, and yield Arguments are not sufficiently instantiated errors: 

?- X > 4.
ERROR: >/2: Arguments are not sufficiently instantiated
?- X is 2 + Y.
ERROR: is/2: Arguments are not sufficiently instantiated
?- 4 is Y + 3.
ERROR: is/2: Arguments are not sufficiently instantiated

This limitation breaks the logical view that Prolog usually provides, since it forces us to think about whether or not a variable has a known value at the moment, which isn't a logical concept but instead an operational one. This places the emphasis away from what the code means and firmly puts it in how the code is executed. Working around this limitation can be incredibly annoying to downright impossible, depending on the problem.

For this portion of the assignment, you'll write a metainterpreter that overcomes this limitation, at least somewhat. For the most part, this metainterpreter executes Prolog normally. However, if this sees a arithmetic constraint containing variables (which normally would cause the error shown before), this will first unify those variables with numbers within some predetermined range. It will then try to solve the constraint as normal. If this succeeds, then execution continues. If this doesn't succeed, then another number in the range is chosen (while there are still numbers remaining to try in the range), and we try again.

Example output for the above queries is shown below, where these queries are executed using the interpretBounds metainterpreter: 

?- interpretBounds((X > 4), 0, 10). % minimum in range is 0, maximum is 10
X = 5 ;
X = 6 ;
X = 7 ;
X = 8 ;
X = 9 ;
X = 10.

?- interpretBounds((X is 2 + Y), 0, 2). % min = 0, max = 2
X = 2,
Y = 0 ;
false.
% because both X and Y are variables, only values between
% 0 and 2 can be chosen for them - this is a little silly
% but it makes handling everything a lot easier (more on
% that in a bit)

?- interpretBounds((4 is Y + 3), 0, 2). % min = 0, max = 2
Y = 1 ;
false.

Note that the bounds restrict the space, so different arithmetic constraints will have different results depending on the bounds. To demonstrate this, consider the first query again below, but with different bounds: 

?- interpretBounds((X > 4), 0, 2). % min = 0, max = 2
false.

As shown, while in general it is true that there is some X that is greater than 4, there are no such values in the range 0 to 2. Phrased another way, the above query is equivalent to the following, for unbounded integers: 

X > 4, X >= 0, X <= 2

For implementing this portion, the following built-in procedures may be helpful:

More details are contained in the comments of numbers.pl.

Step 3: Turn in Your Solution Using Canvas

Log into Canvas, and go to the COMP 410 class. Click “Assignments” on the left pane, then click “Assignment 7”. From here, you need to upload the following files:

In addition, if you collaborated with anyone else, be sure to download collaborators.txt and write the names of the people you collaborated with in the file, one per line. Please submit this file along with the other files.

You can turn in the assignment multiple times, but only the last version you submitted will be graded.