Princeton University
Computer Science Dept.

Computer Science 441
Programming Languages
Fall 1998

Assignment 1
Due Tuesday, 9/29/98
General remarks on all homework assignments:
  1. All homework is due at the beginning of class on the due date. Homework turned in after 9:05 am on the due date will be considered late. Remember you are only allowed two late days for the semester.

  2. You cannot learn a new language the night before the assignment is due. There will always be gotcha's involving the language or compiler that will screw you up until you find the (usually trivial) piece of information that will let you continue. I will have no sympathy if this happens to you the night before an assignment is due.

    I strongly urge you to complete at least the problems in part A before Thursday's class. That way you can ask questions about anything that doesn't work the way you expect.

  3. Homework is expected to be the sole work of each student. Students may discuss problems or receive minor programming help from each other on an occasional basis as long as all parties contributing are given explicit credit for their contributions on the homework. Students must write up all problems individually. Uncredited collaborations will be considered a violation of the disciplinary code and will be handled appropriately. Following university regulations, undergraduates are required to write the following statement at the end of all homework papers: "This paper represents my own work in accordance with University regulations." Of course the statement should be modified if you have collaborated or received help from anyone other than the instructor.

  4. I hope to find a mechanism for you to turn in programs electronically. Until then please turn in well-documented(!) print-outs of programs as well as the answers to non-programming questions. (Among other things, please make sure that identifier names are intelligible so that I can understand what each stands for in the programs.)

    If you cannot make it to class on time, please give your homework to someone else or place it in my mailbox in the CS department sometime before the beginning of class.

Part A: Not to be turned in

  1. Define a function sumsqrs that, given a nonnegative integer n, returns the sum of the squares of the numbers from 1 to n.

    1. Define a function dup which takes an element, e, of any type and returns a tuple with the element duplicated. E.g., 
         dup "ab" = ("ab","ab").
    2. . Define a function list_dup which takes an element, e, of any type, and a positive number, n, and returns a list with n copies of e. E.g., 
         list_dup "ab" 3 = ["ab","ab","ab"].

Part B: To be turned in

  1. Write a function int_to_string which converts an integer (positive or negative) to the string of its digits. Hints: It is easy to write int_to_string if you have a function non_neg_to_string, which converts a non-negative integer to a string. Similarly it is relatively easy to write non_neg_to_string given a function, digit_to_char. Here is a definition of digit_to_char:
       fun digit_to_char (n:int) = chr (n + ord #"0");
    Use a let clause to hide the auxiliary functions.

    1. Write the function zip to compute the Cartesian product of two lists of arbitrary length:
         - zip [1,3,5,7] ["a","b","c","de"];
   val it = [(1,"a"),(3,"b"),(5,"c"),(7,"de")]: (int * string) list
      Note: If the vectors don't have the same length, you may decide how you would like the function to behave. If you don't specify any behavior at all you will get a warning from the compiler that you have not taken care of all possible patterns.

    2. Write the inverse function, unzip, which behaves as follows:
         - unzip [(1,"a"),(3,"b"),(5,"c"),(7,"de")];
   val it = ([1,3,5,7], ["a","b","c","de"]): int list * string list
    3. Write zip3, to zip three lists. Why can't you write a function zip_any that takes a list of any number of lists and zips them into tuples? From the first part of this question it should be pretty clear that for any fixed n, one can write a function zipn. The difficulty here is to write a single function that works for all n!

    1. Recursion is the only means of obtaining looping behavior in ML, but not all recursive programs take the same amount of time to run. Consider, for instance, the following function that raises a number to a power: 
         fun exp base power = 
        if power = 0 then 1 else base * (exp base (power-1));
      There are more efficient means of exponentiation. First write an ML function that squares an integer, and then using this function, design an ML function fastexp which calculates (basepower) for any power >= 0 by the rule
         base0 = 1
   basepower = (base(power/2))2 if m is even
   basepower = base * (base(power-1))    if m is odd
      It is easy to blow this optimization and not save any multiplications. Prove the program you implemented is indeed faster than the original by comparing the number of multiplications that must be done for exponent m in the first and second algorithms. (Hint it is easiest to calculate the number of multiplications if the exponent, power, is of the form 2k for the second algorithm. Give the answer for exponents of this form and then try to give an upper bound for the others. Also recall that ML is call-by-value. That is, the argument to a function is evaluated before the call.)

    2. A Pascal program corresponding to the fast solution above is as follows:
          function exp(base, power: integer): integer;
    var ans:integer
    begin
        ans:= 1;
        while power > 0 do
            if odd(power) then
                begin
                    ans := ans*base;
                    power:= power- 1
                end
            else
                begin
                    base := base * base;
                    power := power div 2
                end;
        exp := ans
    end;
      Please mimic the translation given in class to convert this Pascal program to ML. (Note you will obtain a different - and slightly more efficient - version of the program than the natural recursive solution in part a.)

  4. One can implement binary trees that only store values at the leaves using the datatype declaration
        datatype 'a tree = 
                Leaf of 'a | InternalNode of ('a tree) * ('a tree)
    1. Implement the function isBalanced which determines if a tree is balanced. A tree is balanced if the left and right subtrees are balanced and the height of the left and right subtrees differ by no more than one. You may find it helpful to define an auxiliary function that determines the height of a tree.

    2. What is non-optimal about using a height function to answer part a? How ould you change isBalanced to make it more efficient? You don't have to actually write the new function, just describe what you would need to change.

CS441 | CS Department | Princeton University