Programming Assignment #2 (110 Points)

Due: Mon, Jan 27, 5:00pm

The objective of this assignment is for you to have fun learning about recursion and recursive datatypes. All the problems require relatively little code, so if any function requires more than that, you can be sure that you need to rethink your solution.

The assignment is in the single zip file

that you need to download. After downloading to an appropriate directory, unzip it thus: 
> unzip pa2.zip
and out come tumbling several files including
  • misc.ml, which contains several skeleton OCaml functions with missing bodies that you will fill in;
  • nano.ml, which contains several skeleton OCaml functions with missing bodies that you will fill in;
  • test.ml which contains some sample tests for you to start with, which you can extend in order to test your implementations more fully; and
  • tester.ml, which helps run the tests cases, so you can check your assignments before submitting.

The files misc.ml and nano.ml contain expressions of the form: 

failwith "..."
Your task is to replace the text in those files with the the appropriate OCaml code for each of those expressions.

Note: All the solutions can be done using the purely functional fragment of OCaml, using constructs covered in class, and most require the use of recursion. Solutions using imperative features such as references, while loops or library functions will receive no credit. It is a good idea to start this assignment early; ML programming, while quite simple (when you know how), often seems somewhat foreign at first, particularly when it comes to recursion and list manipulation.

Assignment Testing and Evaluation

Same as for Assignment #1.

Submission Instructions

Same steps as in Assignment #1, but this time:

  • You need to submit a zipfile with two files, misc.ml and nano.ml: 
    > zip firstname_lastname_cse130_pa2.zip misc.ml nano.ml
  • You should use pa2 everywhere instead of pa1 when running validate_pa2 and turnin.

Problem #1: Tail Recursion

We say that a function is tail recursive if every recursive call is a tail call whose value is immediately returned by the procedure. See these two handouts for more details on tail-recursive functions in OCaml.

(A) 15 points

Without using any built-in ML functions, write a tail-recursive OCaml function 

val assoc : int * string * (string * int) list -> int
or more generally, 
val assoc : ’a * ’b * (’b * ’a) list -> ’a
that takes a triple (v, k, [(k1,v1);...;(kn,vn)]) and finds the first ki that equals k. If such a ki is found, then the function should return vi, otherwise, the default value v is returned.

Once you have implemented the function, you should get the following behavior at the ML prompt: 

# assoc (-1, "william", [("ranjit",85);("william",23);("moose",44)]);;    
- : int = 23

# assoc (-1, "bob", [("ranjit",85);("william",23);("moose",44)]);;
- : int = -1

(B) 15 points

Without using any built-in ML functions, modify fill in the skeleton for removeDuplicates to obtain a function of type 

val removeDuplicates : int list -> int list
or more generally, 
val removeDuplicates : ’a list -> ’a list
such that removeDuplicates xs returns the list of elements of xs with the duplicates, i.e. second, third, etc. occurrences, removed, and where the remaining elements appear in the same order as in xs.

For this function only, you may use the List library functions List.rev and List.mem. Once you have implemented the function, you should get the following behavior at the ML prompt: 

# removeDuplicates [1;6;2;4;12;2;13;6;9];;
- : int list = [1;6;2;4;12;13;9]

(C) 20 points

Without using any built-in ML functions, or the while or for construct, write a tail recursive ML function: 

val wwhile : (int -> int * bool) * int -> int
or more generally, 
val wwhile : (’a -> ’a * bool) * ’a -> ’a
such that wwhile (f, x) returns x’ where there exist values v_0, ..., v_n such that
  • x is equal to v_0;
  • x’ is equal to v_n;
  • for each i between 0 and n-2, we have f v_i equals (v_i+1, true); and
  • f v_n-1 equals (v_n, false).
Your function should be tail recursive.

Once you have implemented the function, you should get the following behavior at the ML prompt: 

