Project 2  OCaml and FSMs
Due date: June 23rd (part 1), and June 30th, respectively.
Getting Started
Download the following zip archive p2.zip. It should include the following files:
practice.ml
: your OCaml program.ouput
: test outputs (practice.ml
output)test*.ml/rb
(unit tests):testSimple.ml/rb
: test simple utility functions.testRecursion1.ml/rb
: testget_val
,set_n
,list_swap_val
testRecursion2.ml/rb
: testindex
,uniq
,find_new
,is_sorted
testHigherOrder.ml/rb
: testgrow_lists
,concat_lists
goTest.rb
: script to run all public tests.
Part 1 – Implementing basic OCaml functions
(Note: You are not allowed to use any functions in the List
module for this part)
There are two parts to this project, with two separate due dates. The first part will have you implement some ocaml functions.
In the file practice.ml
, you’ll find a bunch of skeleton functions.
module Examples = struct
(*
* Implement your code here
*)
(* Calculate the length of the list `l` *)
let rec length l = failwith "unimplemented"
(* ... *)
end
This is where you implement the following functions:

length
: calculates the length of a list 
rev
: reverses a list 
hd
: takes the head of a list (first element). You may assume the list always contains at least one element. 
last
: gets the last element of the list. You may again assume the list has at least one element. 
grow_lists x y
: Given list of elements x and list y, prepend every element of x to y. 
concat_lists x
: Given list of lists x, return elements of x concatenated together. 
get_val
: return n’th element of list, or 1 if not found. 
get_vals b n
: list of values at list of indices. 
set_n x n v
: set n’th element of list x to value v, return resulting list. 
list_swap_val b u v
: swap values u,v in list b, assume all list elements are unique. 
index x v
: returns index of value v in list x, or 1 if not found. 
uniq x
: return list of unique members of list x. 
find_new x y
: return list of members of list x not found in list y. 
is_sorted x
: determine whether elements of list x are in sorted order. fold f a l
: fold is a function that takes a function f, an initial accumulator a, and folds f over l. In other words: if l is
[x1;x2;x3]
: fold f a l = f (... (f (f a x1) x2) ...) xn
 if l is
map f l
: map is a function that takes a function f, and applies it pointwise over l. In other words, if l is
[x1;x2;x3]
: map f l = [(f x1); (f x2); (f x3)]
 if l is

