• Sep 4 - Improved explanation of height and width a bit (in trie.ml).
• Sep 4 - Clarified delete should raise Not_found if ks not mapped in trie. Clarified that height and width should also include keys mapped to empty tries.

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.

Here is the code skeleton for the project.

Your first task is to implement tries, which are data structures design for fast access to data indexed by sequences such as strings. More precisely, we'll use the following type for tries:

type ('k, 'v) trie = Trie of 'v option * (('k * ('k, 'v) trie) list)

Here a ('k, 'v) trie maps lists of keys of type 'k to values of type 'v. For example, if we wanted to map strings to the number of times they appear in a text, we might use a (char list, int) trie. A node in a trie is a pair containing an optional value and a list of (key, trie) pairs. For example, here are some tries:

(* empty trie *)
Trie (None, [])

(* maps ['a'] to 1 *)
Trie (None, ['a', Trie (Some 1, [])])

(* maps ['a'] to 1 and ['b'] to 2 *)
Trie (None, ['a', Trie (Some 1, []);
             'b', Trie (Some 2, [])])

(* maps ['a'; 'b'] to 1 *)
Trie (None, ['a', Trie (None, ['b', Trie (Some 1, [])])])

(* maps ['a'; 'b'] to 1 and ['a'; 'c'] to 2 *)
Trie (None, ['a', Trie (None, ['b', Trie (Some 1, []);
                               'c', Trie (Some 2, [])])])

(* maps [] to 1, ['a'] to 2, ['a'; 'b'] to 3 and ['a'; 'c'] to 4 *)
Trie (Some 1, ['a', Trie (Some 2, ['b', Trie (Some 3, []);
                                   'c', Trie (Some 4, [])])])

You must use the type signature given above to implement tries. You should implement the following functions:

type ('k, 'v) trie

val empty : ('k, 'v) trie
val is_empty : ('k, 'v) trie -> bool
val insert : ('k, 'v) trie -> 'k list -> 'v -> ('k, 'v) trie
val find : ('k, 'v) trie -> 'k list -> 'v  
val delete : ('k, 'v) trie -> 'k list -> ('k, 'v) trie
val height : ('k, 'v) trie -> int
val width : ('k, 'v) trie -> int
val map : ('k, 'v) trie -> ('v -> 'u) -> ('k, 'u) trie
val iteri : ('k, 'v) trie -> ('k list -> 'v -> unit) -> unit
val compress : ('k, 'v) trie -> ('k, 'v) trie

You'll find the types above in the interface file trie.mli, and you should put your implementation in trie.ml. You can find more detailed descriptions of the above functions in the .ml file, though probably you can guess how these should behave.

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 amd 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 add two Church numerals (slide 22).

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_trie 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.

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: On GRACE you should use the version of OCaml installed at

/afs/glue.umd.edu/class/fall2015/cmsc/430/0101/public/bin

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. You can use opam to install both OCaml and OUnit

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 honesty 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---please review it at this time.