OCAML代写 | CSCI 2041 Advanced Programming Principles

这个作业是用OCAML完成几个小练习题
CSCI 2041: Advanced Programming Principles
Fall 2020, University of Minnesota
Homework 3
Posted: Feb 21, 2020
Due: March 6, 2020 by midnight
Submission Protocol
We are expecting to see your work in your private github repository for this course within a folder
named hw3 that is itself within the hws folder. Specific to this homework, this folder should contain
five files named prob1.ml through prob5.ml which contain the solutions to Problems 1 through 5,
respectively. Further details of what we expect each of these files to contain are provided with the
individual problem descriptions below. One general point that should be stressed: any functions that
your are asked to write must adhere strictly to the names and types that we have assigned to them. If
you do not respect this requirement, our automated tools will fail on your submission and we will not
be able to grade you solution, meaning also that you will not get credit for your work.
To help you in following the described protocol, we have included skeleton files named prob1.ml
through prob5.ml in the hw3 folder within the hws folder in the public repository for the course. Check
this folder out and copy it over to the right place in the local version of your private repository and get
started in filling the files out as needed for each problem.
Before you start working on the homework, make sure to read the comments on the protocol for
homeworks and the issues we consider when grading. Note in particular that the structure and quality
of your programs do matter. So also does presentation: you must not have excessively long lines and
you must use indentation to make your program text readable. Also avoid using tabs because they
show up differently under different editors and, depending on which editor your grader is using, can
make your code look ugly.
The Preliminary Feedback Process
2020/3/3 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 2/8
We will write scripts that will run tests on the programs asked for in this homework aimed at giving
you preliminary, non-exhaustive feedback on your work. Starting on the day before the submission
deadline, we will enable the feedback script on what you push as a solution. This script will generate
output which will be written to your repository. After pushing to your repository, wait a little while
(about a minute), pull from your repository, and check if a file called hw2_Feedback.md has been
created. If this file has not been created, it would mean that the script is not yet active and so you
should repeat the process of pushing and then pulling at a later time.
If the file hw3_Feedback.md appears in your repository after a pull, open it and look for lines in it that
begin with the string “+ Fail:”. These lines indicate failures of some kind in your code. The text that
follows should help you understand what the failure is and, hopefully, how to correct it. After
correcting any mistakes, you should push again to your repository, wait a little while, and pull again to
receive updated feedback. As we have explained before, you must not rely too much on this feedback
mechanism: our script will omit some secret test cases and there are also other aspects of your code
that the grader will examine in determining the credit to be given to your work.
A couple of important points that bear repeating: First, the feedback file will be created only when you
push a commit that affects the files under hws/hw2 after the script has been enabled. If you pushed
your homework before that time, you will have to push it again later in a way that actually changes the
contents of the folder in order to trigger the feedback. You can do this by, for example, adding some
inconsequential white space somewhere to one of your files in the folder before pushing the
repository. The second point to note is that if you do not pull the feedback before trying to make
another push, then you will encounter a conflict and your commit will fail. If this happens, you will
need to pull from your repository, make a merge and only then try to push. As long as you do not
modify the feedback file yourself, i.e. you treat it as a read-only file, such merges should succeed
automatically.
Problem 1 (5 points)
Define a function
divide_list : (‘a -> bool) -> ‘a list -> ‘a list * ‘a list
that takes a boolean function over a given type and a list of elements of that type and divides the list
into two lists, one containing all the elements that satisfy the boolean function and the other
containing those that do not satisfy it. Here are some example interactions that characterize the
desired behaviour of the function:
# divide_list (fun x -> true) [];;
– : ‘a list * ‘a list = ([], [])
# divide_list (fun x -> if (String.length x < 4) then true else false) [“this”; “is”; “a”; “list”; “of”; “mixed”; “length”; “strings”];; – : string list * string list = ([“is”; “a”; “of”], [“this”; “list”; “mixed”; “length”; “strings”]) # divide_list (fun x -> if (x mod 2 = 0) then true else false) [1;3;6;8;9;10];;
– : int list * int list = ([6; 8; 10], [1; 3; 9])
#
The second expression that we have asked OCaml to evaluate above makes use of a library function
called length that works on strings. This library function is part of a String “module” in OCaml and to
2020/3/3 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 3/8
use it we have to qualify it with the name of the module; this is like the List module and the use that
we made in the lecture of the map function from that module. We will talk explicitly about modules
later in the course, for now just understand how to use what the library modules provide. Also, you
may find it useful to know what OCaml provides you as library functions. For this, look up Part IV of
the OCaml manual.
Note: For credit in this problem, you must define divide_list without the use of any OCaml library
functions.
Problem 2 (5 points)
In class we considered mapping a function over a list. We should be able to do this for any recursive
data type. In this problem we will consider doing it for a binary tree. In particular, let us use the
representation for binary trees obtained from the following type declaration:
type ‘a btree =
Empty
| Node of ‘a * ‘a btree * ‘a btree
Define a function
treemap : ‘a btree -> (‘a -> ‘b) -> ‘b btree
That takes a binary tree and a function that acts on the elements of the binary tree as input and
transforms the tree into a new tree that is obtained by applying the function to each element in the
tree.
To help you understand the function you need to define a bit better, here are some example
applications of it:
# treemap (Node (4, Node (2, Empty, Empty), Node (5, Empty,Empty))) (fun x -> x + 3);;
– : int btree = Node (7, Node (5, Empty, Empty), Node (8, Empty, Empty))
# treemap (Node (4, Node (2, Empty, Empty), Node (5, Empty,Empty))) (fun x -> (x mod 2 = 0));;
– : bool btree =
Node (true, Node (true, Empty, Empty), Node (false, Empty, Empty))
#
Problem 3 (4 + 4 points)
For each of the function definitions below
explicitly follow the process that was explained in connection with the definition of append in
class to determine if the function definition is type correct, and
at the end of it, indicate what type is inferred for the function.
You must show your work for the first of the items above for credit in this problem. Also, do not
forget that you have to complete the type checking process to conclude that the function is in fact
type correct; if you leave it half way through, it is not clear that the type you infer will actually work,
and so you will lose credit.
2020/3/3 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 4/8
1. The function reduce defined as follows:
let rec reduce f lst u =
match lst with
| [] -> u
| (h::t) -> f h (reduce f t u)
2. The function forall2 defined as follows
let rec forall2 p l1 l2 =
match (l1,l2) with
| ([],[]) -> true
| ([],_) -> false
| (_,[]) -> false
| ((h1::t1),(h2::t2)) ->
(p h1 h2) && (forall2 p t1 t2)
Solutions to the two parts of this problem must appear as OCaml comments in distinct areas of the
file named prob3.ml. These areas should themselves begin with the OCaml comment
(* Solution to Part i *)
where i represents the relevant part of the question.
Problem 4 (3 + 3 + 3 points)
Fill in the blanks below to complete the definitions of the functions shown:
1. let append l1 l2 = reduce ___ l1 ___
2. let reverse l1 = accumulate ___ l1 ___
3. let filter f l1 = reduce ___ l1 ___
In case you missed the definition of accumulate in class, here it is
let rec accumulate f lst u =
match lst with
| [] -> u
| (h::t) -> accumulate f t (f h u)
Also, filter takes a boolean valued function and a list and it produces a list with only the items in the
input list that satisfy the input function. Here is a sample interaction that brings its expected
behaviour out:
# filter (fun x -> (x mod 2 = 0)) [1;2;3;4;5;6];;
– : int list = [2; 4; 6]
# filter (fun x -> (x mod 2 = 0)) [];;
– : int list = []
#
We will see a direct definition of filter that does not use any predefined functions in class.
Solutions to the two parts of this problem must appear as OCaml comments in distinct areas of the
file named prob4.ml. These areas should themselves begin with the OCaml comment
2020/3/3 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 5/8
(* Solution to Part i *)
where i represents the relevant part of the question. These solutions should be preceded by the
definitions of reduce and accumulate so that OCaml will be able to successfully compile your file.
Problem 5 (6 + 10 points)
Solutions to the two parts of this problem must appear as OCaml comments in distinct areas of the
file named prob4.ml. These areas should themselves begin with the OCaml comment
(* Solution to Part i *)
where i represents the relevant part of the question.
This problem concerns substituting OCaml expressions for identifiers in other OCaml expressions.
When you substitute into OCaml expressions that do not involve binding, this is not too difficult to
realize. However, things get a bit complicated when you have to consider let or function expressions.
In these cases, you should only substitute if the variable being bound is different from the one being
substituted for. Moreover, when you substitute, you have to be careful not to bind variables in the
expression being substituted in. The goal is to understand these issues concerning binding that apply
not just to OCaml expressions but to other contexts such as when you are building an AI system that
reasons.
Concretely, we return to the representation of OCaml expressions that we had seen before.
Specifically, we will work with the type expr type that is defined by the following declaration:
type expr =
Id of string (* for identifiers *)
| Int of int (* for integers *)
| True (* for the boolean value true *)
| False (* for the boolean value false *)
| Plus of (expr * expr) (* for exp1 + exp2 *)
| Minus of (expr * expr) (* for exp1 – exp2 *)
| Times of (expr * expr) (* for exp1 * exp2 *)
| Div of (expr * expr) (* for exp1 / exp2, division being for integers *)
| Lss of (expr * expr) (* for exp1 < exp2 *) | Eq of (expr * expr) (* for exp1 = exp2, = being equality comparison *) | Gtr of (expr * expr) (* for exp1 > exp2 *)
| And of (expr * expr) (* for exp1 && exp2 *)
| Or of (expr * expr) (* for exp1 || exp2 *)
| Not of expr (* for not exp *)
| Cond of (expr * expr * expr) (* for if exp1 then exp2 else exp3 *)
| Let of (string * expr * expr) (* for let = exp1 in exp2 *)
| Fun of (string * expr) (* for fun (x:ty) -> exp *)
| App of (expr * expr) (* for (exp1 exp2) *)
The eventual task is to define a function
subst : expr -> string -> expr -> expr
that takes an expression, the name of an identifier and an expression to replace it with and returns an
expression that is obtained by replacing all occurrences of the identifier in the first expression by the
second one. How this substitution should work seems fairly straightforward in all the cases except for
those of Let and Fun. The following examples show what the function should do in the simple cases:
2020/3/3 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 6/8
# subst (Plus (Int 5, Id “x”)) “x” (Plus (Int 3,Int 4));;
– : expr = Plus (Int 5, Plus (Int 3, Int 4))
# subst (Times (Int 5, Id “y”)) “x” (Plus (Int 3,Int 4));;
– : expr = Times (Int 5, Id “y”)
# subst (Or (Id “x”, And (Not (Id “x”), Int 5))) “x” True;;
– : expr = Or (True, And (Not True, Int 5))
# subst (Cond (Or (Lss (Id “x”,Int 5), Eq (Id “y”, Int 7)), Id “x”, Int 10))
“x” (Plus (Int 3,Int 4));;
– : expr =
Cond (Or (Lss (Plus (Int 3, Int 4), Int 5), Eq (Id “y”, Int 7)),
Plus (Int 3, Int 4), Int 10)
#
Make sure to understand what substitution is doing in these cases before reading on.
Now on to understanding what it is about the let and function expressions that makes things more
complicated. There are actually two sources for the complication.
First, if the name of the identifier being substituted for is identical to the identifier bound by the
let or the function expression, then no substitution should be made. For example, the following
expression
subst (Let (“x”, Id “y”, (Plus (Id “x”,Id “z”)))) “x” (Int 3)
must not evaluate to
Let (“x”, Id “y”, Plus (Int 3, Id “z”))
but to
Let (“x”, Id “y”, Plus (Id “x”, Id “z”)).
Note, however, that we still have to carry out the substitution in the expression that the identifier
is getting bound to. For example
subst (Let (“x”, Id “x”, (Plus (Id “x”,Id “z”)))) “x” (Int 3)
should evaluate to
Let (“x”, Int 3, Plus (Id “x”, Id “z”)).
Second, when substituting into a let or function expression, we have to be careful that the
expression being substituted does not have identifier occurrences that get accidentally bound in
the expression. For example, the expression
subst (Let (“x”, Id “y”, Plus (Id “x”, Id “z”))) “z” (Plus (Int 3, Id “x”))
must not evaluate to
Let (“x”, Id “y”, Plus (Id “x”, Plus (Int 3, Id “x”)))
Instead, we should first “rename” the identifier bound by the let to get an expression something
like
Let (“var1”, Id “y”, Plus (Id “var1”, Id “z”))
and then carry out the substitution to get
Let (“var1”, Id “y”, Plus (Id “var1”, Plus (Int 3, Id “x”)))
2020/3/3 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 7/8
A natural question here is why the renaming is okay. The reason is simple: the main purpose for
the name of the identifier being bound in a let or function expression is to determine where to
use the expression it is being bound to in the body of the let and so long as we preserve this
correspondence, we are not changing the meaning of the expression.
Having understood the nuances of substitution, let us now turn to how we can realize it correctly. We
will do this in two steps.
1. First, define the function freeIn : expr -> string -> bool that takes an expression and a name
and returns true if that name appears in the expression. Here are some interactions that show
the expected behaviour of freeIn:
# freeIn (Plus (Id “x”, Id “y”)) “x”;;
– : bool = true
# freeIn (Plus (Id “x”, Id “y”)) “z”;;
– : bool = false
# freeIn (Let (“x”, Id “x”, Plus (Id “x”, Id “y”))) “x”;;
– : bool = true
# freeIn (Let (“x”, Id “z”, Plus (Id “x”, Id “y”))) “x”;;
– : bool = false
# freeIn (Fun (“x”, Id “x”)) “x”;;
– : bool = false
# freeIn (Fun (“y”, Id “x”)) “x”;;
– : bool = true
#
This function will be used in the next part.
2. Now define the function subst: expr -> string -> expr -> expr. Use the function freeIn to
determine if renaming is needed in a let or function expression. To determine this, you have to
check if the name bound by the let or by a function argument appears in the expression being
substituted. If you do need to rename, you will need a way to generate a new name. Use the
following code for this:
let namecounter = ref 0
let newname () =
( namecounter := !namecounter + 1; “var” ^ string_of_int !namecounter)
We will talk about the meaning of this code later in the course. For now, just note that every
time you need a new name, you just need to use the expression newname (). Here is an
interaction that shows how to use it and what happens when you do:
# newname ();;
– : string = “var1”
#
There is a possibility of course that the “new name” that is generated in this way also already
appears in the expression but, for this homework, it is okay to assume that the name will
actually be fresh; just be careful not to use an identifier name that begins with “var” in the
testing examples you try. However, if building this kind of reliance on the user into your code
annoys you like it does me, you might try to make the renaming more robust. For example, here
is a case to deliberately break it that my definition if subst resists:
# subst (Let (“y”, Int 5, Id “x”)) “x” (Plus (Id “y”,Id “var1”));;
– : expr = Let (“var2”, Int 5, Plus (Id “y”, Id “var1”))
#
2020/3/3 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 8/8
If you want to build this robustness into your code too but are having difficulties in doing so, ask
for suggestions on Piazza or talk to the instructor.
Last modified: Feb 22, 2020. Created by ngopalan atsign umn dot edu. Copyright (c) Gopalan
Nadathur.
The views and opinions expressed in this page are strictly those of the page author(s). The contents of this page have not
been reviewed or approved by the University of Minnesota.