length_fold
: a (re)implementation of thelength
function that must usefold
. rev_fold
: a (re)implementation of therev
function that must usefold
.
A note on modules
Modules in ocaml are ways to group functions together. You don’t need to know anything about them for this project, but we’ll use them more frequently in subsequent assignments. A module begins with struct
and ends with end
, with value definitions in between.
All values in OCaml have types that are checked at compile time. When OCaml loads a module, it will type check each constituent function to make sure the program makes sense. When you write your program, you should make sure that your functions have the following signature:
KristophersMacBookPro2:p2 micinski$ ocaml
OCaml version 4.02.1
# #use "practice.ml";;
val prt_int : int > unit = <fun>
val string_of_int_list : int list > string = <fun>
val string_of_string_list : string list > string = <fun>
val prt_string_list : string list > unit = <fun>
val prt_int_list : int list > unit = <fun>
val string_of_int_list_list : int list list > string = <fun>
val prt_int_list_list : int list list > unit = <fun>
val prt_bool : bool > unit = <fun>
val string_of_bool_list : bool list > string = <fun>
val prt_bool_list : bool list > unit = <fun>
module Examples :
sig
val fold : ('a > 'b > 'a) > 'a > 'b list > 'a
val map : ('a > 'b) > 'a list > 'b list
val length : 'a list > int
val rev : 'a list > 'a list
val hd : 'a list > 'a
val last : 'a list > 'a
val grow_lists : 'a list > 'a list > 'a list list
val concat_lists : 'a list list > 'a list
val get_val : int list > int > int
val get_vals : int list > int list > int list
val set_n : 'a list > int > 'a > 'a list
val list_swap_val : 'a list > 'a > 'a > 'a list
val index : 'a list > 'a > int
val uniq : 'a list > 'a list
val find_new : 'a list > 'a list > 'a list
val is_sorted : 'a list > bool
val length_fold : 'a list > int
val rev_fold : 'a list > 'a list
end
end
Part 2 – NFAs and DFAs in OCaml
(Note: Feel free to use any functions in the List
module for this part.)
In this part of the project, you will implement NFA and DFA operations in OCaml. To do this, we will use the OCaml module system. You will implement the following operations on NFAs:

(1/3)
e_closure : Nfa.t > int list > int list
. This function takes an nfa and a set of states to the set of states that are reachable via epsilon transitions. 
(1/3)
move : Nfa.t > int list > char > int list
.This function calculates what possible states can be reached starting from a set of states on a given input character. 
(1/3)
accept : Nfa.t > string > bool
. Calculates whether or not a given string is accepted by the NFA.
We’ll explain what all of these type signatures mean in a few minutes.
Bonus: Regex to NFAs (5%), or to_dfa
This is a bonus problem. It’s good for an additional 5% on a project of your choosing.

to_dfa : Nfa.t > Dfa.t
. Creates a DFA from an NFA using the subset construction. 
regexp_to_nfa : Regex.t > Nfa.t
. Creates an nfa that accepts the same language as the regexp.
If you choose to implement this bonus work, let the instructors know so that we can grade your solution.
DFA operations
I have implemented a DFA module that has the following operations:
module type DFA =
sig
(* Abstract type for DFAs *)
type t
type transition = int * char * int
(* Returns a new DFA. make_nfa s fs ts returns an DFA with start
state s, final states fs, and transitions ts.
*)
val make_dfa : int > int list > transition list > t
(* Calculates move in an DFA.
move m ss c returns a list of states that m could
be in, starting from any state in ss and making 1
transition on c.
There should be no duplicates in the output list of states.
*)
val move : t > int > char > int
(* Returns true if the DFA accepts the string, and false otherwise *)
val accept : t > string > bool
end
Module notes
This is the first project in which you will be using OCaml modules (in a real way). For most of the project, you won’t have to worry about them. Inside the Nfa
module, for example, just write the code you normally would. There are a few notes about modules that might be useful for you to know:

Modules are collections of types and values. A module is a concrete piece of code that begins with the
struct
keyword, and ends with theend
keyword. 
Modules have types, named signatures. Signatures begin with a
sig
keyword, and end with anend
keyword. 
Modules begin with a capital letter, as in
Nfa
. 
Modules can be named using the syntax
module Module = struct ... end
. Signatures (also called module types) can be named usingmodule type MODULE = struct ... end
. 
Outside of modules, you reference things inside of the module
Name
using the syntaxName.value
. E.g., you would useDfa.make_dfa
to create a value of typeDfa.t
outside of theDfa
module. 
If you fail to specify a signature for a module, one will be inferred. If you do specify a module (by using the syntax
module Name : NAME
) the module’s operations will be constrained by the module type. E.g., if you definetype t = int
in the moduleName
, but define it astype t
in the signatureNAME
, the user of the module will not be allowed to know that elements of typet
areint
s. This enforces abstraction, and allows the module’s implementation to be changed later without needing to rewrite the code that uses it.
Implementing NFA operations
Your job is to extend the Nfa
module to include implementations of the functions defined in the module. You write code similarly to part one of the project to accomplish this task. In fact, you may find the utility functions helpful in implementing part two of the project. If you wish to use them, simply copy and paste them into the module. (You could also copy and paste them into the Utils
module.)
Be careful in implementing some of these operations. You need to treat lists as sets. This requires some careful consideration. For example:

Make sure you never include an element multiple times in a list, for it to truly be a set. One of your utility functions can help you with this, which one?

When you compare lists, you need to be careful to think about when they would be equal as sets. E.g.,
[1;2;3]
and[3;1;2]
should be considered equal. 
To implement
to_dfa
, make a DFA using the functionDfa.make_dfa
. 
If you can correctly implement the
to_dfa
function, you can use theDfa.accept
method I provided to help you implement one of the functions in this assignment. If you do this, be confident that yourto_dfa
function works! 
There are various times when you might want to redo a computation until a set stops growing. One example of this is closure. One way to do this might be to think about the following: how where can I go on one epsilon transition for every state in some list
l
. Then, how can I write a function that creates one step until I can’t create any more. In general this is called a fixpoint operation. Here’s an example implementation of that pattern in OCaml:
(* I haven't defined uniqify and sets_equal here because
I would give away part one if I did. *)
module L = List
let sum_one_to_four () =
let add_one_if_less_than_four element =
if element < 4 then
[element+1]
else
[]
in
let rec h set =
let new_set = uniqify (set @ (L.flatten
(L.map add_one_if_less_than_four set)))
in
(* We're done growing the set *)
if sets_equal new_set set then set
else
(* Keep going *)
h new_set
in
let initial_set = [1;2] in
h initial_set
(* # sum_one_to_four ();;
 : int list = [4; 1; 2; 3]
*)
Hints and tips

Make sure your function types are the same as the ones listed. In particular, make sure they are general enough. In other words, your
map
function should have the type('a > 'b) > 'a list > 'b list
. 
If you get confused about the types of various things, remember that you can always assert some expression
e
has a typea
with the syntax(e : a)
. In other words, if you get confused because you’re trying to apply a functionf
to an argumentx
, and you’re getting a big type error, remember that you can forcex
to be a certain type by sayingf (x:a)
, wherea
is a type (e.g.,int
/float
,'a > 'b
, etc…) 
When defining functions, you can constrain their input variables by writing
let f (x : type1) (y : type2) : result = ...
. This will result in a function whose type istype1 > type2 > result
. 
You can concatenate lists in OCaml using the
@
operator. This is not the same thing as::
.::
has a type'a > 'a list > 'a list
, meaning it takes an element, and a list, and creates a bigger list. Instead,@
has type'a list > 'a list > 'a list
, meaning it takes two lists (rather than an element and a list) and returns a new list. 
Remember that to define recursive functions, you use
let rec
rather than simplylet
. 
You can read this reference for fold. Here are some more notes. And even more
Submission
Submit practice.ml
and dfa.ml
using the web interface.