CS322 Fall 1999
Module 8 (Metainterpreters)
Assignment 8

Due: 1:30pm, Friday 5 November 1999.

In this assignment you will implement, in CILog, a new programming language ArLog that allows for adjustable parameters in arithmetic expressions and user-defined arithmetic functions.

An ArLog program is a set of clauses of the form:

H <= B.
where H is an atom and B is a body.

A body is either of the form:

Parametrized expressions are of the form:

Parametrized expressions are always evaluated in an environment, where an environment is a list of terms of the form val(P,V) where P is a parameter and V is a number.

We always prove goals within an environment, but the environment can be updated with an assign goal. In a conjunction, the rightmost conjunct is evaluated in the environment that is the result of the evaluation of the leftmost conjunct.

As well as normal clauses defining atoms, the user can define functions using:

F=Exp <= B.
Where F is a user-defined function and Exp is an expression. If B is true, the value of Exp is the value that F evaluates to.

Question 1

Define eval(Exp,Val,Env) that is true if expression Exp evaluates to Val in environment Env. [You do not need to worry about user-defined functions for this question.]

For example, the query

ask eval(3*a+2*b+c, Val, [val(a,4),val(b,5),val(c,7)]).
should return Val=29.

The only CILog built-in predicates you may use are number and is.

Question 2

Define update(Par,Val,Env1,Env2) that is true if Env2 is the same as environment Env1 except that Par has the value Val. You can assume that Par is already assigned a value in Env1.

For example, the query

ask update(b,9,[val(a,4),val(b,5),val(c,7)],E2)
should return E2=[val(a,4),val(b,9),val(c,7)].

Question 3

Define arprove(Body,E1,E2) that is true if the Body can be proved with initial environment E1 and resulting environment E2. The only CILog built-in predicate you can use is >.

For example, suppose the knowledge base is:

addato(X,Y) <= Y is X+a.
foo(X,Y) <= X is a+3 & assign(a,X) & Y is a+3.
The query
ask arprove(addato(3,Y),[val(a,4),val(b,5),val(c,7)],E2).
should return Y=7 and E=[val(a,4),val(b,5),val(c,7)].

The query

ask arprove(foo(X,Y),[val(a,4),val(b,5),val(c,7)],E2).
should return X=7, Y=10, E2=[val(a,7),val(b,5),val(c,7)].

Question 4

[Optional] Modify eval (add a new clause) to allow for user-defined functions.

For example, consider the clauses:

sumsq(X,Y)=X*X+Y*Y <= true.
fact(N)=N*fact(N1) <= N>0 & N1 is N-1.
fact(0)=1 <= true.
then query
ask X is sumsq(3,4)-fact(4).
should return X=1.

Question 5

For each question in this assignment, say how long you spent on it. Was this reasonable? What did you learn?
David Poole