Due date: June 23rd (part 1), and June 30th, respectively.
Download the following zip archive p2.zip. It should include the following files:
practice.ml: your OCaml program.
ouput: test outputs (
testSimple.ml/rb: test simple utility functions.
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
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
map f l = [(f x1); (f x2); (f x3)]
- if l is
length_fold: a (re)implementation of the
lengthfunction that must use
rev_fold: a (re)implementation of the
revfunction that must use
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:
Kristophers-MacBook-Pro-2: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:
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.
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.
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
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.
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
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
structkeyword, and ends with the
Modules have types, named signatures. Signatures begin with a
sigkeyword, and end with an
Modules begin with a capital letter, as in
Modules can be named using the syntax
module Module = struct ... end. Signatures (also called module types) can be named using
module type MODULE = struct ... end.
Outside of modules, you reference things inside of the module
Nameusing the syntax
Name.value. E.g., you would use
Dfa.make_dfato create a value of type
Dfa.toutside of the
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 define
type t = intin the module
Name, but define it as
type tin the signature
NAME, the user of the module will not be allowed to know that elements of type
ints. 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
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.,
[3;1;2]should be considered equal.
to_dfa, make a DFA using the function
If you can correctly implement the
to_dfafunction, you can use the
Dfa.acceptmethod I provided to help you implement one of the functions in this assignment. If you do this, be confident that your
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
mapfunction 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
ehas a type
awith the syntax
(e : a). In other words, if you get confused because you’re trying to apply a function
fto an argument
x, and you’re getting a big type error, remember that you can force
xto be a certain type by saying
f (x:a), where
ais a type (e.g.,
'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 is
type1 -> 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,
'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 recrather than simply
dfa.ml using the web interface.