# let f x = let xx = x*x*x in (xx, xx < 100);;
- val f : int -> int * bool = <fun> 

# wwhile (f,2);;
- : int = 512

(D) 20 points

Without using any built-in ML functions, modify fill in the skeleton for fixpoint to obtain a function 

val fixpoint: (int -> int) * int -> int
or more generally, 
val fixpoint: (’a -> ’a) * ’a -> ’a
such that fixpoint (f, x0) returns the first xi where
  • xi is equal to f x_i-1, and, furthermore,
  • f xi is equal to xi

Once you have implemented the function, you should get the following behavior at the ML prompt: 

# let g x = truncate (1e6 *. cos (1e-6 *. float x));;
val f : int -> int = <fun>

# fixpoint (g, 0);; 
- : int = 739085

# let collatz n =
    if n = 1 then 1
    else if n mod 2 = 0 then n/2
    else 3*n + 1;;
val collatz: int -> int = <fun>

# fixpoint (collatz, 1) ;;
- : int = 1
# fixpoint (collatz, 3) ;;
- : int = 1
# fixpoint (collatz, 48) ;;
- : int = 1
# fixpoint (collatz, 107) ;;
- : int = 1
# fixpoint (collatz, 9001) ;;
- : int = 1

Problem #2: Pretty Printing ML Expressions

In this problem, we will start to experiment with a miniature version of ML, called NanoML, so that we can study various bits of functional languages in detail. That’s right: we’re going to build a toy ML-like programming language using OCaml!

In subsequent assignments, we will implement an evaluator and a type checker for NanoML to ensure that we have a deep understanding of the fundamentals of functional programming and ML.

For now, though, we are going to start by writing a pretty printer for NanoML that takes a NanoML expression and converts it to a string (i.e. source text).

NanoML Expressions

Expressions in our toy language will be described by the following OCaml datatype expr: 

type binary_operator = 
  | And | Or                   (* boolean operators *)
  | Plus | Minus | Mul | Div   (* arithmetic operators *)
  | Lt | Le                    (* arithmetic comparison *)
  | Eq | Ne                    (* equality comparisons *)

type expr =   
  | Int of int
  | Bool of bool
  | Var of string
  | BinaryOp of expr * binary_operator * expr
  | Let of string * expr * expr
  | If of expr * expr * expr
  | Fun of string * expr
  | App of expr * expr

The ingredients that comprise NanoML expressions — integers, booleans, variables, binary operations, let-bindings, if-expressions, function calls, and functions — will behave very similar to the corresponding constructs in OCaml which we have seen.

To help make NanoML and OCaml programs easier to distinguish, however, we will use slightly different syntax for NanoML. For example, the following OCaml function and application 

let succ x = x + 1 in
  succ 5
might, instead, be written in NanoML as 
let succ = function (x) { x + 1 } in
  succ (5)
and would correspond to the following expression of type expr: 
Let ("succ",
     Fun ("x", App (Var "x", Int 1)),
     App (Var "succ", Int 5))
Notice that, unlike OCaml, we use parentheses and curly braces in the syntax of NanoML functions, and we require parentheses around the argument to a function call in NanoML.

A well-engineered pretty printer for a mature programming language usually goes to great lengths to format code so that it is highly readable and conforms to popular style guidelines. We will not make such a concerted effort for NanoML. Instead, we will emit code in a canonical form that uses whitespace liberally. The resulting NanoML source code will not be concise like code we might write by hand, but it will be simpler to implement and could serve as the basis for a fancier pretty printer if needed.

(A) 5 points

Start by filling in the skeleton for the OCaml function 

val indent : int -> string
that computes a “tab” string for a given integer depth, where a tab consists of two spaces. For example: 
# (indent 0, indent 1, indent 2);;
- : string * string * string = ("", "  ", "    ")
For this function, you may choose to use the String library function String.make.

(B) 10+25 points

Fill in the skeleton for the OCaml function 

