Problem Set 1: An introduction to SML

Due Monday, September 6, 2004, 12:01 am.

The goal of this problem set is to expose you to as much of the SML language as possible while learning a bit about functional style programming. If you are not already familiar with SML, it may be a fair amount of new material, so please begin this problem set early.

Instructions: You will do this problem set by modifying the files found in ps1.zip and submitting these through CMS. All programs that you submit must compile. Programs that do not compile will receive an automatic zero. If you are having trouble getting your assignment to compile, please visit consulting hours. If you run out of time, it is better to comment out the parts that do not compile and hand in a file that compiles, rather than handing in a more complete file that does not compile. Also, please pay attention to style. Refer to the CS 312 style guide and lecture notes.

For each of the problems, you will modify an included source file. For functions that are not implemented, you should see something of the form 

raise Fail "Not implemented."

You should remove this text and replace it with the body of the function. We will test some of your code using an automated test script. Do not change published variable names, function names and types. Do not remove our delimiters. Pay careful attention to types.

We will test your code using an automated test script. Do not change variable names. Do not change function names. Do not remove our delimiter comments. Pay scrupulous attention to types. You have been warned.

There are six parts to this assignment.

Part 1: Posting to the newsgroup

Post a test message to cornell.test with the subject "CS312 Test".
DO NOT post test messages to the course newsgroup or you may be penalized.

Part 2: Expressions and Types

A. Provide the types of each of the following expressions, by modifying the included source file types.txt.

  1.  true

  2. [ (1, true), (2, false),  (3, true) ]

  3. (42, (false, “hi”), fn x => x + 3)

  4. fn x => (fn y => x < (y + 1))

  5. (fn (x, y, z) => case x of
                      312 => (x + y, z)
                    | _ => (x - y, not z)) (40, ~2, false)

  6. fn (a, b, c) =>  case a of
                      [] => b andalso (c = “312”)
                    | 1::xs => b
                    | _ => (c = “42”)

  7. let
  val x::xs = [1, 2, 3]
in
  (xs, x)
end
    8. Note: The last expression gives you a "non-exhaustive match" warning. We would normally not write (nor accept) such an expression; it is presented here only for illustrative purposes.

B. Give expressions which have the following types: 

  1.  int * int -> bool
  2.  char list * string * ((int*int) -> bool)
  3.  (real * int * string -> int) list list
  4.  (real list * real list) -> bool list
  5.  (int * string -> char list) list * bool

These are defined in the included file expressions.sig signature. Implement them by modifying the Expression structure found in file expressions.sml.

Part 3: Improving Style

The following functions can be found in the included file style.sml. Find parts which violate the style guide and fix them. At the top of each function add comments briefly describing the style problems you have identified. Do not change function names or function types. 

  1. fun eval(a:int*int*int, x:int):int = (#1 a) + (#2 a) * x + (#3 a) * x * x

  2.  fun test(x:int, y:int):int =
  case x of
  1 => (if (y = 5) then x * y
                else x * x)
    |   2 => x * (if (y = 4)  then y * 2 else x)
 |   _ => x * x

  3. fun mult(l:int list):int = if null(l) then 1 else (if (hd(l) = 0) then mult(tl(l)) else hd(l) * mult(tl(l)))

  4. fun test2(x:bool ,y:bool): bool = 
if (x = true) then (if (y = true) then true else false)
else if (not x = true) then true 

else false

Part 4: Value Declarations

Write the following val declarations by modifying the included file valDecl.sml. Do not change variable names or types.

  1. Bind the third to last letter of this sentence to the variable letter of type char.
  2. Bind your name, age, major and whether your favorite number is 42 to a record of type {name:string, age:int, major:string, iLike42:bool} to the variable personal.
  3. Assign a tuple with the first names of all CS312 consultants in alphabetical order to the variable helpfulPeople. Do not include anybody who also has TA duties!

Part 5: Function declarations

Write the following fun declarations by modifying the included file funDecl.sml. Do not change function names or function types.

  1. Write a function that takes in an argument x of type degree (defined below) and a character c that is either 'C’ or 'F’ representing degrees Celsius or Fahrenheit, respectively. The function should return x converted to degrees of type c. If the input character is not valid, then raise Fail "invalid input." The conversion formula from degrees Fahrenheit to degrees Celsius is C=5*(F-32)/9. 
    2. datatype degree = C of real | F of real
fun convert(x:degree, c:char):degree = raise Fail "Not Implemented"
  2. Write a function that takes one integer argument n and returns an increasingly ordered list of all Fibonacci numbers that are less than or equal to n (do not forget to handle all cases). The first two Fibonacci numbers are f0=0, and f1=1. For k>1 fk=fk-1+fk-2. 
    3. fun fibo(n:int):int list = raise Fail "Not implemented"

Part 6: Using the Basis Library

The basis library is one of the most helpful resources you have on your quest to learn SML. For this part of the assignment, you should browse The Standard ML Basis Library and then write short functions using the functions in the basis library. Modify the included file basisLibrary.sml.

  1. Write a function that takes two integer arguments and returns a tuple consisting of the quotient and the remainder of the first argument divided by the second argument. Handle all possible cases! 
    2. fun quotRem(x:int, y:int):(int*int) = raise Fail "Not implemented"
  2. Write a function that takes a string s and changes all the upper case letters to lower case and all the lower case letters to upper case. 
    3. funchangeCase(s:string):string = raise Fail "Not implemented"
  3. Write a function that takes a string as an argument and replaces all adjacent repeated occurences of a character with a singly instance of that character. removeDupl("aabbacccdd") should return "abacd". 
    4. fun removeDupl(s:string):string = raise Fail "Not implemented"