# 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:

`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.
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*.

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)]*.
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)]*.
[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*.
For each question in this assignment, say how long you spent on it.
Was this
reasonable? What did you learn?

David Poole