CS 6905 Advanced
Topics in Computer Science:
For the following, please keep in mind to first define cns(First,Rest) :& [First|Rest].
1) Define a recursive operation flatten for flattening a list that only contains simple terms and lists, splicing the ordered sequence of elements of each embedded list into the main list (as if omitting square brackets on all inner levels of a list). Define it both in FP and LP versions. As a function, flatten([a,[b,c],d]) should return [a,b,c,d], and as a relation flatten([,a,[b,[c],a],d],Res) should bind Res to [a,b,c,a,d].
Hint: You may use the built-in relation atom for testing whether a term is a constant.
Does any version, or do both, work if you use your definition(s) on non-ground lists?
2) Consider the following operation definitions:
zap([_|T1],[_|T2]) :- zap(T1,T2).
zip(,) :& .
zip([H1|T1],[H2|T2]) :& cns([H1,H2],zip(T1,T2)).
Find out which, if any, operations are functions (_______________________) and which, if any, relations (_______________________).
Describe in concise English (maximal 3 sentences each) what zap and zip are computing.
3) Define a Relfun function returning the Nth Fibonacci number (http://math.holycross.edu/~davids/fibonacci/fibonacci.html) by completing the templates below.
First, define fib-spec as an (inefficient) full-recursive specification using only the subtraction built-in inside some “____”:
fib-spec(0) :& 0.
fib-spec(1) :& ___.
fib-spec(N) :- >(N,1) & +(_________________________,_________________________).
Next, define fib via an (efficient) tail-recursive implementation using the subtraction and addition built-ins inside some “____”:
fib(N) :& fib-tail(N,1,0).
fib-tail(0,Next,Prev) :& ______.
fib-tail(N,Next,Prev) :- >(N,0) & fib-tail(________,_________________,______)).
Explain (in just 3-4 English sentences) the main differences between the two versions.
Could the tail-recursive version be optimized? If yes, only indicate the idea; if no, only hint at why not (in either case, just use 1 English sentence).
Could any of the two functional versions be rewritten into an invertible relation (explain why / why not in 1 English sentence)?
Consider the following fibl definition:
fibl(0) :& .
fibl(1) :& [1,0].
fibl(N) :- >(N,1) & fibl-tail(N,[1,0]).
fibl-tail(2,[Next,Prev|Rest]) :& cns(+(Next,Prev),[Next,Prev|Rest]).
>(N,2) & fibl-tail(-(N,1),cns(+(Next,Prev),[Next,Prev|Rest])).
Explain what values it computes (just in 1 English sentence).
Modify things such the values are ‘embellished’ using one rev(erse) call plus one corresponding trivial change.