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: test get_val, set_n, list_swap_val
- testRecursion2.ml/rb: test index, uniq, find_new, is_sorted
- testHigherOrder.ml/rb: test grow_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
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)]
length_fold: a (re)implementation of the length function that must use fold.
rev_fold: a (re)implementation of the rev function that must use fold.

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:

(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 the end keyword.
Modules have types, named signatures. Signatures begin with a sig keyword, and end with an end 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 using module type MODULE = struct ... end.
Outside of modules, you reference things inside of the module Name using the syntax Name.value. E.g., you would use Dfa.make_dfa to create a value of type Dfa.t outside of the Dfa 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 define type t = int in the module Name, but define it as type t in the signature NAME, the user of the module will not be allowed to know that elements of type t are 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 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 function Dfa.make_dfa.
If you can correctly implement the to_dfa function, you can use the Dfa.accept method I provided to help you implement one of the functions in this assignment. If you do this, be confident that your to_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 $\epsilon$ -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 type a with the syntax (e : a). In other words, if you get confused because you’re trying to apply a function f to an argument x, and you’re getting a big type error, remember that you can force x to be a certain type by saying f (x:a), where a 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 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, @ 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 simply let.
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.

CMSC 330, Summer 2015

Organization of Programming Languages

Project 2 -- OCaml and FSMs

Getting Started

Part 1 – Implementing basic OCaml functions

A note on modules

Part 2 – NFAs and DFAs in OCaml

Bonus: Regex to NFAs (5%), or `to_dfa`

DFA operations

Module notes

Implementing NFA operations

Hints and tips

Submission

Getting Started

Part 1 – Implementing basic OCaml functions

A note on modules

Part 2 – NFAs and DFAs in OCaml

Bonus: Regex to NFAs (5%), or to_dfa

DFA operations

Module notes

Implementing NFA operations

Hints and tips

Submission

Bonus: Regex to NFAs (5%), or `to_dfa`