Question

1. Explain the function/purpose of the following sequence of program statements by expressing the postcondition and then prove that the program is correct using the axiomatic verification method.

Precondition: {x = A and y = B}

t=x x=y y=t

Postcondition:________________

2. Prove that the following grammar is ambiguous.

    <stmt>    -> <assign> | <if-stmt>
    <assign>  -> <id> := <expr>
    <if-stmt> -> if <bool> then <stmt> |

                 if <bool> then <stmt> else <stmt>

Modify the grammar above to make it unambiguous:

3. In this question, you are required to develop two programs using the functional programming paradigm.

3.1 Write a functional program (e.g., Racket program) that integrates two sorted lists into a single sorted list. For instance, if the inputs to your function are the following two sorted lists, (3,6,8,12) and (1,2,7,15), the result should be (1,2,3,6,7,8,12,15). You can use only the following functions: car, cdr, cons, null?, eq? and the recursive use of theintegrate function.

(define (integrate L1 L2)
   (cond

) )

3.2 Write a high-order function multiple in Racket that takes as parameter a function of one argument and returns a function that represents the application of that function to its argument two times.

    (define (multiple .....
        .....

) )

Given the usual definition of the square function, what function is (multiple(multiple square))

4. In this question, you are required to demonstrate your understanding of the logic-based programming paradigm.

4.1 Consider the following append program, append(X, Y, Z) in Prolog, where Z is the result of appending list Y to list X:

    append([],Y,Y).
    append([H|T], L, [H|Result]) :- append(T,L, Result)

Suppose we want to develop a Prolog program to find the last item in a list. That is, last(X,Y)unifies X with the last element in list Y, or last(x,Y) returns true if x is the last item in list Y. How can you write this program in terms of the append program above.

last(X,Y) :-

4.2 Given the following Prolog clauses:

ancestor(X,Y) :- ancestor(Z,Y), parent(X,Z)
ancestor(X,X).
parent(amy,bob)

explain, why Prolog fails to answer given the goal ancestor(X,bob).