CS405 Assignment 6

Due Nov 2, 2004

1. Searching

Write a Prolog function search (Atom, List, Occurrence, Depth ), that counts the occurrence of an atom Atom in a list List, together with its deepest depth in the list List. The depth of an atom in a list is the number parenthesis pairs that the atom is embedded in the list. e.g. in [m, [o, q ], [ h, [j, [k]]]], the depth of m o q h j k is 1 2 2 2 3 4 respectively.

e.g. search (a, [a, [b, c, [d , a] ], [h, a, [b, d, [k, a, [g, a] ]]] ] , Occurrence, Depth )

will return Occurrence=5 Depth=5

2. Deleting

Write a Prolog function replace (Atom, List1, List2), that deletes all occurrence of atom Atom in list List1 (if any), returning the resultant list as list List2

e.g.,

replace(a, [a, [b, c, [d, a] ], [h, a, [b, d, [k, a, [g, a ] ]]] ], List ) will return

List=[[b, c, [d]], [h , [b, d [k, [g ] ]]] ]

3. Consider the Core program segment S below:

i := n;

while (i > 0) loop

i := i - 1;

end loop;

Using the axiomatic semantics of Core

(see http://www.cis.uab.edu/cs405/coreas.pdf ) , show that the assertion

{n>= 0} S {i = 0} is correct.

Hint: Use the loop invariant i >=0 and i <= n. The consequence rules may be used to force the other rules into a form consistent with this loop invariant. (You should analyze the program to understand why this loop invariant was chosen.)