CPSC 370: Functional and Logic Programming (2012)

assigned 2012-10-29

1. Translate SK into a pure λ-term.
2. Translate λNfx.Nf(fx) into an SKI combinator.

assigned 2012-11-20

3. Write Prolog rules for a predicate nth so that nth(2,[a,b,c,d],c). returns true.

   Make your rules cope with as many situations as possible. For instance, it would be nice if your rules find both N=0 and N=2 when given the query. nth(N,[a,b,a,d],a). Comment on the combinations of variables that rules handle.

   N.B., this is builtin as predicate nth0, and there are answers on StackOverflow and elsewhere for how to do this. Write your own! (first.)

4. The goal of this question is to do arithmetic on natural numbers (0,1,2,…) without using the Prolog predicates such as is. To do this represent the natural numbers as zero, s(zero), s(s(zero)), ….

   1. Write a predicate isNat(X) that is true for zero, s(zero), s(s(zero)), …, and no other ground terms..
   2. Write a predicate xTo(?N, ?X) that converts between non-negative integers and isNat numbers.
   3. Using portray, cause Prolog to print s(s(zero)) as N(2), and so on.
   4. Write a predicate xPlus(?X,?Y,?Z) that succeeds when at least two of X, Y, and Z are ground and a solution is possible [ xPlus(X,s(zero),zero) should fail]. The idea that you want to exploit is

      s(X)+Y=s(Z)   iff X+Y=Z.

   5. Write a predicate xTimes(?X,?Y,?Z) that succeeds when at least two of X, Y, and Z are ground and a solution is possible.
   6. Write a predicate xLessEq(?X,?Y) that succeeds when X≤Y.
   7. Write a predicate xQuoRem(+X,+Y,-Z,-W) that succeeds when X=0 or Y>0. Solutions should satisfy xLessEq(s(W),Y),xTimes(Z,Y,X1),xPlus(X1,W,X).

1. Write an integer gcd function.
2. Write an integer lcm function.
3. Consider α trees defined by the datatype
   datatype α tree = Empty | Node of α tree * α * α tree ;
   

   Write a function that takes an integer n and produces a nearly balanced tree whose nodes in-order are the integers 1 through n.

4. Write a function that takes an α list and produces a nearly balanced α tree whose node values are taken from the list.
5. Given that tree folding is defined by
   fun fold (f:β * α * β → β) (b:β) (Empty:α tree) : β = b
   | fold (f:β * α * β → β) (b:β) (Node (l,n,r)) = f(fold f l, n, fold f r)

   write functions that compute
   1. depth
   2. total node count
   3. postorder:α tree → α list, that gives a list of the nodes in post-order.
   using fold.
6. Write a tail recursive version of fold that uses continuations to achieve tail-recursiveness.
7. Consider α queues defined by the datatype
   datatype α queue = Q of α list * α list ;
   as discussed in class.

   Implement the functions

   snoc   : α * α queue -> α queue ;
   pop    : α queue -> (α * α queue) option
   isEmpty: α queue -> bool
         

   where

   snoc

   adds an element to the tail of a queue

   pop

   removes the front element from a queue, return a pair consisting of the front element and the remainder of the queue. Returns NONE if the queue is empty.

   isEmpty

   Self explanatory.

1. Give an example of syntactic sugar in Java.
2. How many partial functions are there from { Scissors, Paper, Rock, Spock, Lizard } ² to { Win, Lose } ?

   How many of these are fair and interesting?

3. Implement a function that takes a pair of real numbers m and b and returns the linear function mx+b.
   • What is wrong with the wording above?
   • Implement this in Standard ML.
   • Implement this in Scheme.
   • Implement this in Java.
4. Implement a function that takes a triple of real numbers (a,b,c) and computes the roots r₁ and r₂ of the quadratic equation 0 = ax² + bx + c .

   To do this, find the larger root (in absolute value) using the quadratic formula. Find the smaller root using the fact that a r₁ r₂ = c.

   • Implement this in Standard ML.
   • Implement this in Scheme.
5. Here is a question about Standard ML syntax.
   • Is it possible to have “let let” in a legal Standard ML program (other than silly ways, such as in a string constant)?
   • Is it possible to have “local local” in a legal Standard ML program (other than silly ways, such as in a string constant)?
   In each case, either give an example showing that it is possible, or give a reasoned argument as to why it is impossible.