Programming Assignment #2 (110 Points)Due: Mon, Jan 27, 5:00pmThe 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.zipand out come tumbling several files including
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 EvaluationSame as for Assignment #1. Submission InstructionsSame steps as in Assignment #1, but this time:
Problem #1: Tail RecursionWe 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 pointsWithout using any built-in ML functions, write a tail-recursive OCaml function val assoc : int * string * (string * int) list -> intor more generally, val assoc : ’a * ’b * (’b * ’a) list -> ’athat 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,
val removeDuplicates : int list -> int listor more generally, val removeDuplicates : ’a list -> ’a listsuch 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 # 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 val wwhile : (int -> int * bool) * int -> intor more generally, val wwhile : (’a -> ’a * bool) * ’a -> ’asuch that wwhile (f, x) returns x’ where there exist
values v_0 , ..., v_n such that
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,
val fixpoint: (int -> int) * int -> intor more generally, val fixpoint: (’a -> ’a) * ’a -> ’asuch that fixpoint (f, x0) returns the first xi where
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 ExpressionsIn 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 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 5might, 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 pointsStart by filling in the skeleton for the OCaml function val indent : int -> stringthat 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 pointsFill in the skeleton for the OCaml function val strExpr : int -> expr -> stringthat 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
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
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 And remember, your string output must match these examples exactly! |