CS 6905 Advanced
Topics in Computer Science: 

Assignment 2 



For the following, please
keep in mind to first define cns(First,Rest) :& [FirstRest]. 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
builtin relation atom for testing whether a term is a constant. FP version: LP version: Does any version, or do
both, work if you use your definition(s) on nonground lists? 2) Consider the following
operation definitions: zap([],[]). zap([_T1],[_T2]) : zap(T1,T2). zip([],[])
:& []. zip([H1T1],[H2T2])
:& 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. zap: zip: 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 fibspec as an (inefficient) fullrecursive specification
using only the subtraction builtin inside some “____”: fibspec(0) :& 0. fibspec(1) :& ___. fibspec(N) : >(N,1) & +(_________________________,_________________________).
Next, define fib via an (efficient) tailrecursive implementation
using the subtraction and addition builtins inside some “____”: fib(N) :& fibtail(N,1,0). fibtail(0,Next,Prev) :& ______. fibtail(N,Next,Prev) : >(N,0) & fibtail(________,_________________,______)). Explain (in just 34 English sentences) the main
differences between the two versions. Could the tailrecursive 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) :& [0]. fibl(1) :& [1,0]. fibl(N) : >(N,1) & fibltail(N,[1,0]). fibltail(2,[Next,PrevRest]) :& cns(+(Next,Prev),[Next,PrevRest]). fibltail(N,[Next,PrevRest]) : >(N,2) & fibltail((N,1),cns(+(Next,Prev),[Next,PrevRest])). 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. 


Maintained by Harold Boley