CIS505 Assignment 7

10 points; due Wednesday, December 10.

Question 1

Prolog is an excellent language for specifiying simple and correct solutions. Let's specify a database like the one you finished for Question 3, Exercise 4:

Say that a database must be built from these key-value bindings: [(b,2), (a,1), (c,4)] These are saved in the Prolog database as these clauses:

mapsTo(b, 2).
mapsTo(a, 1).
mapsTo(c, 4).

There is a Prolog operator, asserta, that lets you add a new clause to a running database. Say that we want to update a to 99. We can say this: ?- asserta(upd(a, 99)).
Now, we see that ?- listing. ... upd(a, 99). mapsTo(b, 2). mapsTo(a, 1). mapsTo(c, 4).
To undo an update, we "retract" the last-inserted upd clause like this: ?- retract(upd(K,_)).
There is also an operator, retractall, which removes all clauses. E.g., retractall(upd(_,_)) removes all the upd clauses.

When it is time to "commit" the updates to the database, we must

collect a list of all the (Key,Value) pairs that appear in all the upd(Key, Value) clauses. (If the same Key appears twice in the list we built, we must remove the older Key, e.g, if we collected [(b,12), (a,9), (b,3), (d,4)], we must remove (b,3) so that we have no duplicates: [(b,12), (a,9), (d,4)].)
retract all upd clauses from our database. (We saved their info in the list in the previous step.) Use the list to retract all outdated mapsTo clauses from the database.
use the list to add new mapsTo clauses to the database.

Your job is to finish the starter database I have already written: you implement the lookup and commit commands. The code you start from is at db70.pl. (You should test what I wrote before you try adding any code to it.)

Here is a demo of how the finished database will behave:

===================================================

1 ?- addDB([(b,2), (a,1), (c,4)]).
true.

2 ?- listing.
 ...
mapsTo(c, 4).
mapsTo(a, 1).
mapsTo(b, 2).
 ...

3 ?- lookup(a).
1
true.

4 ?- update(a, 99).
a updated
true.

5 ?- listing.
  ...
upd(a, 99).
mapsTo(c, 4).
mapsTo(a, 1).
mapsTo(b, 2).
  ...

6 ?- lookup(a).
99
true 

7 ?- update(b, 1000).
b updated
true.

8 ?- revert.
b reverted
true.

9 ?- commit.
Updates to commit:[ (a,99)]
New contents:[ (a,99), (c,4), (b,2)]
true.

10 ?- listing.
  ...
mapsTo(a, 99).
mapsTo(c, 4).
mapsTo(b, 2).
 ...

===================================================

Once you have your solution working, do the above demo and also do an interesting test session with it. Copy-and-paste both sessions into a file, dbtests.txt.

Question 2.

We will use Prolog to specify a backtracking parser and an interpreter for an assignment language. Here is the syntax of a simple, declaration-free assignment language:

===================================================

P : Program
CL : CommandList           E : Expression
C : Command                I : Identifier
                           N : Numeral
P ::=  CL
CL ::=  C  |  C ; CL

C ::=  I = E  |  while E : CL end  |  print I
E ::=  N  |  I  | ( E1 + E2 )  |  ( E1 - E2 )

N ::=  strings of digits
I ::=  strings of lower-case letters

===================================================

A Program is just a CommandList. There are no declarations (like in Python) --- this means a variable is added to the memory the first time it is assigned to. After that, the variable's value is updated in memory each time it is reassigned. The while-loop repeats its body as long as its test evaluates to an non-zero int. (It stops when the test evaluates to 0.)

Here are some example programs. To keep the parser simple, there must be one or more blanks between all words and symbols.

"x = 2".

" x = 2 ;  y = ( x + 1 ) ;  print x".

"x = 3 ; y = 0 ;  while x : x = ( x - 1 ) ; y = ( y + 2 ) ; print x  end".

The system asks for a program, splits it into words, parses it, evaluates it, and prints the final value of memory:

===================================================

?- run.
Type program as a string followed by a period:
|: "x = 3 ; y = 0 ; while x : x = ( x - 1 ) ; y = ( y + 2 ) ; print x  end".

Scanned program: x = 3 ; y = 0 ; while x : x = ( x - 1 ) ; y = ( y + 2 ) ; print x end 

Parse tree: [assign([120],num(3)),assign([121],num(0)),while(iden([120]),[assign([120],sub(iden([120]),num(1))),assign([121],add(iden([121]),num(2))),print([120])])]

Execution:
2
1
0
Final contents of memory
x == 0
y == 6

===================================================

You will finish the system, interpret7.pl, which is posted with this assignment sheet.

What's left for you to do

I've written a driver, parser, and interpreter that works with expressions. You must write the clauses that parse and evaluate Commands:

First, try out my starter system with some sample expressions as input: ?- run. Type program as a string followed by a period: |: "( 2 + 1 )". Scanned program: ( 2 + 1 ) Parse tree: add(num(2),num(1)) Execution: 3 Final contents of memory: true.

Next, change two lines in the run definition so that commands are parsed and executed instead of expressions. (See the comments in the code.)
Now, write the clauses that parse print, assignment, and while. Copy the style of parser code used for parsing expressions. This will be easy. Test your parser with sample progams before coding the interpreter part.
In the interpreter part, write the clauses that interpret the three forms of commands:

The semantics of print(I) is to lookup the int value of variable I in the memory and write it on the display.
The semantics of assign(I, ETREE) is to interpret the int value of ETREE and then bind I to that int in the memory.
The semantics of while(ETREE, CLIST) is to evaluate ETREE to an int; if the int equals 0, then quit; else interpret CLIST and repeat/recurse.

We will model "computer memory" as a collection of predicates, e.g., the result of these two assignments, z = 2; xy = ( z + z ), would be these clauses added to the interpreter:

mapsTo("xy", 4).
mapsTo("z", 2).

I inserted the details as comments in the file, interpret7.pl.

Submission

This is an individual exercise --- do your own work!

Submit to K-State Online a zipped folder containing

your completed program, q70.pl and a nontrivial test case, dbtests.txt.
your completed program, interpret7.pl. and interpret7test.txt, which holds the execution of a test-case program that uses at least one assignment, one print command, and one while-loop.