HW3 - Prolog I

Define the following relations. 10 points each.
  1. noah is a relation between two lists, in which the second list takes the elements from the first list two-by-two. Examples:
    ?- noah([a,b,c,d], [[a,b],[c,d]]).
    yes.
    
    ?- noah([1,B,3,4,5,6,seven,eight], [[A,2]|X]).
    A=1
    B=2
    X=[[3,4],[5,6][seven,eight]]
    
    ?- noah(X,[]).
    X=[]
    
    ?- noah([a,b,c], X).
    no.
    
    ?- noah(X, [a,b]).
    no.
    

  2. noah_n is a relation between a postive integer and two lists. It is like noah above, except that it takes elements not necessarily two at a time, but rather n at a time.
    ?- noah_n(2, [a,b,C,D], [E,[sea,dee]]).
    C=sea
    D=dee
    E=[a,b]
    
    ?- noah_n(1, [a,b,c], X).
    X=[[a],[b],[c]]
    
    ?- noah_n(3, [a,b,c,d,e,f,g,h,i,j,k,l], X).
    X=[[a,b,c],[d,e,f],[g,h,i],[j,k,l]]
    
    ?- noah_n(4, [a,b,c], X).
    no
    
    You can assume that the number is actually given, although you'll get extra style points if it works even when the number is not specified.

  3. subst_list is a relation between two nested lists X and Y, and two arbitrary terms P and Q. Y is just like X, except that all occurances of P have been replaced by Q. You can assume that P and Q are grounded, although you'll get style points if it also works when they are not. (Note: the ``nested lists'' can be non-nested, ie can be just terms. Also, you may wish to use ``cut'' in your definition.)
    ?- subst_list([a,b,c,[a,c,d,c]], X, c, sea).
    X=[a,b,sea,[a,sea,d,sea]]
    
    ?- subst_list(X, [a,b,sea,[a,sea,d,sea]], c, sea).
    X=[a,b,c,[a,c,d,c]]
    

  4. The relation ev is between an expression in a very restricted arithmetic language described below, and a number which that expression evaluates to, in this little language. You can assume that the first argument is fully grounded.
    ?- ev(3,N).
    N=3
    
    ?- ev([+,3,4], N).
    N=7
    
    ?- ev([+,3,[*,8,0.25]], N).
    N=5
    
    Expressions in the ``little language'' are defined as
     E ::= number
         | [+, E, E]
         | [*, E, E]
         | [exp, E]
         | [sin, E]
         | [cos, E]
    
    These have the obvious numeric meanings when evaluated.

  5. evx is like ev except that (1) the little language of expressions is augmented with
     E ::= x
    
    ie the symbol x is now also a valid expression, and (2) it takes a new argument (in the second position) which must be a number, and which gives the value of x. Eg
    ?- ev(3,100,N).
    N=3
    
    ?- ev([+,x,4],100,N).
    N=104
    
    ?- ev([+,3,[*,x,0.25]], 100, Y).
    Y=28
    
    ?- ev([+,3,[sin,x]], 1, N).
    N=3.84147
    

  6. diff is the differentiation relation. It is a relation between two expressions in the little language defined above, in which the second is the derivative of the first with respect to x. You can assume that the first argument is fully grounded, and that the second is just a variable - ie you don't have to worry about making the relation run in reverse, or recognize various different expressions as being equivalent. The derivative calculated may be in a highly non-simplified form, as below. Of course, you get style points if it is simplified.

    Any of the following solutions would be okay, although the last would get style points.

    ?- diff([*,3,[cos,x]], E).
    E=[+,0,[*,3,[*,-1,[sin,x]]]]
    
    ?- diff([*,3,[cos,x]], E).
    E=[+,[*,3,[*,1,[*,-1,[sin,x]]]],[*,0,[cos,x]]]
    
    ?- diff([*,3,[cos,x]], E).
    E=[*,-3,[sin,x]]
    
Please be sure your file loads and runs properly on swiprolog as installed on the CS machines. Turn it in by running eg
~bap/bin/handin hw3.pl
on a regular UNM CS machine.

Due: noon, Fri Sep 28.


Barak Pearlmutter <bap@cs.unm.edu>