val strExpr : int -> expr -> string
that takes an integer depth and NanoML expression e and returns the string representation of e at depth depth, as described below. Make sure there are no extra spaces after curly braces, parentheses, or anywhere else. The output of your pretty printer must exactly match the form explained below, including the length of the string.

Take a look at the function printExpr, defined in expr.ml, which calls strExpr 0 e to print a top-level expression (i.e. at depth zero) and returns the length of this string representation.

  • The string representation of an integer, boolean, or variable should not contain any leading or trailing spaces, regardless of what the depth is.
  • The string representation of a binary operation should use infix notation for the operator, as defined by strBinOp in expr.ml, with a space before and after the operator. For example: 
    # let e1 = BinaryOp (Var "x", Plus, Int 1);;
# printExpr e1;;
x + 1
- : int = 5
    When recursively computing the representation of each operand, the same depth value depth should be used.

Note: You will receive at most 10 points if your pretty printer works for NanoML expressions that do not include functions, function calls, let-expressions, or if-expressions. For the remaining 25 points, implement strExpr for the other cases:

  • The string representation of a function will span multiple lines. The first line starts with the keyword function, followed by the formal parameter inside parentheses, and the line is finished with a newline (i.e. "\n") after an opening curly brace.

    The string representation for the function body should be computed at depth depth + 1, and the first line of the function body (the line immediately after the line with function) should be indented according to depth depth + 1.

    A newline should follow the end of the function body (which may span multiple lines). And the last line for the function should contain only a closing curly brace (followed by a newline) indented at the original depth depth.

    For example: 

    # let e2 = Fun ("x", e1);;
# printExpr e2;;
function (x) {
  x + 1
}
- : int = 24

  • The string representation of a function call should compute the representation of the function and argument using depth depth, separated by a space. And the argument should be wrapped with parentheses. There should be no trailing characters after the closing parenthesis. For example: 
    # let e3 = App (Var "succ", Int 5);;
# printExpr e3;;
succ (5)
- : int = 8
  • The string representation of a let-expression Let ("x", e1, e2) will span multiple lines. The first line should start with the word let, and end with an equals-sign = followed by a newline. The next line should start with an indent of depth + 1, and the representation for expression e1 should be computed with depth parameter depth + 1. Afterwards, the keyword in should appear on its own line at depth depth. Finally, the body e2 of the let-expression should computed starting with depth depth + 1. For example: 
    # let e4 = Let ("succ", e2, e3);;
# printExpr e4;;
let succ =
  function (x) {
    x + 1
  }
in
  succ (5)
- : int = 55
    As discussed before, we will not make any attempt to reduce the copious whitespace introduced by our canonical spacing conventions: 
    # let e5 = Let ("five", Int 5, App (Var "succ", Var "five"));;
# let e6 = Let ("succ", e2, e5);;
# printExpr e6;;
let succ =
  function (x) {
    x + 1
  }
in
  let five =
    5
  in
    succ (five)
- : int = 84
  • Finally, the representation for an if-expression should indent each of the branch expressions at depth depth + 1, similar to the case for function definitions and let-bindings. For example: 
    # let e7 = If (BinaryOp (Var "y", Lt, Var "z"), Var "z", Var "y");;
# printExpr e7;;
if (y < z) {
  z
} else {
  y
}
- : int = 31
    Notice the particular locations of parentheses and braces.

Putting everything together, your pretty printer should produce the following: 

# let e8 = Fun ("y", Fun ("z", e7));;
# let e9 = Let ("max", e8, App (App (Var "max", Int 5), Int 3));;
# printExpr e9;;
let max =
  function (y) {
    function (z) {
      if (y < z) {
        z
      } else {
        y
      }
    }
  }
in
  max (5) (3)
- : int = 134

You may use any built-in OCaml functions, as well as the Printf library function Printf.sprintf, to implement strExpr.

And remember, your string output must match these examples exactly!