# CS322 Fall 1999Module 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:

• `true`
• `A & B ` where A and B are bodies
• `A ` where A is an atom defined by rules
• `X is Exp ` where X is a number and Exp is a parametrized arithmetic expression. This is true if X is the value of the expression Exp.
• `assign(P,Exp) ` where P is a parameter and Exp is a parametrized arithmetic expression. This assigns the value of Exp to the parameter P.
• `E1 > E2 ` where E1 and E2 are parametrized arithmetic expressions. (This, "assign" and "is" are the only built-in relations).

Parametrized expressions are of the form:

• `A+B`, `A*B`, `A-B`, `A/B` where A and B are parametrized expressions
• `N ` where N is a number
• `P ` where P is a parameter (a CILog constant).
• a user-defined function

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