Part I: Due Friday, January 16

The purpose of this part of the homework assignment is to make sure that you have all the tools you need for the semester. Before beginning this exercise, read the web pages about installing the course software.

The file nucleic.ml contains a rather complicated test program. I don't really know what it does, but we can use it to check your installation.

1. Compile and run this program with ocamlc. What is the output of the file nucleic.ml ?
2. What is the value of applying the function check to ()? (Hint, use the toplevel).

Part II: Due Friday, January 23

1. All of the following ML code does what it is supposed to do, but it is difficult to read. Rewrite the following ML expressions so that they follow the style guide.

   let abc(x:bool) (y:bool) (z:bool) : bool =
     if x then if y then true else
   	 if (x && z) then true else false
     else false
   
   let t(b:bool) (x:float) : float =
     match b with false -> cos(x) *. cos(x)
   | true -> (sin(x)+. 1.0) *. (sin(x) +. 1.0)
   
   let arithmetic(x1:(float*float)*float) (x2:(float*float)*float):float*float*float =
   let a = fst (fst x1) in
   let b = snd (fst
   x1) in
   let c = snd x1 in
   let d = fst (fst x2) in
   let e = snd (fst x2) in
   let f = snd x2 
   in
   ((((((b*.f) -. (c*.e)), ((c*.
   d) -. (a*.f)
   ), ((a*.e)-.(b*.d))))))
   
   
   let rec max (l: int list) curr  : int 
   = 
     match l with [] -> curr | (hd :: tl) -> if hd > curr then max tl hd else max tl 
   curr
   			 
   let reverse (l:int list) : int list  = 
     let rec reverse_aux (l: int list) (acc: int list) : int list = 
     if l=[] then acc
     else reverse_aux (List.tl l) ((List.hd l) :: acc) in reverse_aux l [] 

2. Programming Language Syntax

   Here is a grammar for core-ML expressions that we talked about in class:

   expr ::= value 
   	  | var
   	  | expr { expr }+
   	  | expr binary-op expr
   	  | prefix-op expr
   	  | if expr then expr else expr
   	  | let [rec] let-binding in expr
   	  | (expr)
   
   binary-op ::= + | * | - | && | || 
   
   prefix-op ::= not | -
   
   let-binding ::=  pattern = expr	  
   	          |    var {pattern}+ :type = expr
   
   pattern ::=  var
   		  | constant 
   		  | _ 
   		  | (pattern)
   		  | (pattern : type)

   Are the following expressions syntactically correct according to this definition? Why or why not? Typing them into O'Caml will not always help you because O'Caml will accept more terms than this grammar does.

   a)

   let x = 3 

   b)

   let add (x:int) (y:int) = x + y in add 2

   c)

   3 + 4 * 5

   d)

   	
   let count (x:int) :int = 
   	  if x = 0 then 0 else count 1 + (x - 1)
      in count 3

3. More Programming Language Syntax

   Here is a subset of the grammar for the Scheme language that is used in EOPL.

   exp ::= var                 // Variables
      |  integer               // Integers
      | (lambda (var) exp)     // Function definition
      | (exp exp)              // Application of a function to an argument
      | #t                     // true
      | #f                     // false
      | (if exp exp exp)       // First exp is test, 
   	                          // second is then branch, third is else
      | (binary-op exp exp)  
      | (prefix-op exp)
      | (let (var exp) exp)    // local binding
      | (letrec (var exp) exp) // recursive binding
   
   binary-op ::= + | * | - | and | or 
   prefix-op ::= - | not  

   The striking feature about Scheme is that, except for variables and values, every expression must be enclosed by parentheses.

   a) Write the Scheme expression that corresponds to the following ML expression:

   let x = 3 in 
   let y z = x in 
     if true 
     then (y 4) + (y 5) 
     else y 6
   

   b) Is this grammar ambiguous? If so, give an example of an ambiguous expression. If not, describe why not.

4. ML Programming from EOPL 1.2.4

   Define, debug and test the folling procedures. Include your test cases with your solution. For these exercises, there is no need to check that the input matches the description.

   a)

   (* duple n x returns a list containing n copies of x 
    * for example:
    *  duple 2 3  return [3;3]
    *  duple 4 ("ho","ho") returns 
    *      [ ("ho","ho"); ("ho","ho"); ("ho","ho"); ("ho","ho")] *)

   b)

   (* invert lst returns a list with each pair reversed. 
    * for example:
    *   invert [("a",1);("a",2)] returns [(1,"a"),(2,"a")] *)

   c)

   (* filter pred lst returns the list of those elements in 
    * list that satisfy pred.
    * for example:
    *    filter odd? [0;1;2;3;4] return [1;3]
    *)
   

   d)

   (* find pred lst returns the first element of the list that 
   	satisfies the predicate. Because no element may do so, the 
   	answer is returned in an option.
   *)
   

   e)

   (* every pred lst returns false if any element of lst 
    * fails to satisfy pred.
    *)

   f)

   (* list_set lst n x returns a list like lst, except that 
    *	the nth element (using zero-based indexing) is x. 
    * for example:
    *   list_set [1;2;3;4] 2 8 returns  [1;2;8;4]
    *   list_set [1;2;3] 5 10 returns [1;2;3]
    * You can assume n will be >= 0.
    *)
   

   g)

   (* merge lon1 lon2, where lon1 and lon2 are lists of numbers sorted in
    *	ascending order, returns a sorted list of all the numbers in lon1 and
    *	lon2. For example:
    *  merge [1;4] [1;2;8] returns [1;1;2;4;8] 
    *)

   h)

   (* bst is the representation of a binary search tree.  In a node of
   	this tree, the numbers contained in the left subtree are smaller than
   	the int at the node, and the numbers in the right subtree are
   	greater. *)
   
   type bst = N of int * bst * bst | L 
   
   type dir = Left | Right
   
   (* path n bst returns a list of Lefts and Rights, showing how to find
      the node containing n. If n is found at the root, return [].
      You may assume that the number exists in the tree. Use "failwith" 
      for the case that cannot happen.
   
      for example:
       path 17 (N (14, N(7, L, N(12, L, L))
   	 				     N(26, N(20, N(17, L,L), L)
   							     N(31,L,L))))
   	 returns Some [Right; Left; Left]
   *)