Assignment 7: Metainterpreters in Prolog

Due Monday, December 14 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: 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.