Programming Languages: Spring 2005

From SubfireWiki

Contents 1 Question 2. 2 Question 3. 3 Question 5. 4 Question 6. 4.1 Rewriting:

Question 2.

sub(X,Y,Z):- Z is X-Y.

foldl1(_, [],[]).
foldl1(_,[X],X).
foldl1(R,[A,B|T],X):- Q=..[R,A,B,Y], call(Q), foldl1(R,[Y|T],X).

?- foldl1(sub,[1,2,3,4,5],X).

X = -13

Yes
?-

Question 3.

zip: take list a and b, generate list c which contains the pairs from a and b

y f = f (y f)
zip = y (\z l1 l2 -> if l1 == [] || l2 == [] then [] else (head l1, head l2) : z (tail l1) (tail l2))

zipWith: take list a and b and function f, generate list c which contains the result of applying f to each element of a and b

y f = f (y f)
zipWith = y (\zw l1 l2 f -> if l1 == [] || l2 ==[] then [] else f (head l1) (head l2) : zw (tail l1) (tail l2) f)

Question 5.

Copy stuff from Programming Languages: Fall 2005 Question 3, then show that it fits the form of (define (f x) (if (p x) (q x) (f (h x))))

Question 6.

This should look almost exactly like the one from Programming Languages: Fall 2005

Invariants:

To Prove: Fib(n) = = y

At the end of the loop: we have , in particular,

Working backwards: From the end of the loop:

c=c+1:

y=y+temp:

x=y:

temp=x:

Which implies:

Rewriting:

Invariants:

temp=x

x=y

y=y+temp

c=c+1

which is what we want.