Project 1: OCaml Warmup
Due: Tues, Feb 17, 2015 11:59:59pm
Introduction
This project will help refresh your memory on programming in OCaml by asking you to write two small modules and then develop test cases for them. You may find it helpful to review the OCaml slides from CMSC 330.
Part 1: Join Lists
Your first task is to implement directed graphs (henceforth just “graphs”) in OCaml. A graph is a collection of nodes and directed edges. In this particular graph implementation, nodes are labeled with some value, and every node and edge may only appear at most once in the graph. For example, a string graph could have nodes labeled "x", "y", and "happy", and there could be edges from "x" to "happy", from "happy" to "x", etc.
It is up to you to decide how to implement graphs. Whatever implementation strategy you use, your graphs must appear to be functional, which means adding and removing nodes and edges does not change a graph, but rather creates a new graph with the added/removed node/edge.
Your graphs should implement the following signature:
type 'a graph |
|
val empty : 'a graph |
val is_empty : 'a graph -> bool |
val insert : 'a graph -> 'a -> 'a graph |
val delete : 'a graph -> 'a -> 'a graph |
val contains : 'a graph -> 'a -> bool |
val nodes : 'a graph -> 'a list |
val insert_e : 'a graph -> 'a -> 'a -> 'a graph |
val delete_e : 'a graph -> 'a -> 'a -> 'a graph |
val contains_e : 'a graph -> 'a -> 'a -> bool |
val edges : 'a graph -> ('a * 'a) list |
val pred : 'a graph -> 'a -> 'a list |
val succ : 'a graph -> 'a -> 'a list |
val map : ('a -> 'b) -> 'a graph -> 'b graph |
val filter : ('a -> bool) -> 'a graph -> 'a graph |
val is_list : 'a graph -> bool |
val is_binary_tree : 'a graph -> bool |
val path : 'a graph -> 'a -> 'a -> bool |
You’ll find the types above in the interface file graph.mli, and you should put your implementation in graph.ml. You can find more detailed descriptions of the above functions in the .ml file, though probably you can guess how these should behave from your knowledge of graphs.
Part 2: Lambda Calculus
Your next task is to implement a few functions related to Lambda calculus, which you learned about in CMSC 330. Below is an interface file lambda.mli. You must implement the last six of the listed functions in lambda.ml. (We’ve already implemented unparse for you.)
type expr = |
| Var of string |
| Lam of string * expr |
| App of expr * expr |
|
val unparse : expr -> string |
|
val free_vars : expr -> string list |
val subst : string -> expr -> expr -> expr |
val beta : expr -> expr option |
val normal_form : expr -> expr |
val expr_of_int : int -> expr |
val add : expr -> expr -> expr |
These functions should do the following:
free_vars e returns a list of the free variables in e. (Duplicates are allowed.)
subst x e1 e2 returns a copy of e2 in which free occurrences of x have been replaced by e1. Be sure to implement capture-avoiding substitution, i.e., bound variables should be renamed as needed to avoid capture free variables under a lambda. For example, subst "x" (Var "y") (Lam("y", Var "x")) should return something equivalent to Lam("z", Var "y") and not Lam("y", Var "y").
beta e applies one step of call-by-value beta reduction to e, or returns None if no reduction is possible, according to the following rules:
Var x and Lam (x, e) do not reduce (they return None).
App (e1, e2)
Returns App(e1’, e2) if e1 reduces to e1’.
Returns App(e1, e2’) if e1 cannot be reduced and e2 reduces to e2’.
Returns subst x e2 e if e1==Lam(x,e) and e2 cannot be reduced.
normal_form e keeps applying beta to e until the expression cannot be reduced any more, and then returns the result.
expr_of_int n returns the Church numeral (see slide 19 at the link above) encoding of a non-negative OCaml integer.
add e1 e2 adds two Church numerals (slide 22).
Part 3: Unit Testing
Your last task is to write unit tests for parts 1 and 2 above, using OUnit. Put your test cases in the file test.ml, and be sure to add your test cases to the suites suite_graph and suite_lambda, as appropriate. We will grade this part of the project by running your test cases against various correct and incorrect implementations. A test case will only be counted as correct if it passes a correct implementation and fails at least one incorrect implementation.
What to Turn In
Put all your code in the code skeleton we have supplied, and upload your solution to the submit server. You can either upload your solution via the web interface, or you can run java -jar submit.jar in the project directory.
Important note: Follow the instructions from the OCaml lecture notes to get OCaml working on linuxlab (We will not be using linuxlab; I will report what to do instead in class). Please post any questions you have about this on Piazza. You are welcome to install OCaml on your own machine, though we can’t provide much support for that. We do recommend using opam to manage the installation process if you choose to do that.
Academic Integrity
The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: “I pledge on my honor that I have not given or received any unauthorized assistance on this assignment.” Consequently your program is requested to contain this pledge in a comment near the top.
Please carefully read the Academic Integrity section
of the course syllabus. Any evidence of impermissible
cooperation on projects, use of disallowed materials or resources, or
unauthorized use of computer accounts, will be submitted to the
Student Honor Council, which could result in an XF for the course, or
suspension or expulsion from the University. Be sure you understand
what you are and what you are not permitted to do in regards to
academic integrity when it comes to project assignments. These
policies apply to all students, and the Student Honor Council does not
consider lack of knowledge of the policies to be a defense for
violating them. Full information is found in the course
syllabus—