CPSC 425 Spring 2004
Final Exam (Take home portion)

Each of the two questions below constitutes 10% of the final exam grade. You may use your textbook for this course (Webber), your class notes, and the ML and Prolog interpreters on cs.roanoke.edu, but you may not use any other print or electronic resources and you may not discuss these problems with anyone. Electronic versions should be e-mailed to me before you come to the in-class portion of the exam, and hardcopy is due at that time.
  1. Write a Prolog predicate mergesort(list1,list2) that uses the mergesort algorithm and succeeds when list2 is a sorted version of list1. I recommend an approach similar to the one we used when we did mergesort in ML (Chapter 7). In particular, when dividing the list in half, it's convenient to split it so that one list contains the odd-numbered elements, and the other contains the even-numbered elements. This is what the halve function does in the ML example. Note that predicates <, >, and = behave as you would expect in Prolog.

  2. We talked in class about representing objects using functions of type message -> response. Using this model, we discussed the following representation for a node in a linked list of strings:
    datatype message = 
      | GetData
      | GetLink
    datatype response =
        Pred of bool
      | Data of string
      | Object of message -> response
    fun root msg = Pred false;
    fun null IsNull = Pred true
      | null message = root message
    fun node data link GetData = Data data
      | node data link GetLink = Object link
      | node data link other = root other
    Using this model, write the following functions:


    - val list1 = makeList ["1"];
    val list1 = fn : message -> response
    - isLast list1;
    val it = true : bool
    - last list1;
    val it = Data "1" : response
    - val list2 = makeList["a", "b", "c"];
    val list2 = fn : message -> response
    - isLast list2;
    val it = false : bool
    - last list2;
    val it = Data "c" : response