Prolog ==== 1. Consider the following Prolog predicate definition remove_at(X,[X|Xs],1,Xs). remove_at(X,[Y|Xs],K,[Y|Ys]) :- K1 is K - 1, remove_at(X,Xs,K1,Ys). It works for queries like ?- remove_at(X,[a,b,c,d],2,R). X = b R = [a,c,d]. However, it throws an exception for queries like ?- remove_at(c,[a,b,c,d],V,R). ERROR: remove_at/4: Arguments are not sufficiently instantiated How would you modify the predicate definition to make it work for the above query? 2. Write the prolog predicate flatten(L,R) that flattens a list of lists in L to a single list R. The equivalent OCaml function is given by let rec flatten l = match l with [] | [[]] -> [] |[]::t -> flatten t |[h]::t -> h::flatten t |((h1::t1)::t) -> h1::flatten(t1::t);; Answers ==== 1. remove_at(X,[X|Xs],1,Xs). remove_at(X,[Y|Xs],K,[Y|Ys]) :- remove_at(X,Xs,K1,Ys), K is K1 + 1. 2. flatten([],[]):-!. flatten([[]],[]):-!. flatten([[]|T2],T):- flatten(T2,T),!. flatten([[H]|T2],[H|T]):- flatten(T2,T),!. flatten([[H1|T1]|T2],[H1|T]):- flatten([T1|T2],T). Lambda Calculus ==== 1. Find the lambda encoding obtained by evaluating the expression (alpha 3 1) Given: 1 = \f.\y.f y 3 = \f.\y.f (f (f y)) alpha M N = \x.(M (N x)) For more examples, see http://www.cs.umd.edu/class/fall2011/cmsc330/tests/prac5-soln-fall09.pdf Answers ==== 1. alpha 3 1 = \x.(3 (1 x)) = \x.(3 ((\f.\y.f y) x)) //Substitute encoding for 1 = \x.(3 (\y.x y)) //Beta reduction f->x = \x.(\f.\y.f (f (f y)) (\y.x y)) //Substitute encoding for 3 = \x.(\y.(\y.x y) ((\y.x y) ((\y.x y) y))) //Beta reduction f->(\y.x y) = \x.(\y.(\y.x y) ((\y.x y) (x y))) //Beta reduction y->y = \x.(\y.(\y.x y) (x (x y))) //Beta reduction y->(x y) = \x.(\y.x (x (x y))) //Beta reduction y->(x (x y)) = \f.(\y.f (f (f y))) //Alpha conversion x->f = 3 Here alpha is actually the encoding for the multiplication operator.